In Chapter 2 we saw the basic workings of the tree algorithm. Now we will discuss some methods that can be used to optimise the performance of this type of code. Although most of these techniques are not specific to tree codes, they are not always straightforward to implement within a hierarchical data structure. It therefore seems worthwhile to reconsider some of the common tricks of the N-body trade, in order to make sure that the tree code is optimised in every sense – not just in its N log N scaling.

There are basically two points of possible improvement:

• Improvement of the accuracy of the particle trajectory calculation by means of higher order integration schemes and individual timesteps. This is especially important for problems involving many close encounters of the particles, that is, ‘collisional’ problems.

• Speedup of the computation time needed to evaluate a single timestep by use of modern software and hardware combinations, such as vectorisation, and special-purpose hierarchical or parallel computer architecture.

Individual Timesteps

For most many-body simulations one would like the total simulated time T = ntΔt (where nt is the number of timesteps) to be as large as possible to approach the hydrodynamic limit. However, the choice of the timestep Δt has to be a compromise between this aim and the fact that as Δt increases, the accuracy of the numerical integration gets rapidly worse.