Computer Science – Numerical Analysis
Scientific paper
2009-02-15
SIAM J. Sci. Comput. 32, (2010) pp. 3495-3523
Computer Science
Numerical Analysis
29 pages, 2 tables, 6 figures
Scientific paper
10.1137/090760969
Numerical algorithms have two kinds of costs: arithmetic and communication, by which we mean either moving data between levels of a memory hierarchy (in the sequential case) or over a network connecting processors (in the parallel case). Communication costs often dominate arithmetic costs, so it is of interest to design algorithms minimizing communication. In this paper we first extend known lower bounds on the communication cost (both for bandwidth and for latency) of conventional (O(n^3)) matrix multiplication to Cholesky factorization, which is used for solving dense symmetric positive definite linear systems. Second, we compare the costs of various Cholesky decomposition implementations to these lower bounds and identify the algorithms and data structures that attain them. In the sequential case, we consider both the two-level and hierarchical memory models. Combined with prior results in [13, 14, 15], this gives a set of communication-optimal algorithms for O(n^3) implementations of the three basic factorizations of dense linear algebra: LU with pivoting, QR and Cholesky. But it goes beyond this prior work on sequential LU by optimizing communication for any number of levels of memory hierarchy.
Ballard Grey
Demmel James
Holtz Olga
Schwartz Oded
No associations
LandOfFree
Communication-optimal Parallel and Sequential Cholesky 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 Communication-optimal Parallel and Sequential Cholesky Decomposition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Communication-optimal Parallel and Sequential Cholesky Decomposition will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-718219