Approximate Generalized Inverses with Iterative Refinement for \epsilon-Accurate Preconditioning of Singular Systems
From MaRDI portal
Publication:5028552
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.
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
Cites work
- scientific article; zbMATH DE number 5979094 (Why is no real title available?)
- scientific article; zbMATH DE number 1012640 (Why is no real title available?)
- scientific article; zbMATH DE number 1953444 (Why is no real title available?)
- scientific article; zbMATH DE number 852536 (Why is no real title available?)
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- scientific article; zbMATH DE number 3367052 (Why is no real title available?)
- scientific article; zbMATH DE number 5180707 (Why is no real title available?)
- scientific article; zbMATH DE number 3027894 (Why is no real title available?)
- scientific article; zbMATH DE number 3111121 (Why is no real title available?)
- A Flexible Inner-Outer Preconditioned GMRES Algorithm
- A Multigrid Tutorial, Second Edition
- A Robust Preconditioner with Low Memory Requirements for Large Sparse Least Squares Problems
- A comparison of preconditioned Krylov subspace methods for large‐scale nonsymmetric linear systems
- A multilevel Crout ILU preconditioner with pivoting and row permutation
- A new analysis of iterative refinement and its application to accurate solution of ill-conditioned sparse linear systems
- A robust incomplete factorization preconditioner for positive definite matrices
- A stationary iterative pseudoinverse algorithm
- Accelerated projection methods for computing pseudoinverse solutions of systems of linear equations
- Algorithm 915: SuiteSparseQR: multifrontal multithreaded rank-revealing sparse QR factorization
- An Approximate Minimum Degree Ordering Algorithm
- Application of the generalized finite difference method to solve the advection-diffusion equation
- Augmented Implicitly Restarted Lanczos Bidiagonalization Methods
- Breakdown-free GMRES for Singular Systems
- Convergence of inner-iteration GMRES methods for rank-deficient least squares problems
- Crout Versions of ILU for General Sparse Matrices
- DGMRES: A GMRES-type algorithm for Drazin-inverse solution of singular nonsymmetric linear systems
- Eigenvectors from eigenvalues: a survey of a basic identity in linear algebra
- Encyclopedia of parallel computing.
- Finite elements and fast iterative solvers. With applications in incompressible fluid dynamics
- Flexible Inner-Outer Krylov Subspace Methods
- GMRES On (Nearly) Singular Systems
- GMRES methods for least squares problems
- GMRES-type methods for inconsistent systems
- Generalized inverses. Theory and applications.
- Gmsh: a 3-D finite element mesh generator with built-in pre- and post-processing facilities
- HILUCSI: Simple, robust, and fast multilevel ILU for large‐scale saddle‐point problems from PDEs
- Incomplete Methods for Solving $A^T Ax = b$
- Incremental Condition Estimation
- Inner-Iteration Krylov Subspace Methods for Least Squares Problems
- Iterative Refinement Implies Numerical Stability for Gaussian Elimination
- LAPACK Users' Guide
- LSMR: An Iterative Algorithm for Sparse Least-Squares Problems
- LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
- Least-squares solution of overdetermined inconsistent linear systems using kaczmarz's relaxation
- MINRES-QLP: a Krylov subspace method for indefinite or singular symmetric systems
- MIQR: A Multilevel Incomplete QR Preconditioner for Large Sparse Least‐Squares Problems
- Methods of conjugate gradients for solving linear systems
- Multilevel Preconditioners Constructed From Inverse-Based ILUs
- Numerical solution of saddle point problems
- On GMRES for singular EP and GP systems
- On algorithms for permuting large entries to the diagonal of a sparse matrix
- On backtracking failure in Newton-GMRES methods with a demonstration for the Navier-Stokes equations
- On pressure boundary conditions for the incompressible Navier-Stokes equations
- On the Finite Element Solution of the Pure Neumann Problem
- On the singular Neumann problem in linear elasticity
- On the use of two QMR algorithms for solving singular systems and applications in Markov chain modeling
- Preconditioning of linear least squares by robust incomplete factorization for implicitly held normal equations
- Preconditioning techniques for nonsymmetric and indefinite linear systems
- Projection method for solving a singular system of linear equations and its applications
- Rang revealing QR factorizations
- Right preconditioned MINRES for singular systems.
- Solution of Sparse Indefinite Systems of Linear Equations
- Strategies for Scaling and Pivoting for Sparse Symmetric Indefinite Problems
- The Finite Element Method for Three‐Dimensional Thermomechanical Applications
- The State-of-the-Art of Preconditioners for Sparse Linear Least-Squares Problems
- The University of Florida sparse matrix collection
- Using FGMRES to obtain backward stability in mixed precision
Describes a project that uses
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)
