On convergence rate of the randomized Gauss-Seidel method

DOI10.1016/j.laa.2020.10.028zbMath1459.65040OpenAlexW3095761189WikidataQ114152097 ScholiaQ114152097MaRDI QIDQ2228499

Lu Wang, Wen-Ting Wu, Zhong Zhi Bai

Publication date: 17 February 2021

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.laa.2020.10.028

zbMATH Keywords

convergence ratesystem of linear equationsrandomized Kaczmarz methodrandomized Gauss-Seidel method

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20) Numerical mathematical programming methods (65K05) Convex programming (90C25) Iterative numerical methods for linear systems (65F10) Linear equations (linear algebraic aspects) (15A06)

Related Items

A two-step randomized Gauss-Seidel method for solving large-scale linear least squares problems ⋮ On Relaxed Greedy Randomized Augmented Kaczmarz Methods for Solving Large Sparse Inconsistent Linear Systems ⋮ A Fast Block Coordinate Descent Method for Solving Linear Least-Squares Problems ⋮ Randomized Kaczmarz iteration methods: algorithmic extensions and convergence theory ⋮ Randomized Kaczmarz method with adaptive stepsizes for inconsistent linear systems ⋮ On the convergence of randomized and greedy relaxation schemes for solving nonsingular linear systems of equations ⋮ On multi-step randomized extended Kaczmarz method for solving large sparse inconsistent linear systems ⋮ On convergence rates of Kaczmarz-type methods with different selection rules of working rows ⋮ Faster Deterministic Pseudoinverse-Free Block Extension of Motzkin Method for Large Consistent Linear Systems ⋮ On greedy randomized block Gauss-Seidel method with averaging for sparse linear least-squares problems ⋮ A doubly stochastic block Gauss-Seidel algorithm for solving linear equations ⋮ On two-subspace randomized extended Kaczmarz method for solving large linear least-squares problems ⋮ A Partially Greedy Randomized Extended Gauss-Seidel Method for Solving Large Linear Systems

Uses Software

• SparseMatrix

Cites Work

• Greedy and randomized versions of the multiplicative Schwarz method
• A randomized Kaczmarz algorithm with exponential convergence
• Error bounds and convergence analysis of feasible descent methods: A general approach
• On the convergence of the coordinate descent method for convex differentiable minimization
• On convergence rate of the randomized Kaczmarz method
• A new greedy Kaczmarz algorithm for the solution of very large linear systems
• On the Meany inequality with applications to convergence analysis of several row-action iteration methods
• Coordinate descent algorithms
• Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems
• The university of Florida sparse matrix collection
• Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
• Convergence Properties of the Randomized Extended Gauss--Seidel and Kaczmarz Methods
• Row-Action Methods for Huge and Sparse Systems and Their Applications
• Random permutations fix a worst case for cyclic coordinate descent