Introduction

Aboria is a C++ library that supports the implementation of particle-based numerical methods. Here we define a particle-based method as consisting of three key properties:

There exists a set of $N$ particles that have positions within an hypercube of $n$ dimensions. The boundaries of the hypercube can optionally be periodic.
The numerical method in question can be described in terms of non-linear operators on the $N$ particle positions and/or variables defined at these positions.
These operators are defined solely by the particle positions and variables (e.g. neighbourhood interactions), there are no pre-defined connections or edges between the particles.

Aboria attempts to provide a general purpose library that can be used to support the implementation of particle-based numerical methods. The idea is to give the user complete control to define of operators on the particle set, while implementing efficiently the difficult algorithmic aspects of particle-based methods, such as neighbourhood searches and fast summation algorithms. However, even at this level it is not a one-fits-all situation and Aboria is designed to allow users to choose specific algorithms that are best suited to the particular application. For example, calculating neighbourhood interactions for a uniform particle distribution is best done using a regular cell-list data structure, while for a highly non-uniform particle distribution a tree data structure like a kd-tree might be preferable . For neighbourhood interactions that are zero beyond a certain radius, a radial search is the best algorithm to obtain interacting particle pairs, while for interactions that can be approximated for well-separated clusters of particles, the fast multipole method is an efficient fast summation algorithm.

Design

The diagram below shows the high-level design of Aboria, which consists of three separate and complimentary abstraction levels.

Aboria Level 1

This implements a particle container class which holds the particle data (positions and other user-defined variables). This class is itself based on the Standard Template Library (STL) vector class (Level 0 in the figure above ), which serves as the lowest-level data container. The user can specify the dimension of the particle's position, as well as the variables defined at each particle (velocity, temperature etc.), and the Level 1 particle set container will combine multiple Level 0 vectors to form a single data structure.

This Level 1 particle set container generally (but not fully) follows the STL specification, with its own iterators and traits. It supports operations to add particles (i.e. the STL push_back member function), remove particles (i.e. erase), and can return a single particle given an index $i$ (i.e. operator[]). This index operation returns a lightweight type containing references to the corresponding index in the set of zipped Level 0 vectors. Individual variables can be obtained from this lightweight type via get functions provided by Aboria.

Aboria Level 1 also includes multiple neighbour search classes, which can be used for fast neighbour searches throughout a hypercube domain with periodic or non-periodic boundaries. The particle set container interacts with a neighbour searching classes to embed the particles within the domain ensuring that the two data structures are kept in sync, while still allowing for updates to the particles positions throughout the domain. The current version of the code has four possible neighbour search classes:

Two types of cell lists, one supporting serial insertion and parallel queries, the other supporting parallel insertion and queries.
A kd-tree, useful for clustered particle distributions and for using Aboria's fast multipole capabilities
A hyper oct-tree

Aboria Level 2

This implements neighbourhood searching and fast summation algorithms useful for particle-based methods, using the particle set and neighbour search classes in Level 1. Currently this includes:

Neighbourhood searches using a $p$-norm distance measure, where $p$ can be any integer greater than 0, as well as $p \rightarrow \infty$ (chebyshev distance)
Approximation of kernel operators using interpolation with chebyshev polynomials, the fast multipole method, or hierarchical H2 matrices.

Note that all these algorithms can work with any neighbour search data structure, and in any number of dimensions.

Aboria Level 3

The highest abstraction level in Aboria implements two higher level APIs, suitable for implementing particle-based methods:

kernel operators specified by C++ lambda functions. These can be wrapped in Eigen matrix replacement classes, so they can be treated as standard matrices, and used in iterative solvers.
a Domain Specific Language (DSL) for specifying non-linear operators on the set of particles, using the Boost.Proto library. Users can use standard C++ operators (e.g. *, + or /), and/or a set of supplied functions (e.g. sqrt, pow or norm), to express any non-linear operator over individual particles or particle pairs.