7 results on '"Ballard, Grey"'
Search Results
2. Graph Expansion Analysis for Communication Costs of Fast Rectangular Matrix Multiplication
- Author
-
Ballard, Grey, Demmel, James, Holtz, Olga, Lipshitz, Benjamin, and Schwartz, Oded
- Subjects
Computer Science - Data Structures and Algorithms ,Computer Science - Computational Complexity ,Computer Science - Numerical Analysis - Abstract
Graph expansion analysis of computational DAGs is useful for obtaining communication cost lower bounds where previous methods, such as geometric embedding, are not applicable. This has recently been demonstrated for Strassen's and Strassen-like fast square matrix multiplication algorithms. Here we extend the expansion analysis approach to fast algorithms for rectangular matrix multiplication, obtaining a new class of communication cost lower bounds. These apply, for example to the algorithms of Bini et al. (1979) and the algorithms of Hopcroft and Kerr (1971). Some of our bounds are proved to be optimal.
- Published
- 2012
- Full Text
- View/download PDF
3. Strong Scaling of Matrix Multiplication Algorithms and Memory-Independent Communication Lower Bounds
- Author
-
Ballard, Grey, Demmel, James, Holtz, Olga, Lipshitz, Benjamin, and Schwartz, Oded
- Subjects
Computer Science - Data Structures and Algorithms ,Computer Science - Computational Complexity ,Computer Science - Distributed, Parallel, and Cluster Computing ,Computer Science - Numerical Analysis ,Mathematics - Combinatorics ,Mathematics - Numerical Analysis ,68W10, 68W40 ,F.2.1 - Abstract
A parallel algorithm has perfect strong scaling if its running time on P processors is linear in 1/P, including all communication costs. Distributed-memory parallel algorithms for matrix multiplication with perfect strong scaling have only recently been found. One is based on classical matrix multiplication (Solomonik and Demmel, 2011), and one is based on Strassen's fast matrix multiplication (Ballard, Demmel, Holtz, Lipshitz, and Schwartz, 2012). Both algorithms scale perfectly, but only up to some number of processors where the inter-processor communication no longer scales. We obtain a memory-independent communication cost lower bound on classical and Strassen-based distributed-memory matrix multiplication algorithms. These bounds imply that no classical or Strassen-based parallel matrix multiplication algorithm can strongly scale perfectly beyond the ranges already attained by the two parallel algorithms mentioned above. The memory-independent bounds and the strong scaling bounds generalize to other algorithms., Comment: 4 pages, 1 figure
- Published
- 2012
4. Communication-Optimal Parallel Algorithm for Strassen's Matrix Multiplication
- Author
-
Ballard, Grey, Demmel, James, Holtz, Olga, Lipshitz, Benjamin, and Schwartz, Oded
- Subjects
Computer Science - Data Structures and Algorithms ,Computer Science - Computational Complexity ,Computer Science - Distributed, Parallel, and Cluster Computing ,Computer Science - Numerical Analysis ,Mathematics - Combinatorics ,Mathematics - Numerical Analysis ,68W40, 68W10 ,F.2.1 - Abstract
Parallel matrix multiplication is one of the most studied fundamental problems in distributed and high performance computing. We obtain a new parallel algorithm that is based on Strassen's fast matrix multiplication and minimizes communication. The algorithm outperforms all known parallel matrix multiplication algorithms, classical and Strassen-based, both asymptotically and in practice. A critical bottleneck in parallelizing Strassen's algorithm is the communication between the processors. Ballard, Demmel, Holtz, and Schwartz (SPAA'11) prove lower bounds on these communication costs, using expansion properties of the underlying computation graph. Our algorithm matches these lower bounds, and so is communication-optimal. It exhibits perfect strong scaling within the maximum possible range. Benchmarking our implementation on a Cray XT4, we obtain speedups over classical and Strassen-based algorithms ranging from 24% to 184% for a fixed matrix dimension n=94080, where the number of nodes ranges from 49 to 7203. Our parallelization approach generalizes to other fast matrix multiplication algorithms., Comment: 13 pages, 3 figures
- Published
- 2012
5. Graph Expansion and Communication Costs of Fast Matrix Multiplication
- Author
-
Ballard, Grey, Demmel, James, Holtz, Olga, and Schwartz, Oded
- Subjects
Computer Science - Data Structures and Algorithms ,Computer Science - Computational Complexity ,Computer Science - Distributed, Parallel, and Cluster Computing ,Computer Science - Numerical Analysis ,Mathematics - Combinatorics ,Mathematics - Numerical Analysis ,F.2.1 - Abstract
The communication cost of algorithms (also known as I/O-complexity) is shown to be closely related to the expansion properties of the corresponding computation graphs. We demonstrate this on Strassen's and other fast matrix multiplication algorithms, and obtain first lower bounds on their communication costs. In the sequential case, where the processor has a fast memory of size $M$, too small to store three $n$-by-$n$ matrices, the lower bound on the number of words moved between fast and slow memory is, for many of the matrix multiplication algorithms, $\Omega((\frac{n}{\sqrt M})^{\omega_0}\cdot M)$, where $\omega_0$ is the exponent in the arithmetic count (e.g., $\omega_0 = \lg 7$ for Strassen, and $\omega_0 = 3$ for conventional matrix multiplication). With $p$ parallel processors, each with fast memory of size $M$, the lower bound is $p$ times smaller. These bounds are attainable both for sequential and for parallel algorithms and hence optimal. These bounds can also be attained by many fast algorithms in linear algebra (e.g., algorithms for LU, QR, and solving the Sylvester equation).
- Published
- 2011
- Full Text
- View/download PDF
6. Minimizing Communication in Linear Algebra
- Author
-
Ballard, Grey, Demmel, James, Holtz, Olga, and Schwartz, Oded
- Subjects
Computer Science - Computational Complexity ,Computer Science - Data Structures and Algorithms ,Computer Science - Numerical Analysis ,Mathematics - Numerical Analysis - Abstract
In 1981 Hong and Kung proved a lower bound on the amount of communication needed to perform dense, matrix-multiplication using the conventional $O(n^3)$ algorithm, where the input matrices were too large to fit in the small, fast memory. In 2004 Irony, Toledo and Tiskin gave a new proof of this result and extended it to the parallel case. In both cases the lower bound may be expressed as $\Omega$(#arithmetic operations / $\sqrt{M}$), where M is the size of the fast memory (or local memory in the parallel case). Here we generalize these results to a much wider variety of algorithms, including LU factorization, Cholesky factorization, $LDL^T$ factorization, QR factorization, algorithms for eigenvalues and singular values, i.e., essentially all direct methods of linear algebra. The proof works for dense or sparse matrices, and for sequential or parallel algorithms. In addition to lower bounds on the amount of data moved (bandwidth) we get lower bounds on the number of messages required to move it (latency). We illustrate how to extend our lower bound technique to compositions of linear algebra operations (like computing powers of a matrix), to decide whether it is enough to call a sequence of simpler optimal algorithms (like matrix multiplication) to minimize communication, or if we can do better. We give examples of both. We also show how to extend our lower bounds to certain graph theoretic problems. We point out recently designed algorithms for dense LU, Cholesky, QR, eigenvalue and the SVD problems that attain these lower bounds; implementations of LU and QR show large speedups over conventional linear algebra algorithms in standard libraries like LAPACK and ScaLAPACK. Many open problems remain., Comment: 27 pages, 2 tables
- Published
- 2009
- Full Text
- View/download PDF
7. Communication-optimal Parallel and Sequential Cholesky Decomposition
- Author
-
Ballard, Grey, Demmel, James, Holtz, Olga, and Schwartz, Oded
- Subjects
Computer Science - Numerical Analysis ,Computer Science - Computational Complexity ,Computer Science - Data Structures and Algorithms ,Mathematics - Numerical Analysis ,F.2.1 - Abstract
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., Comment: 29 pages, 2 tables, 6 figures
- Published
- 2009
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.