RASHO: a restricted additive Schwarz preconditioner with harmonic overlap.
Maksymilian Dryja, Xiao‐Chuan Cai, Marcus V. Sarkis · 2002
A restricted additive Schwarz (RAS) preconditioning technique was introduced recently for solving general nonsymmetric sparse linear systems [1, 3, 4, 7, 8, 9, 11]. The RAS preconditioner improves the classical additive Schwarz preconditioner (AS), [10], in the sense that it reduces the number of iterations of the iterative method, such as GMRES, and also reduces the communication cost per iteration when implemented on distributed memory computers. However, RAS in its original form is a nonsymmetric preconditioner and therefore the cannot be used with the Conjugate Gradient method (CG). In this paper, we provide an extension of RAS for symmetric positive definite problems using the so-called harmonic overlaps (RASHO). Both RAS and RASHO outperform their counterparts of the classical additive Schwarz variants. Roughly speaking, the design of RASHO is based on a much deeper understanding of the behavior of Schwarz type methods in the overlapping regions, and in the construction of the overlap. Under RASHO, the overlap is obtained by extending the nonoverlapping subdomains only in the directions that do not cut the boundaries of other subdomains, and all functions are made harmonic in the overlapping regions. As a result, the subdomain problems in RASHO are smaller than those of AS, and the communication cost is also smaller when implemented on distributed memory computers, since the right-hand sides of discrete harmonic systems are always zero that do not need to be communicated. We will show numerically that RASHO preconditioned CG takes less number of iterations than the corresponding AS preconditioned CG. An almost optimal convergence theory will be ∗Department of Computer Science, University of Colorado, Boulder, CO 80309, ([email protected]). The work was supported in part by the NSF grants ASC-9457534, ECS-9725504, and ACI-0072089. †Faculty of Mathematics, Informatics and Mechanics, Warsaw University, Warsaw, ([email protected]). This work was supported in part by the NSF grant CCR-9732208 and in part by the Polish Science Foundation grant 2 P03A 021 16. ‡Mathematical Sciences Department, Worcester Polytechnic Institute, Worcester, MA 01609, ([email protected]). The work was supported in part by the NSF grant CCR-9984404.