Content deleted Content added
→References: URL Updated, old link was broken. |
m →Sub-cubic algorithms: Update the link to the PDF. |
||
Line 154:
| volume = 18
| year = 1989| citeseerx = 10.1.1.531.9309
}}</ref><ref name="robinson">{{Cite journal | last1=Robinson | first1=Sara | title=Toward an Optimal Algorithm for Matrix Multiplication | url=
Since any algorithm for multiplying two {{math|''n'' × ''n''}}-matrices has to process all {{math|2''n''<sup>2</sup>}} entries, there is an asymptotic lower bound of {{math|Ω(''n''<sup>2</sup>)}} operations. Raz proved a lower bound of {{math|Ω(''n''<sup>2</sup> log(''n''))}} for bounded coefficient arithmetic circuits over the real or complex numbers.<ref>[[Ran Raz]]. On the complexity of matrix product. In Proceedings of the thirty-fourth annual ACM symposium on Theory of computing. ACM Press, 2002. {{doi|10.1145/509907.509932}}.</ref>
| |||