Technical Report 2007-008

Finite Element Block-Factorized Preconditioners

Erik Bängtsson and Maya Neytcheva

March 2007

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} A₁₁&A₁₂\ A₂₁&A₂₂end{bmatrix} \beginmatrixfine,\ coarse.end{matrix} .

The matrix A admits the exact factorization

A = \beginbmatrixA₁₁&0\ A₂₁&S_Aend{bmatrix} \beginbmatrixI₁&A₁₁^-1A₁₂\ 0& I₂end{bmatrix} ,

where S_A=A₂₂-A₂₁A₁₁^-1A₁₂ and I₁, I₂ are identity matrices of corresponding size. The particular form of preconditioners we analyze here is

M_B = \beginbmatrixB₁₁&0\ A₂₁&Send{bmatrix} \beginbmatrixI₁&Z₁₂\ 0& I₂end{bmatrix} ,

where S is assumed to be some available good quality approximation of the Schur complement matrix S_A.

We propose two methods to construct an efficient, sparse and computationally cheap approximation B₁₁^-1 of the inverse of the pivot block A₁₁^-1, required when solving systems with the block factorized preconditioner M_B. Furthermore, we propose an approximation Z₁₂ of the off-diagonal matrix block product A₁₁^-1A₁₂, 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.