Unstructured Additive Schwarz--Conjugate Gradient Method for Elliptic Problems with Highly Discontinuous Coefficients

This paper concerns the iterative solution of symmetric elliptic problems with piecewise constant coefficients in two or three space dimensions discretized by linear finite element methods on unstructured triangular or tetrahedral meshes. The effect of the discontinuous coefficients is studied by first postulating that there are d fixed regions of the domain where the coefficient takes constant positive values a = (a1, . . . , ad)and then considering certain (positive) coefficient sequences {a(m)} in which some of these values approach $0$ or $\infty$ as $m \rightarrow \infty$. We consider the performance of additive Schwarz domain decomposition preconditioners constructed from local solves on automatically generated subdomains together with a global solve on some coarser grid. Assuming no relationship between the regions on which the coefficient function is constant and either the subdomains or the coarse grid, we show that the preconditioned conjugate gradient method converges (in both the energy and the Euclidean norms) with a number of iterations which grows only logarithmically in the size of the maximum jump ${\cal J}^{(m)} := \max\{a_k^{(m)}/a_l^{(m)} \ : \ k, l = 1, \ldots , d\} $, as $m\rightarrow \infty$. The result is obtained by a careful analysis of the preconditioned matrix. It cannot be obtained by the usual procedure of estimating condition numbers: a simple example is given in which the condition number of both the original and the preconditioned stiffness matrices degrade linearly in ${\cal J}^{(m)}$. Recent results of Chan, Smith, and Zou have shown that by using this preconditioner together with the conjugate gradient method, the number of iterations can be bounded independently of the mesh diameter provided the subdomains have overlap commensurate with the size of the coarse mesh. Our results now show that this method is also highly resilient to discontinuous coefficients, even if no attention is paid to the coefficient discontinuity in the construction of the solver.