Approximate inverse preconditionings for sparse linear systems

Work partially supported by National Science Foundation grants CDA 8820752 and RII-OK- 8610676 (Task lo), Oklahoma Center for Advancement of Science and Technology Grants RB9-008 (3748) and ARO-36 (3910), and by the Applied Mathematical Sciences subprogram of the Office of Energy Research, US. Department of Energy, under Contract W-31-109-Eng-38.

Abstract

We discuss a procedure for the adaptive construction of sparse approximate inverse preconditionings for general sparse linear systems. The approximate inverses are based on minimizing a consistent norm of the difference between the identity and the preconditioned matrix. The analysis provides positive definiteness and condition number estimates for the preconditioned system under certain circumstances. We show that for the 1-norm, restricting the size of the difference matrix below 1 may require dense approximate inverses. However, this requirement does not hold for the 2-norm, and similarly reducing the Frobenius norm below 1 does not generally require that much fill-in. Moreover, for the Frobenius norm, the calculation of the approximate inverses yields naturally column-oriented parallelism. General sparsity can be exploited in a straightforward fashion. Numerical criteria are considered for determining which columns of the sparse approximate inverse require additional fill-in. Spare algorithms are discussed for the location of potential fill-in within each column. Results using a minimum-residual-type iterative method are presented to illustrate the potential of the method.

Keywords:

• Inverse preconditioning
• sparse linear systems
• adaptive method

Work partially supported by National Science Foundation grants CDA 8820752 and RII-OK- 8610676 (Task lo), Oklahoma Center for Advancement of Science and Technology Grants RB9-008 (3748) and ARO-36 (3910), and by the Applied Mathematical Sciences subprogram of the Office of Energy Research, US. Department of Energy, under Contract W-31-109-Eng-38.

Work partially supported by National Science Foundation grants CDA 8820752 and RII-OK- 8610676 (Task lo), Oklahoma Center for Advancement of Science and Technology Grants RB9-008 (3748) and ARO-36 (3910), and by the Applied Mathematical Sciences subprogram of the Office of Energy Research, US. Department of Energy, under Contract W-31-109-Eng-38.

Notes

Work partially supported by National Science Foundation grants CDA 8820752 and RII-OK- 8610676 (Task lo), Oklahoma Center for Advancement of Science and Technology Grants RB9-008 (3748) and ARO-36 (3910), and by the Applied Mathematical Sciences subprogram of the Office of Energy Research, US. Department of Energy, under Contract W-31-109-Eng-38.