Matrix Multiplication: Difference between revisions
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: | ||
== | {{DISPLAYTITLE:Matrix Multiplication (Matrix Product)}} | ||
== Description == | |||
Matrix | 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 == | |||
{| class="wikitable sortable" style="text-align:center;" width="100%" | |||
! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference | |||
|- | |||
[ Strassen's algorithm (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 | | [[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.ezproxy.canberra.edu.au/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 | | [[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.ezproxy.canberra.edu.au/document/4567976 Time] | ||
|- | |||
[https:// | | [[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.ezproxy.canberra.edu.au/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.ezproxy.canberra.edu.au/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.ezproxy.canberra.edu.au/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.ezproxy.canberra.edu.au/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.ezproxy.canberra.edu.au/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.ezproxy.canberra.edu.au/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.ezproxy.canberra.edu.au/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.ezproxy.canberra.edu.au/abstract/document/5438580 Time] | |||
|- | |- | ||
| | | [[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.ezproxy.canberra.edu.au/doi/abs/10.1137/1.9781611973730.16 Time] | ||
| | |||
| | |||
|- | |- | ||
| | | [[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.ezproxy.canberra.edu.au/doi/abs/10.1137/1.9781611973730.16 Time] | ||
| | |||
| | |||
|- | |- | ||
| | | [[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.ezproxy.canberra.edu.au/science/article/pii/S0890540118300099 Time] | ||
| | |||
| | |||
|- | |- | ||
| | |} | ||
== 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
Error creating thumbnail: Unable to save thumbnail to destination