Matrix Multiplication

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.

Parameters

$n$ : dimension of square matrix

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 11 of 11 algorithms


Vassilevska Williams	2014	$O(n^{2.372873})$	$O(n^2)$
François Le Gall	2014	$O(n^{2.3728639})$	$O(n^2)$
Coppersmith–Winograd algorithm	1990	$O(n^{2.3755})$	$O(n^2)$
Strassen's algorithm	1986	$O(n^{\log(54)/\log(5)})$ , approximately $O(n^{2.4785})$	$O(n^2)$
Romani's algorithm	1981	$O(n^{2.51665})$	$O(n^2)$
Coppersmith–Winograd algorithm	1981	$O(n^{2.495548})$	$O(n^2)$
Schonhage's algorithm	1980	$O(n^{3\log(52)/\log(110)})$ , approximately $O(n^{2.5218})$	$O(n^2)$
Bini's algorithm	1979	$O(n^{2.7799})$	$O(n^2)$
Pan's algorithm	1978	$O(n^{\log(143640)/\log(70)})$ , approximately $O(n^{2.795})$	$O(n^2)$
Strassen's algorithm	1969	$O(n^{\log(7)/\log(2)})$ , approximately $O(n^{2.807})$	$O(n^2)$
Naive algorithm	1940	$O(n^3)$	$O(1)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms