New Breakthrough Brings Matrix Multiplication Closer to Ideal | Quanta Magazine

Abstraction: New technique lowers matrix multiplication exponent omega, biggest gain in 14 years

Key points:

• Duan, Zhou (Tsinghua) and Wu (UC Berkeley) improved the upper bound for omega (matrix multiplication exponent) to ~2.371866, down from 2.3728596; largest single improvement since 2010
• Identified a "hidden loss" in Strassen's laser method: the process was systematically discarding useful blocks, wasting potential efficiency
• A January 2024 follow-on paper refined the technique further, reducing omega to 2.371552 and extended improvements to rectangular matrix multiplication
• Standard n×n multiplication requires n^3 steps; the theoretical lower bound (omega=2) equals the time just to write the answer
• The Coppersmith-Winograd algorithm (1987) combined with the laser method has been the backbone of all improvements; a 2015 proof shows this approach cannot reach below omega=2.3078
• Applications of faster matrix multiplication span graphics, network theory, graph algorithms, and machine learning

Connections: Matrix Multiplication · Computational Complexity · Algorithms

Source: https://www.quantamagazine.org/new-breakthrough-brings-matrix-multiplication-closer-to-ideal-20240307/