More Asymmetry Yields Faster Matrix Multiplication
Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei Zhou
摘要
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. Together with recent advances in numerical optimization [Dupont et al. arXiv:2608.16884], the method yields a new bound on the square matrix multiplication exponent ω < 2.371177, improved from the previous bound of ω < 2.371552. We also improve the bounds of the exponents for multiplying rectangular matrices of various shapes.
问问这篇 Paper
智能体会读完全文。
Lune 把这篇 Paper 索引到了每一个公式,引用它的顶会 Paper 也一样。你提问,回答直接引用原文。
引用它的顶会 Paper29
- Consistent Low-Rank ApproximationDavid Woodruff, Samson ZhouICLR 2026 · 被引用 62 次
- No Exponential Quantum Speedup for SIS∞ AnymoreRobin Kothari, Ryan O'Donnell, Kewen WuSTOC 2026 · 被引用 12 次
- Error-Correction of Matrix Multiplication AlgorithmsShuichi Hirahara, Nobutaka ShimizuSTOC 2025 · 被引用 5 次
- Subquadratic Algorithms and Hardness for Attention with Any TemperatureShreya Gupta, Boyang Huang, Barna Saha, Yinzhan Xu 等ICLR 2026 · 被引用 5 次
- Invariant subspaces and PCA in nearly matrix multiplication timeAleksandros Sobczyk, Marko Mladenovic, Mathieu LuisierNeurIPS 2024 · 被引用 4 次
它引用的顶会 Paper4
- A Refined Laser Method and Faster Matrix MultiplicationJosh Alman, Virginia Vassilevska WilliamsSODA 2021 · 被引用 275 次
- New Bounds for Matrix Multiplication: from Alpha to OmegaVirginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei ZhouSODA 2024 · 被引用 90 次
- Faster Matrix Multiplication via Asymmetric HashingRan Duan, Hongxun Wu, Renfei ZhouFOCS 2023 · 被引用 54 次
- Faster Rectangular Matrix Multiplication by Combination Loss AnalysisFrançois Le GallSODA 2024 · 被引用 8 次
相关 Paper
- Improving the Leading Constant of Matrix MultiplicationJosh Alman, Hantao YuSODA 2025 · 被引用 2 次
- The Time Complexity of Fully Sparse Matrix MultiplicationAmir Abboud, Karl Bringmann, Nick Fischer, Marvin KünnemannSODA 2024 · 被引用 6 次
- Faster Algorithms for Bounded-Difference Min-Plus ProductShucheng Chi, Ran Duan, Tianle XieSODA 2022 · 被引用 5 次
- Faster min-plus product for monotone instancesShucheng Chi, Ran Duan, Tianle Xie, Tianyi ZhangSTOC 2022 · 被引用 12 次
- An improved cutting plane method for convex optimization, convex-concave games, and its applicationsHaotian Jiang, Yin Tat Lee, Zhao Song, Sam Chiu-wai WongSTOC 2020 · 被引用 54 次
