Parallel Implementation and Practical Use of Sparse Approximate Inverse Preconditioners with a Priori Sparsity Patterns
Author:
- 1 February 2001
- journal article
- research article
- Published by SAGE Publications in The International Journal of High Performance Computing Applications
- Vol. 15 (1) , 56-74
Abstract
This paper describes and tests a parallel message-passing code for constructing sparse approximate inverse preconditioners using Frobenius norm minimization. The sparsity patterns of the preconditioners are chosen as patterns of powers of sparsified matrices. Sparsification is necessary when powers of a matrix have a large number of nonzeros, making the approximate inverse computation expensive. For our test problems, the minimum solution time is achieved with approximate inverses with less than twice the number of nonzeros of the original matrix. Additional accuracy is not compensated by the increased cost per iteration. The results lead to further understanding of how to use these methods and how well these methods work in practice. In addition, this paper describes programming techniques required for high performance, including one-sided communication, local coordinate numbering, and load repartitioning.Keywords
This publication has 20 references indexed in Scilit:
- Dynamic load balancing in computational mechanicsComputer Methods in Applied Mechanics and Engineering, 2000
- Towards Realistic Performance Bounds for Implicit CFD Codes2000
- An MPI Implementation of the SPAI Preconditioner on the T3EThe International Journal of High Performance Computing Applications, 1999
- Approximate Inverse Preconditioners via Sparse-Sparse IterationsSIAM Journal on Scientific Computing, 1998
- On a Class of Preconditioning Methods for Dense Linear Systems from Boundary ElementsSIAM Journal on Scientific Computing, 1998
- Parallel Preconditioning with Sparse Approximate InversesSIAM Journal on Scientific Computing, 1997
- Factorized Sparse Approximate Inverse Preconditionings I. TheorySIAM Journal on Matrix Analysis and Applications, 1993
- Approximate inverse preconditionings for sparse linear systemsInternational Journal of Computer Mathematics, 1992
- Explicit preconditioning of systems of linear algebraic equations with dense matricesJournal of Mathematical Sciences, 1988
- Parallel algorithms for the solution of certain large sparse linear systemsInternational Journal of Computer Mathematics, 1984