Efficient Algebraic Two-Level Schwarz Preconditioner for Sparse Matrices

DOI10.1137/22M1469833zbMATH Open1521.65026arXiv2201.02250OpenAlexW4380083373MaRDI QIDQ6098522FDOQ6098522

Authors: Hussam al Daas, Pierre Jolivet, Tyrone Rees 

Publication date: 14 June 2023

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Abstract: Domain decomposition methods are among the most efficient for solving sparse linear systems of equations. Their effectiveness relies on a judiciously chosen coarse space. Originally introduced and theoretically proved to be efficient for self-adjoint operators, spectral coarse spaces have been proposed in the past few years for indefinite and non-self-adjoint operators. This paper presents a new spectral coarse space that can be constructed in a fully-algebraic way unlike most existing spectral coarse spaces. We present theoretical convergence result for Hermitian positive definite diagonally dominant matrices. Numerical experiments and comparisons against state-of-the-art preconditioners in the multigrid community show that the resulting two-level Schwarz preconditioner is efficient especially for non-self-adjoint operators. Furthermore, in this case, our proposed preconditioner outperforms state-of-the-art preconditioners.

Full work available at URL: https://arxiv.org/abs/2201.02250

Recommendations

• Algebraic two-level preconditioners for the Schur complement method
• An algebraic multilevel preconditioner with low-rank corrections for sparse symmetric matrices
• Two-level Nyström-Schur preconditioner for sparse symmetric positive definite matrices
• Algebraic multigrid preconditioners for sparse approximations of boundary element matrices
• Preconditioning Sparse Matrices with Alternating and Multiplicative Operator Splittings
• Parallel algebraic multilevel Schwarz preconditioners for a class of elliptic PDE systems
• A discovery algorithm for the algebraic construction of optimized Schwarz preconditioners
• Application of Sparse Matrix Solvers as Effective Preconditioners
• A robust algebraic multilevel domain decomposition preconditioner for sparse symmetric positive definite matrices
• Algebraic multilevel iterative preconditioning methods for h-matrices

zbMATH Keywords

sparse linear systemsnon-self-adjoint operatorstwo-level Schwarz methodsalgebraic domain decomposition methods

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) Preconditioners for iterative methods (65F08) Numerical solution of discretized equations for boundary value problems involving PDEs (65N22)

Cites Work

• Title not available (Why is that?)
• The University of Florida sparse matrix collection
• New development in freefem++
• GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
• Streamline upwind/Petrov-Galerkin formulations for convection dominated flows with particular emphasis on the incompressible Navier-Stokes equations
• A Restricted Additive Schwarz Preconditioner for General Sparse Linear Systems
• Title not available (Why is that?)
• Automatic spectral coarse spaces for robust finite element tearing and interconnecting and balanced domain decomposition\ algorithms
• Abstract robust coarse spaces for systems of PDEs via generalized eigenproblems in the overlaps
• Variational Iterative Methods for Nonsymmetric Systems of Linear Equations
• A coarse space construction based on local Dirichlet-to-Neumann maps
• Title not available (Why is that?)
• Comparison of two-level preconditioners derived from deflation, domain decomposition and multigrid methods
• Aggregation-Based Algebraic Multigrid for Convection-Diffusion Equations
• An introduction to domain decomposition methods. Algorithms, theory, and parallel implementation
• Domain Decomposition Algorithms for Indefinite Elliptic Problems
• Parallel Multilevel series k-Way Partitioning Scheme for Irregular Graphs
• An aggregation-based algebraic multigrid method
• FETI-DP Methods with an Adaptive Coarse Space
• Spectral AMGe ($\rho$AMGe)
• Spectral element agglomerate algebraic multigrid methods for elliptic problems with high-contrast coefficients
• Multilevel Spectral Domain Decomposition
• Title not available (Why is that?)
• Direct methods for sparse matrices
• Adaptive coarse spaces for FETI-DP in three dimensions
• Energy-minimizing coarse spaces for two-level Schwarz methods for multiscale PDEs
• Algebraic multigrid methods
• Iterative methods for linear systems of equations: a brief historical journey
• SHEM: An Optimal Coarse Space for RAS and Its Multiscale Approximation
• On the Dirichlet-to-Neumann coarse space for solving the Helmholtz problem using domain decomposition
• A scalable nonlinear fluid-structure interaction solver based on a Schwarz preconditioner with isogeometric unstructured coarse spaces in 3D
• Analysis of the SORAS domain decomposition preconditioner for non-self-adjoint or indefinite problems
• Nonsymmetric reduction-based algebraic multigrid
• A comparison of coarse spaces for Helmholtz problems in the high frequency regime
• KSPHPDDM and PCHPDDM: extending PETSc with advanced Krylov methods and robust multilevel overlapping Schwarz preconditioners
• A multilevel Schwarz preconditioner based on a hierarchy of robust coarse spaces
• Two-level preconditioning for \(h\)-version boundary element approximation of hypersingular operator with GenEO
• Nonsymmetric algebraic multigrid based on local approximate ideal restriction (\(\ell\)AIR)
• Monolithic overlapping Schwarz domain decomposition methods with GDSW coarse spaces for incompressible fluid flow problems
• A robust algebraic multilevel domain decomposition preconditioner for sparse symmetric positive definite matrices
• AMG by element agglomeration and constrained energy minimization interpolation
• A class of efficient locally constructed preconditioners based on coarse spaces
• A Robust Algebraic Domain Decomposition Preconditioner for Sparse Normal Equations
• Overlapping Schwarz methods with GenEO coarse spaces for indefinite and nonself-adjoint problems

Cited In (7)

• Fully algebraic domain decomposition preconditioners with adaptive spectral bounds
• Robust preconditioners via generalized eigenproblems for hybrid sparse linear solvers
• A scalable two-level domain decomposition eigensolver for periodic Schrödinger eigenstates in anisotropically expanding domains
• A class of efficient locally constructed preconditioners based on coarse spaces
• A robust algebraic multilevel domain decomposition preconditioner for sparse symmetric positive definite matrices
• Algebraic two-level preconditioners for the Schur complement method
• Two-level algebraic domain decomposition preconditioners using Jacobi-Schwarz smoother and adaptive coarse grid corrections

This page was built for publication: Efficient Algebraic Two-Level Schwarz Preconditioner for Sparse Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6098522)