Sparse Approximate Inverse PreconditioningEdmond Chow
Lawrence Livermore National Laboratory
Friday September 1st - 11 a.m., CERFACS Conference Room
A sparse approximate inverse approximates the inverse of a matrix or its factors by a sparse matrix, using the assumption that the exact inverses contain many small nonzeros that may be neglected. Sparse approximate inverses have generally been used as preconditioners for the iterative solution of linear systems, and may also be used to construct sparse approximations, such as sparse approximations to the Schur complement. Their attractiveness lies in the parallel way they may be constructed and applied as a preconditioner.
This talk will begin with a short survey of sparse approximate inverses, including methods of choosing the pattern of a sparse approximate inverse either a priori or as part of an adaptive algorithm. We will then focus on methods of choosing a priori patterns which are patterns of powers of sparsified matrices. These patterns are related to various other approximate inverse sparsity patterns through matrix graph theory and heuristics about a PDE's Green's function. We will also discuss the use of approximate inverses in multilevel preconditioners that can achieve scalable convergence rates.
This work was performed under the auspices of the U.S. Department of Energy by University of California Lawrence Livermore National Laboratory under contract No. W-7405-Eng-48.
Cerfacs' Conferences 1999-2001 Home Page