User:Fawly/Computational complexity of matrix multiplication: Difference between revisions

Revision as of 21:30, 21 May 2021

Revision as of 20:26, 23 May 2021

Line 31:

| url-status = dead

}}</ref><ref name="robinson">{{Citation | last=Robinson | first=Sara | title=Toward an Optimal Algorithm for Matrix Multiplication | url=https://archive.siam.org/pdf/news/174.pdf | date=November 2005 | journal=SIAM News | volume=38 | issue=9 | quote=Even if someone manages to prove one of the conjectures—thereby demonstrating that {{math|1=''ω'' = 2}}—the wreath product approach is unlikely to be applicable to the large matrix problems that arise in practice. [...] the input matrices must be astronomically large for the difference in time to be apparent.}}</ref>

[[Freivalds' algorithm]] is a simple [[Monte Carlo algorithm]] that, given matrices {{mvar|A}}, {{mvar|B}} and {{mvar|C}}, verifies in {{math|Θ(''n''²)}} time if {{math|''AB'' {{=}} ''C''}}.

== The matrix multiplication exponent ==

Line 263 ⟶ 261:

* [[CYK algorithm#Valiant's algorithm|CYK algorithm, §Valiant's algorithm]]

* [[Matrix chain multiplication]]

* [[Matrix multiplication]]

* [[Sparse matrix-vector multiplication]]

* [[Freivalds' algorithm]] is, a simple [[Monte Carlo algorithm]] that, given matrices {{mvar|A}}, {{mvar|B}} and {{mvar|C}}, verifies in {{math|Θ(''n''²)}} time if {{math|''AB'' {{=}} ''C''}}.

==References==