Grey Ballard and James Demmel and Ioana Dumitriu

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2011-14

February 11, 2011

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-14.pdf

Algorithms have two costs: arithmetic and communication. The latter represents the cost of moving data, either between levels of a memory hierarchy, or between processors over a network. Communication often dominates arithmetic and represents a rapidly increasing proportion of the total cost, so we seek algorithms that minimize communication. In recent work, lower bounds were presented on the amount of communication required for essentially all $O(n^3)$-like algorithms for linear algebra, including eigenvalue problems and the SVD. Conventional algorithms, including those currently implemented in (Sca)LAPACK, perform asymptotically more communication than these lower bounds require. In this paper we present parallel and sequential eigenvalue algorithms (for pencils, nonsymmetric matrices, and symmetric matrices) and SVD algorithms that do attain these lower bounds, and analyze their convergence and communication costs.

---

BibTeX citation:

@techreport{Ballard:EECS-2011-14,
    Author= {Ballard, Grey and Demmel, James and Dumitriu, Ioana},
    Title= {Minimizing Communication for Eigenproblems and the Singular  Value Decomposition},
    Year= {2011},
    Month= {Feb},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-14.html},
    Number= {UCB/EECS-2011-14},
    Abstract= {Algorithms have two costs: arithmetic and communication. The latter represents the cost of moving data, 
either between levels of a memory hierarchy, or between processors over a
network. Communication often dominates arithmetic and represents a rapidly increasing proportion of the total cost,
so we seek algorithms that minimize communication. In recent work, lower bounds
were presented on the amount of communication required for essentially all
$O(n^3)$-like algorithms for linear algebra, including eigenvalue problems
and the SVD. Conventional algorithms, including those currently implemented in (Sca)LAPACK, perform asymptotically more communication
than these lower bounds require. In this paper we present parallel and sequential
eigenvalue algorithms
(for pencils, nonsymmetric matrices, and symmetric matrices) and SVD algorithms
that do attain these lower bounds, and analyze their convergence and communication
costs.},
}

EndNote citation:

%0 Report
%A Ballard, Grey 
%A Demmel, James 
%A Dumitriu, Ioana 
%T Minimizing Communication for Eigenproblems and the Singular  Value Decomposition
%I EECS Department, University of California, Berkeley
%D 2011
%8 February 11
%@ UCB/EECS-2011-14
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-14.html
%F Ballard:EECS-2011-14