[Numpy-discussion] fast way of doing "cross-multiplications" ?

[Fernando Perez]

On 7/18/06, Tim Hochberg <tim.hochberg at cox.net> wrote:
> Eric Emsellem wrote:
> > thanks for the tips. (indeed your "add.reduce" is correct: I just wrote
> > this down too quickly, in the script I have a "sum" included).
> >
> > And yes you are right for the memory issue, so I may just keep the loop
> > in and try to make it work on a fast PC...(or use parallel processes)
> >
> > (is "sum" different than "add.reduce"?)
> >
> > thanks again to both Bill Baxter and Perry Greenfield for their fast
> > (and helpful!) answers.
> >
> I just wanted to add that there are faster, but considerably complicated
> ways to attack this class of problems. The one I've looked at in the
> past was the fast multipole method and I believe there are others. I'm
> not sure whether these can be implemented efficiently in numpy, but you
> may want to take a look into this kind of more sophisticated/complicated
> approach if brute forcing the calculation doesn't work.

Indeed, FMM is the best known method that can turn this O(n^2) problem
into O(n*log(n)).  As Tim indicates, there is no easy way out of this
one.  Incidentally, there is a talk about FMM on the scipy'06
schedule, in case you are going to attend.

An alternative approach to FMM (conceptually similar in some ways) is
described here:

http://amath.colorado.edu/faculty/fperez/talks/0604_sanum_mwadap.pdf

Unfortunately this isn't exactly a half-hour optimization effort, as
the required machinery is pretty heavy duty.  And yes, this has all
been done in python and runs on current numpy/scipy (though it has
Fortran, C and C++ sprinkled as needed).

Cheers,

f