How fast can we multiply?
Les Schaffer
godzilla at netmeg.net
Wed Jul 21 08:56:34 EDT 1999
Tim 'multiply-this!' Peters rejoiced so:
> Turns out it's possible to multiply two 2x2 matrices using 7
> multiplies. Since matmult can be "blocked", a larger matrix can be
> treated as a 2x2 array of smaller submatrices, and the same trick
> recursively applied. In the end you get a method with runtime
> O(n**log2(7)) ~= O(n**2.81) instead of O(n**3).
okay, THAT stuff...
Numerical Recipes attributes this to Strassen -- i've seen some stuff
on the web on it too:
http://www.cs.engr.uky.edu/~lewis/cs-alg/materials/Strassen.html
http://www.compapp.dcu.ie/~aileen/research/matmult4.html
http://www.cs.duke.edu/~luoma/strass/strass.html
i'll grab a look at Knuth ....
> The intmult trick is less work to code, and yields a bigger payoff
> earlier.
yeah, and N has to be large enough to justify using strassen ...
les
More information about the Python-list
mailing list