Provably Good Partitioning and Load Balancing Algorithms for Parallel Adaptive N-Body Simulation

DOI10.1137/S1064827595288942zbMath0907.68219OpenAlexW1996639891MaRDI QIDQ4389263

Shang-Hua Teng

Publication date: 12 May 1998

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s1064827595288942

zbMATH Keywords

partitioningparallel processingload balancingscientific computing\(N\)-body simulationadaptive computinghierarchical methodstree-codesthe fast multipole method

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items

Parallel accelerated Stokesian dynamics with Brownian motion, Spectral partitioning works: planar graphs and finite element meshes, A GPU-accelerated fast multipole method based on barycentric Lagrange interpolation and dual tree traversal, An exact algorithm for graph partitioning, Optimal cache-oblivious mesh layouts, The fast multipole method: Numerical implementation, Fast multipole methods on graphics processors, Fast electrostatic force calculation on parallel computer clusters, Revision of DASHMM: Dynamic Adaptive System for Hierarchical Multipole Methods, PetFMM-A dynamically load-balancing parallel fast multipole library, Min-max-boundary domain decomposition, Communications overlapping in fast multipole particle dynamics methods, A parallel hierarchical-element method for contour dynamics simulations, \(K\)-means clustering for optimal partitioning and dynamic load balancing of parallel hierarchical \(N\)-body simulations, Fast multipole preconditioners for sparse matrices arising from elliptic equations

Uses Software

• MESHPART

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An O(n log n) algorithm for the all-nearest-neighbors problem
• The order of Appel's algorithm
• The Parallel Multipole Method on the Connection Machine
• An analysis of the finite element method for natural convection problems
• A Fast Adaptive Multipole Algorithm for Particle Simulations
• An Implementation of the Fast Multipole Method without Multipoles
• Geometric Mesh Partitioning: Implementation and Experiments
• Preconditioned, Adaptive, Multipole-Accelerated Iterative Methods for Three-Dimensional First-Kind Integral Equations of Potential Theory
• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• Separators for sphere-packings and nearest neighbor graphs
• How Good is Recursive Bisection?
• Geometric Separators for Finite-Element Meshes
• A fast algorithm for particle simulations