Distributed Algorithm.

[Robert G. Brown]

On Thu, 14 Dec 2000, Michael T. Prinkey wrote:

> ... Just to expand on this point a bit, the presence
> of long distance interactions do not automatically preclude efficient
> parallelization, even over fast ethernet.  The LANL folks hve a nice
> code that (I think) uses multipole expansions for long range
> interactions. (http://loki-www.lanl.gov/papers/)  Effectively, this
> lumps distant effects into a few terms in an perturbative expansion.
> There is a truncation error that typically scales as some power of 1/r
> so for distant particles, you get good results with a few terms.  For
> nearby particles, you need to do the full potential/force calculation
> particle by particle.  They also typically use quad-tree or oct-tree
> storage structures as part of the decomposition/multipole expansion
> strategy.  Those keywords and the LANL papers should probably get you
> started.  Note too that the multipole approach is very useful even for
> serial code.  For N particles, the full (naive) interaction algorithm
> scales as O(N^2).  With multipole approaches, I believe that this can
> drop to O(N ln N) or lower.  Those are important when N ~ 10^6 and
> higher.

Thanks, I probably should have mentioned this in more detail (and I'm
glad you did), but from the problem description ("simulating the motion
of nodes") it didn't really sound like he was solving a physics
problem;-)

However, being a physicist (after all) this is the kind of thing I find
VERY interesting (my dissertation was on multipolar multiple scattering
band theory, which is a sort of penultimate "parallelization" of an
infinite range interaction with an infinite number of interacting
entities, and I've started working on the theory again a bit very
recently:-), so I hope that if the problem being solved is indeed a
coupled ODE type problem with some underlying spatial geometry that a
description is posted in more detail.

In fact, it is useful for everybody on the list to remember to post some
DETAIL with their questions, at least when doing so won't violate some
sort of NDA.  This both helps educate everybody on the list (I, at
least, love to listen in on what folks are doing and how they are trying
to do it even when it is irrelevant to physics) and it makes the
subsequent discussions more focussed and technically interesting.

    rgb

-- 
Robert G. Brown	                       http://www.phy.duke.edu/~rgb/
Duke University Dept. of Physics, Box 90305
Durham, N.C. 27708-0305
Phone: 1-919-660-2567  Fax: 919-660-2525     email:rgb at phy.duke.edu