A massively parallel algorithm for the approximate calculation of inverse p-th roots of large sparse matrices
Lass M, Mohr S, Wiebeler H, Kühne TD, Plessl C (2018)
Publication Type: Conference contribution
Publication year: 2018
Publisher: Association for Computing Machinery, Inc
Conference Proceedings Title: Proceedings of the Platform for Advanced Scientific Computing Conference, PASC 2018
Event location: Basel, CHE
ISBN: 9781450358910
Abstract
We present the submatrix method, a highly parallelizable method for the approximate calculation of inverse p-th roots of large sparse symmetric matrices which are required in different scientific applications. Following the idea of Approximate Computing, we allow imprecision in the final result in order to utilize the sparsity of the input matrix and to allow massively parallel execution. For an n × n matrix, the proposed algorithm allows to distribute the calculations over n nodes with only little communication overhead. The result matrix exhibits the same sparsity pattern as the input matrix, allowing for efficient reuse of allocated data structures. We evaluate the algorithm with respect to the error that it introduces into calculated results, as well as its performance and scalability. We demonstrate that the error is relatively limited for well-conditioned matrices and that results are still valuable for errorresilient applications like preconditioning even for ill-conditioned matrices.We discuss the execution time and scaling of the algorithm on a theoretical level and present a distributed implementation of the algorithm using MPI and OpenMP. We demonstrate the scalability of this implementation by running it on a high-performance compute cluster comprised of 1024 CPU cores, showing a speedup of 665× compared to single-threaded execution.
Involved external institutions
Universität Paderborn
Germany (DE)
Barcelona Supercomputing Center / Centro Nacional de Supercomputación
Spain (ES)
Germany (DE)
Barcelona Supercomputing Center / Centro Nacional de Supercomputación
Spain (ES)
How to cite
APA:
Lass, M., Mohr, S., Wiebeler, H., Kühne, T.D., & Plessl, C. (2018). A massively parallel algorithm for the approximate calculation of inverse p-th roots of large sparse matrices. In Proceedings of the Platform for Advanced Scientific Computing Conference, PASC 2018. Basel, CHE: Association for Computing Machinery, Inc.
MLA:
Lass, Michael, et al. "A massively parallel algorithm for the approximate calculation of inverse p-th roots of large sparse matrices." Proceedings of the 5th Platform for Advanced Scientific Computing Conference, PASC 2018, Basel, CHE Association for Computing Machinery, Inc, 2018.
BibTeX: Download