N-body Methods Code and Matlab Binaries

Detailed Usage

Kernels

The code comes with support for a few kernels. However, the code is designed so that other kernels can be implemented in C and used quite easily. The provided kernels are:

Gaussian - 'gaussian'

influence = weight * exp(-distance^2/h^2)

where h, the bandwidth, is the only kernel parameter and the distance is the L2-norm.

Laplacian - 'laplacian'

influence = weight * exp(-distance/h)

where h, the bandwidth, is the only kernel parameter and the distance is the L1-norm.

Polynomial - 'polynomial'

influence = weight * (distance^q + b)^c

where p, q, b and c are the kernel parameters, giving the distance as the Lp-norm.

Sigmoidal - 'sigmoid'

influence = weight * tanh(alpha * distance^q - beta)

where p, q, alpha and beta are the kernel parameters, giving the distance as the Lp-norm.

LPQ (increasing) - 'lpq'

influence = weight * (1 + distance^q)

where p, q and 'increasing' are the kernel parameters, giving the distance as the Lp-norm and 'increasing' is set to 1.

LPQ (decreasing) - 'lpq'

influence = weight / (1 + distance^q)

where p, q and 'increasing' are the kernel parameters, giving the distance as the Lp-norm and 'increasing' is set to 0.

Gaussian (negative) - 'gaussian_neg'

influence = weight * -exp(-distance^2/h^2)

where h, the bandwidth, is the only kernel parameter and the distance is the L2-norm. This is an example of a kernel where the influences are always negative.

Gaussian Derivative - 'dog'

influence = weight * -2 * distance / h * exp(-distance^2/h^2)

where h, the bandwidth, is the only kernel parameter and the distance is the L2-norm. This is an example of a kernel that does not, in general, satisfy the monotonicity requirement of the kd-tree dual-tree algorithm or the triangle inequality requirement of the anchors hierarchy dual-tree algorithm. However, certain ranges of distances with certain kernel bandwidths can satisfy these requirements (eg. all distances are less than 1 and the bandwidth is 3).

Note

Options

While most of the arguments to the nbody_methods function are straightforward, the influence_descriptor and weights_descriptor arguments require some explanation. In particular, these arguments give the dual-tree algorithms information about the inputs that it can use to compute answers fast.

The influence_descriptor argument

The influence_descriptor argument tells a dual-tree algorithm whether or not the influences given by the kernel on the input points are all positive ('positive'), all negative ('negative') or both positive and negative ('mixed'). This information is needed for the max-product algorithm when it is bounding the value of the maximum influence of a node.

The weights_descriptor argument

The weights_descriptor argument tells a dual-tree algorithm whether or not the weights associated with the source particles are all positive ('positive'), all negative ('negative') or both positive and negative ('mixed'). This information is needed for the sum-product and max-product algorithms when they are bounding the influence values of a node.

Warning!

The 'mixed' argument in both cases is reserved for the case when you know for certain that the values of the influences or weights take on both positive and negative values. It is not, in general, to be used when you simply don't know what values the influence or weights will take on. However, the combination of 'mixed' and 'mixed' for both descriptors does allow for the case where one or both ranges are unknown. Of course, this combination of descriptors also leads to the the slowest running time.

Custom Kernels

It is expected that many users will want to use a kernel other than one that has been provided. As such, the process of adding and using user-defined kernels is detailed below:

1. Add kernel_name.h and kernel_name.c files to the src/common/kernels directory.
2. Implement the 5 kernel functions that are to be assigned to the function pointers in kernel.h
   • name_kernel_init - initialize the kernel by setting its parameters
   • name_kernel_destroy - destroy the kernel by freeing its parameters
   • name_kernel_influence - compute the influence of a source particle on a target particle given the source particle's weight and the distance between the particles
   • name_kernel_distance - compute the distance between two particles
   • name_kernel_increasing - if the kernel's influence increases with distance this should be 1 and if the kernel's influence decreases with distance it should be 0.
3. Add a string-kernel binding to src/common/utils.c in the function 'setup_kernel'. This is just the assignment of function pointers. You will also have to add kernel_name.h to the '#include's in src/common/utils.c
4. On Linux or Solaris, add the kernel_name.c file to the appropriate place in the Makefile. On Windows, add the kernel_name.h and kernel_name.c files to the solution.