Loading...
On the convergence of randomized and greedy relaxation schemes for solving nonsingular linear systems of equations
Frommer, Andreas Szyld, Daniel B.
Frommer, Andreas
Szyld, Daniel B.
Citations
Altmetric:
Genre
Journal article
Date
2022-11-16
Advisor
Committee member
Group
Department
Mathematics
Permanent link to this record
Collections
Research Projects
Organizational Units
Journal Issue
DOI
http://dx.doi.org/10.1007/s11075-022-01431-7
Abstract
We extend results known for the randomized Gauss-Seidel and the Gauss-Southwell methods for the case of a Hermitian and positive definite matrix to certain classes of non-Hermitian matrices. We obtain convergence results for a whole range of parameters describing the probabilities in the randomized method or the greedy choice strategy in the Gauss-Southwell-type methods. We identify those choices which make our convergence bounds best possible. Our main tool is to use weighted â„“1-norms to measure the residuals. A major result is that the best convergence bounds that we obtain for the expected values in the randomized algorithm are as good as the best for the deterministic, but more costly algorithms of Gauss-Southwell type. Numerical experiments illustrate the convergence of the method and the bounds obtained. Comparisons with the randomized Kaczmarz method are also presented.
Description
Citation
Frommer, A., Szyld, D.B. On the convergence of randomized and greedy relaxation schemes for solving nonsingular linear systems of equations. Numer Algor 92, 639–664 (2023). https://doi.org/10.1007/s11075-022-01431-7
Citation to related work
Springer
Has part
Numerical Algorithms, Vol. 92
ADA compliance
For Americans with Disabilities Act (ADA) accommodation, including help with reading this content, please contact scholarshare@temple.edu