Scripts: Validation and Benchmarking

Validation

scripts.validation.validation_main()

Validators

scripts.validators.common.VALIDATION_OUTPUT_DIR = PosixPath('output/validation')

The validation output directory

class scripts.validators.common.ValidationFunction(*args, **kwargs)

Bases: Protocol

A custom protocol for any validation function. Allows for the addition of name and filename attributes.

Variables:

  • name (str) – The name of the validation, like a desired figure name for reproduction.

  • filename (Path) – The output filename for the produced figure, video, etc.

name
filename
scripts.validators.common.produces_validation(*, name, output_type='png')

Simple internal decorator for all validation functions that produce figures.

Parameters:

  • name (str) – The name of the validation.

  • output_type (str) – The output type for the produced figure, video, etc. (default is .png).

Figure Reproduction

scripts.validators.figure_reproduction.coplanar_simulation(dtheta, dx, dy)

Produces a coplanar simulation based on the parameters \(\Delta \theta\), \(\Delta x\), and \(\Delta y\) as seen in figure 8 of Mabrouk and Floryan [4].

Parameters:

  • dtheta (float) – The angular separation between the fish.

  • dx (float) – The horizontal separation between the fish.

  • dy (float) – The vertical separation between the fish.

Returns:

A (2,3,N) matrix consisting of the trajectories for each fish.

Return type:

NDArray

scripts.validators.figure_reproduction.reproduce_2025_fig_8()

Reproduces figure 8 of Mabrouk and Floryan [4].

scripts.validators.figure_reproduction.generate_fish_circle(r, n, x)

Radially distributes \(n\) fish on the yz-axis at \(x\). The circle is oriented such that its axis of symmetry is the \(x\)-axis and all of the fish are oriented to face the \(x\)-axis.

Parameters:

  • r – The radius of the circle.

  • n – The number of fish.

  • x – The position along the \(x\)-axis to place them.

Returns:

The system of fish.

Return type:

NDArray

scripts.validators.figure_reproduction.reproduce_2024_fig_16()

Reproduces figure 16 of Mabrouk and Floryan [3].

Octree Visualization

scripts.validators.octree_validation.draw_wireframe_cube(center, side_length, ax)

Draws a wireframe cube centered at center with side length side_length.

Parameters:

  • center (NDArray) – The cartesian position of the center of the cube.

  • side_length (float) – The side length of the cube.

scripts.validators.octree_validation.draw_octree_3d_recurse(current_node, ax, current_depth=0, *, max_depth=None, particle_size=20)

Recurses through each of the Octree nodes and draws the associated data and octant wireframes.

Parameters:

  • current_node (OctreeNode) – The present octree node to draw.

  • current_depth (int) – The current recursive depth of this node.

  • ax (Axes) – The current MatPlotLib axes to draw to.

  • max_depth (int) – The maximum recursive depth to reach. Default is None, meaning no maximum limit/displaying the full tree.

  • particle_size (int) – The size of the fish-particles to draw.

scripts.validators.octree_validation.draw_octree_3d(octree, max_depth=None)

Produces a 3-D octree plot of root, similar to Figure 2 of Barnes and Hut [1].

Parameters:

  • octree (OctreeNode) – The root of the octree to draw.

  • max_depth (int) – The maximum recursive depth to draw (default None, meaning no limit).

scripts.validators.octree_validation.compute_octree_2d_positions_recurse(node, positions, depth, x, dx, dy)

Recursively builds a list of where each of the nodes for the Octree should go when placed in 2-D space based on the Octant indices.

Parameters:

  • node (OctreeNode) – The current node.

  • positions (dict) – The current (global) dictionary of past positions. This is passed by reference, so this dictionary will be appended to throughout all recursive calls.

  • depth (int) – The current depth of this recursion, starting from 0 (the root node).

  • x (int) – The current \(x\)-position of this node, starting from 0 (the center of the image).

  • dx (float) – The horizontal spacing.

  • dy (float) – The vertical spacing.

Returns:

