Abstract
We introduce a new parallel algorithm for solving sparse LU factorization of planar matrices, which commonly arise in the finite element method for 2D PDEs. Existing scalable methods, such as the multifrontal approach with subtree-to-subcube mapping by Gupta et al. [1] and right-looking with 3D mapping by Sao et al. [2] fail to achieve optimal communication costs for these matrices. Our new algorithm combines 3D mapping and subtree-to-subcube mapping to minimize communication costs while allowing trade-offs between extra memory and reduced communication. We demonstrate that our proposed algorithm attains the communication lower bound up to a factor of O(log log n) in the memory-optimal case and up to a factor of O(log P) in the memory-independent case for an n-dimensional planar sparse matrix on P processors.
| Original language | English |
|---|---|
| Title of host publication | SPAA 2023 - Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures |
| Publisher | Association for Computing Machinery |
| Pages | 427-430 |
| Number of pages | 4 |
| ISBN (Electronic) | 9781450395458 |
| DOIs | |
| State | Published - Jun 17 2023 |
| Event | 35th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2023 - Orlando, United States Duration: Jun 17 2023 → Jun 19 2023 |
Publication series
| Name | Annual ACM Symposium on Parallelism in Algorithms and Architectures |
|---|
Conference
| Conference | 35th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2023 |
|---|---|
| Country/Territory | United States |
| City | Orlando |
| Period | 06/17/23 → 06/19/23 |
Funding
∗This manuscript has been authored by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725 with the U.S. Department of Energy. The publisher, by accepting the article for publication, acknowledges that the United States Government retains a non-exclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this manuscript, or allow others to do so, for United States Government purposes. The Department of Energy will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan (http://energy.gov/downloads/doe-public-access-plan). This work was supported by the U.S. Department of Energy (DOE), Office of Science, Advanced Scientific Computing Research (ASCR) through the Mathematical Multifaceted Integrated Capability Centers (MMICCS) program, Program Manager William Spotz, under Award No. ERKJ401.
Keywords
- communication optimal algorithms
- sparse lu factorization