Partitioning sparse matrices for parallel preconditioned iterative methods

Bora Uçar and Cevdet Aykanat

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.

Key words. matrix partitioning, preconditioning, iterative method, parallel computing

AMS Subject Classifications. 05C50, 05C65, 65F10, 65F35, 65F50, 65Y05