2020/08/28 by Yingzhou Li, Li, Yingzhou, Jack Poulson +3 · 1 citation
Computer Science · #65F99 #65Y05 #Complexity and Algorithms in Graphs #Distributed #FOS: Computer and information sciences #FOS: Mathematics #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Parallel #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2008.12441
openalex publication_date 2020/08/28 · openalex created_date 2020/09/08 · openalex updated_date 2026/07/28
We introduce a data distribution scheme for H-matrices and a distributed-memory algorithm for H-matrix-vector multiplication. Our data distribution scheme avoids an expensive Ω(P2) 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((N log N)/(P) + αlog P + βlog2 P ) for 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.