×

Towards an adaptive treecode for \(N\)-body problems. (English) Zbl 1452.70001

Summary: \(N\)-body problems are notoriously expensive to compute. For \(N\) bodies, evaluating a sum directly scales like \({\mathcal{O}}(N^2)\). A treecode approximation to the \(N\)-body problem is highly desirable because for a given level of accuracy, the computation scales instead like \({\mathcal{O}}(N\log{N})\). A main component of the treecode approximation, is computing the Taylor coefficients and moments of a cluster-particle approximation. For the two-parameter family of regularized kernels previously introduced [B. W. Ong et al., J. Sci. Comput. 71, No. 3, 1212–1237 (2017; Zbl 1378.65184)], computing the Taylor coefficients directly is algebraically messy and undesirable. This work derives a recurrence relationship and provides an algorithm for computing the Taylor coefficients of two-parameter family of regularized kernels. The treecode is implemented in Cartesian coordinates, and numerical results verify that the recurrence relationship facilitates computation of \(G^{\varepsilon ,n}({\mathbf{x}})\) and its derivatives.

MSC:

70-08 Computational methods for problems pertaining to mechanics of particles and systems
70F10 \(n\)-body problems
65P99 Numerical problems in dynamical systems
41A58 Series expansions (e.g., Taylor, Lidstone series, but not Fourier series)
41A63 Multidimensional problems

Citations:

Zbl 1378.65184

Software:

PEPC
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barnes, J.; Hut, P., A hierarchical O (NlogN) force-calculation algorithm, Nature, 324, 446-449 (1986) · doi:10.1038/324446a0
[2] Bate, RR; Mueller, DD; White, JE, Fundamentals of Astrodynamics (1971), Mineola: Dover Publications, Mineola
[3] Beygelzimer, A., Kakade, S., Langford, J.: Cover trees for nearest neighbor. In: Proceedings of the 23rd International Conference on Machine Learning, ICML ’06, pp. 97-104. Association for Computing Machinery, New York, NY, USA (2006). 10.1145/1143844.1143857
[4] Birdsall, CK; Langdon, AB, Plasma Physics via Computer Simulation (2004), Boca Raton: CRC Press, Boca Raton
[5] Christlieb, A.; Krasny, R.; Verboncoeur, J., A treecode algorithm for simulating electron dynamics in a Penning-Malmberg trap, Comput. Phys. Commun., 164, 1, 306-310 (2004) · Zbl 1196.81012 · doi:10.1016/j.cpc.2004.06.076
[6] Christlieb, AJ; Krasny, R.; Verboncoeur, JP; Emhoff, JW; Boyd, ID, Grid-free plasma simulation techniques, IEEE Trans. Plasma Sci., 34, 2, 149-165 (2006) · doi:10.1109/TPS.2006.871104
[7] Coifman, R.; Rokhlin, V.; Wandzura, S., The fast multipole method for the wave equation: a pedestrian prescription, IEEE Antennas Propag. Mag., 35, 3, 7-12 (1993) · doi:10.1109/74.250128
[8] Duan, Z.; Krasny, R., An adaptive treecode for computing nonbonded potential energy in classical molecular systems, J. Comput. Chem., 22, 2, 184-195 (2001) · doi:10.1002/1096-987X(20010130)22:2<184::AID-JCC6>3.0.CO;2-7
[9] Jackson, JD, Classical Electrodynamics (1999), Hoboken: Wiley, Hoboken · Zbl 0920.00012
[10] Leonard, A., Vortex methods for flow simulation, J. Comput. Phys., 37, 3, 289-335 (1980) · Zbl 0438.76009 · doi:10.1016/0021-9991(80)90040-6
[11] Lindsay, K.; Krasny, R., A particle method and adaptive treecode for vortex sheet motion in three-dimensional flow, J. Comput. Phys., 172, 2, 879-907 (2001) · Zbl 1002.76093 · doi:10.1006/jcph.2001.6862
[12] Ong, BW; Christlieb, AJ; Quaife, BD, A new family of regularized kernels for the harmonic oscillator, J. Sci. Comput., 71, 3, 1212-1237 (2017) · Zbl 1378.65184 · doi:10.1007/s10915-016-0336-0
[13] Speck, R.; Arnold, L.; Gibbon, P., Towards a petascale tree code: scaling and efficiency of the PEPC library, J. Comput. Sci., 2, 2, 138-143 (2011) · doi:10.1016/j.jocs.2011.01.011
[14] van Elteren, A.; Bédorf, J.; Portegies Zwart, S., Multi-scale high-performance computing in astrophysics: simulating clusters with stars, binaries and planets, Philos. Trans. R. Soc. A (2018) · doi:10.1098/rsta.2018.0153
[15] Winckelmans, GS; Leonard, A., Contributions to vortex particle methods for the computation of three-dimensional incompressible unsteady flows, J. Comput. Phys., 109, 2, 247-273 (1993) · Zbl 0795.76065 · doi:10.1006/jcph.1993.1216
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.