Efficient Preconditioned Solution Methods for Elliptic Partial Differential Equations

Preconditioners based on various multilevel extensions of two-level finite element methods (FEM) lead to iterative methods which have an optimal order computational complexity with respect to the size of the system. The methods can be based on block matrix factorized form, recursively extended via certain matrix polynomial approximations of the arising Schur complement matrices, or on additive, i.e., block diagonal form, using stabilizations of the condition number at certain levels. In this survey, the method in focus is the Algebraic MultiLevel Iteration (AMLI). It was introduced and studied by Axelsson and Vassilevski for the case of isotropic elliptic problems in [1,2], and is referred to as AMLI. The further development of robust AMLI methods for elliptic problems is systematically discussed in the recently published monograph [3].

While a huge amount of papers are dealing with the solution of FEM elliptic systems, the related time dependent problems are much less studied. A comparative analysis of robust AMLI methods for elliptic and parabolic problems is presented in this chapter. A unified framework for both Courant conforming and Crouzeix-Raviart nonconforming linear finite element discretizations in space is used. The considered multiplicative AMLI methods are based on an approximated block two-by-two factorization of the original system matrix. A key ingredient for the efficiency of the AMLI preconditioners is the quality of the utilized block two-by-two splitting, quantified by the so-called Cauchy- Bunyakowski-Schwarz (CBS) constant, which measures the abstract angle between the two subspaces, associated with the two-by-two block splitting of the matrix. All presented methods lead to preconditioners with spectral equivalence bounds which hold uniformly with respect to both the problem and discretization parameters, and optimal total computational complexity of the related Preconditioned Conjugate Gradient (PCG) or Generalized Conjugate Gradient (GCG) solvers. The theoretical results are supported by numerical tests with an emphasis on the case of nonconforming FEM systems.

Various block preconditioners for two by two block linear saddle point systems are studied. All block preconditioners are derived from a splitting of the (1,1) block of the two by two block matrix. We analyze the properties of the corresponding preconditioned matrices, in particular their spectra, and discuss the computational performance of the preconditioned iterative methods. It is shown that fast convergence depends mainly on the quality of the splitting of the (1,1) block. Moreover, some strategies of the implementation of the block preconditioners based on purely algebraic considerations are discussed. Thus, applying our block preconditioners to the related saddle point problems, we obtain preconditioned iterative methods in a “black box” fashion.

We discuss a family of block preconditioners for iterative solution of symmetric saddle point type problems arising from PDE discretizations. The building blocks consist of preconditioners for smaller sized, symmetric positive definite operators, which induce a norm in which the whole system is continuous and stable uniformly with respect to the mesh size h. We provide eigenvalue estimates and derive conditions under which the conjugate residual method using block preconditioners has convergence rate bounded independently of h.

The purpose of this chapter is to discuss a general approach to the construction of preconditioners for the linear systems of algebraic equations arising from discretizations of systems of partial differential equations. The discussion here is closely tied to our earlier paper [1], where we gave a comprehensive review of a mathematical theory for constructing preconditioners based on the mapping properties of the coefficient operator of the underlying differential systems. In the presentation given below we focus more on specific examples, while just an outline of the general theory is given.

High-order finite elements are necessary for many large scale scientific computing problems because either long time integrations need high accuracy at each time step or modelling certain physics requires the use of high-order finite elements. To reduce the costs of high-order finite elements, robust and efficient linear solvers with minimal memory requirements are crucial. This implies the need for a robust and efficient preconditioner. In the 1980s, Orszag [J. Comp. Phys, 37, 70 (1980)] showed that an inexpensive preconditioner can be defined based on a matrix that is generated from rediscretizing the finite element problem on a finer mesh using low-order finite elements. The matrix was sparse and its inverse proved to be an effective preconditioner.

In this work, we describe a similar sparse preconditioner. However, this preconditioner does not require the user to rediscretize the problem, but only to provide access to the high-order element stiffness matrices. The preconditioner is then an approximate inversion of this sparse matrix with algebraic multigrid, or any other robust method. The sparse matrix is constructed by representing the high-order element stiffness matrices with a sparse approximation generated using a least-squares approach. The least-squares approach aims to accurately represent the low-order modes of the highorder element stiffness matrix. We compare results to Orszag's approach, where the inverse of the sparse matrix is approximated with a single V-cycle of algebraic multigrid, and to a naive approach that uses a single V-cycle of algebraic multigrid, built from the original high-order system, as the preconditioner.

In this work we present a survey of some geometric results on tetrahedral partitions and their refinements in a unified manner. They can be used for mesh generation and adaptivity in practical calculations by the finite element method (FEM), and also in theoretical finite element (FE) analysis. Special emphasis is laid on the correspondence between relevant results and terminology used in FE computations, and those established in the area of discrete and computational geometry (DCG).

We consider local multigrid methods for adaptive finite element and adaptive edge element discretized boundary value problems as well as multilevel preconditioned iterative solvers for the finite element discretization of a special class of saddle point problems. The local multigrid methods feature local smoothing processes on adaptively refined meshes and are applied to adaptive P1 conforming finite element discretizations of linear second order elliptic boundary value problems and to adaptive curl-conforming edge element approximations of H(curl)-elliptic problems and the timeharmonic Maxwell equations. On the other hand, the multilevel preconditioned iterative schemes feature block-diagonal or upper block-triangular preconditioned GMRES or BiCGStab applied to the resulting algebraic saddle point problems and preconditioned CG applied to the associated Schur complement system.

As technologically relevant applications of the above methods to problems in electromagnetism and acoustics, we consider the numerical simulation of Logging-While-Drilling tools in oil exploration and the numerical simulation of piezoelectrically actuated surface acoustic waves, respectively.

Full text available