A hierarchical O(N) force calculation algorithm
From MaRDI portal
Publication:697691
DOI10.1006/JCPH.2002.7026zbMATH Open1130.85303arXivastro-ph/0202512OpenAlexW3103772912MaRDI QIDQ697691FDOQ697691
Publication date: 17 September 2002
Published in: Journal of Computational Physics (Search for Journal in Brave)
Abstract: A novel code for the approximate computation of long-range forces between N mutually interacting bodies is presented. The code is based on a hierarchical tree of cubic cells and features mutual cell-cell interactions which are calculated via a Cartesian Taylor expansion in a symmetric way, such that total momentum is conserved. The code benefits from an improved and simple multipole acceptance criterion that reduces the force error and the computational effort. For N>10^4, the computational costs are found empirically to rise sub-linear with N. For applications in stellar dynamics, this is the first competitive code with complexity O(N), it is faster than the standard tree code by a factor ten or more.
Full work available at URL: https://arxiv.org/abs/astro-ph/0202512
Recommendations
- Publication:3359807
- An \(O(n)\) time hierarchical tree algorithm for computing force field in \(n\)-body simulations
- A cost optimal parallel algorithm for computing force field in \(N-\)body simulations on a CREW PRAM
- A modified tree code: Don't laugh; it runs
- scientific article; zbMATH DE number 1222823
Galactic and stellar dynamics (85A05) Numerical approximation and computational geometry (primarily algorithms) (65D99) Applications to the sciences (65Z05)
Cites Work
- A fast algorithm for particle simulations
- Title not available (Why is that?)
- A fast adaptive multipole algorithm in three dimensions
- A portable parallel particle program
- Skeletons from the treecode closet
- A comparison between the fast multipole algorithm and the tree-code to evaluate gravitational forces in 3-D
Cited In (21)
- An adaptive error-controlled hybrid fast solver for regularized vortex methods
- An equivalent definition of the histogram of forces: theoretical and algorithmic implications
- Analytic integration of the Newton potential over cuboids and an application to fast multipole methods
- Non-intrusive hierarchical coupling strategies for multi-scale simulations in gravitational dynamics
- Fast algorithms for large dense matrices with applications to biofluids
- Relativistic space-charge field calculation by interpolation-based treecode
- A Smooth Partition of Unity Finite Element Method for Vortex Particle Regularization
- A sparse octree gravitational \(N\)-body code that runs entirely on the GPU processor
- How to improve the diagnosis of kinetic energy in \(\delta f\) PIC codes
- A fast algorithm with error bounds for quadrature by expansion
- Variable order revised binary treecode
- Predicting the dark matter velocity distribution in galactic structures: tests against hydrodynamic cosmological simulations
- The block-P\(^{3}\)M algorithm
- A Directional Equispaced Interpolation-Based Fast Multipole Method for Oscillatory Kernels
- Fast multipole preconditioners for sparse matrices arising from elliptic equations
- Revision of DASHMM: Dynamic Adaptive System for Hierarchical Multipole Methods
- A GPU-accelerated fast multipole method based on barycentric Lagrange interpolation and dual tree traversal
- Comparison of two different tree algorithms
- An improved fast multipole method for electrostatic potential calculations in a class of coarse-grained molecular simulations
- A splitting-free vorticity redistribution method
- A GPU-parallelized interpolation-based fast multipole method for the relativistic space-charge field calculation
Uses Software
This page was built for publication: A hierarchical \({\mathcal O}(N)\) force calculation algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q697691)
