Incomplete Sparse Approximate Inverses for Parallel Preconditioning

Hartwig Anzt, Thomas K. Huckle, Jürgen Bräckle, Jack Dongarra

Research output: Contribution to journalArticlepeer-review

34 Scopus citations

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 languageEnglish
Pages (from-to)1-22
Number of pages22
JournalParallel Computing
Volume71
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'Incomplete Sparse Approximate Inverses for Parallel Preconditioning'. Together they form a unique fingerprint.

Cite this