Algebraic construction of adaptive coarse spaces for two-level schwarz preconditioners

Two-level domain decomposition preconditioners lead to fast convergence and scalability of iterative solvers. However, for highly heterogeneous problems with a rapidly varying coefficient function, the condition number of the preconditioned system generally depends on the contrast of the coefficient function. As a result, the convergence may deteriorate. Enhancing the coarse space by functions constructed from suitable local eigenvalue problems restores robust, contrast-independent convergence; these coarse spaces are often denoted as adaptive or spectral coarse spaces. However, these eigenvalue problems typically rely on nonalgebraic information such that the adaptive coarse spaces cannot be constructed from the fully assembled system matrix. In this paper, a novel algebraic adaptive coarse space which relies on the a-orthogonal decomposition of (local) finite element (FE) spaces into functions that solve the elliptic PDE with some trace and FE functions that are zero on the boundary is proposed. In particular, the basis is constructed from eigenmodes of two types of local eigenvalue problems associated with the edges of the domain decomposition. To approximate functions that solve the PDE locally, we employ a transfer eigenvalue problem which has originally been proposed for the construction of optimal local approximation spaces for multiscale methods. In addition, we make use of a Dirichlet eigenvalue problem that is a slight modification of the Neumann eigenvalue problem used in the adaptive generalized Dryja-Smith-Widlund (AGDSW) coarse space. Both eigenvalue problems rely solely on local Dirichlet matrices, which can be extracted from the fully assembled system matrix, allowing for an algebraic construction. By combining arguments from multiscale and domain decomposition methods, we derive a contrast-independent upper bound for the condition number. While we restrict ourselves here to a two-dimensional diffusion problem discretized by low-order FEs on regular meshes, the proposed framework is general, and we conjecture that the approach can be readily extended, for instance, to other elliptic problems, three dimensions, or, under mild assumptions, higher-order discretizations. The robustness of the method is confirmed numerically for a variety of heterogeneous coefficient distributions, including binary random distributions and a coefficient function constructed from the SPE10 benchmark. The results are comparable to those of the nonalgebraic AGDSW coarse space as well as for those cases where the convergence of the classical algebraic generalized Dryja-Smith-Widlund coarse space deteriorates. Moreover, the coarse space dimension is the same as or comparable to the AGDSW coarse space for all numerical experiments.