THE METHOD OF DIAGONAL COMPENSATION OF REDUCED MATRIX ENTRIES AND MULTILEVEL ITERATION

A method to construct preconditioners to a symmetric, positive definite matrix based on partitionings of Schur complements in two by two matrix block forms and approximating these by simpler structured matrices whose block factorization can be formed is considered. This partitioning, approximation and formation of Schur complements can continue until a matrix with sufficiently small order is found. To increase the accuracy of the preconditioner for this matrix sequence, the arising new Schur complements on each level are approximated by matrix polynomials involving the inverse of the preconditioner on the next level and the Schur complement itself. Conditions for computational complexity of optimal order for each iteration lead to an upper bound of the degree of the polynomials and conditions for an optimal rate of convergence lead to a lower bound. For large classes of problems these conditions permit the construction of preconditioners of a computational complexity proportional to the degree of freedom on the finest level. The method is an algebraic formulation and extension of a method presented previously for nine-point and mixed five- and nine-point difference matrices.