Home Original page

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