--- _id: '1590' abstract: - lang: eng text: "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 x 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.\r\n\r\nWe 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 error-resilient 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 665x compared to single-threaded execution." author: - first_name: Michael full_name: Lass, Michael id: '24135' last_name: Lass orcid: 0000-0002-5708-7632 - first_name: Stephan full_name: Mohr, Stephan last_name: Mohr - first_name: Hendrik full_name: Wiebeler, Hendrik last_name: Wiebeler - first_name: Thomas full_name: Kühne, Thomas id: '49079' last_name: Kühne - first_name: Christian full_name: Plessl, Christian id: '16153' last_name: Plessl orcid: 0000-0001-5728-9982 citation: ama: 'Lass M, Mohr S, Wiebeler H, Kühne T, Plessl C. A Massively Parallel Algorithm for the Approximate Calculation of Inverse p-th Roots of Large Sparse Matrices. In: Proc. Platform for Advanced Scientific Computing (PASC) Conference. ACM; 2018. doi:10.1145/3218176.3218231' apa: Lass, M., Mohr, S., Wiebeler, H., Kühne, T., & Plessl, C. (2018). A Massively Parallel Algorithm for the Approximate Calculation of Inverse p-th Roots of Large Sparse Matrices. Proc. Platform for Advanced Scientific Computing (PASC) Conference. Platform for Advanced Scientific Computing Conference (PASC), Basel, Switzerland. https://doi.org/10.1145/3218176.3218231 bibtex: '@inproceedings{Lass_Mohr_Wiebeler_Kühne_Plessl_2018, place={New York, NY, USA}, title={A Massively Parallel Algorithm for the Approximate Calculation of Inverse p-th Roots of Large Sparse Matrices}, DOI={10.1145/3218176.3218231}, booktitle={Proc. Platform for Advanced Scientific Computing (PASC) Conference}, publisher={ACM}, author={Lass, Michael and Mohr, Stephan and Wiebeler, Hendrik and Kühne, Thomas and Plessl, Christian}, year={2018} }' chicago: 'Lass, Michael, Stephan Mohr, Hendrik Wiebeler, Thomas Kühne, and Christian Plessl. “A Massively Parallel Algorithm for the Approximate Calculation of Inverse P-Th Roots of Large Sparse Matrices.” In Proc. Platform for Advanced Scientific Computing (PASC) Conference. New York, NY, USA: ACM, 2018. https://doi.org/10.1145/3218176.3218231.' ieee: 'M. Lass, S. Mohr, H. Wiebeler, T. Kühne, and C. Plessl, “A Massively Parallel Algorithm for the Approximate Calculation of Inverse p-th Roots of Large Sparse Matrices,” presented at the Platform for Advanced Scientific Computing Conference (PASC), Basel, Switzerland, 2018, doi: 10.1145/3218176.3218231.' mla: Lass, Michael, et al. “A Massively Parallel Algorithm for the Approximate Calculation of Inverse P-Th Roots of Large Sparse Matrices.” Proc. Platform for Advanced Scientific Computing (PASC) Conference, ACM, 2018, doi:10.1145/3218176.3218231. short: 'M. Lass, S. Mohr, H. Wiebeler, T. Kühne, C. Plessl, in: Proc. Platform for Advanced Scientific Computing (PASC) Conference, ACM, New York, NY, USA, 2018.' conference: end_date: 2018-07-04 location: Basel, Switzerland name: Platform for Advanced Scientific Computing Conference (PASC) start_date: 2018-07-02 date_created: 2018-03-22T10:53:01Z date_updated: 2023-09-26T11:48:12Z department: - _id: '27' - _id: '518' - _id: '304' doi: 10.1145/3218176.3218231 external_id: arxiv: - '1710.10899' keyword: - approximate computing - linear algebra - matrix inversion - matrix p-th roots - numeric algorithm - parallel computing language: - iso: eng place: New York, NY, USA project: - _id: '32' grant_number: PL 595/2-1 / 320898746 name: Performance and Efficiency in HPC with Custom Computing - _id: '52' name: Computing Resources Provided by the Paderborn Center for Parallel Computing publication: Proc. Platform for Advanced Scientific Computing (PASC) Conference publication_identifier: isbn: - 978-1-4503-5891-0/18/07 publisher: ACM quality_controlled: '1' status: public title: A Massively Parallel Algorithm for the Approximate Calculation of Inverse p-th Roots of Large Sparse Matrices type: conference user_id: '15278' year: '2018' ...