A distributed memory parallel randomized Kaczmarz for sparse system of equations

Date

2024-01-01

Author

Bölükbaşı, Ercan Selçuk
TORUN, FAHREDDİN ŞÜKRÜ
Manguoğlu, Murat

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

30
views

3
downloads

Cite This

Kaczmarz algorithm is an iterative projection method for solving system of linear equations that arise in science and engineering problems in various application domains. In addition to classical Kaczmarz, there are randomized and parallel variants. The main challenge of the parallel implementation is the dependency of each Kaczmarz iteration on its predecessor. Because of this dependency, frequent communication is required which results in a substantial overhead. In this study, a new distributed parallel method that reduces the communication overhead is proposed. The proposed method partitions the problem so that the Kaczmarz iterations on different blocks are less dependent. A frequency parameter is introduced to see the effect of communication frequency on the performance. The communication overhead is also decreased by allowing communication between processes only if they have shared non-zero columns. The experiments are performed using problems from various domains to compare the effects of different partitioning methods on the communication overhead and performance. Finally, parallel speedups of the proposed method on larger problems are presented.

Subject Keywords

distributed memory, iterative methods, Kaczmarz, parallel computing, randomized Kaczmarz

URI

https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85202487279&origin=inward
https://hdl.handle.net/11511/111132

Collections

Department of Computer Engineering, Article