Songklod Riyavong : October 5, 2004
Parallel preconditioners based on partitioning sparse matrices.
Songklod Riyavong
Tuesday October 5, 2:00 p.m. at CERFACS
Abstract
This work discusses experiments with parallel preconditioners that are constructed from partitioned general sparse matrices. Before partitioning, we preprocess the matrices by scaling and column permutation using the HSL routine MC64. The MC64 scaling ensures that, if the matrix is structurally nonsingular, the modulus of the largest entry in each row and column is 1. The column permutation puts 1's on the main diagonal and hence ensures that the diagonal blocks of the partitioned scaled matrix are structurally nonsingular.
To actually partition the matrix we use the multilevel hypergraph partitioning tool PaToH. We investigate how to construct efficient block-diagonal preconditioners for solving sparse linear systems of equations. Ideally, all entries would be in the blocks on the diagonal and the system would be decoupled. To ensure that large elements of the matrix are contained in the diagonal blocks we drop small entries from the scaled matrix according to an empirical dropping strategy before we perform the partitioning. After forming the diagonal blocks we calculate the ratio of the Frobenius norm of the diagonal blocks of the matrix to the Frobenius norm of the entire matrix. The drop tolerance that gives the highest ratio of the norms of the two matrices is used in our study.
After such preprocessing, the problems are solved in parallel by GMRES with right preconditioning. In our experiments, we use ilu(0) and a direct method to solve the block-diagonal systems in the preconditioning operation. We test the algorithm with matrices selected from different application areas and compare numerical results for the different preconditioning methods. We will show that our dropping strategy can significantly reduce the required number of iterations. We study the scalability of the algorithm and the speedup of the calculation when the number of processors is increased up to 16. Finally, we present some conclusions.
