A Robust Algebraic Domain Decomposition Preconditioner for Sparse Normal Equations
From MaRDI portal
Publication:5075692
DOI10.1137/21M1434891zbMATH Open1492.65070arXiv2107.09006OpenAlexW3185705022MaRDI QIDQ5075692FDOQ5075692
Authors: Hussam al Daas, J. A. Scott, Pierre Jolivet 
Publication date: 11 May 2022
Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)
Abstract: Solving the normal equations corresponding to large sparse linear least-squares problems is an important and challenging problem. For very large problems, an iterative solver is needed and, in general, a preconditioner is required to achieve good convergence. In recent years, a number of preconditioners have been proposed. These are largely serial and reported results demonstrate that none of the commonly used preconditioners for the normal equations matrix is capable of solving all sparse least-squares problems. Our interest is thus in designing new preconditioners for the normal equations that are efficient, robust, and can be implemented in parallel. Our proposed preconditioners can be constructed efficiently and algebraically without any knowledge of the problem and without any assumption on the least-squares matrix except that it is sparse. We exploit the structure of the symmetric positive definite normal equations matrix and use the concept of algebraic local symmetric positive semi-definite splittings to introduce two-level Schwarz preconditioners for least-squares problems. The condition number of the preconditioned normal equations is shown to be theoretically bounded independently of the number of subdomains in the splitting. This upper bound can be adjusted using a single parameter that the user can specify. We discuss how the new preconditioners can be implemented on top of the PETSc library using only 150 lines of Fortran, C, or Python code. Problems arising from practical applications are used to compare the performance of the proposed new preconditioner with that of other preconditioners.
Full work available at URL: https://arxiv.org/abs/2107.09006
Recommendations
- A robust algebraic multilevel domain decomposition preconditioner for sparse symmetric positive definite matrices
- A preconditioner for the normal equations
- Low-Rank Correction Methods for Algebraic Domain Decomposition Preconditioners
- Algebraic multigrid preconditioners for sparse approximations of boundary element matrices
- Robust algebraic multilevel preconditioners for anisotropic problems
- Using explicit preconditioned domain decomposition methods for solving singular perturbed linear problems
- A New Family of Preconditioners for Domain Decomposition
- Robust preconditioners via generalized eigenproblems for hybrid sparse linear solvers
- Preconditioners for nonconforming domain decomposition methods
- scientific article; zbMATH DE number 179274
normal equationsalgebraic domain decompositiontwo-level preconditioneradditive Schwarzsparse linear least-squares
Computational methods for sparse matrices (65F50) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Preconditioners for iterative methods (65F08)
Cites Work
- LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
- Title not available (Why is that?)
- The University of Florida sparse matrix collection
- MIQR: A Multilevel Incomplete QR Preconditioner for Large Sparse Least‐Squares Problems
- A fully asynchronous multifrontal solver using distributed dynamic scheduling
- Implementing Multifrontal Sparse Solvers for Multicore Architectures with Sequential Task Flow Runtime Systems
- GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
- A Restricted Additive Schwarz Preconditioner for General Sparse Linear Systems
- Algorithm 915: SuiteSparseQR: multifrontal multithreaded rank-revealing sparse QR factorization
- Abstract robust coarse spaces for systems of PDEs via generalized eigenproblems in the overlaps
- Title not available (Why is that?)
- Comparison of two-level preconditioners derived from deflation, domain decomposition and multigrid methods
- A Krylov--Schur algorithm for large eigenproblems
- An introduction to domain decomposition methods. Algorithms, theory, and parallel implementation
- SLEPc
- Parallel Multilevel series k-Way Partitioning Scheme for Irregular Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Reducing Complexity in Parallel Algebraic Multigrid Preconditioners
- Block-iterative methods for consistent and inconsistent linear equations
- Title not available (Why is that?)
- The augmented block Cimmino distributed method
- The State-of-the-Art of Preconditioners for Sparse Linear Least-Squares Problems
- Energy-minimizing coarse spaces for two-level Schwarz methods for multiscale PDEs
- Generalized approximate inverse preconditioners for least squares problems
- Distance-two interpolation for parallel algebraic multigrid
- Solving mixed sparse-dense linear least-squares problems by preconditioned iterative methods
- Strengths and Limitations of Stretching for Least-squares Problems with Some Dense Rows
- SHEM: An Optimal Coarse Space for RAS and Its Multiscale Approximation
- A scalable nonlinear fluid-structure interaction solver based on a Schwarz preconditioner with isogeometric unstructured coarse spaces in 3D
- 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
- Preconditioning of linear least squares by robust incomplete factorization for implicitly held normal equations
- Iterated preconditioned LSQR method for inverse problems on unstructured grids
- Monolithic overlapping Schwarz domain decomposition methods with GDSW coarse spaces for incompressible fluid flow problems
- Sparse Matrix-Matrix Products Executed Through Coloring
- A class of efficient locally constructed preconditioners based on coarse spaces
- Extensions of the Augmented Block Cimmino Method to the Solution of Full Rank Rectangular Systems
Cited In (8)
- Low-Rank Correction Methods for Algebraic Domain Decomposition Preconditioners
- Approximating sparse Hessian matrices using large-scale linear least squares
- Multigrid preconditioning for regularized least-squares problems
- Multilevel Spectral Domain Decomposition
- Efficient Algebraic Two-Level Schwarz Preconditioner for Sparse Matrices
- Preconditioning of linear least squares by robust incomplete factorization for implicitly held normal equations
- A robust algebraic multilevel domain decomposition preconditioner for sparse symmetric positive definite matrices
- Thick-restarted joint Lanczos bidiagonalization for the GSVD
Uses Software
This page was built for publication: A Robust Algebraic Domain Decomposition Preconditioner for Sparse Normal Equations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5075692)
