DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

Implementation and Performance Engineering of the Kaczmarz Method for Parallel Systems

Alappat, Christie Louis (2016) Implementation and Performance Engineering of the Kaczmarz Method for Parallel Systems. Master's, Friedrich-Alexander Universität Erlangen-Nürnberg.

[img] PDF

Official URL: https://blogs.fau.de/essex/files/2012/11/MAThesis-LousChrsties.pdf


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.

Item URL in elib:https://elib.dlr.de/114763/
Document Type:Thesis (Master's)
Title:Implementation and Performance Engineering of the Kaczmarz Method for Parallel Systems
AuthorsInstitution or Email of AuthorsAuthors ORCID iD
Alappat, Christie LouisFriedrich-Alexander Universität Erlangen-NürnbergUNSPECIFIED
Date:30 November 2016
Refereed publication:No
Open Access:Yes
Gold Open Access:No
In ISI Web of Science:No
Keywords:Kaczmarz Method, Performance Engineering, Multi-Core CPU, data dependencies
Institution:Friedrich-Alexander Universität Erlangen-Nürnberg
Department:Professur für Höchstleistungsrechnen
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Space
HGF - Program Themes:Space Technology
DLR - Research area:Raumfahrt
DLR - Program:R SY - Technik für Raumfahrtsysteme
DLR - Research theme (Project):R - Vorhaben SISTEC
Location: Köln-Porz
Institutes and Institutions:Institut of Simulation and Software Technology
Deposited By: Thies, Jonas
Deposited On:05 Dec 2017 09:15
Last Modified:31 Jul 2019 20:12

Repository Staff Only: item control page

Help & Contact
electronic library is running on EPrints 3.3.12
Copyright © 2008-2017 German Aerospace Center (DLR). All rights reserved.