Crate kifmm

Kernel Independent Fast Multipole Method (KiFMM)

A Kernel Independent Fast Multipole method designed for portability, and flexible algorithmic construction.

Notable features of this library are:

• Highly competitive single-node implementation of the kernel independent fast multipole method, with a Laplace/Helmholtz implementation provided.
• BLAS and FFT acceleration for the the field translations (M2L)
• The ability to handle multiple right hand sides when using BLAS based M2L
• Overdetermined check and equivalent surface construction when using BLAS based M2L
• The ability to vary expansion orders by level, useful for oscillatory problems
• Experimental distributed implementation

Example Usage

Fmm objects are built using the SingleNodeBuilder objects, for which we give a single node example below. These objects implement the Fmm trait, which allows for the evaluation of the algorithm and interaction with the results.

Basic usage for evaluating an FMM between a set of source and target points

use green_kernels::{laplace_3d::Laplace3dKernel, types::GreenKernelEvalType};
use kifmm::{Evaluate, DataAccess, BlasFieldTranslationSaRcmp, FftFieldTranslation, SingleNodeBuilder, ChargeHandler};
use kifmm::tree::helpers::points_fixture;
use rlst::{rlst_dynamic_array2, RawAccessMut, RawAccess};

// Setup random sources and targets
let n_sources = 1000;
let n_targets = 2000;
let sources = points_fixture::<f32>(n_sources, None, None, Some(0));
let targets = points_fixture::<f32>(n_targets, None, None, Some(1));

// FMM parameters
let n_crit = Some(150); // Threshold for number of particles in a leaf box
let depth = None; //
let expansion_order = [5]; // Expansion order of multipole/local expansions
let prune_empty = true; // Whether to exclude empty boxes in octrees

// FFT based Field Translation
{
    let nvecs = 1;
    let tmp = vec![1.0; n_sources * nvecs];
    let mut charges = rlst_dynamic_array2!(f32, [n_sources, nvecs]);
    charges.data_mut().copy_from_slice(&tmp);

    // Build FMM object, with a given kernel and field translation
    let mut fmm_fft = SingleNodeBuilder::new(false)
        .tree(sources.data(), targets.data(), n_crit, depth, prune_empty)
        .unwrap()
        .parameters(
            charges.data(),
            &expansion_order,
            Laplace3dKernel::new(), // Set the kernel
            GreenKernelEvalType::Value, // Set the type of evaluation, either just potentials or potentials + potential gradients
            FftFieldTranslation::new(None), // Choose a field translation method, could replace with BLAS field translation
        )
        .unwrap()
        .build()
        .unwrap();

    // Run the FMM
    fmm_fft.evaluate();

    // Optionally clear, to re-evaluate with new charges
    let nvecs = 1;
    let tmp = vec![1.0; n_sources * nvecs];
    let mut new_charges = rlst_dynamic_array2!(f32, [n_sources, nvecs]);
    new_charges.data_mut().copy_from_slice(&tmp);
    fmm_fft.clear();
    fmm_fft.attach_charges_unordered(charges.data());
}

More sophisticated examples, such as setting up FMMs to operate on multiple input charge vectors, or distributed computation, can be found in the examples folder.

Modules

bindings

C bindings for KIFMM-rs. Used as a basis for language bindings into Python, C and other C ABI compatible languages.

fftw

FFTW Bindings

fmm

A three dimensional kernel-independent fast multipole method library.

linalg

Selection of useful linear algebra routines

sorting

Parallel sorting algorithms

traits

Trait Definitions

tree

Single and Multi Node Octrees specialised for usage in the FMM

Macros

excall

Exclusive call of FFTW interface.

Structs

BlasFieldTranslationIa

Stores data and metadata for BLAS based acceleration scheme for field translation.

BlasFieldTranslationSaRcmp

Stores data and metadata for BLAS based acceleration scheme for field translation.

FftFieldTranslation

Stores data and metadata for FFT based acceleration scheme for field translation.

KiFmm

Holds all required data and metadata for evaluating a kernel independent FMM on a single node.

KiFmmMulti

Holds all required data and metadata for evaluating a kernel independent FMM on on multiple nodes.

MultiNodeBuilder

Builder for distributed FMM, example usage can be found in the examples directory.

MultiNodeFmmTree

Represents an octree structure for Fast Multipole Method (FMM) calculations on distributed nodes.

SingleNodeBuilder

A builder for constructing a Kernel-Independent Fast Multipole Method (KiFMM) object for simulations on a single node.

SingleNodeFmmTree

Represents an octree structure for Fast Multipole Method (FMM) calculations on a single node.

Enums

FmmSvdMode

Variants of SVD algorithms

Traits

ChargeHandler

Clear buffers and attach charges to a runtime FMM object

DataAccess

Data access for objects which implement the FMM

DataAccessMulti

Data access in a multi-node setting for objects which implement the FMM.

Evaluate

Defines evaluation of the FMM on a single node, which has implemented DataAccess

EvaluateMulti

Defines evaluation of the FMM in a multinode setting, which has implemented DataAccessMulti