Exploiting Data Sparsity in Parallel Matrix Powers Computations

Nicholas Knight, Erin Carson and James Demmel

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2013-47
May 3, 2013

http://www.eecs.berkeley.edu/Pubs/TechRpts/2013/EECS-2013-47.pdf

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 efficiency, 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+USVH, where D is sparse and USVH 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 differential 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 24x speedups on petascale machines.


BibTeX citation:

@techreport{Knight:EECS-2013-47,
    Author = {Knight, Nicholas and Carson, Erin and Demmel, James},
    Title = {Exploiting Data Sparsity in Parallel Matrix Powers Computations},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2013},
    Month = {May},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2013/EECS-2013-47.html},
    Number = {UCB/EECS-2013-47},
    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 efficiency, 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 <i>A</i> = <i>D</i>+<i>USV<sup>H</sup></i>, where <i>D</i> is sparse and <i>USV<sup>H</sup></i> 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 (<i>H</i>) matrices, such as multigrid methods, fast multipole methods, numerical partial differential 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 <i>k</i> sparse matrix-vector multiplications, our algorithm asymptotically reduces the parallel latency by a factor of <i>O</i>(<i>k</i>) 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 24x speedups on petascale machines.}
}

EndNote citation:

%0 Report
%A Knight, Nicholas
%A Carson, Erin
%A Demmel, James
%T Exploiting Data Sparsity in Parallel Matrix Powers Computations
%I EECS Department, University of California, Berkeley
%D 2013
%8 May 3
%@ UCB/EECS-2013-47
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2013/EECS-2013-47.html
%F Knight:EECS-2013-47