Distributed-memory hierarchical interpolative factorization


Journal Article

© 2017, The Author(s). The hierarchical interpolative factorization (HIF) offers an efficient way for solving or preconditioning elliptic partial differential equations. By exploiting locality and low-rank properties of the operators, the HIF achieves quasi-linear complexity for factorizing the discrete positive definite elliptic operator and linear complexity for solving the associated linear system. In this paper, the distributed-memory HIF (DHIF) is introduced as a parallel and distributed-memory implementation of the HIF. The DHIF organizes the processes in a hierarchical structure and keeps the communication as local as possible. The computation complexity is O(NlogNP) and O(NP) for constructing and applying the DHIF, respectively, where N is the size of the problem and P is the number of processes. The communication complexity is O(Plog3P)α+O(N2/3P)β where α is the latency and β is the inverse bandwidth. Extensive numerical examples are performed on the NERSC Edison system with up to 8192 processes. The numerical results agree with the complexity analysis and demonstrate the efficiency and scalability of the DHIF.

Full Text

Duke Authors

Cited Authors

  • Li, Y; Ying, L

Published Date

  • December 1, 2017

Published In

Volume / Issue

  • 4 / 1

Electronic International Standard Serial Number (EISSN)

  • 2197-9847

International Standard Serial Number (ISSN)

  • 2522-0144

Digital Object Identifier (DOI)

  • 10.1186/s40687-017-0100-6

Citation Source

  • Scopus