An Optimal Order Algebraic Multilevel Method
J. K. Kraus
We consider preconditioners for large sparse matrices arising from discretization
of partial differential equations (PDEs) of predominant elliptic type.
The author proposes a purely algebraic multilevel method based on approximate cyclic reduction.
Within an incomplete LU decomposition process spanning trees of matrix graphs are constructed that rest on a local optimization principle. A red-black coloring of these subgraphs yields the partitioning of the unknowns (into fine- and coarse-grid variables) and is also utilized to determine appropriate approximations of the Schur complements (the coarse-grid operators) on different levels.
This idea is combined with algebraic multilevel iterations (AMLI) of V- and W-cycle type.
The resulting method is robust with respect to anisotropy and discontinuities in the coefficients of the PDEs.
It can be used with two- and three-dimensional discretizations as well as with
unstructured grids and is also applicable to a class of nonselfadjoint boundary value problems.
Moreover, performing special W-cycles the resulting algorithm is shown to be of optimal
order of computational complexity under reasonable assumptions.