| Presentation | 2012-09-03 Faster Algorithms for Rectangular Matrix Multiplication GallFrancois Le, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Let α be the maximal value such that the product of an n x n^α matrix by an n^α x n matrix can be computed with n^2+o(1) arithmetic operations. In this paper we show that α > 0.30298, which improves the previous record α > 0.29462 by Coppersmith (Journal of Complexity, 1997). More generally, we construct a new algorithm for multiplying an n x n^κ matrix by an n^κ x n matrix, for any value κ≠1. The complexity of this algorithm is better than all known algorithms for rectangular matrix multiplication. In the case of square matrix multiplication (i.e., for κ=1), we recover exactly the complexity of the algorithm by Coppersmith and Winograd (Journal of Symbolic Computation, 1990). These new upper bounds can be used to improve the time complexity of several known algorithms that rely on rectangular matrix multiplication. For example, we directly obtain a 0(n^2.5302)-time algorithm for the all-pairs shortest paths problem over directed graphs with small integer weights, improving over the 0(n^2.575)-time algorithm by Zwick (JACM 2002), and also improve the time complexity of sparse square matrix multiplication. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | |
| Paper # | COMP2012-32 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2012/8/27(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Faster Algorithms for Rectangular Matrix Multiplication |
| Sub Title (in English) | |
| Keyword(1) | |
| 1st Author's Name | GallFrancois Le |
| 1st Author's Affiliation | Department of Computer ScienceGraduate School of Information Science and TechnologyThe University of Tokyo() |
| Date | 2012-09-03 |
| Paper # | COMP2012-32 |
| Volume (vol) | vol.112 |
| Number (no) | 199 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |