ON DISTRIBUTED MEMORY PARALLEL RANDOMIZED KACZMARZ FOR SPARSE SYSTEM OF EQUATIONS

Date

2024-9-2

Author

Bölükbaşı, Ercan Selçuk

Metadata

Show full item record

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

Item Usage Stats

34
views

31
downloads

Cite This

It is common for science and engineering problems to be modeled as system of linear equations. Kaczmarz algorithm is a row action method based on iterative projections for solving such equations derived from various application domains. Since each Kaczmarz iteration is dependent on the previous one, several row selection strategies have emerged including the randomized Kaczmarz. Same dependency also makes the parallel implementation of Kaczmarz challenging. Because of the nature of Kaczmarz iterations, it is required to communicate frequently which results in a substantial overhead. In this study, two different methods to solve sparse systems are proposed for distributed memory architectures: The first method is a hybrid approach that uses sequential randomized Kaczmarz as the solver for the smaller reduced system constructed with parallel DS factorization. The second one is a parallel randomized Kaczmarz method to reduce the communication overhead. It partitions the system to decrease the dependency between Kaczmarz iterations executed on different blocks. Additional decrease on the communication overhead is ensured by limiting the communication between processes to the shared nonzero indices. The experiments are performed on problems from various domains to compare the effects of those methods on the communication overhead and performance. Finally, parallel speedups of the proposed parallel randomized Kaczmarz method on larger problems are presented.

Subject Keywords

Parallel computing, Randomization, Kaczmarz, Distributed memory, Iterative methods

URI

https://hdl.handle.net/11511/111459

Collections

Graduate School of Natural and Applied Sciences, Thesis