Module: SpaceCharge

The SpaceCharge module bundles different approaches to efficiently simulate the electric interaction between particles (space charge).

The module contains submodules implementing individual calculation approaches, generalized interface classes are located in the module itself:

class FieldCalculator

Subclassed by BTree::ParallelTree, BTree::Tree, SpaceCharge::GenericSpaceChargeSolver

Public Functions

virtual ~FieldCalculator() = default
virtual Core::Vector getEFieldFromSpaceCharge(Core::Particle &particle) = 0
class GenericSpaceChargeSolver : public SpaceCharge::FieldCalculator

Abstract base class for Barnes-Hut Tree nodes

Subclassed by ExaFMMt::FMMSolver, FMM3D::FMMSolver, SpaceCharge::FullSumSolver

Public Functions

GenericSpaceChargeSolver()

Default Constructor

void insertParticle(Core::Particle &particle, std::size_t ext_index)

Insert particle into the field solver

Parameters:

  • particle – the particle to insert

  • ext_index – an external index number for the particle / numerical particle id (most likely from simion)

void removeParticle(std::size_t ext_index)

Removes a particle with a given particle index / particle id and its hosting leaf node from the fmm solver

Parameters:

ext_index – the external numerical particle id

std::size_t getNumberOfParticles() const

Gets the number of particles in the fmm solver

virtual Core::Vector getEFieldFromSpaceCharge(Core::Particle &particle) override
virtual void computeChargeDistribution() = 0

Sub Module: BTree

The BTree sub module provides an Barnes-Hut tree implementation for space charge calculation.

Tree Node Base Classes

Barnes-Hut trees are in fact tree structures which are formed by a set of nodes and connections (edges) between them. BTree::AbstractNode is an abstract base class for all tree nodes, it bundles all characteristics and methods all nodes have. BTree::GenericBaseNode bundles generic basic methods which are applicable for all concrete node types, e.g. particle insertion into the node or particle removal from the node.

class AbstractNode

Abstract base class for Barnes-Hut Tree nodes

Subclassed by BTree::GenericBaseNode< Node >, BTree::GenericBaseNode< ParallelNode >, BTree::GenericBaseNode< NodType >

Public Types

enum Octant

Sub-Octants of a node (e.g. SWT = south west top, NEB = north east bottom)

Values:

enumerator SWT
enumerator NWT
enumerator SET
enumerator NET
enumerator SWB
enumerator NWB
enumerator SEB
enumerator NEB

Public Functions

AbstractNode(Core::Vector min, Core::Vector max)

Constructs a tree node

Parameters:

  • min – the lower corner of the node (spatial xlo,ylo,zlo corner)

  • max – the upper corner of the node (spatial xhi,yhi,zhi corner)

  • parent – the parent node, the new node will be a subnode of that node (can be nullptr for root nodes)

virtual ~AbstractNode() = default
AbstractNode(const AbstractNode &that) = default
std::size_t getNumberOfParticles() const

Gets the number of particles in the node including the suboctant nodes and thus all particles in the spatial extend of the node

BTree::TreeParticle *getParticle() const

Gets a pointer to the particle in the node

Core::Vector getCenter() const

Returns the spatial center of the node

Core::Vector getMax() const

Returns the “upper” corner of the node (corner with xHi, yHi, zHi coordinates)

Core::Vector getMin() const

Returns the “lower” corner of the node (corner with xLo, yLo, zLo coordinates)

double getCharge() const

Returns the total charge of the node (including the contributions of the subnodes)

Core::Vector getCenterOfCharge() const

Returns the geometric center of charge of the node (including the contribution of the subnodes)

Octant getOctant(Core::Vector location) const

Returns the sub-octant of the current node where a given location falls into

Parameters:

location – a location to get the sub-octant for

Returns:

the sub octant in which given location falls into

virtual void initAsRoot() = 0
virtual bool isRoot() const = 0
virtual void updateParents() = 0
virtual void updateSelf() = 0
virtual void removeMyselfFromTree() = 0
virtual void insertParticle(BTree::TreeParticle *particle) = 0
virtual void computeChargeDistributionRecursive() = 0
virtual std::string toString() const = 0

Public Static Functions

static int getNumberOfNodes()

Return total number of existing tree nodes

static void setTheta(double newTheta)

