news@sun.eng.sun.com (news) (09/01/89)
I recently ran across a book by a Dr. Greengard (MIT Press, 1988) which describes an algorithm that calculates the n-body problem with respect to gravitational or electrostatic fields such that the complexity is O(n) rather than O(n^2). It appears to use quadtrees and fields. I would think that if this is possible, source code would be available to do this...or at least an understandable description of the algorithm (the book is rather dry). Please send me pointers to better descriptions, third party analysis or best of all *shareware*/*public domain* software that implements the Greengard algorithm. (If you have Greengard's email address...) Please send me mail directly since I don't read all these newsgroups. Thanks in advance, Paul E. Baclaski Sun Microsystems peb@sun.com
aboulang@bbn.com (Albert Boulanger) (09/08/89)
Here is one TR on the O(N) algorithm: MIT AI TR 995: An O(N) Algorithm for Three-Dimensional N-Body Simulations Feng Zhao. His code runs on the Connection Machine in log N time. These fast O(N) family of algrorithms are being used with Chorin's vortex method (which reduces fluid-dynamics problems to N-body problems) for fast fluid simulations on the Connection Machine. Albert Boulanger BBN Systems & Technologies aboulanger@bbn.com