Abstract
In this paper, we propose a new preconditioning method that can be seen as a generalization of block-Jacobi methods, or as a simplification of the sparse approximate inverse (SAI) preconditioners. The “Incomplete Sparse Approximate Inverses” (ISAI) is in particular efficient in the solution of sparse triangular linear systems of equations. Those arise, for example, in the context of incomplete factorization preconditioning. ISAI preconditioners can be generated via an algorithm providing fine-grained parallelism, which makes them attractive for hardware with a high concurrency level. In a study covering a large number of matrices, we identify the ISAI preconditioner as an attractive alternative to exact triangular solves in the context of incomplete factorization preconditioning.
Original language | English |
---|---|
Pages (from-to) | 1-22 |
Number of pages | 22 |
Journal | Parallel Computing |
Volume | 71 |
DOIs | |
State | Published - Jan 2018 |
Funding
This material is based upon work supported by the U.S. Department of Energy Office of Science, Office of Advanced Scientific Computing Research, Applied Mathematics program under Award Number DE-SC0016513. This research was also supported by the Exascale Computing Project (17-SC-20-SC), a collaborative effort of the U.S. Department of Energy Office of Science and the National Nuclear Security Administration. The authors would also like to acknowledge the Swiss National Computing Centre (CSCS) for granting computing resources in the Small Development Project entitled “Energy-Efficient preconditioning for iterative linear solvers” (#d65). The authors would like to thank Edmond Chow from Georgia Tech for comments on an earlier version of the manuscript. Also the unknown reviewers provided us in a very diligent revision process with a comprehensive list constructive comments for which we are in particular thankful.
Keywords
- Approximate sparse triangular solves
- Incomplete LU factorization
- Incomplete Sparse Approximate Inverse
- Parallel computing
- Preconditioning