Random reordering in SOR-type methods

DOI10.1007/S00211-016-0829-7zbMATH Open1365.65084arXiv1510.04727OpenAlexW2963625383MaRDI QIDQ522242FDOQ522242

Authors: Peter Oswald, Wei-Qi Zhou 

Publication date: 13 April 2017

Published in: Numerische Mathematik (Search for Journal in Brave)

Abstract: When iteratively solving linear systems By=b with Hermitian positive semi-definite $B$, and in particular when solving least-squares problems for $Ax=b$ by reformulating them as $A{A}^{a}sty=b$, it is often observed that SOR-type methods (Gauss-Seidel, Kaczmarz) perform suboptimally for the given equation ordering, and that random reordering improves the situation on average.This paper is an attempt to provide some additional theoretical support for this phenomenon. We show eerror bounds for two randomized versions, called shuffled and preshuffled SOR, that improve asymptotically upon the best known bounds fro SOR with cyclic ordering. Our results are based on studying the behavior of the triangular truncation of Hermitian matrices with respect to their permutations.

Full work available at URL: https://arxiv.org/abs/1510.04727

Recommendations

• A fast randomized algorithm for overdetermined linear least-squares regression
• A generalized successive overrelaxation method for least squares problems
• Randomized extended Kaczmarz for solving least squares
• Faster least squares approximation
• Correction to: ``Random reordering in SOR-type methods
• A sufficient and necessary condition of the convergence of the SAOR iterative method for consistently ordered matrices
• The convergence of the two-block SAOR method for least-squares problems
• A Randomized Solver for Linear Systems with Exponential Convergence
• A fast randomized algorithm for orthogonal projection
• On the convergence rate of SOR: A worst case estimate

zbMATH Keywords

randomizationconvergenceGauss-Seidel methodsuccessive overrelaxationlinear least squaresAnderson's paving conjectureKacmarz algorithm

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20) Iterative numerical methods for linear systems (65F10)

Cites Work

• A randomized Kaczmarz algorithm with exponential convergence
• Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
• Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
• Iterative solution of large sparse systems of equations. Transl. from the German
• Coordinate descent algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• Iterative Methods for Solving Partial Difference Equations of Elliptic Type
• On the convergence rate of SOR: A worst case estimate
• Title not available (Why is that?)
• The Hadamard Operator Norm of a Circulant and Applications
• Convergence analysis for Kaczmarz-type methods in a Hilbert space framework
• Consequences of the Marcus/Spielman/Srivastava Solution of the Kadison-Singer Problem
• Orderings of the successive overrelaxation scheme

Cited In (10)

• A linear algebra perspective on the random multi-block ADMM: the QP case
• Convergence analyses based on frequency decomposition for the randomized row iterative method
• Correction to: ``Random reordering in SOR-type methods
• On the equivalence between SOR-type methods for linear systems and the discrete gradient methods for gradient systems
• A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems
• Sampling discretization and related problems
• A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility
• On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
• Randomness and permutations in coordinate descent methods
• Properties and applications of a conjugate transform on Schatten classes

This page was built for publication: Random reordering in SOR-type methods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q522242)