@Article{CSIAM-AM-2-3,
author = {Yingzhou, Li and Poulson, Jack and Ying, Lexing},
title = {Distributed-Memory $\mathcal{H}$-Matrix Algebra I: Data Distribution and Matrix-Vector Multiplication},
journal = {CSIAM Transactions on Applied Mathematics},
year = {2021},
volume = {2},
number = {3},
pages = {431--459},
abstract = {<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>},
issn = {2708-0579},
doi = {https://doi.org/10.4208/csiam-am.2020-0206},
url = {https://global-sci.com/article/82352/distributed-memory-mathcalh-matrix-algebra-i-data-distribution-and-matrix-vector-multiplication}
}