  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 keep the communication as local as possible.
The computation complexity is $O\left(\frac{N\log N}{P}\right)$ and
$O\left(\frac{N}{P}\right)$ 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\left(\sqrt{P}\log^3
P\right)\alpha + O\left(\frac{N^{2/3}}{\sqrt{P}}\right)\beta$ where $\alpha$ is
the latency and $\beta$ 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.
