Computational complexity of matrix multiplication: Difference between revisions

Revision as of 06:46, 9 October 2022

Revision as of 05:28, 22 October 2022

Line 17:

}}</ref> The optimal number of field operations needed to multiply two square {{math|''n'' × ''n''}} matrices [[big O notation|up to constant factors]] is still unknown. This is a major open question in [[theoretical computer science]].

{{As of|20202022|1210}}, the matrixbest multiplicationannounced algorithmbound withon bestthe [[Time complexity|asymptotic complexity]] runsof ina matrix multiplication algorithm is {{math|O(''n''^{2.372859637188})}} time, given by JoshDuan, AlmanWu and [[Virginia Vassilevska Williams]].Zhou<ref name="aw20dwz22">

{{Citation

| last1=Duan

| first1=Ran

| last2=Wu

| first2=Hongxun

| last3=Zhou

| first3=Renfei

| year = 2022

| arxiv=2210.10173

| title = Faster Matrix Multiplication via Asymmetric Hashing

| url=https://arxiv.org/abs/2210.10173}}</ref> announced in a preprint. This improves on the bound of {{math|O(''n''^2.3728596)}} time, given by Josh Alman and [[Virginia Vassilevska Williams]].<ref name="aw20">

{{Citation

| last1=Alman