The Nested Recursive Two-Level Factorization Method for Nine-Point Difference Matrices

Nested recursive two-level factorization methods for nine-point difference matrices are analyzed. Somewhat similar in construction to multilevel methods for finite element matrices, these methods use recursive red-black orderings of the meshes, approximating the nine-point stencils by five-point ones in the red points and then forming the reduced system explicitly. Because this Schur complement is again a nine-point matrix (on a skew grid this time), the process of approximating and factorizing can be applied anew. Progressing until a sufficiently coarse grid has been reached, this procedure gives a multilevel preconditioner for the original matrix. Solving the levels in V-cycle order will not give an optimal order method (that is, with a total work proportional to the number of unknowns), but we show that using certain combinations of V-cycles and W-cycles will give methods of both optimal order of numbers of iterations and computational complexity. Since all systems to be solved during a preconditioner solve are of diagonal form, the method is suitable for execution on massively parallel architectures.