comparison: src/bisection_tree.rs
src/bisection_tree.rs
- branch
- dev
- changeset 197
- 1f301affeae3
- parent 5
- 59dc4c5883f4
equal
deleted
inserted
replaced
| 196:3697375f4ee9 | 197:1f301affeae3 |
|---|---|
| 12 support, i.e., set $\\{x \mid f(x) ≠ 0 \\}$, compared to the support of the entire sum. | 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 | 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]. | 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 | 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 | 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 | 17 $f_k$. [`BTFN`]s support basic vector space operations, and |
| 18 [maximisation][BTFN::maximise] via a [branch-and-bound strategy][BTSearch::search_and_refine]. | 18 [minimisation][crate::bounds::MinMaxMapping::minimise] and |
| 19 [maximisation][crate::bounds::MinMaxMapping::maximise] | |
| 20 via a [branch-and-bound strategy][BTSearch::search_and_refine]. | |
| 19 | 21 |
| 20 The nodes of a bisection tree also store aggregate information about the objects stored in the | 22 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 | 23 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 | 24 $\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 | 25 on each $f_k$. This is done [locally][LocalAnalysis] for every node and corresponding subcube |
| 40 | 42 |
| 41 A new [`BTFN`] can be constructed with [`BTFN::construct`] given an implementation of | 43 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 | 44 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. | 45 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, | 46 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 | 47 use [`crate::bounds::MinMaxMapping::minimise`]. |
| 48 [`crate::bounds::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 | 49 [`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, | 50 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`]. | 51 it is more efficient to use [`crate::bounds::MinMaxMapping::has_upper_bound`] and |
| 52 [`crate::bounds::MinMaxMapping::has_lower_bound`]. | |
| 49 */ | 53 */ |
| 50 | 54 |
| 51 mod supportid; | 55 mod supportid; |
| 52 pub use supportid::*; | 56 pub use supportid::*; |
| 53 mod aggregator; | 57 mod aggregator; |
