New tensor method sharpens upper bound on matrix multiplication speed

Semidirect sums of tensors and the matrix multiplication exponent

Computational ComplexityData Structures and Algorithms

Summary

Multiplying large matrices quickly is a fundamental problem in computing, and researchers measure speed by an exponent called omega (ω). The OpenAI preprints improved this exponent to 2.25, meaning potentially faster matrix multiplication. This paper explains the key technique behind that improvement—a new way to analyze tensors using something called the untwisting lemma for semidirect sums. The authors also relate this method to earlier work and suggest it could help analyze other complex mathematical objects.

What this means in practice

A theory result. No direct application yet.

Authors

Baitian Li

Abstract

This note is an exposition of the recent preprints from OpenAI that establish the bound $ω\leq 9/4$ on the matrix multiplication exponent. We argue that the heart of these preprints is a new technique, which we formulate as the untwisting lemma for semidirect sums of tensors. This gives a generally applicable method for analyzing tensors. We also discuss further consequences of this method, as well as the relation between the OpenAI proof and previous work.