Orthogonal projections of the identity: spectral analysis and applications to approximate inverse preconditioning

Abstract

Many strategies for constructing different structures of sparse approximate inverse preconditioners for large linear systems have been proposed in the literature. In a more general framework, this paper analyzes the theoretical effectiveness of the optimal preconditioner (in the Frobenius norm) of a linear system over an arbitrary subspace of M-n(R). For this purpose, the spectral analysis of the Frobenius orthogonal projections of the identity matrix onto the linear subspaces of M-n(R) is performed. This analysis leads to a simple, general criterion: The effectiveness of the optimal approximate inverse preconditioners (parametrized by any vectorial structure) improves at the same time as the smallest singular value (or the smallest eigenvalue's modulus) of the corresponding preconditioned matrices increases to 1.