Domain Decomposition Algorithms for Indefinite Elliptic Problems

Abstract

Iterative methods for linear systems of algebraic equations arising from the finite element discretization of nonsymmetric and indefinite elliptic problems are considered. Methods previously known to work well for positive definite, symmetric problems are extended to certain nonsymmetric problems, which can also have some eigenvalues in the left half plane. This paper presents an additive Schwarz method applied to linear, second order, symmetric or nonsymmetric, indefinite elliptic boundary value problems in two and three dimensions. An alternative linear system, which has the same solution as the original problem, is derived and this system is then solved by using GMRES, an iterative method of conjugate gradient type. In each iteration step, a coarse mesh finite element problem and a number of local problems are solved on small, overlapping subregions into which the original region is subdivided. The rate of convergence is shown to be independent of the number of degrees of freedom and the number of local problems if the coarse mesh is fine enough. The performance of the method in two dimensions is illustrated by results of several numerical experiments. Two other iterative methods for solving the same class of elliptic problems in two dimensions is also considered. Using an observation of Dryja and Widlund, it is shown that the rate of convergence of certain iterative substructuring methods deteriorates only quite slowly when the local problems increase in size. A similar result is established for Yserentant’s hierarchical basis method.