Straggler-tolerant stationary methods for linear systems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929538395537408 |
|---|---|
| author | Kalantzis, Vassilis Xi, Yuanzhe Horesh, Lior Saad, Yousef |
| author_facet | Kalantzis, Vassilis Xi, Yuanzhe Horesh, Lior Saad, Yousef |
| contents | In this paper, we consider the iterative solution of linear algebraic equations under the condition that matrix-vector products with the coefficient matrix are computed only partially. At the same time, non-computed entries are set to zeros. 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 realized in hybrid cloud computing architectures following the controller-worker distributed model under the influence of straggling workers. We propose straggler-tolerant Richardson iteration scheme and Chebyshev semi-iterative schemes, and prove 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_01098 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Straggler-tolerant stationary methods for linear systems Kalantzis, Vassilis Xi, Yuanzhe Horesh, Lior Saad, Yousef Numerical Analysis 65F08, 65F10, 68M15, 68Q87 In this paper, we consider the iterative solution of linear algebraic equations under the condition that matrix-vector products with the coefficient matrix are computed only partially. At the same time, non-computed entries are set to zeros. 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 realized in hybrid cloud computing architectures following the controller-worker distributed model under the influence of straggling workers. We propose straggler-tolerant Richardson iteration scheme and Chebyshev semi-iterative schemes, and prove 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. |
| title | Straggler-tolerant stationary methods for linear systems |
| topic | Numerical Analysis 65F08, 65F10, 68M15, 68Q87 |
| url | https://arxiv.org/abs/2407.01098 |