Unstructured additive Schwarz-conjugate gradient method for elliptic problems with highly discontinuous coefficients

This paper concerns the iterative solution of symmetric elliptic problems w ith piecewise constant coefficients in two or three space dimensions discre tized by linear finite element methods on unstructured triangular or tetrah edral meshes. The effect of the discontinuous coefficients is studied by fi rst postulating that there are d fixed regions of the domain where the coef ficient takes constant positive values a = (a(1),..., a(d)) and then consid ering certain (positive) coefficient sequences {a((m))} in which some of th ese values approach 0 or infinity as m --> infinity. We consider the perfor mance of additive Schwarz domain decomposition preconditioners constructed from local solves on automatically generated subdomains together with a glo bal solve on some coarser grid. Assuming no relationship between the region s on which the coefficient function is constant and either the subdomains o r the coarse grid, we show that the preconditioned conjugate gradient metho d converges (in both the energy and the Euclidean norms) with a number of i terations which grows only logarithmically in the size of the maximum jump J((m)) := max{a(k)((m)) / a(l)((m)) : k, l = 1,..., d}, as m --> infinity. The result is obtained by a careful analysis of the preconditioned matrix. It cannot be obtained by the usual procedure of estimating condition number s: a simple example is given in which the condition number of both the orig inal and the preconditioned stiffness matrices degrade linearly in J((m)). Recent results of Chan, Smith, and Zou have shown that by using this precon ditioner together with the conjugate gradient method, the number of iterati ons can be bounded independently of the mesh diameter provided the subdomai ns have overlap commensurate with the size of the coarse mesh. Our results now show that this method is also highly resilient to discontinuous coeffic ients, even if no attention is paid to the coefficient discontinuity in the construction of the solver.