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.