Sets the multipole acceptance criterion (theta) for the nodes

static double getTheta()

Gets current value of multipole acceptance criterion (theta)

static Core::Vector calculateElectricField(const Core::Vector &r1, const Core::Vector &r2, double charge2)

Computes the electric field on a test charge located at r1 from a charge located at r2

Parameters:

  • r1 – the position of the small test charge (in m)

  • r2 – the position of the charge “charge2” (in m)

  • charge2 – the charge of “charge2” (in coulomb)

Returns:

The electric field at the position r1

Public Static Attributes

static constexpr double CHARGE_EPSILON = Core::ELEMENTARY_CHARGE * 1e-3

lower boundary of possible charge in nodes,

template<class NodType>
class GenericBaseNode : public BTree::AbstractNode

Templated base class for nodes in Barnes-Hut tree, which bundles generalizable methods / algorithms for concrete tree node types NodType.

This class uses the Curiously recurring template pattern (CRTP) / F-bound idiom to generalize functionality for concrete tree nodes.

Template Parameters:

NodType – the concrete node type to generate generalizable methods for

Public Functions

GenericBaseNode(Core::Vector min, Core::Vector max, NodType *parent)

Basic constructor

Parameters:

  • min – The lower corner of the node

  • max – The upper corner of the node

  • parent – A node which is the parent node in the tree structure of this node

GenericBaseNode(const GenericBaseNode &that) = delete
GenericBaseNode &operator=(const GenericBaseNode &that) = delete
~GenericBaseNode() override

Destructor

virtual void initAsRoot() override

Inits a node as root of a tree

virtual bool isRoot() const override

Returns true if the node is a root (has no parent)

NodType *createOctNode(Octant oct)

Creates a new sub-octant node as a child of this node in one of the sub octants of this node.

Parameters:

oct – the location / sub-octant where the new node should be created

Returns:

the newly created sub-octant node

NodType **getOctants()

Get links to the child octant nodes

Returns:

c style array with pointers to the child octant nodes

virtual void removeMyselfFromTree() override

Removes this node from the tree structure

virtual void updateSelf() override

Updates the state of this node

virtual void updateParents() override

Updates the internal state of the parent nodes of this node up to the tree root

virtual void insertParticle(BTree::TreeParticle *particle) override

Inserts a particle into the node. If the node is already occupied, the node is subdivided into sub-nodes and the particle is inserted in the according sub-nodes.

Parameters:

particle – the particle to insert into the node.

virtual void computeChargeDistributionRecursive() override

Computes the charge distribution in this node and its subnodes and updates the node and its subnodes with updates charge and center of charge values

virtual std::string toString() const override

Returns a string which reflects the state of the node

virtual void printTree(int level) const

Prints the tree with this node as root to cout

Parameters:

level – level of the current tree node with respect to the tree root (should be 0 when called manually)

void writeToStream(std::ostream &filestream, void (*writeFct)(std::ostream &filestream, const NodType *node)) const

A method to export internal information to a filestream. The data transformation and formatting is done by a passed write function. The write function is recursively applied to all subnodes of this node and thus the whole subtree below this node.

Parameters:

  • filestream – a filestream to write to

  • writeFct – a function, taking the filestream and a Core node, which extracts information from the node

virtual void testNodeIntegrity(int level)

Tests the node integrity of the subtree with the current node as root

Parameters:

  • debug – prints some additional information to cout if true

  • level – level of the current tree node with respect to the tree root (should be 0 when called manually)

Throws:

logic_error – if an inconsistent node is found

Parallelized Barnes-Hut Tree

A partly parallelized version of a Barnes-Hut tree is realized in BTree::ParallelTree, which uses BTree::ParallelNode as node class.

class ParallelTree : public SpaceCharge::FieldCalculator

Public Functions

ParallelTree(Core::Vector min, Core::Vector max)

Constructor: Constructs a new tree

Parameters:

  • min – the lower spatial boundary of the tree domain

  • min – the upper spatial boundary of the tree domain

ParallelNode *getRoot() const

Get the tree root node

treeParticlePtrList *getParticleList() const

Get a linear particle linked list of the particles in the tree

std::size_t getNumberOfParticles() const

Gets the number of particles in the tree

std::size_t init()

