A LINEAR MOVING ADAPTIVE PARTICLE-MESH N-BODY ALGORITHM

We present the theory, algorithm, and numerical experiments for the im plementation of a new N-body algorithm, called APM. It scales linearly with the number of particles for the computational effort per time st ep. The resolution is fully adaptive, with a typical smoothing length comparable to the local interparticle separation. This is accomplished through the use of a dynamical coordinate system, which adjusts itsel f to the local density distribution. For the Poisson solver a multigri d iteration scheme is used. The scheme is fully data parallel and data local. A specific implementation of this algorithm is described which is available to the astrophysics community. It is optimized for scala r, vector, and shared memory parallel machines. Performance characteri stics are compared to traditional particle-mesh (PM) algorithms. The a lgorithm inherently has a threefold higher computing cost than the PM method with the same number of grid cells, but offers much higher reso lution, and currently appears to be amongst the fastest adaptive high- resolution N-body algorithms.