Sparse Factorizations and Scalable Algorithms for Differential and Integral Operators

Yingzhou Li, Stanford University
January 25th, 2017 at 3:30PM–4:30PM in 891 Evans Hall [Map]

This talk focus on the Distributed-memory hierarchical interpolative factorization (DHIF) which offers an efficient way for solving or preconditioning elliptic partial differential equations. By exploiting locality and low-rank properties of the operators, the DHIF achieves quasi-linear complexity for factorizing the discrete positive definite elliptic operator and linear complexity for solving the associated linear system. The DHIF organizes the processes in a hierarchical structure and keep the communication as local as possible. The computation complexity is O(N log N / P) and O( N / P ) for constructing and applying the DHIF, respectively, where N is the size of the problem and P is the number of processes. 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.