Matrix multiplication algorithm: Difference between revisions

Revision as of 01:20, 17 December 2024

Revision as of 05:26, 19 December 2024

Line 211:

| archive-date = 2014-03-05

| 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> Victor Pan proposed so-called feasible sub-cubic matrix multiplication algorithms with an exponent slightly above 2.77, but in return with a much smaller hidden constant coefficient. <ref>{{Citation | last1=Laderman | first1=Julian | last2=Pan | first2=Victor |last3=Sha | first3=Xuan-He | title=On practical algorithms for accelerated matrix multiplication | year=1992 | journal=Linear Algebra and its Applications | volume=162-164 | pages=557-588 | doi=10.1016/0024-3795(92)90393-O}}</ref>, <ref>{{Citation | last1=Respondek | first1=Jerzy S. | title=Correction of ‘J. Laderman, V. Pan, X.–H. Sha, On practical Algorithms for Accelerated Matrix Multiplication, Linear Algebra and its Applications. Vol. 162-164 (1992) pp. 557-588’ | year=2024 | journal=Linear and Multilinear Algebra | pages=1-11 | doi=10.1080/03081087.2024.2391807 }}</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''}}.