TY - JOUR
T1 - Distributed-Memory $\mathcal{H}$-Matrix Algebra I: Data Distribution and Matrix-Vector Multiplication
AU - Li , Yingzhou
AU - Poulson , Jack
AU - Ying , Lexing
JO - CSIAM Transactions on Applied Mathematics
VL - 3
SP - 431
EP - 459
PY - 2021
DA - 2021/08
SN - 2
DO - http://doi.org/10.4208/csiam-am.2020-0206
UR - https://global-sci.org/intro/article_detail/csiam-am/19445.html
KW - Parallel fast algorithm, $\mathcal{H}$-matrix, distributed-memory, parallel computing.
AB - <p style="text-align: justify;">We introduce a data distribution scheme for $\mathcal{H}$-matrices and a distributed-memory algorithm for $\mathcal{H}$-matrix-vector multiplication. Our data distribution scheme
avoids an expensive $Ω(P^2)$ scheduling procedure used in previous work, where $P$ is
the number of processes, while data balancing is well-preserved. Based on the data
distribution, our distributed-memory algorithm evenly distributes all computations
among $P$ processes and adopts a novel tree-communication algorithm to reduce the
latency 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 is
applied to address both two- and three-dimensional problems of various sizes among
various numbers of processes. On thousands of processes, good parallel efficiency is
still observed.</p>