What type of matrices is approximate inverse preconditioner $||I - AM||_F$ well suited for?

Question

Take sparse approximate inverse preconditioner $M \approx A^{-1}$ given by solution of

$$\underset{M \in S}{\mbox{min}} \; ||I - AM||_F,$$

where $S$ is a set of sparse matrices and $||.||_F$ is the Frobenius norm (see [1] for details).

I am wondering which specific characteristics of the matrix would make this preconditioner very efficient? For instance, it is not difficult to see why Jacobi scaling is efficient for diagonally dominant matrices, SOR for tridiagonal matrices, multigrid for discretizated elliptic operators, etc. But I am lacking an insight into how the preconditioner above could implicitly or explicitly exploit any particular (perhaps structure-related?) characteristics of the matrix.

[1] http://mathcs.emory.edu/~benzi/Web_papers/comp.pdf

Answer 1

I'm not an expert on this topic, but I have read a few papers concerning this in the hopes of finding a useful preconditioner for my problem. I think though that understanding of this topic is rather incomplete.

Some work in the direction of proving effectiveness of sparse approximate inverse preconditioners aims to show that off diagonals of (exact) inverse matrices have some kind of rapid decay property. Theorems like this effectively say that the inverse of said matrix has the potential to be approximated sparsely. See for example This paper and the citations therein.