How fast can we multiply?

[Christian Tismer]

Les Schaffer wrote:
> 
> Tim and Christian spoke:
> 
> C> Then I also had a look into NumPy and its matrix multiplication.  I
> C> stunned. Again no attempt to optimize big O. It could be done with
> C> Python, the algorithms are known, the fruit is waiting to be picked.
> 
> T> Large dense matmult isn't very common.  Sing along:
> 
> i dont see the connection between floating point matrix multiplies and
> the integer arithmetic tim sketched out in the previous post.
> 
> Spock, explain!

The floating point property is not the point.
It is just a similar strategy : divide and conquer.
Multplying long ints is breaking them into vectors of smaller
size, and then figure out where a mult can be saved by some
more adds.
The way for matrices is factorizing the multiplicants
into smaller ones and then figuring out which mults
can be saved.

And for both also applies: The low level math for the small
pieces which are below a threshold, are still done by the
fast, "dumb" C routines.
Elegant problem reduction is done with Python which controls
that, and saves calls to the low level.

ciao - chris

-- 
Christian Tismer             :^)   <mailto:tismer at appliedbiometrics.com>
Applied Biometrics GmbH      :     Have a break! Take a ride on Python's
Kaiserin-Augusta-Allee 101   :    *Starship* http://starship.python.net
10553 Berlin                 :     PGP key -> http://wwwkeys.pgp.net
PGP Fingerprint       E182 71C7 1A9D 66E9 9D15  D3CC D4D7 93E2 1FAE F6DF
     we're tired of banana software - shipped green, ripens at home