Sparse Approximate Inverse Methods

In undergraduates numerical mathematics courses I was strongly warned that inverting a matrix for computational purposes is generally very inefficient. Not only do we have to do more computation than factorization, but we also lose sparsity in the matrix. However, doing a search in the literature, I found that for many computational settings the inverse, although dense, may contain many small entries that can be dropped. As a result we approximate the inverse by a sparse matrix. Techniques for constructing such a sparse approximate inverse can be effectively used in many applications of numerical analysis, e.g. for preconditioning of linear systems and for smoothing multigrid methods. I describe some of the most popular algorithms and through some theory, numerical experiments and examples of applications, I show that sparse approximate inverse methods can be competitive, sometimes even superior, to standard factorization methods based on incomplete LU decomposition.