A tuple storing the range of \(x\)-positions (min, max) for this tree (to use when producing the canvas.

Return type:

tuple[int, int]

scripts.validators.octree_validation.draw_octree_node_2d_recurse(node, positions, ax, label_offset)

Draws this node and its children to the specified axes.

Parameters:

  • node (OctreeNode) – The current node.

  • positions (dict) – The dictionary mapping OctreeNode ID’s to image coordinates.

  • ax (Axes) – The MatPlotLib axes to draw to.

  • label_offset (float) – The horizontal offset for each node label.

scripts.validators.octree_validation.draw_octree_2d(octree, horizontal_spacing=2.0, vertical_spacing=3.0, label_offset=20)

Draw an octree as a 2D parent-child tree.

Parameters:

  • horizontal_spacing (float) – Horizontal distance multiplier between nodes.

  • vertical_spacing (float) – Vertical distance multiplier between tree levels.

  • label_offset (float) – Distance in points between node and text label.

Returns:

The MatPlotLib Axes that the Octree was drawn to.

Return type:

Axes

scripts.validators.octree_validation.generate_octree_figures(n)

Benchmarking

scripts.benchmark.perform_time_test(n, bh_ratio=None, repeats=3)

Times a singular calculation for the state derivative of a random system of size \(n\).

Parameters:

  • n (int) – The system size.

  • bh_ratio (Optional[float]) – The Barnes-Hut Ratio, if Barnes-Hut approximation is to be used.

  • repeats (int) – The number of times to repeat the experiment for this configuration (default 3).

Returns:

The mean runtime for computing \(d\mathbf{X}/dt\) in milliseconds.

Return type:

float

scripts.benchmark.generate_comparison_figure(min_log_n, max_log_n)

Generates the timing comparison between Brute-Force and Barnes-Hut.

Parameters:

  • min_log_n (int) – The starting \(\log_2 N\) (default 1).

  • max_log_n (int) – The ending \(\log_2 N\) (default 5).

The relationship between the input size \(N\) and the output time \(t\) is defined as

\[t_{BF} = \mathcal{O}(N^2) = k_{BF} N^2\]

for brute-force and

\[t_{BH} = \mathcal{O}(N \log_2 N) = k_{BH} N \log_2 N\]

for the Barnes-Hut approximation. The proportionality constants, \(k_{BF}\) and \(k_{BH}\), represent the inherent, non-algorithmic system load from how I’ve written the program across the two systems, and as a result of performing object-based recursion for Barnes-Hut and utilizing Numba (and parallelization) for Brute-Force, we can be fairly confident that \(k_{BF} << k_{BH}\) (which makes this comparison somewhat difficult at low \(N\), as the proportionality coefficients will dominate there).

Given these relationships, the produced plot is made logarithmic, i.e.,

\[\log_2 t_{BF} = \log_2 k_{BF} + 2 \log_2 N\]

for brute-force and

\[\log_2 t_{BH} = \log_2 k_{BH} + \log_2 N + \log_2 \log_2 N\]

for the barnes-hut approximation. These functions are essentially linear, given \(y := \log_2 t, b := \log_2 k\), \(x := \log_2 N\), and the fact that \(\log_2 \log_2 N\) is essentially constant at high \(N\), thus we can perform linear regression to compute the proportionality constants as the \(y\)-intercept, and validate the functional forms of each.

In addition to this form, the benchmarker also produces a plot of \(k\) as a function of \(N\) for both Brute-Force and Barnes-Hut by normalizing the non-logarithmic runtime by the algorithmic growth function. For Brute-Force, this is

\[y := k_{BF} = \frac{t_{BF}}{N^2}\]

and for Barnes-Hut, this is

\[y := k_{BH} = \frac{t_{BH}}{N \log_2 N},\]

and this should produce either a flat/constant or an asymptotic curve as \(k\) should be roughly constant (and ideally, quite small). This acts as a verification measure, because if this curve shows that \(k\) is a function of \(N\) in a nonnegligible way, then the algorithm is likely contains a bug.