Randomized Block Adaptive Linear System Solvers
From MaRDI portal
Publication:6094749
Abstract: Randomized linear solvers randomly compress and solve a linear system with compelling theoretical convergence rates and computational complexities. However, such solvers suffer a substantial disconnect between their theoretical rates and actual efficiency in practice. Fortunately, these solvers are quite flexible and can be adapted to specific problems and computing environments to ensure high efficiency in practice, even at the cost of lower effectiveness (i.e., having a slower theoretical rate of convergence). While highly efficient adapted solvers can be readily designed by application experts, will such solvers still converge and at what rate? To answer this, we distill three general criteria for randomized adaptive solvers, which, as we show, will guarantee a worst-case exponential rate of convergence of the solver applied to consistent and inconsistent linear systems irrespective of whether such systems are over-determined, under-determined or rank-deficient. As a result, we enable application experts to design randomized adaptive solvers that achieve efficiency and can be verified for effectiveness using our theory. We demonstrate our theory on twenty-six solvers, nine of which are novel or novel block extensions of existing methods to the best of our knowledge.
Recommendations
- Randomized iterative methods for linear systems
- An adaptive block Lanczos algorithm
- Accelerating Linear System Solutions Using Randomization Techniques
- A Randomized Solver for Linear Systems with Exponential Convergence
- On randomized partial block Kaczmarz method for solving huge linear algebraic systems
- On greedy randomized block Kaczmarz method for consistent linear systems
- scientific article; zbMATH DE number 592771
- Randomized methods for rank-deficient linear systems
- Block descent methods and hybrid procedures for linear systems
- A randomised iterative method for solving factorised linear systems
Cites work
- A Matrix Inequality
- A mean ergodic theorem
- A randomized Kaczmarz algorithm with exponential convergence
- A weighted randomized Kaczmarz method for solving linear systems
- An Implicit Representation and Iterative Solution of Randomly Sketched Linear Systems
- Analyzing random permutations for cyclic coordinate descent
- Approximate solution of systems of linear equations†
- Faster randomized block Kaczmarz algorithms
- scientific article; zbMATH DE number 1953444 (Why is no real title available?)
- scientific article; zbMATH DE number 3892457 (Why is no real title available?)
- Iterative Hessian sketch: fast and accurate solution approximation for constrained least-squares
- Markov chains and stochastic stability
- Minimizing Certain Convex Functions
- On Adaptive Sketch-and-Project for Solving Linear Systems
- On block Gaussian sketching for the Kaczmarz method
- On greedy randomized Kaczmarz method for solving large sparse linear systems
- On Improving Linear Solver Performance: A Block Variant of GMRES
- On the Meany inequality with applications to convergence analysis of several row-action iteration methods
- Parallel random coordinate descent method for composite minimization: convergence analysis and error bounds
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Randomized block Kaczmarz method with projection for solving least squares
- Randomized extended Kaczmarz for solving least squares
- Randomized iterative methods for linear systems
- Randomized numerical linear algebra: Foundations and algorithms
- Sketching as a tool for numerical linear algebra
- Stochastic reformulations of linear systems: algorithms and convergence theory
- The Relaxation Method for Linear Inequalities
- The Relaxation Method for Linear Inequalities
Cited in
(5)- An adaptive block Lanczos algorithm
- A doubly stochastic block Gauss-Seidel algorithm for solving linear equations
- Towards Practical Large-Scale Randomized Iterative Least Squares Solvers through Uncertainty Quantification
- Solving, tracking and stopping streaming linear inverse problems
- Randomized Kaczmarz methods with beyond-Krylov convergence
This page was built for publication: Randomized Block Adaptive Linear System Solvers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6094749)
