Speakers
Prof.
Peter Hobson
(Brunel University (GB))Dr
raul lopes
(School of Design and Engineering - Brunel University, UK)
Description
Variations of kd-trees represent a fundamental data structure frequently used in geometrical algorithms, Computational Statistics, and clustering. They have numerous applications, for example in track fitting, in the software of the LHC experiments and in physics in general. Computer simulations of N-body systems, for example, have seen applications in the study of dynamics of interacting galaxies, particle beam physics, and molecular dynamics in biochemistry. The many-body tree methods devised by Barnes and Hutt in the 1980s and the Fast Multipole Method introduced in 1987 by Greengard and Rokhlin use variants of kd-trees to reduce the computation time upper bound to O(n log n) or even O(n) from the
O(n^2) demanded by Particle in Cell algorithms. Naive approaches to
kd-trees can, however, lead to algorithms that produce uncompressed trees and use O(n^2) work to build a tree for n items. We present an
algorithm that uses the principle of well-separated pairs decomposition to always produce compressed trees in O(n log n) work. We present and evaluate parallel implementations for the algorithm that can take advantage of multi-core architectures.
Primary author
Dr
raul lopes
(School of Design and Engineering - Brunel University, UK)
Co-authors
Ivan Reid
(Brunel University (GB))
Prof.
Peter Hobson
(Brunel University (GB))
