Tue, 06 Dec 2022 08:58:49 +0200
README improvements
5 | 1 | /*! |
2 | Geometrical bisection trees and efficient representations of sums of functions. | |
3 | ||
4 | [Bisection trees][BTImpl] subdivide at each branching node a [cubical][crate::sets::Cube] domain of | |
5 | dimension $N$ into $P=2^N$ subcubes at a branching point. Objects implementing [`Support`] can be | |
6 | [inserted][BTImpl::insert] into the leaves of the tree via a low storage requirement identifier. | |
7 | The identifier is inserted into *every* leaf node of the tree intersected by the cube provided | |
8 | by [`Support::support_hint`]. | |
9 | ||
10 | Bisection tree functions or [`BTFN`]s use bisection trees for efficient presentations of sums | |
11 | $\sum_{k=1}^m f_k$ of mathematical functions $f_k$, where each $f_k$ typically has a small | |
12 | support, i.e., set $\\{x \mid f(x) ≠ 0 \\}$, compared to the support of the entire sum. | |
13 | To do so, the data type representing $f_k$ needs to implement [`Support`]. To evaluate the | |
14 | value of the sum, each $f_k$ also needs to implement [`Mapping`][crate::mapping::Mapping]. | |
15 | Moreover, the sum needs to be represented by a [`SupportGenerator`] that associates to a | |
16 | low-storage-requirement identifier (typically `usize`) an object of the type that represents | |
17 | $f_k$. [`BTFN`]s support basic vector space operations, and [minimisation][BTFN::minimise] and | |
18 | [maximisation][BTFN::maximise] via a [branch-and-bound strategy][BTSearch::search_and_refine]. | |
19 | ||
20 | The nodes of a bisection tree also store aggregate information about the objects stored in the | |
21 | tree via an [`Aggregator`]. This way, rough upper and lower [bound][Bounds] estimates on | |
22 | $\sum_{k=1}^m f_k$ can be efficiently maintained in the tree, based on corresponding estimates | |
23 | on each $f_k$. This is done [locally][LocalAnalysis] for every node and corresponding subcube | |
24 | of the domain of the tree. | |
25 | ||
26 | ## Type parameters | |
27 | ||
28 | The various types and traits herein depend on several type parameters: | |
29 | ||
30 | - `N` is the geometrical dimension and `F` the numerical type for coordinates. | |
31 | - `P` is the branching factor and would generally equal $2^N$, but has to be explicitly specified | |
32 | due to current restrictions in Rust's const generics. | |
33 | - `D` is the data/identifier stored in the bisection tree, and `A` the [aggregate][Aggregator] | |
34 | information of all the data in a branch. | |
35 | ||
36 | ## Starting points | |
37 | ||
38 | [`BTImpl::new`] creates a new bisection tree. [`BTImpl::insert`] can be used to insert new data | |
39 | into it. [`BTImpl::iter_at`] iterates over the data at a point `x` of the domain of the tree. | |
40 | ||
41 | A new [`BTFN`] can be constructed with [`BTFN::construct`] given an implementation of | |
42 | a [`SupportGenerator`]. They can be summed and multipliced by a schalar using standard arithmetic | |
43 | operations. The types of the objects in two summed `BTFN`s do not need to be the same. | |
44 | To find an approximate minimum of a `BTFN` using a branch-and-bound strategy, | |
45 | use [`BTFN::minimise`]. [`Bounded::bounds`] provides a shortcut to [`GlobalAnalysis`] with the | |
46 | [`Bounds`] aggregator. If the rough bounds so obtained do not indicate that the `BTFN` is in some | |
47 | given bounds, instead of doing a full minimisation and maximisation for higher quality bounds, | |
48 | it is more efficient to use [`BTFN::has_upper_bound`] and [`BTFN::has_lower_bound`]. | |
49 | */ | |
0 | 50 | |
51 | mod supportid; | |
52 | pub use supportid::*; | |
53 | mod aggregator; | |
54 | pub use aggregator::*; | |
55 | mod either; | |
56 | pub use either::*; | |
57 | mod support; | |
58 | pub use support::*; | |
59 | mod bt; | |
60 | pub use bt::*; | |
61 | mod refine; | |
62 | pub use refine::*; | |
63 | mod btfn; | |
64 | pub use btfn::*; |