Multiresolution approximate inverse preconditioners

We introduce a new preconditioner for elliptic PDEs on unstructured meshes. Using a wavelet-inspired basis we compress the inverse of the matrix, allo wing an effective sparse approximate inverse by solving the sparsity vs. ac curacy conflict. The key issue in this compression is to use second generat ion wavelets which can be adapted to the unstructured mesh, the true bounda ry conditions, and even the PDE coefficients. We also show how this gives a new perspective on multiresolution algorithms such as multigrid, interpret ing the new preconditioner as a variation on node-nested multigrid. In part icular, we hope the new preconditioner will combine the best of both worlds : fast convergence when multilevel methods can succeed but with robust perf ormance for more difficult problems. The rest of the paper discusses the core issues for the preconditioner: ord ering and construction of a factored approximate inverse in the multiresolu tion basis, robust interpolation on unstructured meshes, automatic mesh coa rsening, and purely algebraic alternatives. Some exploratory numerical expe riments suggest the superiority of the new basis over the standard basis fo r several tough problems, including discontinuous anisotropic coefficients, strong convection, and indefinite reaction problems on unstructured meshes , with scalability like hierarchical basis methods achieved.