A hierarchical O(N) force calculation algorithm
From MaRDI portal
Publication:697691
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.
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
Cites work
- scientific article; zbMATH DE number 1069612 (Why is no real title available?)
- A comparison between the fast multipole algorithm and the tree-code to evaluate gravitational forces in 3-D
- A fast adaptive multipole algorithm in three dimensions
- A fast algorithm for particle simulations
- A portable parallel particle program
- Skeletons from the treecode closet
Cited in
(23)- A Treecode for Accurate Force Calculations
- An adaptive error-controlled hybrid fast solver for regularized vortex methods
- A Directional Equispaced Interpolation-Based Fast Multipole Method for Oscillatory Kernels
- A GPU-parallelized interpolation-based fast multipole method for the relativistic space-charge field calculation
- Comparison of two different tree algorithms
- A splitting-free vorticity redistribution method
- A sparse octree gravitational \(N\)-body code that runs entirely on the GPU processor
- Analytic integration of the Newton potential over cuboids and an application to fast multipole methods
- A smooth partition of unity finite element method for vortex particle regularization
- The block-P\(^{3}\)M algorithm
- An improved fast multipole method for electrostatic potential calculations in a class of coarse-grained molecular simulations
- Revision of DASHMM: dynamic adaptive system for hierarchical multipole methods
- DEM simulations of toner particles with an \(O(N \log N)\) hierarchical tree code algorithm
- Fast algorithms for large dense matrices with applications to biofluids
- Predicting the dark matter velocity distribution in galactic structures: tests against hydrodynamic cosmological simulations
- Non-intrusive hierarchical coupling strategies for multi-scale simulations in gravitational dynamics
- How to improve the diagnosis of kinetic energy in \(\delta f\) PIC codes
- Relativistic space-charge field calculation by interpolation-based treecode
- A fast algorithm with error bounds for quadrature by expansion
- Fast multipole preconditioners for sparse matrices arising from elliptic equations
- Variable order revised binary treecode
- An equivalent definition of the histogram of forces: theoretical and algorithmic implications
- A GPU-accelerated fast multipole method based on barycentric Lagrange interpolation and dual tree traversal
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)
