|
sigma
1.0.0
|
Implements truncated multivariate polynomial algebra. More...
#include <taylor.hpp>
Classes | |
| struct | Order |
| Tag type used to pass the truncation order to constructors. More... | |
Public Types | |
| using | size_type = std::size_t |
| Type used for indexing, offsets, and truncation order. | |
| using | value_t = ValueType |
| Type used for storing floating point values. | |
| using | deviation_t = Monomial::variable_t |
| Opaque type used to identify an expansion variable. | |
| using | monomial_t = Monomial |
| Sparse exponent multi-index type. | |
| using | coeffs_t = std::map<monomial_t, value_t> |
| Type used to map monomials to their coefficients. | |
| using | interval_t = Interval<value_t> |
| Type of an interval. | |
Public Member Functions | |
| Taylor () | |
| Constructs an empty Taylor polynomial. | |
| Taylor (value_t center, Order order=default_max_order()) | |
| Constructs a Taylor polynomial from a constant value. | |
| Taylor (value_t lo, value_t hi, Order order=default_max_order()) | |
| Constructs a Taylor polynomial from a lower and upper bound. | |
| Taylor (const interval_t &interval, Order order=default_max_order()) | |
| Constructs a Taylor polynomial from an interval. | |
| Taylor (value_t constant, coeffs_t coeffs, Order order=default_max_order()) | |
| Constructs a Taylor polynomial from a full set of state. | |
| Taylor (const Taylor &other)=default | |
Makes a deep copy of other. | |
| Taylor (Taylor &&other) noexcept=default | |
Constructs a Taylor polynomial by moving other. | |
| Taylor & | operator= (const Taylor &other)=default |
Assigns the value of other to this polynomial. | |
| Taylor & | operator= (Taylor &&other) noexcept=default |
Moves the value of other to this polynomial. | |
| interval_t | range () const |
| Returns an interval enclosing the values of *this. | |
| size_type | max_order () const noexcept |
| Returns the truncation order of *this. | |
| value_t | constant () const |
| Returns the constant term of *this. | |
| const coeffs_t & | coefficients () const noexcept |
| Returns the non-constant coefficients of *this. | |
| size_type | n_terms () const noexcept |
| Returns the number of terms in the polynomial. | |
| bool | empty () const noexcept |
| Checks if this Taylor polynomial represents the empty set. | |
| bool | contains (value_t value) const |
Checks if *this contains value. | |
| bool | contains (const interval_t &interval) const |
Checks if *this contains interval. | |
| bool | contains (const Taylor &other) const |
Checks if *this contains other. | |
| interval_t | bound () const |
| Returns an interval enclosing the values of the polynomial. | |
| Taylor | derivative (deviation_t var) const |
Returns the partial derivative of *this with respect to var. | |
| Taylor | truncate (size_type new_order) const |
Returns *this with every term above new_order dropped. | |
| std::string | print_polynomial_form () const |
| Creates a string of the polynomial form of *this. | |
| std::string | print_interval_form () const |
| Creates a string of the interval form of *this. | |
| Taylor | operator- () const |
| Returns the additive inverse of *this. | |
| Taylor & | operator+= (value_t value) |
Overwrites *this with the sum of *this and value. | |
| Taylor & | operator+= (const Taylor &other) |
Overwrites *this with the sum of *this and other. | |
| Taylor | operator+ (value_t value) const |
Returns the sum of *this and value. | |
| Taylor | operator+ (const Taylor &other) const |
Returns the sum of *this and other. | |
| Taylor & | operator-= (value_t value) |
Overwrites *this with the difference of *this and value. | |
| Taylor & | operator-= (const Taylor &other) |
Overwrites *this with the difference of *this and other. | |
| Taylor | operator- (value_t value) const |
Returns the difference of *this and value. | |
| Taylor | operator- (const Taylor &other) const |
Returns the difference of *this and other. | |
| Taylor & | operator*= (value_t value) |
Overwrites *this with the product of *this and value. | |
| Taylor & | operator*= (const Taylor &other) |
Overwrites *this with the product of *this and other. | |
| Taylor | operator* (value_t value) const |
Returns the product of *this and value. | |
| Taylor | operator* (const Taylor &other) const |
Returns the product of *this and other. | |
| Taylor & | operator/= (value_t value) |
Overwrites *this with the quotient of *this and value. | |
| Taylor & | operator/= (const Taylor &other) |
Overwrites *this with the quotient of *this and other. | |
| Taylor | operator/ (value_t value) const |
Returns the quotient of *this and value. | |
| Taylor | operator/ (const Taylor &other) const |
Returns the quotient of *this and other. | |
| Taylor | compose_ (const std::vector< value_t > &outer_coeffs) const |
| Evaluates a truncated outer Taylor series about the constant term of *this. | |
| Taylor | multiplicative_inverse () const |
| Returns the multiplicative inverse of *this. | |
| bool | operator== (const Taylor &other) const |
Checks if *this and other represent the same polynomial. | |
| bool | operator!= (const Taylor &other) const |
Checks if *this and other represent different polynomials. | |
Static Public Member Functions | |
| static constexpr Order | default_max_order () |
| The truncation order used when none is specified. | |
| static deviation_t | make_deviation () |
Related Symbols | |
(Note that these are not member symbols.) | |
| template<typename ValueType> | |
| std::ostream & | operator<< (std::ostream &os, const Taylor< ValueType > &t) |
| Outputs the range of a Taylor polynomial to an output stream. | |
| template<typename ValueType> | |
| Taylor< ValueType > | operator* (ValueType value, const Taylor< ValueType > &t) |
| Multiplies a scalar by a Taylor polynomial. | |
Implements truncated multivariate polynomial algebra.
| ValueType | The numeric type of the constant term and coefficients. |
Follows the design described in docs/taylor.md, which this class implements Eq. \(\eqref{eq:tm-poly}\) of:
\[ P(\delta) = \sum_{\left|\beta\right| \leq n} c_{\beta}\, \delta^{\beta} \qquad \delta \in [-1, 1]^v \]
where each expansion variable \(\delta_i\) is normalized to \([-1, 1]\), exactly as Affine's error symbols are.
Taylor is a truncated polynomial and nothing else: it makes no claim to enclose any particular function, and arithmetic that would produce terms above the truncation order simply discards them (there is no remainder to put them in). TaylorModel, which will pair a Taylor with a remainder interval_t to restore that guarantee, is not yet implemented; nor are the elementary functions (exp, log, sqrt, ...), the Eigen compatibility layer, or the multiplicative inverse/division they require. Those arrive together in a later pass.
N.b. like Affine, an empty Taylor (default-constructed, or explicitly constructed from an empty interval) represents the empty set, not the constant 0. This is a different notion of "empty" than Monomial's, which denotes its multiplicative identity.
|
inline |
Constructs an empty Taylor polynomial.
An empty Taylor represents the empty set, exactly as an empty Affine does. Its order is set to default_max_order(), though this is moot until the object becomes non-empty.
| none | No throw guarantee |
|
inline |
Constructs a Taylor polynomial from a constant value.
The resulting polynomial has no non-constant coefficients and represents the single value given by center.
| [in] | center | The constant term of the polynomial. |
| [in] | order | The truncation order, defaults to default_max_order(). |
| none | No throw guarantee |
|
inline |
Constructs a Taylor polynomial from a lower and upper bound.
The resulting polynomial has a single non-constant coefficient (on a freshly minted expansion variable) and, evaluated over its domain, spans the interval defined by the lower and upper bounds. If order is 0, that coefficient cannot be represented and is discarded, so the polynomial collapses to its median.
| [in] | lo | The lower bound. |
| [in] | hi | The upper bound. |
| [in] | order | The truncation order, defaults to default_max_order(). |
| std::bad_alloc | If memory allocation for the coefficient fails. Strong throw guarantee. |
|
inlineexplicit |
Constructs a Taylor polynomial from an interval.
For a non-empty interval, the resulting polynomial has a single non-constant coefficient on a freshly minted expansion variable (dropped if order is 0). If interval is empty, the resulting polynomial is also empty.
| [in] | interval | The interval represented by the polynomial. |
| [in] | order | The truncation order, defaults to default_max_order(). |
| std::bad_alloc | If memory allocation for the coefficient fails. Strong throw guarantee. |
|
inline |
Constructs a Taylor polynomial from a full set of state.
This constructor allows for the creation of a polynomial by specifying the full state (the constant term, the non-constant coefficients, and the truncation order). Any entry of coeffs whose monomial has degree above order is dropped, so the invariant that no stored term exceeds the truncation order holds regardless of what is passed in. This ctor is meant primarily for use by other parts of Sigma, but can be used by users as well.
| [in] | constant | The constant term of the polynomial. |
| [in] | coeffs | The non-constant coefficients of the polynomial. |
| [in] | order | The truncation order, defaults to default_max_order(). |
| none | No throw guarantee |
| auto sigma::Taylor< ValueType >::bound | ( | ) | const |
Returns an interval enclosing the values of the polynomial.
Computes \(B(P)\) of Eq. \(\eqref{eq:tm-bound}\) using Berz and Makino's quadratic fast bounder (QFB), per docs/taylor.md's "Dominated and fast bounders" section. For each expansion variable \(\delta_i\), its diagonal contribution \(c_{e_i}\delta_i + c_{2e_i}\delta_i^2\) (the linear and pure-quadratic terms in \(\delta_i\) alone) is bounded exactly, in closed form, by completing the square – no dependency-problem overestimation, since each \(\delta_i\) is independent of every other. Everything else (cross terms and degree- \(\geq 3\) terms) is bounded by the naive per-term baseline instead. The two are summed with the constant term to produce the final enclosure.
| std::domain_error | If *this is empty. Strong throw guarantee. |
|
inlinenoexcept |
Returns the non-constant coefficients of *this.
| none | No throw guarantee |
| auto sigma::Taylor< ValueType >::compose_ | ( | const std::vector< value_t > & | outer_coeffs | ) | const |
Evaluates a truncated outer Taylor series about the constant term of *this.
This is the hook every elementary function (sqrt, exp, log, pow, multiplicative_inverse, ...) is built from – the direct generalization of Affine::apply_affine_transform to arbitrary order. Given the Taylor coefficients of an outer function \(g\) about \(c_f\) = constant(), i.e. outer_coeffs[k] = \(\frac{1}{k!}\frac{d^k g}{df^k}(c_f)\), this computes
\[ \sum_{k=0}^{n} \texttt{outer\_coeffs}[k]\, \bar{P}^{\,k} \]
where \(\bar{P}\) = *this - constant() and \(n\) = max_order(), using ordinary Taylor polynomial addition and multiplication (which truncate at \(n\)). Because \(\bar{P}\) has no constant term, \(\bar{P}^{k}\) has no terms below degree \(k\), so entries of outer_coeffs beyond index \(n\) would only ever multiply terms that are truncated away; callers need not (but may) supply them.
| [in] | outer_coeffs | The Taylor coefficients of the outer function about constant(), starting from k=0. |
| std::domain_error | If *this is empty. Strong throw guarantee. |
| std::bad_alloc | If memory allocation for the new polynomial fails. Strong throw guarantee. |
|
inline |
Returns the constant term of *this.
This is \(c_f\): the coefficient of the \(\beta = 0\) monomial.
| std::domain_error | If *this is empty. Strong throw guarantee. |
|
inline |
Checks if *this contains interval.
| [in] | interval | The interval to check. |
interval, false otherwise.| none | No throw guarantee |
|
inline |
|
inline |
Checks if *this contains value.
| [in] | value | The value to check. |
value, false otherwise.| none | No throw guarantee |
| auto sigma::Taylor< ValueType >::derivative | ( | deviation_t | var | ) | const |
Returns the partial derivative of *this with respect to var.
Ordinary term-by-term polynomial differentiation: a term \(c\,\delta^{\beta}\) with \(\beta_{\texttt{var}} = e > 0\) differentiates to \(ce\,\delta^{\beta - e_{\texttt{var}}}\), where \(e_{\texttt{var}}\) is the multi-index with a 1 in the var slot and 0 elsewhere; terms not involving var vanish. Differentiation cannot raise degree, so it never has terms to drop. The truncation order of the result is the same as *this.
| [in] | var | The expansion variable to differentiate with respect to. |
var.| std::domain_error | If *this is empty. Strong throw guarantee. |
|
inlinenoexcept |
Checks if this Taylor polynomial represents the empty set.
| none | No throw guarantee |
|
inlinestatic |
Returns a process-wide unique integer ID for a new expansion variable. Delegates to Monomial::make_variable() so Taylor's variables and Monomial's share a single numbering.
|
inlinenoexcept |
Returns the truncation order of *this.
| none | No throw guarantee |
| auto sigma::Taylor< ValueType >::multiplicative_inverse | ( | ) | const |
Returns the multiplicative inverse of *this.
The multiplicative inverse is obtained by composing the Taylor series of \(1/x\) about constant() with *this, via compose_(). See compose_() for details on how the composition works.
| std::domain_error | If *this is empty or its constant term is 0. Strong throw guarantee. |
| std::bad_alloc | If memory allocation for the new polynomial fails. Strong throw guarantee. |
|
inlinenoexcept |
Returns the number of terms in the polynomial.
This counts the constant term (if *this is not empty) plus the number of non-constant coefficients, regardless of whether any of those coefficients happen to be 0.
| none | No throw guarantee |
|
inline |
Checks if *this and other represent different polynomials.
| [in] | other | The polynomial to compare with *this. |
other represent different polynomials, false otherwise.| none | No throw guarantee |
|
inline |
Returns the product of *this and other.
This is a convenience method for calling Taylor(*this) *= other.
| [in] | other | The polynomial to multiply *this by. |
other.| std::bad_alloc | If memory allocation for the new polynomial fails. Strong throw guarantee. |
|
inline |
Returns the product of *this and value.
This is a convenience method for calling Taylor(*this) *= value.
| [in] | value | The value to multiply *this by. |
value.| std::bad_alloc | If memory allocation for the new polynomial fails. Strong throw guarantee. |
| auto sigma::Taylor< ValueType >::operator*= | ( | const Taylor< ValueType > & | other | ) |
Overwrites *this with the product of *this and other.
Implements the polynomial part of Eq. \(\eqref{eq:tm-mul}\), \((P_1 P_2)_{\leq n}\): the exact product, truncated to the smaller of *this's and other's truncation orders. Unlike TaylorModel (not yet implemented), Taylor has no remainder to bound the discarded terms into, so they are simply dropped – consistent with Taylor making no claim to enclose anything. As with operator+=(Taylor), mixed orders resolve to the smaller of the two.
| [in] | other | The polynomial to multiply *this by. |
| std::bad_alloc | If memory allocation for the new polynomial fails. Strong throw guarantee. |
|
inline |
Overwrites *this with the product of *this and value.
| [in] | value | The value to multiply *this by. |
| none | No throw guarantee |
|
inline |
Returns the sum of *this and other.
This is a convenience method for calling Taylor(*this) += other.
| [in] | other | The polynomial to add to *this. |
other.| std::bad_alloc | If memory allocation for the new polynomial fails. Strong throw guarantee. |
|
inline |
Returns the sum of *this and value.
This is a convenience method for calling Taylor(*this) += value.
| [in] | value | The value to add to *this. |
value.| std::bad_alloc | If memory allocation for the new polynomial fails. Strong throw guarantee. |
| auto sigma::Taylor< ValueType >::operator+= | ( | const Taylor< ValueType > & | other | ) |
Overwrites *this with the sum of *this and other.
Implements Eq. \(\eqref{eq:tm-add}\)'s polynomial part: coefficients are summed monomial-wise. If *this and other have different truncation orders, the result's order is the smaller of the two, and terms of the higher-order operand above that order are dropped before adding (see docs/taylor.md's "Mixed orders resolve
downward").
| [in] | other | The polynomial to add to *this. |
| std::bad_alloc | If memory allocation for the new polynomial fails. Strong throw guarantee. |
|
inline |
Overwrites *this with the sum of *this and value.
If *this is empty, the resulting polynomial has a constant term of value and no coefficients. Otherwise this adds value to the constant term and leaves the coefficients unchanged.
| [in] | value | The value to add to *this. |
| none | No throw guarantee |
| auto sigma::Taylor< ValueType >::operator- | ( | ) | const |
Returns the additive inverse of *this.
| std::bad_alloc | If memory allocation for the new polynomial fails. Strong throw guarantee. |
|
inline |
Returns the difference of *this and other.
This is a convenience method for calling Taylor(*this) -= other.
| [in] | other | The polynomial to subtract from *this. |
other.| std::bad_alloc | If memory allocation for the new polynomial fails. Strong throw guarantee. |
|
inline |
Returns the difference of *this and value.
This is a convenience method for calling Taylor(*this) -= value.
| [in] | value | The value to subtract from *this. |
value.| std::bad_alloc | If memory allocation for the new polynomial fails. Strong throw guarantee. |
|
inline |
Overwrites *this with the difference of *this and other.
This is implemented as *this += -other. See the documentation for operator+=(Taylor) and operator-() for details.
| [in] | other | The polynomial to subtract from *this. |
| std::bad_alloc | If memory allocation for the new polynomial fails. Strong throw guarantee. |
|
inline |
Overwrites *this with the difference of *this and value.
| [in] | value | The value to subtract from *this. |
| none | No throw guarantee |
|
inline |
Returns the quotient of *this and other.
This is a convenience method for calling Taylor(*this) /= other.
| [in] | other | The polynomial to divide *this by. |
other.| std::domain_error | If other is empty or has a zero constant term. |
| std::bad_alloc | If memory allocation for the multiplicative inverse of other fails. Strong throw guarantee. |
|
inline |
Returns the quotient of *this and value.
This is a convenience method for calling Taylor(*this) /= value.
| [in] | value | The value to divide *this by. |
value.| std::domain_error | If value is zero. |
|
inline |
Overwrites *this with the quotient of *this and other.
This method is implemented as the product of this and other.multiplicative_inverse(). See the documentation for operator=(Taylor) and multiplicative_inverse() for more details on how these operations work.
| [in] | other | The polynomial to divide *this by. |
| std::domain_error | If other is empty or has a zero constant term. |
| std::bad_alloc | If memory allocation for the multiplicative inverse of other fails. Strong throw guarantee. |
|
inline |
Overwrites *this with the quotient of *this and value.
| [in] | value | The value to divide *this by. |
| std::domain_error | If value is zero. |
|
inline |
Checks if *this and other represent the same polynomial.
Two Taylor polynomials are equal if they are both empty, or if they have the same truncation order, the same constant term, and the same coefficients.
| [in] | other | The polynomial to compare with *this. |
other represent the same polynomial, false otherwise.| none | No throw guarantee |
|
inline |
Creates a string of the interval form of *this.
This is a convenience method for calling range().print_interval_form().
| std::domain_error | If *this is empty. Strong throw guarantee. |
| std::bad_alloc | If memory allocation for the string fails. Strong throw guarantee. |
| std::string sigma::Taylor< ValueType >::print_polynomial_form | ( | ) | const |
Creates a string of the polynomial form of *this.
The polynomial is written as the constant term plus each coefficient times its monomial (see Monomial::print()). If *this contains multiple coefficients, the order in which they are printed follows the ordering of coeffs_t.
| std::bad_alloc | If memory allocation for the string fails. Strong throw guarantee. |
|
inline |
| auto sigma::Taylor< ValueType >::truncate | ( | size_type | new_order | ) | const |
Returns *this with every term above new_order dropped.
If new_order is greater than or equal to max_order(), this simply relabels the truncation order; no coefficients are dropped, since none exceed it.
| [in] | new_order | The truncation order of the result. |
new_order.| std::domain_error | If *this is empty. Strong throw guarantee. |
|
Multiplies a scalar by a Taylor polynomial.
| ValueType | The type of the values in the polynomial. |
This is a convenience method for calling t * value.
| [in] | value | The scalar to multiply by. |
| [in] | t | The Taylor polynomial to multiply. |
| std::bad_alloc | If memory allocation for the new polynomial fails. Strong throw guarantee. |
|
Outputs the range of a Taylor polynomial to an output stream.
| ValueType | The type of the values in the polynomial. |
For a non-empty polynomial, this method defers to the output operator for interval_t to print the value of range(). An empty polynomial is printed as "∅", matching Interval's own operator<<, rather than throwing (range() throws for an empty polynomial). See Taylor::print_polynomial_form() for a string representation showing the individual terms instead.
| [in] | os | The output stream to write to. |
| [in] | t | The Taylor polynomial to output. |
| none | No throw guarantee |