Distributed Algorithm.

[Michael T. Prinkey]

> If the ODE's are long range, and the step of the ith node depends on the
> state of all N-1 other nodes, well, you may have a problem that just
> doesn't parallelize very well, at least on the less expensive beowulf
> architectures.  In that case, your alternatives are to spend a lot more
> money on communications than on computation -- buy a truly high speed
> network like e.g. Myrinet and use it with relatively cheap and slow
> processors, and you might be able to scale up to some decent limit.
> Greg Lindahl has presented studies of alpha/myrinet clusters that scaled
> well for e.g. gravitation problems (another long range interaction) that
> might be relevant at Linux Expo (the one in Raleigh a year and a half
> ago) that are probably in the proceedings.

Well put, Dr. Brown.  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.

Regards,

Mike Prinkey
Aeolus Research, Inc.