Matrix Multiplication: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
(Created page with "== 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 repre...")
 
No edit summary
 
(6 intermediate revisions by the same user not shown)
Line 1: Line 1:
== Problem Description==
{{DISPLAYTITLE:Matrix Multiplication (Matrix Product)}}
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.
== Description ==  


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.
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.  


== Bounds Chart ==
== Related Problems ==  
[[File:Matrix_MultiplicationBoundsChart.png|1050px]]


== Step Chart ==
Subproblem: [[Boolean Matrix Multiplication]], [[ Matrix Product Verification]]
[[File:Matrix_MultiplicationStepChart.png|1050px]]


== Improvement Table ==
Related: [[Boolean Matrix Multiplication (Combinatorial)]], [[Matrix Product Verification]], [[Distance Product]], [[$(\min, \leq)$ Product]]
{| class="wikitable" style="text-align:center;" width="100%"
!width="20%" | Complexity Classes !! width="40%" | Algorithm Paper Links !! width="40%" | Lower Bounds Paper Links
|-
| rowspan="1" | Exp/Factorial
|
|
|-
| rowspan="1" | Polynomial > 3
|
|
|-
| rowspan="1" | Cubic
| [- Naive algorithm (1940)]


[https://link.springer.com/article/10.1007%2FBF02165411 Strassen's algorithm (1969) (1969)]
== Parameters ==


[https://ieeexplore.ieee.org/document/4567976 Pan's algorithm (1978)]
$n$: dimension of square matrix


[https://link.springer.com/article/10.1007/BF01395989 Bini's algorithm (1979)]
== Table of Algorithms ==


[https://epubs.siam.org/doi/abs/10.1137/0210032 Schonhage's algorithm (1980)]
{| class="wikitable sortable"  style="text-align:center;" width="100%"


[https://www.sciencedirect.com/science/article/pii/0304397583900543 Romani's algorithm (1980)]
! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference


[https://ieeexplore.ieee.org/document/4568320 Coppersmith–Winograd algorithm (1981)]
|-


[ Strassen's algorithm (1986) (1986)]
| [[Naive algorithm (Matrix Multiplication Matrix Product)|Naive algorithm]] || 1940 || $O(n^{3})$ || $O({1})$ auxiliary || Exact || Deterministic || 
 
|-
[http://www.cs.umd.edu/~gasarch/TOPICS/ramsey/matrixmult.pdf Coppersmith–Winograd algorithm (1990) (1990)]
| [[Strassen's algorithm (Matrix Multiplication Matrix Product)|Strassen's algorithm]] || 1969 || $O(n^{(log7/log2)}) ~ O(n^{2.{80}7})$ || $O(n^{2})$ || Exact || Deterministic || [https://link.springer.com/article/10.1007%2FBF02165411 Time] & [http://www.cs.cmu.edu/afs/cs/academic/class/15750-s17/ScribeNotes/lecture1.pdf Space]
 
|-
[http://theory.stanford.edu/~virgi/matrixmult-f.pdf Williams 2014 (2014)]
| [[Pan's algorithm (Matrix Multiplication Matrix Product)|Pan's algorithm]] || 1978 || $O(n^{(log({143640})/log({70}))}) ~ O(n^{2.{79}5})$ || $O(n^{2})$ || Exact || Deterministic || [https://ieeexplore.ieee.org/document/4567976 Time]
 
|-
[https://arxiv.org/abs/1401.7714 François Le Gall 2014 (2014)]
| [[Romani's algorithm (Matrix Multiplication Matrix Product)|Romani's algorithm]] || 1981 || $O(n^{2.{5166}5})$ || $O(n^{2})$ || Exact || Deterministic || [https://epubs.siam.org/doi/abs/10.1137/0211020 Time]
|
|-
| [[Coppersmith–Winograd algorithm (Matrix Multiplication Matrix Product)|Coppersmith–Winograd algorithm]] || 1981 || $O(n^{2.{49554}8})$ || $O(n^{2})$ || Exact || Deterministic || [https://epubs.siam.org/doi/abs/10.1137/0211038 Time]
|-
| [[Strassen's algorithm (Matrix Multiplication Matrix Product)|Strassen's algorithm]] || 1986 || $O(n^{(log54/log5)}) ~ O(n^{({2.4785})})$ || $O(n^{2})$ || Exact || Deterministic || [https://ieeexplore.ieee.org/abstract/document/4568194 Time]
|-
| [[Coppersmith–Winograd algorithm (Matrix Multiplication Matrix Product)|Coppersmith–Winograd algorithm]] || 1990 || $O(n^{2.{375}5})$ || $O(n^{2})$ || Exact || Deterministic || [http://www.cs.umd.edu/~gasarch/TOPICS/ramsey/matrixmult.pdf Time]
|-
| [[Vassilevska Williams (Matrix Multiplication Matrix Product)|Vassilevska Williams]] || 2014 || $O(n^{2.{37287}3})$ || $O(n^{2})$ || Exact || Deterministic || [http://theory.stanford.edu/~virgi/matrixmult-f.pdf Time]
|-
| [[François Le Gall (Matrix Multiplication Matrix Product)|François Le Gall]] || 2014 || $O(n^{2.{372863}9})$ || $O(n^{2})$ || Exact || Deterministic || [https://arxiv.org/abs/1401.7714 Time]
|-
| [[Bini's algorithm (Matrix Multiplication Matrix Product)|Bini's algorithm]] || 1979 || $O(n^{2.{779}9})$ || $O(n^{2})$ || $O(n logn)$ error || Deterministic || [https://doi.org/10.1016/0020-0190(79)90113-3 Time]
|-
| [[Schonhage's algorithm (Matrix Multiplication Matrix Product)|Schonhage's algorithm]] || 1980 || $O(n^{({3}*\log {52}/l \og {110})}) ~ O(n^{2.{521}8})$ || $O(n^{2})$ || ? || Deterministic || [https://epubs.siam.org/doi/abs/10.1137/0210032 Time]
|-
| [[Output-Sensitive Quantum BMM (Boolean Matrix Multiplication Matrix Product)|Output-Sensitive Quantum BMM]] || 2018 || O*( \min \{n^{1/3} L^{17/{3}0}, n^{1.5} L^{1/4}\}) ||  || Exact || Quantum || [https://dl.acm.org/doi/pdf/10.1145/3186893, Time]
|-
| [[ (Boolean Matrix Multiplication (Combinatorial) Matrix Product)| ]] || 2018 || $O(n^{3} / log^{2.25} n)$ ||  || Exact || Deterministic || [https://dl.acm.org/doi/pdf/10.1145/3186893, Time]
|-
| [[O'Neil 1973 (Boolean Matrix Multiplication Matrix Product)|O'Neil]] || 1973 || $O(n^{3})$ ||  || Exact || Deterministic || [https://core.ac.uk/download/pdf/82467126.pdf Time]
|-
| [[Method of Four Russians (Boolean Matrix Multiplication (Combinatorial) Matrix Product)|Method of Four Russians]] || 1970 || $O(n^{3}/(log n)$^{2}) ||  || Exact || Deterministic || [https://scholar.google.com/scholar?hl=en&as_sdt=0%2C22&q=On+economical+construction+of+the+transitive+closure+of+an+oriented+graph.&btnG= Time]
|-
| [[Bansal, Williams (Boolean Matrix Multiplication (Combinatorial) Matrix Product)|Bansal, Williams]] || 2009 || $O(n^{3} * (log log n)$^{2} / log^{2.25} n) ||  || Exact || Randomized || [https://ieeexplore.ieee.org/abstract/document/5438580 Time]
|-
| [[Bansal, Williams (Boolean Matrix Multiplication (Combinatorial) Matrix Product)|Bansal, Williams]] || 2009 || $O(n^{3} * (log log n)$^{2} / (w * (log n)^{7}/{6})) ||  || Exact || Randomized || [https://ieeexplore.ieee.org/abstract/document/5438580 Time]
|-
|-
| rowspan="1" | Quadratic
| [[Chan (Boolean Matrix Multiplication (Combinatorial) Matrix Product)|Chan]] || 2015 || $O(n^{3} * (log log n)$^{3} / log^{3} n) ||  || Exact || Deterministic || [https://epubs.siam.org/doi/abs/10.1137/1.9781611973730.16 Time]
|
|
|-
|-
| rowspan="1" | nlogn
| [[Chan (Boolean Matrix Multiplication (Combinatorial) Matrix Product)|Chan]] || 2015 || $O(n^{3} * (log w)$^{3} / (w * log^{2} n)) ||  || Exact || Deterministic || [https://epubs.siam.org/doi/abs/10.1137/1.9781611973730.16 Time]
|
|
|-
|-
| rowspan="1" | Linear
| [[Yu (Boolean Matrix Multiplication (Combinatorial) Matrix Product)|Yu]] || 2015 || $O(n^{3}*poly(log log n)$/log^{4} n) ||  || Exact || Deterministic || [https://www.sciencedirect.com/science/article/pii/S0890540118300099 Time]
|
|
|-
|-
| rowspan="1" | logn
|}
|
 
|
== Time Complexity Graph ==
|-|}
 
[[File:Matrix Product - Matrix Multiplication - Time.png|1000px]]
 
== References/Citation ==
 
https://arxiv.org/pdf/2010.05846.pdf

Latest revision as of 09:05, 28 April 2023

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}*\log {52}/l \og {110})}) ~ O(n^{2.{521}8})$ $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} / log^{2.25} n)$ Exact Deterministic Time
O'Neil 1973 $O(n^{3})$ Exact Deterministic Time
Method of Four Russians 1970 $O(n^{3}/(log n)$^{2}) Exact Deterministic Time
Bansal, Williams 2009 $O(n^{3} * (log log n)$^{2} / log^{2.25} n) Exact Randomized Time
Bansal, Williams 2009 $O(n^{3} * (log log n)$^{2} / (w * (log n)^{7}/{6})) Exact Randomized Time
Chan 2015 $O(n^{3} * (log log n)$^{3} / log^{3} n) Exact Deterministic Time
Chan 2015 $O(n^{3} * (log w)$^{3} / (w * log^{2} n)) Exact Deterministic Time
Yu 2015 $O(n^{3}*poly(log log n)$/log^{4} n) Exact Deterministic Time

Time Complexity Graph

Matrix Product - Matrix Multiplication - Time.png

References/Citation

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

Retrieved from "https://algorithm-wiki.csail.mit.edu/w/index.php?title=Matrix_Multiplication&oldid=47647"