math.NA cs.DC cs.NA
Distributed memory mathcal H matrix Algebra I Data Distribution and Matrix vector Multiplication. 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 Omega(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 O Big( frac N log N P alpha log P beta log 2 P Big) for mathcal H matrices under weak admissibility condition, where N is the matrix size, alpha denotes the latency, and beta 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.