Minimizing Communication for Eigenproblems and the Singular Value Decomposition

Details Minimizing Communication for Eigenproblems and the Singular Value Decomposition Minimizing Communication for Eigenproblems and the Singular Value Decomposition

2010-11-13

arxiv.org/abs/1011.3077v1

Mathematics

Numerical Analysis

43 pages, 11 figures

Scientific paper

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 \cite{BDHS10} 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.

Affiliated with

Also associated with

No associations

Rating

Minimizing Communication for Eigenproblems and the Singular Value Decomposition does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Minimizing Communication for Eigenproblems and the Singular Value Decomposition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimizing Communication for Eigenproblems and the Singular Value Decomposition will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-445095