Inits the internal data structures after a structural change on the tree structure and returns the total number of tree nodes.

Returns:

the total number of nodes in this tree

std::vector<std::size_t> countNodesOnLevels()

Counts and returns the number of nodes on the individual tree levels and

virtual Core::Vector getEFieldFromSpaceCharge(Core::Particle &particle)

Computes the electric field acting on a given particle from the charged particles in this tree

Parameters:

particle – A particle to calculate the total electric field for

Returns:

The electric field on the particle resulting from the particles in the tree

void insertParticle(Core::Particle &particle, std::size_t ext_index)

Insert particle into the tree

Parameters:

  • particle – the particle to insert

  • ext_index – an external index number for the particle / numerical particle id (most likely from simion)

void removeParticle(std::size_t ext_index)

Removes a particle with a given particle index / particle id and its hosting leaf node from the tree

Parameters:

ext_index – the external numerical particle id

BTree::TreeParticle *getParticle(std::size_t ext_index) const

Retrieves a particle from the tree by its external index

Parameters:

ext_index – the external particle index

Returns:

the retrieved particle

void updateParticleLocation(std::size_t extIndex, Core::Vector newLocation, int *numNodesChanged)

Upates the location of a particle in this tree.

Parameters:

  • extIndex – Index / ID of the Particle to modify

  • newLocation – Location to set for the selected particle

  • numNodesChanged – an integer reference to count the number of structurally changed nodes

std::size_t updateNodes(int ver)

Updates the internal state of the nodes in this tree. The update is performed serialized and parallelized.

Parameters:

ver – number of nodes which have changed in terms of tree structure (0 means that the structure of the tree has not changed and the serialized data structures has not to be updated)

Returns:

the total number of nodes in the tree

void printParticles() const
class ParallelNode : public BTree::GenericBaseNode<ParallelNode>

Public Functions

ParallelNode(Core::Vector min, Core::Vector max, ParallelNode *parent)

Constructs a tree node

Parameters:

  • min – the lower corner of the node (spatial xlo,ylo,zlo corner)

  • max – the upper corner of the node (spatial xhi,yhi,zhi corner)

  • parent – the parent node, the new node will be a subnode of that node (can be nullptr for root nodes)

ParallelNode(const ParallelNode &that) = delete
ParallelNode &operator=(const ParallelNode &that) = delete
void serializeIntoVector(std::vector<BTree::ParallelNode*> &serializedNodes, std::size_t treeLevel, std::vector<std::size_t> &insertPositions)

Serializes the subtree with this node as root into a serialized vector of pointers to the nodes. The nodes are sorted according to their level. The current insert position on the individual tree levels are given in a second vector. The given serializedNodes vector has to be sufficiently large to hold all nodes of the sub tree and the initial insertPositions have to be at the correct positions so that nodes of the individual tree levels fit into the serialized vector without overlap

Parameters:

  • serializedNodes – A vector of node pointers in which the subtree is serialized into

  • treeLevel – The current tree level (starting from the root)

  • insertPositions – A vector with the current insert positions in the serialized vector for the individual tree levels

std::size_t maximumRecursionDepth() const

Determines the maximum depth, in terms of tree levels, of the (sub) tree with this node as root

Returns:

The maximum number of tree levels of the subtree with this node as root

void countNodesOnLevel(std::size_t level, std::vector<std::size_t> &numOfNodesOnLevels) const

Count nodes on individual tree levels in the subtree with this node as root.

Parameters:

  • level – The level of this node is on the global tree

  • numOfNodesOnLevels – a vector, one element per tree level, to count the the nodes number into

Serial Barnes-Hut Tree

A legacy, non parallelized, simple version of a Barnes-Hut tree is BTree::Tree, which uses BTree::Node as node class. This tree version is mostly used for benchmarks or comparison purposes.

class Tree : public SpaceCharge::FieldCalculator

Public Functions

Tree(Core::Vector min, Core::Vector max)

Constructs a new tree

Parameters:

  • min – the lower spatial boundary of the tree domain

  • max – the upper spatial boundary of the tree domain

Node *getRoot() const

Gets the tree root

treeParticlePtrList *getParticleList()

Gets a linear particle list of the particles in the tree

Returns:

a linearized linked list of the particles in the tree

std::size_t getNumberOfParticles() const

