Global iterative methods for sparse approximate inverses of symmetric positive definite matrices

Abstract

This work is motivated by symmetric positive definite (SPD) matrices for which the best sparse approximate inverse (SPAI) with the prescribed nonzero pattern of $A^k$ for some moderate value of $k$, e.g., 1, 2, 3, or 4, fails to capture essential features of the inverse, such as definiteness. In this context, we consider short-recurrence iterative methods for the computation of SPAIs, that is, methods with sparse matrix iterates whose nonzero structure is globally updated at each iteration based on short-recurrence relations. In particular, we consider the minimal residual (MR) method, its newly proposed variant enriched with one previous search direction, namely the locally optimal minimal residual (LOMR) method, and the conjugate gradient (CG) method with sparse matrix iterates and Frobenius inner products. We show that, for SPD matrices, the MR method converges linearly with rate $(1-{\lambda }_{\min }^2/\mathrm{tr}(A^2){)}^{1/2}$, irrespective of the initial guess. While LOMR inherits unconditional monotone convergence from MR, its observed convergence behavior is that of a monotonically decreasing lower envelope to the CG residual norm without the occasional spurious oscillations proper to CG. All three methods are implemented with practical dropping strategies to control the growth of nonzero patterns in the approximate inverse. Numerical experiments are performed where SPAIs are computed with a prescribed cap on density, and the performance of those SPAIs as preconditioners for CG solves is quantitatively assessed for each method.

37 pages, 12 figures, 6 tables