One of the most central computational problems in physics is the
simulation of a particle system with gravitational or Coulombic forces.
The first task is to compute the potential field of the system.
The potential at each point is the sum of the various potentials
determined by the particles.
The potential at contributed by a particle at
is often of
the form
, where
depends on the strength of
the charge (or mass) of the particle at
.
Assuming infinite arithmetic, it is easy to compute
the potential in time, where
is the number of particles.
A method, called the fast multipole method,
based on multipole expansion was developed in [65]
and refined by introducing computational-geometric
ideas in distance geometry [25].
To apply the fast multipole method, one must first construct a tree
decomposition of the set of particles, along with a set of pairs of
nodes in the tree. This step can be shown to require time
in the algebraic model. Given such a decomposition, the fast multipole
method requires only linear time. However, the constants involved in the fast
multipole method are so large that for realistic numbers of particles, this
turns out to be the most time-consuming part of the computation.
The large constant in the fast multipole method arises both from geometry and from the need to manipulate series expansions, the size of which grows with the desired output precision. Despite the large constant, the method has proven useful for simulations involving millions of particles, for which the direct approach is not even feasible. Reduction of this constant would have significant practical implications for particle simulation, both by speeding up existing applications, and extending the useful range of the fast multipole method to smaller sets of particles.
There is a great deal of flexibility in the geometrical decomposition needed for the fast multipole method, and some gains could result from investing more effort in this part of the algorithm. Currently, the tree computed is a fairly standard box decomposition that guarantees a small number of pairs of nodes for which the fast multipole method must be applied. However, for any given point set, there may be another tree that results in a somewhat smaller number of pairs, in which case it may be worthwhile to expend the effort needed to find such a tree.
The efficient implementation of the fast multipole method poses non-trivial technical challenges. For example, in current implementations, one typically constructs a tree in which the leaves are subsets of particles rather than single particles, and computes the potential between these subsets directly. The size of these subsets has a strong effect on the efficiency of an implementation, and must be chosen carefully in order for the method to be of any benefit.
Efficient parallel implementations would be particularly useful, because a particle simulation can require many potential computations, each of which carries the simulation through one small time step. The more steps that can be performed, the more can be learned about the dynamics of large particle systems, so any speed increases will have a direct impact on computational physics.