Get the number of particles in the tree

Returns:

the number of particles in the tree

void computeChargeDistribution()

Computes / initalizes the charge distribution in the tree: The charge in the individual tree nodes is calculated from the particles in the tree

virtual Core::Vector getEFieldFromSpaceCharge(Core::Particle &particle) override

Computes the electric field from the particles in the tree on a given test particle

Parameters:

particle – a testparticle on which the electric force from the tree acts

Returns:

the electric force on that particle

void insertParticle(Core::Particle &particle, size_t ext_index)

Insert an unwrapped particle into the tree

Parameters:

  • particle – the particle to insert

  • ext_index – an external index number for the particle / numerical particle id (most likely from a SIMION simulation)

void removeParticle(size_t ext_index)

Removes a particle with a given particle index / particle id and its hosting leaf node from the tree

Parameters:

ext_index – the external numerical particle index

BTree::TreeParticle *getParticle(size_t ext_index) const

Retrieves a particle from the tree by its external index

Parameters:

ext_index – the external particle index

Returns:

the retrieved particle

void updateParticleLocation(size_t ext_index, Core::Vector newLocation)

Updates the location of a particle in the tree (the position of particles managed by the tree should not be updated directly via the particle, this will invalidate the tree)

Parameters:

  • ext_index – the external index of the particle to update

  • newLocation – a new location of that particle

void printParticles() const

Prints the particles in the tree to cout

class Node : public BTree::GenericBaseNode<Node>

Public Functions

Node(Core::Vector min, Core::Vector max, Node *parent)

Constructs a tree node

Parameters:

  • min – the lower corner of the node (spatial xlo,ylo,zlo corner)

  • max – the upper corner of the node (spatial xhi,yhi,zhi corner)

  • parent – the parent node, the new node will be a subnode of that node (can be nullptr for root nodes)

Node(const Node &that) = delete
Node &operator=(const Node &that) = delete
Core::Vector computeElectricFieldFromTree(Core::Particle &targetP)

Computes the electric field on a given particle from the charged particles in a tree with this node as root node

Parameters:

targetP – a particle to calculate the total electric field for

Returns:

the electric force on the particle resulting from the particles in the tree with this node as root

void testSpatialTreeIntegrity()

Tests if all tree nodes are within the spatial limits of their parent nodes

Throws:

logic_error – if an inconsistent node is found

void testNodeParticleIntegrity()

Tests if the particles in the nodes of the subtree with this node as root are consistent, regarding the spatial positions.

Throws:

logic_error – if a particle is found which is out of the spatioal bounds of its containing node

bool isNodeInSubtree(const Node *nodeToFind, bool debug) const

Checks if a tree node is in a subtree with this node as root

Parameters:

  • nodeToFind – pointer to the node to find in the subtree

  • debug – prints information about the found node to cout if true

Returns:

true if the given node is found in the subtree

bool isParticleInSubtree(const TreeParticle *particle, bool debug) const

Checks if a particle is in a subtree with this node as root

Parameters:

  • particle – pointer to a particle to find in the subtree

  • debug – prints information about the found particle if true

Returns:

true if the particle is found in the subtree

Sub Modules: Fast Multipole Methods (FMM)

Two submodules provide interfaces to external fast multipole method (FMM) libraries to allow fast space charge calculations with FMM.

exafmm-t Interface

Interface to exafmm-t for coulombic interaction (space charge) calculations. This modules a build with the path to exafmm-t passed via EXAFMMT_PATH variable in the cmake configuration, as described in the installation guide.

class FMMSolver : public SpaceCharge::GenericSpaceChargeSolver

Public Functions

virtual Core::Vector getEFieldFromSpaceCharge(Core::Particle &particle) override
virtual void computeChargeDistribution() override
void setExpansionOrder(int expansionOrder)
void setMaxBodiesPerLeaf(int maxBodiesPerLeaf)

FMM3D Interface

Interface to FMM3D for coulombic interaction (space charge) calculations. This modules a build with the path to exafmm-t passed via FMM_3D_PATH variable in the cmake configuration, as described in the installation guide

class FMMSolver : public SpaceCharge::GenericSpaceChargeSolver

Public Functions

virtual void computeChargeDistribution() override
void setRequestedPrecision(double requestedPrecision)