Partitioning Sparse Matrices for Parallel Preconditioned Iterative Methods
- 1 January 2007
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 29 (4), 1683-1709
- https://doi.org/10.1137/040617431
Abstract
This paper addresses the parallelization of the preconditioned iterative methods that use explicit preconditioners such as approximate inverses. Parallelizing a full step of these methods requires the coefficient and preconditioner matrices to be well partitioned. We first show that different methods impose different partitioning requirements for the matrices. Then we develop hypergraph models to meet those requirements. In particular, we develop models that enable us to obtain partitionings on the coefficient and preconditioner matrices simultaneously. Experiments on a set of unsymmetric sparse matrices show that the proposed models yield effective partitioning results. A parallel implementation of the right preconditioned BiCGStab method on a PC cluster verifies that the theoretical gains obtained by the models hold in practice. © 2007 Society for Industrial and Applied MathematicsKeywords
This publication has 30 references indexed in Scilit:
- Permuting Sparse Rectangular Matrices into Block-Diagonal FormSIAM Journal on Scientific Computing, 2004
- Preconditioning Techniques for Large Linear Systems: A SurveyJournal of Computational Physics, 2002
- A parallel solver for large-scale Markov chainsApplied Numerical Mathematics, 2002
- Approximate inverse preconditioning in the parallel solution of sparse eigenproblemsNumerical Linear Algebra with Applications, 2000
- Parallel strategies for crash and impact simulationsComputer Methods in Applied Mechanics and Engineering, 2000
- Preconditioning Highly Indefinite and Nonsymmetric MatricesSIAM Journal on Scientific Computing, 2000
- Robust Approximate Inverse Preconditioning for the Conjugate Gradient MethodSIAM Journal on Scientific Computing, 2000
- A comparative study of sparse approximate inverse preconditionersApplied Numerical Mathematics, 1999
- A Sparse Approximate Inverse Preconditioner for Nonsymmetric Linear SystemsSIAM Journal on Scientific Computing, 1998
- A Sparse Approximate Inverse Preconditioner for the Conjugate Gradient MethodSIAM Journal on Scientific Computing, 1996