PROVABLY GOOD PARTITIONING AND LOAD BALANCING ALGORITHMS FOR PARALLELADAPTIVE N-BODY SIMULATION

We present an efficient and provably good partitioning and load balanc ing algorithm for parallel adaptive N-body simulation. The main ingred ient of our method is a novel geometric characterization of a class of communication graphs that can be used to support hierarchical N-body methods such as the fast multipole method (FMM) and the Barnes-Hut met hod (BH). We show that communication graphs of these methods have a go od partition that can be found efficiently sequentially and in paralle l. In particular, we show that an N-body communication graph (either f or BH or for FMM) can be partitioned into two subgraphs with equal com putation load by removing only O(root nlog n) and O(n(2/3)(log n)(1/3) ) number of nodes, respectively, for two and three dimensions. These b ounds on node-partition imply bounds on edge-partition of O(root n(log n)(3/2)) and O(n(2/3)(log n)(4/3)), respectively, for two and three d imensions. To the best of our knowledge, this is the first theoretical result on the quality of partitioning N-body communication graphs for nonuniformly distributed particles. Our results imply that parallel a daptive N-body simulation can be made as scalable as computation on re gular grids and as efficient as parallel N-body simulation on uniforml y distributed particles.