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, \leq)$ 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.{80}7})$	$O(n^{2})$	Exact	Deterministic	Time & Space
Pan's algorithm	1978	$O(n^{(log({143640})/log({70}))}) ~ O(n^{2.{79}5})$	$O(n^{2})$	Exact	Deterministic	Time
Romani's algorithm	1981	$O(n^{2.{5166}5})$	$O(n^{2})$	Exact	Deterministic	Time
Coppersmith–Winograd algorithm	1981	$O(n^{2.{49554}8})$	$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.{375}5})$	$O(n^{2})$	Exact	Deterministic	Time
Vassilevska Williams	2014	$O(n^{2.{37287}3})$	$O(n^{2})$	Exact	Deterministic	Time
François Le Gall	2014	$O(n^{2.{372863}9})$	$O(n^{2})$	Exact	Deterministic	Time
Bini's algorithm	1979	$O(n^{2.{779}9})$	$O(n^{2})$	$O(n logn)$ error	Deterministic	Time
Schonhage's algorithm	1980	$O(n^{({3}*log52/log110)}) ~ O(n^{2.{521}8})$	$O(n^{2})$	?	Deterministic	Time

Time Complexity graph

Space Complexity graph

Pareto Decades graph

References/Citation

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