A generic multiresolution preconditioner for sparse symmetric systems
For practitioners solving sparse symmetric linear systems, this provides a general-purpose preconditioner that works without geometric information, but results are preliminary and incremental over existing multiresolution methods.
The paper introduces a new multiresolution preconditioner for symmetric linear systems that constructs a custom wavelet basis adapted to the system without geometric assumptions, using Multiresolution Matrix Factorization. Numerical experiments show effectiveness on PDE discretizations and off-the-shelf matrices.
We introduce a new general purpose multiresolution preconditioner for symmetric linear systems. Most existing multiresolution preconditioners use some standard wavelet basis that relies on knowledge of the geometry of the underlying domain. In constrast, based on the recently proposed Multiresolution Matrix Factorization (MMF) algorithm, we construct a preconditioner that discovers a custom wavelet basis adapted to the given linear system without making any geometric assumptions. Some advantages of the new approach are fast preconditioner-vector products, invariance to the ordering of the rows/columns, and the ability to handle systems of any size. Numerical experiments on finite difference discretizations of model PDEs and off-the-shelf matrices illustrate the effectiveness of the MMF preconditioner.