4. Preconditioners for Elliptic Linear Systems of Equations

The linear systems that arise in the solution of e.g. the Poisson equation have the following properties

sparse, non-symmetric coefficient matrix
condition numbers grows like 4^L with the maximal level of refinement L
the transpose of the coefficient matrix is not easily available

Therefore, preconditioned BiCGStab,BiCGStab(l) or GMRES solvers are used. In [4,6,7] two preconditioners were analysed:
simple diagonal scaling and a combination of diagonal scaling and a basis transform to so-called Lifting-Wavelets.
Simple diagonal scaling works fine for 4th and higher order wavelets; while the Lifting-preconditioner yields almost level-independent condition numbers for all wavelets. The figures below show convergence histories for a Poisson problem on a regular sparse grids of different size with the low order Hierarchical basis. Left: the results for the diagonal scaling. Right: the Lifting-preconditioner.