Mercurial > repos > alg_tools / file revision

/*!
Geometrical bisection trees and efficient representations of sums of functions.

[Bisection trees][BTImpl] subdivide at each branching node a [cubical][crate::sets::Cube] domain of
dimension $N$ into $P=2^N$ subcubes at a branching point. Objects implementing [`Support`] can be
[inserted][BTImpl::insert] into the leaves of the tree via a low storage requirement identifier.
The identifier is inserted into *every* leaf node of the tree intersected by the cube provided
by [`Support::support_hint`].

Bisection tree functions or [`BTFN`]s use bisection trees for efficient presentations of sums
$\sum_{k=1}^m f_k$ of mathematical functions $f_k$, where each $f_k$ typically has a small
support, i.e., set $\\{x \mid f(x) ≠ 0 \\}$, compared to the support of the entire sum.
To do so, the data type representing $f_k$ needs to implement [`Support`]. To evaluate the
value of the sum, each $f_k$ also needs to implement [`Mapping`][crate::mapping::Mapping].
Moreover, the sum needs to be represented by a [`SupportGenerator`] that associates to a
low-storage-requirement identifier (typically `usize`) an object of the type that represents
$f_k$. [`BTFN`]s support basic vector space operations, and [minimisation][BTFN::minimise] and
[maximisation][BTFN::maximise] via a [branch-and-bound strategy][BTSearch::search_and_refine].

The nodes of a bisection tree also store aggregate information about the objects stored in the
tree via an [`Aggregator`]. This way, rough upper and lower [bound][Bounds] estimates on
$\sum_{k=1}^m f_k$ can be efficiently maintained in the tree, based on corresponding estimates
on each $f_k$. This is done [locally][LocalAnalysis] for every node and corresponding subcube
of the domain of the tree.

## Type parameters

The various types and traits herein depend on several type parameters:

- `N` is the geometrical dimension and `F` the numerical type for coordinates.
- `P` is the branching factor and would generally equal $2^N$, but has to be explicitly specified
  due to current restrictions in Rust's const generics.
- `D` is the data/identifier stored in the  bisection tree, and `A` the [aggregate][Aggregator]
  information of all the data in a branch.

## Starting points

[`BTImpl::new`] creates a new bisection tree. [`BTImpl::insert`] can be used to insert new data
into it. [`BTImpl::iter_at`] iterates over the data at a point `x` of the domain of the tree.

A new [`BTFN`] can be constructed with [`BTFN::construct`] given an implementation of
a [`SupportGenerator`]. They can be summed and multipliced by a schalar using standard arithmetic
operations. The types of the objects in two summed `BTFN`s do not need to be the same.
To find an approximate minimum of a `BTFN` using a branch-and-bound strategy,
use [`BTFN::minimise`]. [`Bounded::bounds`] provides a shortcut to [`GlobalAnalysis`] with the
[`Bounds`] aggregator. If the rough bounds so obtained do not indicate that the `BTFN` is in some
given bounds, instead of doing a full minimisation and maximisation for higher quality bounds,
it is more efficient to use [`BTFN::has_upper_bound`] and [`BTFN::has_lower_bound`].
*/

mod supportid;
pub use supportid::*;
mod aggregator;
pub use aggregator::*;
mod either;
pub use either::*;
mod support;
pub use support::*;
mod bt;
pub use bt::*;
mod refine;
pub use refine::*;
mod btfn;
pub use btfn::*;