Technical Report 2007-008

Finite Element Block-Factorized Preconditioners

Erik Bängtsson and Maya Neytcheva

March 2007

Abstract:

In this work we consider block-factorized preconditioners for the iterative solution of systems of linear algebraic equations arising from finite element discretizations of scalar and vector partial differential equations of elliptic type.

For the construction of the preconditioners we utilize a general two-level standard finite element framework and the corresponding block two-by-two form of the system matrix, induced by a splitting of the finite element spaces, referred to as fine and coarse, namely,

A = begin{bmatrix} A11&A12\ A21&A22end{bmatrix} \beginmatrixfine,\ coarse.end{matrix} .
The matrix A admits the exact factorization
A = \beginbmatrixA11&0\ A21&SAend{bmatrix} \beginbmatrixI1&A11-1A12\ 0& I2end{bmatrix} ,
where SA=A22-A21A11-1A12 and I1, I2 are identity matrices of corresponding size. The particular form of preconditioners we analyze here is
MB = \beginbmatrixB11&0\ A21&Send{bmatrix} \beginbmatrixI1&Z12\ 0& I2end{bmatrix} ,
where S is assumed to be some available good quality approximation of the Schur complement matrix SA.

We propose two methods to construct an efficient, sparse and computationally cheap approximation B11-1 of the inverse of the pivot block A11-1, required when solving systems with the block factorized preconditioner MB. Furthermore, we propose an approximation Z12 of the off-diagonal matrix block product A11-1A12, which further reduces the computational complexity of the preconditioning step. All three approximations are based on element-by-element manipulations of local finite element matrices.

The approach is applicable for both selfadjoint and non-selfadjoint problems, in two as well as in three dimensions. We analyze in detail the 2D case and provide extensive numerical evidence for the efficiency of the proposed matrix approximations.

Available as PDF (544 kB, no cover)

Download BibTeX entry.