Straggler-Tolerant Stationary Methods for Linear Systems
- 17 January 2025
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 48 (5) , S1-S22
Abstract
In this paper, we consider the iterative solution of sparse systems of linear algebraic equations under the condition that sparse matrix-vector products with the coefficient matrix are computed only partially. At the same time, noncomputed entries are set to zero. We assume that both the number of computed entries and their associated row index set are random variables, with the row index set sampled uniformly given the number of computed entries. This model of computations is prevalent to that realized in hybrid cloud computing architectures following the controller-worker distributed model under the influence of straggling workers. We propose a randomized Richardson iterative scheme and a randomized Chebyshev semi-iterative method within this model and prove the sufficient conditions for their convergence in expectation. Numerical experiments verify the presented theoretical results as well as the effectiveness of the proposed schemes on a few sparse matrix problems.Keywords
All Related Versions
Funding Information
- National Science Foundation (DMS 2208412)
- RTG (DMS 2038118)
- National Science Foundation (DMS 2208456)
This publication has 38 references indexed in Scilit:
- Parallel cloud solution of large algebraic multivalued systemsApplied Numerical Mathematics, 2024
- parGeMSLR: A parallel multilevel Schur complement low-rank preconditioning and solution package for general sparse matricesParallel Computing, 2022
- Asynchronous Richardson iterations: theory and practiceNumerical Algorithms, 2020
- Fault Recovery Methods for Asynchronous Linear SolversInternational Journal of Parallel Programming, 2020
- SLA-RALBA: cost-efficient and resource-aware load balancing algorithm for cloud computingThe Journal of Supercomputing, 2019
- Modeling the asynchronous Jacobi method without communication delaysJournal of Parallel and Distributed Computing, 2019
- Performance analysis of asynchronous parallel JacobiNumerical Algorithms, 2017
- Evaluation of the performance of inexact GMRESJournal of Computational and Applied Mathematics, 2011
- Chaotic relaxationLinear Algebra and its Applications, 1969
- Chebyshev semi-iterative methods, successive overrelaxation iterative methods, and second order Richardson iterative methodsNumerische Mathematik, 1961