Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

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