More Asymmetry Yields Faster Matrix Multiplication
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914979538534400 |
|---|---|
| author | Alman, Josh Duan, Ran Williams, Virginia Vassilevska Xu, Yinzhan Xu, Zixuan Zhou, Renfei |
| author_facet | Alman, Josh Duan, Ran Williams, Virginia Vassilevska Xu, Yinzhan Xu, Zixuan Zhou, Renfei |
| contents | We present a new improvement on the laser method for designing fast matrix multiplication algorithms. The new method further develops the recent advances by [Duan, Wu, Zhou FOCS 2023] and [Vassilevska Williams, Xu, Xu, Zhou SODA 2024]. Surprisingly the new improvement is achieved by incorporating more asymmetry in the analysis, circumventing a fundamental tool of prior work that requires two of the three dimensions to be treated identically. The method yields a new bound on the square matrix multiplication exponent $$ω<2.371339,$$ improved from the previous bound of $ω<2.371552$. We also improve the bounds of the exponents for multiplying rectangular matrices of various shapes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_16349 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | More Asymmetry Yields Faster Matrix Multiplication Alman, Josh Duan, Ran Williams, Virginia Vassilevska Xu, Yinzhan Xu, Zixuan Zhou, Renfei Data Structures and Algorithms Computational Complexity We present a new improvement on the laser method for designing fast matrix multiplication algorithms. The new method further develops the recent advances by [Duan, Wu, Zhou FOCS 2023] and [Vassilevska Williams, Xu, Xu, Zhou SODA 2024]. Surprisingly the new improvement is achieved by incorporating more asymmetry in the analysis, circumventing a fundamental tool of prior work that requires two of the three dimensions to be treated identically. The method yields a new bound on the square matrix multiplication exponent $$ω<2.371339,$$ improved from the previous bound of $ω<2.371552$. We also improve the bounds of the exponents for multiplying rectangular matrices of various shapes. |
| title | More Asymmetry Yields Faster Matrix Multiplication |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2404.16349 |