Difference between revisions of "Matrix Multiplication"

From Algorithm Wiki
Jump to navigation Jump to search
 
Line 23: Line 23:
|-
|-
| rowspan="1" | Cubic
| rowspan="1" | Cubic
|
| [- Naive algorithm (1940)]
 
[https://link.springer.com/article/10.1007%2FBF02165411 Strassen's algorithm (1969) (1969)]
 
[https://ieeexplore.ieee.org/document/4567976 Pan's algorithm (1978)]
 
[https://link.springer.com/article/10.1007/BF01395989 Bini's algorithm (1979)]
 
[https://epubs.siam.org/doi/abs/10.1137/0210032 Schonhage's algorithm (1980)]
 
[https://www.sciencedirect.com/science/article/pii/0304397583900543 Romani's algorithm (1980)]
 
[https://ieeexplore.ieee.org/document/4568320 Coppersmith–Winograd algorithm (1981)]
 
[ Strassen's algorithm (1986) (1986)]
 
[http://www.cs.umd.edu/~gasarch/TOPICS/ramsey/matrixmult.pdf Coppersmith–Winograd algorithm (1990) (1990)]
 
[http://theory.stanford.edu/~virgi/matrixmult-f.pdf Williams 2014 (2014)]
 
[https://arxiv.org/abs/1401.7714 François Le Gall 2014 (2014)]
|
|
|-
|-

Latest revision as of 16:04, 20 September 2021

Problem Description

Matrix multiplication or multiplication of matrices is one of the operations that can be performed on matrices in linear algebra. Multiplication of matrix A with matrix B is possible when both the given matrices, A and B are compatible. Matrix multiplication is a binary operation, that gives a matrix from two given matrices.

Matrix multiplication was first introduced in 1812 by French mathematician Jacques Philippe Marie Binet, in order to represent linear maps using matrices. Let us understand the rule for multiplication of matrices and matrix multiplication formula in detail in the following sections.

Bounds Chart

Matrix MultiplicationBoundsChart.png

Step Chart

Matrix MultiplicationStepChart.png

Improvement Table

Complexity Classes Algorithm Paper Links Lower Bounds Paper Links
Exp/Factorial
Polynomial > 3
Cubic [- Naive algorithm (1940)]

Strassen's algorithm (1969) (1969)

Pan's algorithm (1978)

Bini's algorithm (1979)

Schonhage's algorithm (1980)

Romani's algorithm (1980)

Coppersmith–Winograd algorithm (1981)

[ Strassen's algorithm (1986) (1986)]

Coppersmith–Winograd algorithm (1990) (1990)

Williams 2014 (2014)

François Le Gall 2014 (2014)

Quadratic
nlogn
Linear
logn