Implementation and Performance Engineering of the Kaczmarz Method for Parallel Systems

Abstract

The Kaczmarz method is a simple and robust iterative solver for linear systems of equations. It is used in different fields of science and engineering ranging from medical imaging to solving convection dominated flows, Helmholtz equations and eigenvalue problems. In this thesis we investigate hardware-efficiency and scalable shared memory parallelization strategies for the Kaczmarz method when used as a solver for sparse linear systems. The inherent data dependencies of this method hinder fine-grained parallelism like SIMD or multi-threading to be used efficiently. However, there exist techniques like multicoloring which can enable this level of parallelism. A critical analysis of the multicoloring approach both in terms of performance and qualitative behavior reveals its deficiencies on modern compute platforms. Starting with existing ideas, this thesis proposes a novel "block multicoloring" method, which leverages structural features of (partly) bandor hull-structured matrices. A thorough node-level performance analysis demonstrates that this approach outperforms traditional multicoloring significantly (up to 3x on a single compute node) for a selection of relevant application matrices and never falls behind it even for malicious cases. Finally, our Kaczmarz implementation combined with block multicoloring is used as a linear solver in the FEAST method, to compute inner eigenvalues of large sparse matrices. These first results demonstrate the applicability of the presented approach and indicate its superiority for large scale computations as compared to direct solvers which are state-of-the art for FEAST method.