View source for Exponent of matrix multiplication

The mystical '''exponent of matrix multiplication''' is a least upper bound of sorts on the asymptotic complexity of matrix multiplication.

It is the smallest number ''ω'' such that for every <math>\epsilon > 0</math>, there are constants ''c'' and ''d'' and an algorithm ''Γ'' such that for every <math>n > d</math>, the algorithm ''Γ'' computes the product of two given <math>n\times n</math> matrices using no more than <math>cn^{\omega+\epsilon}</math> elementary arithmetic operations.

Volker Strassen discovered a method of multiplying two 2×2 matrices using only seven rather than eight elementary multiplications, at the cost of an enormous overhead of performing some 14 more elementary additions and subtractions. However the method does not depend on the commutativity of the elementary multiplication, and therefore it can be applied recursively, in theory, to multiply larger and larger matrices. Eventually, (for matrices with hundreds of thousands of entries,) the overhead of performing so many more additions and subtractions is majorized by the slight gains in efficiency realized by performing one less elementary multiplication at each recursive step.

* https://en.wikipedia.org/wiki/Strassen_algorithm
* https://www.geeksforgeeks.org/strassens-matrix-multiplication/
* https://arxiv.org/abs/2010.05846
* https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=45ca7614ea03449812527e523e385f3af91a85ba

Thus <math>\omega \in [2,\log_2 7]</math>.