Parallelization Strategies for the Randomized Kaczmarz Algorithm on Large-Scale Dense Systems
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914660748361728 |
|---|---|
| author | Ferreira, Inês Acebrón, Juan A. Monteiro, José |
| author_facet | Ferreira, Inês Acebrón, Juan A. Monteiro, José |
| contents | The Kaczmarz algorithm is an iterative technique designed to solve consistent linear systems of equations. It falls within the category of row-action methods, focusing on handling one equation per iteration. This characteristic makes it especially useful in solving very large systems. The recent introduction of a randomized version, the Randomized Kaczmarz method, renewed interest in the algorithm, leading to the development of numerous variations. Subsequently, parallel implementations for both the original and Randomized Kaczmarz method have since then been proposed. However, previous work has addressed sparse linear systems, whereas we focus on solving dense systems. In this paper, we explore in detail approaches to parallelizing the Kaczmarz method for both shared and distributed memory for large dense systems. In particular, we implemented the Randomized Kaczmarz with Averaging (RKA) method that, for inconsistent systems, unlike the standard Randomized Kaczmarz algorithm, reduces the final error of the solution. While efficient parallelization of this algorithm is not achievable, we introduce a block version of the averaging method that can outperform the RKA method. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_17474 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Parallelization Strategies for the Randomized Kaczmarz Algorithm on Large-Scale Dense Systems Ferreira, Inês Acebrón, Juan A. Monteiro, José Distributed, Parallel, and Cluster Computing Numerical Analysis 15A06, 15A52, 65F10, 65F20, 68W20, 65Y05, 68W10, 68W15 The Kaczmarz algorithm is an iterative technique designed to solve consistent linear systems of equations. It falls within the category of row-action methods, focusing on handling one equation per iteration. This characteristic makes it especially useful in solving very large systems. The recent introduction of a randomized version, the Randomized Kaczmarz method, renewed interest in the algorithm, leading to the development of numerous variations. Subsequently, parallel implementations for both the original and Randomized Kaczmarz method have since then been proposed. However, previous work has addressed sparse linear systems, whereas we focus on solving dense systems. In this paper, we explore in detail approaches to parallelizing the Kaczmarz method for both shared and distributed memory for large dense systems. In particular, we implemented the Randomized Kaczmarz with Averaging (RKA) method that, for inconsistent systems, unlike the standard Randomized Kaczmarz algorithm, reduces the final error of the solution. While efficient parallelization of this algorithm is not achievable, we introduce a block version of the averaging method that can outperform the RKA method. |
| title | Parallelization Strategies for the Randomized Kaczmarz Algorithm on Large-Scale Dense Systems |
| topic | Distributed, Parallel, and Cluster Computing Numerical Analysis 15A06, 15A52, 65F10, 65F20, 68W20, 65Y05, 68W10, 68W15 |
| url | https://arxiv.org/abs/2401.17474 |