# FMM Cost Model¶

This module helps predict the running time of each step of FMM

FMMTranslationCostModel describes the translation or evaluation cost of a single operation. For example, m2p describes the cost for translating a single multipole expansion to a single target.

AbstractFMMCostModel uses FMMTranslationCostModel and calibration parameter to compute the total cost of each step of FMM in each box. There is an AbstractFMMCostModel, implemented by FMMCostModel.

examples/cost_model.py demostrates how the calibration and evaluation are performed.

A similar module in pytential extends the functionality of his module to incorporate QBX-specific operations.

## Translation Cost of a Single Operation¶

class boxtree.cost.FMMTranslationCostModel(ncoeffs_fmm_by_level, uses_point_and_shoot)

Provides modeled costs for individual translations or evaluations.

Note

Current implementation assumes the calibration parameters are linear in the modeled cost. For example, var(“c_p2l”) * self.ncoeffs_fmm_by_level[level] is valid, but var(“c_p2l”) ** 2 * self.ncoeffs_fmm_by_level[level] is not.

boxtree.cost.make_pde_aware_translation_cost_model(dim, nlevels)

Create a cost model for FMM translation operators that make use of the knowledge that the potential satisfies a PDE.

For example, this factory is used for complex Taylor and Fourier-Bessel expansions in 2D, and spherical harmonics (with point-and-shoot) in 3D.

boxtree.cost.make_taylor_translation_cost_model(dim, nlevels)

Create a cost model for FMM translation based on Taylor expansions in Cartesian coordinates.

## Cost Model Classes¶

class boxtree.cost.AbstractFMMCostModel(translation_cost_model_factory=<function make_pde_aware_translation_cost_model>)

An interface to obtain both FMM operation counts and calibrated (e.g. in seconds) cost estimates.

cost_per_box(traversal, level_to_order, calibration_params, ndirect_sources_per_target_box=None, box_target_counts_nonchild=None)

Predict the per-box costs of a new traversal object.

Parameters
Returns

a numpy.ndarray or pyopencl.array.Array of shape (nboxes,), where the ith entry represents the cost of all stages for box i.

cost_per_stage(traversal, level_to_order, calibration_params, ndirect_sources_per_target_box=None, box_target_counts_nonchild=None)

Predict the per-stage costs of a new traversal object.

Parameters
Returns

a dict, mapping FMM stage names to cost numbers.

estimate_calibration_params(model_results, timing_results, time_field_name='wall_elapsed', additional_stage_to_param_names=())
Parameters
Returns

a dict of calibration parameters. If there is no model result for a particular stage, the estimated calibration parameter for that stage is NaN.

abstract aggregate_over_boxes(per_box_result)

Sum all entries of per_box_result into a number.

Parameters

per_box_result – an object of numpy.ndarray or pyopencl.array.Array, the result to be sumed.

Returns

a float, the result of the sum.

static get_unit_calibration_params()
Parameters

translation_cost_model_factory – a function, which takes tree dimension and the number of tree levels as arguments, returns an object of TranslationCostModel.

class boxtree.cost.FMMCostModel(queue, translation_cost_model_factory=<function make_pde_aware_translation_cost_model>)

An OpenCL-based realization of AbstractFMMCostModel.

Note

For methods in this class, argument traversal should live in device memory.

Parameters
• queue – a pyopencl.CommandQueue object on which the execution of this object runs.

• translation_cost_model_factory – a function, which takes tree dimension and the number of tree levels as arguments, returns an object of TranslationCostModel.