On 7/18/06, Tim Hochberg <[EMAIL PROTECTED]> 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 ------------------------------------------------------------------------- Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys -- and earn cash http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV _______________________________________________ Numpy-discussion mailing list Numpy-discussion@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/numpy-discussion
