Algorithms Column

摘要

The exponent ω of matrix multiplication is the infimum over all real numbers c such that for all ε > 0 there is an algorithm that multiplies n × n matrices using at most O(n~(c+ε)) arithmetic operations over an arbitrary field. A trivial lower bound on ω is 2, and the best known upper bound until recently was ω < 2.376 achieved by Coppersmith and Winograd in 1987. There were two independent improvements on ω, one by Stothers in 2010 who showed that ω < 2.374, and one by myself that ultimately resulted in ω < 2.373. Here I discuss the road to these improvements and conclude with some open questions.