Approximate Generalized Inverses with Iterative Refinement for \epsilon-Accurate Preconditioning of Singular Systems
From MaRDI portal
Publication:5028552
DOI10.1137/20M1364126zbMATH Open1482.65044arXiv2009.01673OpenAlexW4206522135MaRDI QIDQ5028552FDOQ5028552
Publication date: 10 February 2022
Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)
Abstract: We introduce a new class of preconditioners to enable flexible GMRES to find a least-squares solution, and potentially the pseudoinverse solution, of large-scale sparse, asymmetric, singular, and potentially inconsistent systems. We develop the preconditioners based on a new observation that generalized inverses (i.e., ) enable the preconditioned Krylov subspaces to converge in a single step. We then compute an approximate generalized inverse (AGI) efficiently using a hybrid incomplete factorization (HIF), which combines multilevel incomplete LU with rank-revealing QR on its final Schur complement. We define the criteria of -accuracy and stability of AGI to guarantee the convergence of preconditioned GMRES for consistent systems. For inconsistent systems, we fortify HIF with iterative refinement to obtain HIFIR, which allows accurate computations of the null-space vectors. By combining the two techniques, we then obtain a new solver, called PIPIT, for obtaining the pseudoinverse solutions for systems with low-dimensional null spaces. We demonstrate the robustness of HIF and HIFIR and show that they improve both accuracy and efficiency of the prior state of the art by orders of magnitude for systems with up to a million unknowns.
Full work available at URL: https://arxiv.org/abs/2009.01673
Recommendations
- Generalized approximate inverse preconditioners for least squares problems
- Convergence and preconditioning of inexact inverse subspace iteration for generalized eigenvalue problems
- scientific article; zbMATH DE number 2104044
- On Least-Squares Approximate Inverse-Based Preconditioners
- Approximate Inverse Preconditioners for the Conjugate Gradient Method
- Approximate Inverse Preconditioners via Sparse-Sparse Iterations
- Approximate inverse preconditioner by computing approximate solution of Sylvester equation
- A class of approximate inverse preconditioners for solving linear systems
- Convergence of inexact inverse iteration with application to preconditioned iterative solvers
- Mixed Precision Iterative Refinement with Sparse Approximate Inverse Preconditioning
generalized inversesiterative refinementpseudoinverse solutionflexible Krylov subspaceshybrid incomplete factorizationrank-deficient least squaresvariable preconditions
Computational methods for sparse matrices (65F50) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Preconditioners for iterative methods (65F08)
Cites Work
- Gmsh: a 3-D finite element mesh generator with built-in pre- and post-processing facilities
- LAPACK Users' Guide
- LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
- The university of Florida sparse matrix collection
- MIQR: A Multilevel Incomplete QR Preconditioner for Large Sparse Least‐Squares Problems
- The Finite Element Method for Three‐Dimensional Thermomechanical Applications
- DGMRES: A GMRES-type algorithm for Drazin-inverse solution of singular nonsymmetric linear systems
- MINRES-QLP: A Krylov Subspace Method for Indefinite or Singular Symmetric Systems
- LSMR: An Iterative Algorithm for Sparse Least-Squares Problems
- Rang revealing QR factorizations
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- An Approximate Minimum Degree Ordering Algorithm
- Methods of conjugate gradients for solving linear systems
- Generalized inverses. Theory and applications.
- On algorithms for permuting large entries to the diagonal of a sparse matrix
- GMRES On (Nearly) Singular Systems
- Numerical solution of saddle point problems
- A Robust Preconditioner with Low Memory Requirements for Large Sparse Least Squares Problems
- Title not available (Why is that?)
- Encyclopedia of Parallel Computing
- Accelerated projection methods for computing pseudoinverse solutions of systems of linear equations
- Title not available (Why is that?)
- Augmented Implicitly Restarted Lanczos Bidiagonalization Methods
- Algorithm 915, SuiteSparseQR
- GMRES Methods for Least Squares Problems
- Iterative Refinement Implies Numerical Stability for Gaussian Elimination
- Solution of Sparse Indefinite Systems of Linear Equations
- Title not available (Why is that?)
- Title not available (Why is that?)
- Multilevel Preconditioners Constructed From Inverse-Based ILUs
- GMRES-type methods for inconsistent systems
- A Multigrid Tutorial, Second Edition
- Strategies for Scaling and Pivoting for Sparse Symmetric Indefinite Problems
- Finite elements and fast iterative solvers. With applications in incompressible fluid dynamics
- A Flexible Inner-Outer Preconditioned GMRES Algorithm
- Breakdown-free GMRES for Singular Systems
- On the Finite Element Solution of the Pure Neumann Problem
- Title not available (Why is that?)
- Convergence of Inner-Iteration GMRES Methods for Rank-Deficient Least Squares Problems
- Inner-Iteration Krylov Subspace Methods for Least Squares Problems
- Application of the generalized finite difference method to solve the advection-diffusion equation
- Projection method for solving a singular system of linear equations and its applications
- Least-squares solution of overdetermined inconsistent linear systems using kaczmarz's relaxation
- On pressure boundary conditions for the incompressible Navier-Stokes equations
- A robust incomplete factorization preconditioner for positive definite matrices
- Using FGMRES to obtain backward stability in mixed precision
- Crout Versions of ILU for General Sparse Matrices
- On backtracking failure in Newton-GMRES methods with a demonstration for the Navier-Stokes equations
- Preconditioning techniques for nonsymmetric and indefinite linear systems
- A multilevel Crout ILU preconditioner with pivoting and row permutation
- Flexible Inner-Outer Krylov Subspace Methods
- The State-of-the-Art of Preconditioners for Sparse Linear Least-Squares Problems
- On the use of two QMR algorithms for solving singular systems and applications in Markov chain modeling
- Eigenvectors from eigenvalues: A survey of a basic identity in linear algebra
- A New Analysis of Iterative Refinement and Its Application to Accurate Solution of Ill-Conditioned Sparse Linear Systems
- Incremental Condition Estimation
- Title not available (Why is that?)
- Incomplete Methods for Solving $A^T Ax = b$
- A stationary iterative pseudoinverse algorithm
- A comparison of preconditioned Krylov subspace methods for large‐scale nonsymmetric linear systems
- On GMRES for Singular EP and GP Systems
- On the singular Neumann problem in linear elasticity
- Right preconditioned MINRES for singular systems †
- Preconditioning of linear least squares by robust incomplete factorization for implicitly held normal equations
- HILUCSI: Simple, robust, and fast multilevel ILU for large‐scale saddle‐point problems from PDEs
Cited In (1)
Uses Software
This page was built for publication: Approximate Generalized Inverses with Iterative Refinement for $\epsilon$-Accurate Preconditioning of Singular Systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5028552)
