Wavelet sparse approximate inverse preconditioners (Q1371669)

The authors are interested in solving large sparse problems of the form \(Ax= b\) using sparse approximate inverse preconditioners. This amounts to first solving \(AMy= b\) and then computing \(x= My\). The aim is to choose \(M\) such that it has as much sparsity as possible while \(AM\) is still an approximation to the identity matrix. The main idea in the present paper is to represent \(A\) in a different basis in which \(A^{-1}\) has a sparse approximation. Specifically, if \(A^{-1}\) presents some piecewise smoothness then one uses a wavelet transformation to convert this smoothness into small wavelet coefficients. The authors compare this idea to that of a hierarchical basis preconditioner (to which it is closely related) and present a large number of interesting numerical experiments. The weak points of the method are also fairly discussed with suggestions for future work.