Distributed-Memory $\mathcal{H}$-Matrix Algebra I: Data Distribution and Matrix-Vector Multiplication (CSIAM Transactions on Applied Mathematics, 2021)
We introduce a data distribution scheme for $\mathcal{H}$-matrices and a distributed-memory algorithm for $\mathcal{H}$-matrix-vector multiplication. Our data distribution schemeavoids an expensive $Ω(P^2)$ scheduling procedure used in previous work, where $P$ isthe number of processes, while data balancing is well-preserved. Based on the datadistribution, our distributed-memory algorithm evenly distributes all computationsamong $P$ processes and adopts a novel tree-communication algorithm to reduce thelatency cost. The overall complexity of our algorithm is $\mathscr{O}(\frac{Nlog N}{P} +αlog P+βlog^2P)$ for $\mathcal{H}$-matrices under weak admissibility condition, where $N$ is the matrix size, $α$ denotes the latency, and $β$ denotes the inverse bandwidth. Numerically, our algorithm isapplied to address both two- and three-dimensional problems of various sizes amongvarious numbers of processes. On thousands of processes, good parallel efficiency isstill observed.