Hybrid Domain Decomposition with Unstructured Subdomains ∗

Abstract. We develop several new domain decomposition methods for solving large scale systems of symmetric, positive definite algebraic equations arising from discretizations of partial differential equations by conforming finite elements. First, the hybrid Schwarz alternating method is developed and analyzed. This method treats the coarse space in a multiplicative and the local spaces in an additive fashion, resulting in faster convergence at little extra cost. Then four methods based on reduction to interfaces and space splitting are presented, two using a coarse space consisting of linear functions and two with coarse space of piecewise constant functions on subdomain interfaces. Finally, we study an overlapping Schwarz method with a discrete harmonic coarse space, piecewise constant on interfaces. The condition numbers of all methods are proved to grow at most as log 2 (H/h) and to be bounded independently of the number of subdomains when the subdomains form a shape regular coarse triangulation both in 2D and 3D. The methods with piecewise constant coarse space can be implemented as “black box ” solvers without any reference to geometry and are suitable for subdomains of arbitrary shape