A Robust Algebraic Domain Decomposition Preconditioner for Sparse Normal Equations
From MaRDI portal
Publication:5075692
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.
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
Cites work
- scientific article; zbMATH DE number 671790 (Why is no real title available?)
- scientific article; zbMATH DE number 749527 (Why is no real title available?)
- scientific article; zbMATH DE number 949303 (Why is no real title available?)
- scientific article; zbMATH DE number 2088244 (Why is no real title available?)
- A Krylov--Schur algorithm for large eigenproblems
- A Restricted Additive Schwarz Preconditioner for General Sparse Linear Systems
- A class of efficient locally constructed preconditioners based on coarse spaces
- A fully asynchronous multifrontal solver using distributed dynamic scheduling
- A multilevel Schwarz preconditioner based on a hierarchy of robust coarse spaces
- A scalable nonlinear fluid-structure interaction solver based on a Schwarz preconditioner with isogeometric unstructured coarse spaces in 3D
- Abstract robust coarse spaces for systems of PDEs via generalized eigenproblems in the overlaps
- Algorithm 915: SuiteSparseQR: multifrontal multithreaded rank-revealing sparse QR factorization
- An introduction to domain decomposition methods. Algorithms, theory, and parallel implementation
- Block-iterative methods for consistent and inconsistent linear equations
- Comparison of two-level preconditioners derived from deflation, domain decomposition and multigrid methods
- Distance-two interpolation for parallel algebraic multigrid
- Energy-minimizing coarse spaces for two-level Schwarz methods for multiscale PDEs
- Extensions of the Augmented Block Cimmino Method to the Solution of Full Rank Rectangular Systems
- GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
- Generalized approximate inverse preconditioners for least squares problems
- Implementing Multifrontal Sparse Solvers for Multicore Architectures with Sequential Task Flow Runtime Systems
- Iterated preconditioned LSQR method for inverse problems on unstructured grids
- KSPHPDDM and PCHPDDM: extending PETSc with advanced Krylov methods and robust multilevel overlapping Schwarz preconditioners
- LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
- MIQR: A Multilevel Incomplete QR Preconditioner for Large Sparse Least‐Squares Problems
- Monolithic overlapping Schwarz domain decomposition methods with GDSW coarse spaces for incompressible fluid flow problems
- Parallel Multilevel series k-Way Partitioning Scheme for Irregular Graphs
- Preconditioned iterative methods for solving linear least squares problems
- Preconditioning of linear least squares by robust incomplete factorization for implicitly held normal equations
- Reducing Complexity in Parallel Algebraic Multigrid Preconditioners
- SHEM: An Optimal Coarse Space for RAS and Its Multiscale Approximation
- SLEPc
- Solving mixed sparse-dense linear least-squares problems by preconditioned iterative methods
- Sparse Matrix-Matrix Products Executed Through Coloring
- Strengths and Limitations of Stretching for Least-squares Problems with Some Dense Rows
- The State-of-the-Art of Preconditioners for Sparse Linear Least-Squares Problems
- The University of Florida sparse matrix collection
- The augmented block Cimmino distributed method
- Two-level preconditioning for h-version boundary element approximation of hypersingular operator with GenEO
Cited in
(8)- Thick-restarted joint Lanczos bidiagonalization for the GSVD
- 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
Describes a project that uses
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)
