Exploiting Data Sparsity in Parallel Matrix Powers Computations
Abstract
The increasingly high relative cost of moving data on modern parallel machines has caused a paradigm shift in the design of high-performance algorithms: to achieve e ciency, one must focus on strategies which minimize data movement, rather than minimize arithmetic operations. We call this a communication-avoiding approach to algorithm design. In this work, we derive a new parallel communication-avoiding matrix powers algorithm for matrices of the form A = D+USV(H), where D is sparse and USV(H) has low rank but may be dense. Matrices of this form arise in many practical applications, including power-law graph analysis, circuit simulation and algorithms involving hierarchical (H) matrices, such as multigrid methods, fast multipole methods numerical partial di erential equation solvers, and preconditioned iterative methods. If A has this form, our algorithm enables a communication-avoiding approach. We demonstrate that, with respect to the cost of computing k sparse matrix-vector multiplications, our algorithm asymptotically reduces the parallel latency by a factor of O(k) for small additional bandwidth and computation costs. Using problems from real-world applications, our performance model predicts that this reduction in communication allows for up to 24 speedups on petascale machines.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 03, 2013
- Accession Number
- ADA584727
Entities
People
- Erin Carson
- James Demmel
- Nicholas Knight
Organizations
- University of California, Berkeley