Accelerating the distributed Kaczmarz algorithm by strong over-relaxation

DOI10.1016/J.LAA.2020.10.035MaRDI QIDQ2228508zbMATH OpenOpenAlexFDO

Authors Riley Borgard, Haley Duba, Chloe Makdad, Randal Tuggle, Steven N. Harding, Jay P. Mayfield, Eric S. Weber

Publication date 17 February 2021

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

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

zbMATH Keywords

distributed algorithmKaczmarz algorithmlinear systems of equations

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Linear equations (linear algebraic aspects) (15A06) Iterative numerical methods for linear systems (65F10)

Abstract: The distributed Kaczmarz algorithm is an adaptation of the standard Kaczmarz algorithm to the situation in which data is distributed throughout a network represented by a tree. We isolate substructures of the network and study convergence of the distributed Kazmarz algorithm for relatively large relaxation parameters associated to these substructures. If the system is consistent, then the algorithm converges to the solution of minimal norm; however, if the system is inconsistent, then the algorithm converges to an approximated least-squares solution that is dependent on the parameters and the network topology. We show that the relaxation parameters may be larger than the standard upper-bound in literature in this context and provide numerical experiments to support our results.

Recommendations

• Faster randomized block Kaczmarz algorithms
• A new greedy Kaczmarz algorithm for the solution of very large linear systems
• An accelerated randomized Kaczmarz algorithm
• Kaczmarz algorithm with relaxation in Hilbert space
• An accelerated randomized Kaczmarz method via low-rank approximation

Cites work

• A Randomized Incremental Subgradient Method for Distributed Optimization in Networked Systems
• A Storage-Efficient Algorithm for Finding the Regularized Solution of a Large, Inconsistent System of Equations
• A randomized Kaczmarz algorithm with exponential convergence
• Component averaging: An efficient iterative parallel algorithm for large and sparse unstructured problems
• Distributed asynchronous deterministic and stochastic gradient optimization algorithms
• Faster randomized block Kaczmarz algorithms
• Gossip algorithms
• Iterative algorithms for large partitioned linear systems, with applications to image reconstruction
• Matrix theory. Basic results and techniques
• Paved with good intentions: analysis of a randomized block Kaczmarz method
• Projection method for solving a singular system of linear equations and its applications
• Randomized block Kaczmarz method with projection for solving least squares
• Randomized extended Kaczmarz for solving least squares
• Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
• The Kaczmarz algorithm, row action methods, and statistical learning algorithms
• The angles between the null spaces of X rays
• The mathematics of computerized tomography

This page was built for publication: Accelerating the distributed Kaczmarz algorithm by strong over-relaxation

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