Volume 60, pp. 169-196, 2024.

Fully algebraic domain decomposition preconditioners with adaptive spectral bounds

Loïc Gouarin and Nicole Spillane

Abstract

In this article a new family of preconditioners is introduced for symmetric positive definite linear systems. The new preconditioners, called the AWG preconditioners (for Algebraic-Woodbury-GenEO), are constructed algebraically. By this we mean that only the knowledge of the matrix A for which the linear system is being solved is required. Thanks to the GenEO spectral coarse space technique, the condition number of the preconditioned operator is bounded theoretically from above. This upper bound can be made smaller by enriching the coarse space with more spectral modes. The novelty is that, unlike in previous work on the GenEO coarse spaces, no knowledge of a partially non-assembled form of A is required. Indeed, the spectral coarse space technique is not applied directly to A but to a low-rank modification of A of which a suitable non-assembled form is known by construction. The extra cost is a second (and to this day rather expensive) coarse solve in the preconditioner. One of the AWG preconditioners has already been presented in a short preprint by Spillane [Domain Decomposition Methods in Science and Engineering XXVI, Springer, Cham, 2022, pp. 745–752]. This article is the first full presentation of the larger family of AWG preconditioners. It includes proofs of the spectral bounds as well as numerical illustrations.

Full Text (PDF) [1.1 MB], BibTeX , DOI: 10.1553/etna_vol60s169

Key words

preconditioner, domain decomposition, coarse space, algebraic, linear system, Woodbury matrix identity

AMS subject classifications

65F10, 65N30, 65N55

Links to the cited ETNA articles

[15] Vol. 45 (2016), pp. 524-544 Juan G. Calvo and Olof B. Widlund: An adaptive choice of primal constraints for BDDC domain decomposition algorithms
[32] Vol. 45 (2016), pp. 75-106 Axel Klawonn, Patrick Radtke, and Oliver Rheinbach: A comparison of adaptive coarse spaces for iterative substructuring in two dimensions
[39] Vol. 37 (2010), pp. 123-146 Yvan Notay: An aggregation-based algebraic multigrid method
[41] Vol. 46 (2017), pp. 273-336 Clemens Pechstein and Clark R. Dohrmann: A unified framework for adaptive BDDC