Survey of a class of iterative row-action methods: The Kaczmarz method
Open Access
- 26 September 2024
- journal article
- research article
- Published by Springer Nature in Numerical Algorithms
- Vol. 99 (4) , 2097-2135
Abstract
The Kaczmarz algorithm is an iterative method that solves linear systems of equations. It stands out among iterative algorithms when dealing with large systems for two reasons. First, at each iteration, the Kaczmarz algorithm uses a single equation, resulting in minimal computational work per iteration. Second, solving the entire system may only require the use of a small subset of the equations. These characteristics have attracted significant attention to the Kaczmarz algorithm. Researchers have observed that randomly choosing equations can improve the convergence rate of the algorithm. This insight led to the development of the Randomized Kaczmarz algorithm and, subsequently, several other variations emerged. In this paper, we extensively analyze the native Kaczmarz algorithm and many of its variations using large-scale systems as benchmarks. Through our investigation, we have verified that, for consistent systems, various row sampling schemes can outperform both the original and Randomized Kaczmarz method. Specifically, sampling without replacement and using quasirandom numbers are the fastest techniques. However, for inconsistent systems, the Conjugate Gradient method for Least-Squares problems overcomes all variations of the Kaczmarz method for these types of systems.Keywords
All Related Versions
Funding Information
- Fundação para a Ciência e a Tecnologia (URA-HPC PTDC/08838/2022)
This publication has 41 references indexed in Scilit:
- Selectable Set Randomized KaczmarzNumerical Linear Algebra with Applications, 2022
- Randomized Kaczmarz with averagingBIT Numerical Mathematics, 2020
- AIR Tools II: algebraic iterative reconstruction methods, improved implementationNumerical Algorithms, 2017
- Generalized row-action methods for tomographic imagingNumerical Algorithms, 2013
- Randomized Kaczmarz solver for noisy linear systemsBIT Numerical Mathematics, 2010
- A Randomized Kaczmarz Algorithm with Exponential ConvergenceJournal of Fourier Analysis and Applications, 2008
- Block-iterative methods for consistent and inconsistent linear equationsNumerische Mathematik, 1980
- Iterative reconstruction algorithmsComputers in Biology and Medicine, 1976
- On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integralsNumerische Mathematik, 1960
- A quadratic programming procedureNaval Research Logistics Quarterly, 1957