Matrix Multiplication

Description

Matrix Multiplication or Matrix Product is a binary operation that produces a matrix from two matrices with entries in a field; or; more generally; in a ring or even a semiring.

Related Problems

Subproblem: Boolean Matrix Multiplication, Matrix Product Verification

Related: Boolean Matrix Multiplication (Combinatorial), Matrix Product Verification, Distance Product, $(min,\le )$ Product

Parameters

$n$: dimension of square matrix

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Naive algorithm	1940	$O(n^3)$	$O(1)$ auxiliary	Exact	Deterministic
Strassen's algorithm	1969	$O(n^{(log7/log2)})O(n^{2.807})$	$O(n^2)$	Exact	Deterministic	Time & Space
Pan's algorithm	1978	$O(n^{(log(143640)/log(70))})O(n^{2.795})$	$O(n^2)$	Exact	Deterministic	Time
Romani's algorithm	1981	$O(n^{2.51665})$	$O(n^2)$	Exact	Deterministic	Time
Coppersmith–Winograd algorithm	1981	$O(n^{2.495548})$	$O(n^2)$	Exact	Deterministic	Time
Strassen's algorithm	1986	$O(n^{(log54/log5)})O(n^{(2.4785)})$	$O(n^2)$	Exact	Deterministic	Time
Coppersmith–Winograd algorithm	1990	$O(n^{2.3755})$	$O(n^2)$	Exact	Deterministic	Time
Vassilevska Williams	2014	$O(n^{2.372873})$	$O(n^2)$	Exact	Deterministic	Time
François Le Gall	2014	$O(n^{2.3728639})$	$O(n^2)$	Exact	Deterministic	Time
Bini's algorithm	1979	$O(n^{2.7799})$	$O(n^2)$	$O(nlogn)$ error	Deterministic	Time
Schonhage's algorithm	1980	$O(n^{(3\ast \log 52/l\text{og}110)})O(n^{2.5218})$	$O(n^2)$	?	Deterministic	Time
Output-Sensitive Quantum BMM	2018	O*( \min \{n^{1/3} L^{17/{3}0}, n^{1.5} L^{1/4}\})		Exact	Quantum	Time
	2018	$O(n^3/lo{g}^{2.25}n)$		Exact	Deterministic	Time
O'Neil	1973	$O(n^3)$		Exact	Deterministic	Time
Method of Four Russians	1970	$O(n^3/(logn)$^{2})		Exact	Deterministic	Time
Bansal, Williams	2009	$O(n^3\ast (loglogn)$^{2} / log^{2.25} n)		Exact	Randomized	Time
Bansal, Williams	2009	$O(n^3\ast (loglogn)$^{2} / (w * (log n)^{7}/{6}))		Exact	Randomized	Time
Chan	2015	$O(n^3\ast (loglogn)$^{3} / log^{3} n)		Exact	Deterministic	Time
Chan	2015	$O(n^3\ast (logw)$^{3} / (w * log^{2} n))		Exact	Deterministic	Time
Yu	2015	$O(n^3\ast poly(loglogn)$/log^{4} n)		Exact	Deterministic	Time

Time Complexity Graph

Space Complexity Graph

Time-Space Tradeoff

References/Citation

https://arxiv.org/pdf/2010.05846.pdf