SC22 Proceedings

The International Conference for High Performance Computing, Networking, Storage, and Analysis

Technical Papers Archive

Scalable Linear Time Dense Direct Solver for 3-D Problems without Trailing Sub-Matrix Dependencies

Authors: Qianxiang Ma, Sameer Deshmukh, and Rio Yokota (Tokyo Institute of Technology)

Abstract: HSS and H^2-matrices are hierarchical low-rank matrix formats that can reduce the complexity of factorizing dense matrices from O(N^3) to O(N). For HSS matrices, it is possible to remove the dependency on the diagonal blocks during Cholesky/LU factorization, which results in a highly parallel algorithm. However, the weak admissibility of HSS limits it’s applicability to simple problems in 1-D and 2-D geometries. On the other hand, the strong admissibility of H^2-matrices allows it to handle actual 3-D problems, but introduces the dependency on the diagonal blocks during the factorization. In the present work, we propose a decoupling of the low-rank basis and the Schur complement basis in H^2-matrices, which allows us to remove the dependency on the diagonal blocks. This results in a highly parallel H^2-matrix factorization. We compare with other scalable approximate dense matrix factorization codes such as Lorapo.

Back to Technical Papers Archive Listing