sigma  1.0.0
Loading...
Searching...
No Matches
taylor.hpp
Go to the documentation of this file.
1#pragma once
2#include <algorithm>
3#include <cmath>
4#include <optional>
8#include <sstream>
9#include <utility>
10#include <vector>
11
15
16namespace sigma {
17
45template<typename ValueType>
46class Taylor {
47public:
49 using size_type = std::size_t;
50
52 using value_t = ValueType;
53
56
59
61 using coeffs_t = std::map<monomial_t, value_t>;
62
65
77 struct Order {
81 explicit Order(size_type v) : value(v) {}
82 };
83
85 static constexpr Order default_max_order() { return Order(2); }
86
87 // --- Constructors and Assignment ----------------------------------------
88
97 Taylor() : m_order_(default_max_order().value) {}
98
109 Taylor(value_t center, Order order = default_max_order()) :
110 Taylor(interval_t(center, center), order) {}
111
127 Taylor(value_t lo, value_t hi, Order order = default_max_order()) :
128 Taylor(interval_t(lo, hi), order) {}
129
144 explicit Taylor(const interval_t& interval,
145 Order order = default_max_order()) :
146 m_order_(order.value) {
147 if(interval.empty()) { return; }
148 m_constant_ = interval.median();
149 if(interval.radius() > 0) {
150 monomial_t mono(make_deviation());
151 if(mono.degree() <= m_order_) {
152 m_coeffs_[mono] = interval.radius();
153 }
154 }
155 }
156
175 Order order = default_max_order()) :
176 m_constant_(constant), m_order_(order.value) {
177 for(auto&& [mono, coeff] : coeffs) {
178 if(mono.degree() <= m_order_) { m_coeffs_[mono] = coeff; }
179 }
180 }
181
183 Taylor(const Taylor& other) = default;
184
186 Taylor(Taylor&& other) noexcept = default;
187
189 Taylor& operator=(const Taylor& other) = default;
190
192 Taylor& operator=(Taylor&& other) noexcept = default;
193
194 // -- State Accessors -----------------------------------------------------
195
205 interval_t range() const { return bound(); }
206
213 size_type max_order() const noexcept { return m_order_; }
214
224 assert_not_empty_();
225 return *m_constant_;
226 }
227
235 const coeffs_t& coefficients() const noexcept { return m_coeffs_; }
236
247 size_type n_terms() const noexcept {
248 return m_coeffs_.size() + (empty() ? 0 : 1);
249 }
250
257 bool empty() const noexcept { return !m_constant_; }
258
267 bool contains(value_t value) const {
268 if(empty()) { return false; }
269 return range().contains(value);
270 }
271
280 bool contains(const interval_t& interval) const {
281 if(interval.empty()) { return true; }
282 if(empty()) { return false; }
283 return range().contains(interval);
284 }
285
297 bool contains(const Taylor& other) const { return contains(other.range()); }
298
318
338
351 Taylor truncate(size_type new_order) const;
352
365 std::string print_polynomial_form() const;
366
378 std::string print_interval_form() const {
379 return range().print_interval_form();
380 }
381
382 // -- Arithmetic Operators ------------------------------------------------
383
392
406 if(empty()) { return *this = Taylor(value, Order(m_order_)); }
407 (*m_constant_) += value;
408 return *this;
409 }
410
427 Taylor& operator+=(const Taylor& other);
428
440 Taylor operator+(value_t value) const { return Taylor(*this) += value; }
441
453 Taylor operator+(const Taylor& other) const {
454 return Taylor(*this) += other;
455 }
456
466 if(empty()) { return *this = Taylor(-value, Order(m_order_)); }
467 (*m_constant_) -= value;
468 return *this;
469 }
470
483 Taylor& operator-=(const Taylor& other) { return *this += -other; }
484
496 Taylor operator-(value_t value) const { return Taylor(*this) -= value; }
497
509 Taylor operator-(const Taylor& other) const {
510 return Taylor(*this) -= other;
511 }
512
522 if(empty()) { return *this; }
523 (*m_constant_) *= value;
524 for(auto&& [mono, coeff] : m_coeffs_) { coeff *= value; }
525 return *this;
526 }
527
545 Taylor& operator*=(const Taylor& other);
546
558 Taylor operator*(value_t value) const { return Taylor(*this) *= value; }
559
571 Taylor operator*(const Taylor& other) const {
572 return Taylor(*this) *= other;
573 }
574
584 if(value == 0) { throw std::domain_error("Division by zero"); }
585 return *this *= value_t(1.0 / value);
586 }
587
605 Taylor& operator/=(const Taylor& other) {
606 return *this *= other.multiplicative_inverse();
607 }
608
619 Taylor operator/(value_t value) const { return Taylor(*this) /= value; }
620
635 Taylor operator/(const Taylor& other) const {
636 return Taylor(*this) /= other;
637 }
638
667 Taylor compose_(const std::vector<value_t>& outer_coeffs) const;
668
683
684 // -- Comparison Operators ------------------------------------------------
685
699 bool operator==(const Taylor& other) const {
700 if(empty() != other.empty()) { return false; }
701 if(empty()) { return true; }
702 if(m_order_ != other.m_order_) { return false; }
703 if(m_constant_ != other.m_constant_) { return false; }
704 return m_coeffs_ == other.m_coeffs_;
705 }
706
716 bool operator!=(const Taylor& other) const { return !(*this == other); }
717
722
723private:
725 void assert_not_empty_() const {
726 if(empty()) { throw std::domain_error("Taylor polynomial is empty"); }
727 }
728
733 static interval_t diagonal_extrema_(value_t lin, value_t quad) {
734 if(quad == value_t{0}) {
735 auto mag = std::fabs(lin);
736 return interval_t(-mag, mag);
737 }
738 value_t f_lo = quad - lin; // f(-1)
739 value_t f_hi = quad + lin; // f(1)
740 value_t vertex = -lin / (value_t{2} * quad);
741 value_t f_vertex = -(lin * lin) / (value_t{4} * quad);
742 bool vertex_in_domain = vertex >= value_t{-1} && vertex <= value_t{1};
743
744 if(quad > value_t{0}) { // convex: vertex is the minimum
745 auto lo = vertex_in_domain ? f_vertex : std::min(f_lo, f_hi);
746 return interval_t(lo, std::max(f_lo, f_hi));
747 }
748 // concave: vertex is the maximum
749 auto hi = vertex_in_domain ? f_vertex : std::max(f_lo, f_hi);
750 return interval_t(std::min(f_lo, f_hi), hi);
751 }
752
755 std::optional<value_t> m_constant_;
756
759 coeffs_t m_coeffs_;
760
762 size_type m_order_;
763};
764
765// -- Non-member functions -------------------------------------------------
766
786template<typename ValueType>
787std::ostream& operator<<(std::ostream& os, const Taylor<ValueType>& t) {
788 if(t.empty()) {
789 os << "∅";
790 return os;
791 }
792 os << t.range();
793 return os;
794}
795
811template<typename ValueType>
813 return t * value;
814}
815
816// -- Out-of-line definitions ------------------------------------------------
817
818template<typename ValueType>
820 assert_not_empty_();
821 interval_t domain(value_t{-1}, value_t{1});
822
823 // Each variable's linear and pure-quadratic coefficients (c_{e_i} and
824 // c_{2e_i}), collected so their sum can be bounded exactly below.
825 std::map<deviation_t, std::pair<value_t, value_t>> diagonal;
826
827 // Naive per-term bound of everything QFB doesn't capture exactly: cross
828 // terms (more than one variable) and degree->= 3 single-variable terms.
829 interval_t remainder(value_t{0}, value_t{0});
830
831 for(auto&& [mono, coeff] : m_coeffs_) {
832 auto&& exps = mono.exponents();
833 if(exps.size() == 1) {
834 auto [var, exp] = *exps.begin();
835 if(exp == 1) {
836 diagonal[var].first += coeff;
837 continue;
838 }
839 if(exp == 2) {
840 diagonal[var].second += coeff;
841 continue;
842 }
843 }
844 interval_t term(value_t{1}, value_t{1});
845 for(auto&& [var, exp] : exps) { term *= pow(domain, exp); }
846 term *= coeff;
847 remainder += term;
848 }
849
850 interval_t total(constant(), constant());
851 total += remainder;
852 for(auto&& [var, coeffs] : diagonal) {
853 auto [lin, quad] = coeffs;
854 total += diagonal_extrema_(lin, quad);
855 }
856 return total;
857}
858
859template<typename ValueType>
861 assert_not_empty_();
862 value_t new_constant{0};
863 coeffs_t new_coeffs;
864 for(auto&& [mono, coeff] : m_coeffs_) {
865 auto e = mono.exponent(var);
866 if(e == 0) { continue; }
867 auto exps = mono.exponents();
868 exps[var] = e - 1;
869 value_t new_coeff = coeff * static_cast<value_t>(e);
870 monomial_t new_mono(exps);
871 if(new_mono.empty()) {
872 new_constant += new_coeff;
873 } else {
874 new_coeffs[new_mono] += new_coeff;
875 }
876 }
877 return Taylor(new_constant, std::move(new_coeffs), Order(m_order_));
878}
879
880template<typename ValueType>
882 assert_not_empty_();
883 coeffs_t new_coeffs;
884 for(auto&& [mono, coeff] : m_coeffs_) {
885 if(mono.degree() <= new_order) { new_coeffs[mono] = coeff; }
886 }
887 return Taylor(*m_constant_, std::move(new_coeffs), Order(new_order));
888}
889
890template<typename ValueType>
892 if(empty()) { return "∅"; }
893 std::stringstream ss;
894 ss << constant();
895 for(auto&& [mono, coeff] : m_coeffs_) {
896 ss << " + " << coeff << "*" << mono;
897 }
898 return ss.str();
899}
900
901template<typename ValueType>
903 if(empty()) { return *this; }
904 coeffs_t new_coeffs;
905 for(auto&& [mono, coeff] : m_coeffs_) { new_coeffs[mono] = -coeff; }
906 return Taylor(-constant(), std::move(new_coeffs), Order(m_order_));
907}
908
909template<typename ValueType>
911 if(empty()) { return *this = other; }
912 if(other.empty()) { return *this; }
913 auto new_order = std::min(m_order_, other.m_order_);
914 auto lhs = truncate(new_order);
915 auto rhs = other.truncate(new_order);
916 value_t new_constant = *lhs.m_constant_ + *rhs.m_constant_;
917 coeffs_t new_coeffs = lhs.m_coeffs_;
918 for(auto&& [mono, coeff] : rhs.m_coeffs_) { new_coeffs[mono] += coeff; }
919 return *this =
920 Taylor(new_constant, std::move(new_coeffs), Order(new_order));
921}
922
923template<typename ValueType>
925 if(empty() || other.empty()) { return *this = Taylor(); }
926 auto new_order = std::min(m_order_, other.m_order_);
927 auto lhs = truncate(new_order);
928 auto rhs = other.truncate(new_order);
929 value_t new_constant = (*lhs.m_constant_) * (*rhs.m_constant_);
930 coeffs_t new_coeffs;
931 for(auto&& [mono, coeff] : rhs.m_coeffs_) {
932 new_coeffs[mono] += (*lhs.m_constant_) * coeff;
933 }
934 for(auto&& [mono, coeff] : lhs.m_coeffs_) {
935 new_coeffs[mono] += coeff * (*rhs.m_constant_);
936 }
937 for(auto&& [mono1, c1] : lhs.m_coeffs_) {
938 for(auto&& [mono2, c2] : rhs.m_coeffs_) {
939 auto mono = mono1 * mono2;
940 if(mono.degree() > new_order) { continue; }
941 new_coeffs[mono] += c1 * c2;
942 }
943 }
944 return *this =
945 Taylor(new_constant, std::move(new_coeffs), Order(new_order));
946}
947
948template<typename ValueType>
949auto Taylor<ValueType>::compose_(const std::vector<value_t>& outer_coeffs) const
950 -> Taylor {
951 assert_not_empty_();
952 Taylor bar(value_t{0}, m_coeffs_, Order(m_order_));
953 value_t c0 = outer_coeffs.empty() ? value_t{0} : outer_coeffs[0];
954 Taylor result = Taylor(c0, Order(m_order_));
955 Taylor power = bar;
956 for(size_type k = 1; k < outer_coeffs.size(); ++k) {
957 result += power * outer_coeffs[k];
958 if(k + 1 < outer_coeffs.size()) { power *= bar; }
959 }
960 return result;
961}
962
963template<typename ValueType>
965 assert_not_empty_();
966 if(constant() == value_t{0}) {
967 throw std::domain_error("Division by zero");
968 }
970}
971
974
977
978} // namespace sigma
979
Models a closed numeric interval.
Definition interval.hpp:29
value_t median() const
Returns the midpoint of the interval.
Definition interval.hpp:84
value_t radius() const
Returns the half-width of the interval.
Definition interval.hpp:98
bool empty() const
Is *this the empty interval?
Definition interval.hpp:108
Represents a sparse multi-index exponent.
Definition monomial.hpp:33
static variable_t make_variable()
Definition monomial.hpp:295
size_type variable_t
Opaque type used to identify an expansion variable.
Definition monomial.hpp:39
Implements truncated multivariate polynomial algebra.
Definition taylor.hpp:46
interval_t range() const
Returns an interval enclosing the values of *this.
Definition taylor.hpp:205
Taylor(const interval_t &interval, Order order=default_max_order())
Constructs a Taylor polynomial from an interval.
Definition taylor.hpp:144
Taylor(const Taylor &other)=default
Makes a deep copy of other.
Taylor operator*(const Taylor &other) const
Returns the product of *this and other.
Definition taylor.hpp:571
Monomial monomial_t
Definition taylor.hpp:58
Taylor & operator/=(value_t value)
Overwrites *this with the quotient of *this and value.
Definition taylor.hpp:583
std::string print_polynomial_form() const
Creates a string of the polynomial form of *this.
Definition taylor.hpp:891
Taylor & operator+=(const Taylor &other)
Overwrites *this with the sum of *this and other.
Definition taylor.hpp:910
Taylor operator+(value_t value) const
Returns the sum of *this and value.
Definition taylor.hpp:440
static deviation_t make_deviation()
Definition taylor.hpp:721
std::size_t size_type
Definition taylor.hpp:49
Taylor & operator=(Taylor &&other) noexcept=default
Moves the value of other to this polynomial.
bool empty() const noexcept
Definition taylor.hpp:257
Taylor(value_t constant, coeffs_t coeffs, Order order=default_max_order())
Constructs a Taylor polynomial from a full set of state.
Definition taylor.hpp:174
Taylor & operator+=(value_t value)
Overwrites *this with the sum of *this and value.
Definition taylor.hpp:405
bool contains(value_t value) const
Checks if *this contains value.
Definition taylor.hpp:267
bool operator!=(const Taylor &other) const
Checks if *this and other represent different polynomials.
Definition taylor.hpp:716
bool contains(const Taylor &other) const
Checks if *this contains other.
Definition taylor.hpp:297
Taylor(value_t lo, value_t hi, Order order=default_max_order())
Constructs a Taylor polynomial from a lower and upper bound.
Definition taylor.hpp:127
bool contains(const interval_t &interval) const
Checks if *this contains interval.
Definition taylor.hpp:280
Taylor operator-() const
Returns the additive inverse of *this.
Definition taylor.hpp:902
Interval< value_t > interval_t
Definition taylor.hpp:64
std::map< monomial_t, value_t > coeffs_t
Definition taylor.hpp:61
Taylor & operator/=(const Taylor &other)
Overwrites *this with the quotient of *this and other.
Definition taylor.hpp:605
bool operator==(const Taylor &other) const
Checks if *this and other represent the same polynomial.
Definition taylor.hpp:699
Taylor operator/(value_t value) const
Returns the quotient of *this and value.
Definition taylor.hpp:619
Taylor & operator-=(value_t value)
Overwrites *this with the difference of *this and value.
Definition taylor.hpp:465
Taylor & operator*=(value_t value)
Overwrites *this with the product of *this and value.
Definition taylor.hpp:521
Taylor operator+(const Taylor &other) const
Returns the sum of *this and other.
Definition taylor.hpp:453
Taylor multiplicative_inverse() const
Returns the multiplicative inverse of *this.
Definition taylor.hpp:964
Taylor operator*(value_t value) const
Returns the product of *this and value.
Definition taylor.hpp:558
Taylor operator/(const Taylor &other) const
Returns the quotient of *this and other.
Definition taylor.hpp:635
Taylor compose_(const std::vector< value_t > &outer_coeffs) const
Evaluates a truncated outer Taylor series about the constant term of *this.
Definition taylor.hpp:949
Taylor & operator*=(const Taylor &other)
Overwrites *this with the product of *this and other.
Definition taylor.hpp:924
Taylor truncate(size_type new_order) const
Returns *this with every term above new_order dropped.
Definition taylor.hpp:881
Taylor()
Constructs an empty Taylor polynomial.
Definition taylor.hpp:97
Taylor derivative(deviation_t var) const
Returns the partial derivative of *this with respect to var.
Definition taylor.hpp:860
std::string print_interval_form() const
Creates a string of the interval form of *this.
Definition taylor.hpp:378
Taylor & operator-=(const Taylor &other)
Overwrites *this with the difference of *this and other.
Definition taylor.hpp:483
size_type n_terms() const noexcept
Returns the number of terms in the polynomial.
Definition taylor.hpp:247
static constexpr Order default_max_order()
The truncation order used when none is specified.
Definition taylor.hpp:85
value_t constant() const
Definition taylor.hpp:223
Taylor(value_t center, Order order=default_max_order())
Constructs a Taylor polynomial from a constant value.
Definition taylor.hpp:109
Taylor & operator=(const Taylor &other)=default
Assigns the value of other to this polynomial.
std::ostream & operator<<(std::ostream &os, const Taylor< ValueType > &t)
Outputs the range of a Taylor polynomial to an output stream.
Definition taylor.hpp:787
Taylor operator-(value_t value) const
Returns the difference of *this and value.
Definition taylor.hpp:496
Taylor(Taylor &&other) noexcept=default
Constructs a Taylor polynomial by moving other.
Monomial::variable_t deviation_t
Definition taylor.hpp:55
const coeffs_t & coefficients() const noexcept
Returns the non-constant coefficients of *this.
Definition taylor.hpp:235
float value_t
Definition taylor.hpp:52
interval_t bound() const
size_type max_order() const noexcept
Returns the truncation order of *this.
Definition taylor.hpp:213
Taylor< ValueType > operator*(ValueType value, const Taylor< ValueType > &t)
Multiplies a scalar by a Taylor polynomial.
Definition taylor.hpp:812
Taylor operator-(const Taylor &other) const
Returns the difference of *this and other.
Definition taylor.hpp:509
Defines the Interval class.
Defines the Monomial class.
The primary namespace for the sigma library.
Definition affine.hpp:12
Affine< T > exp(const Affine< T > &a)
Calculate the exponential of an affine form.
Definition exponents.ipp:31
Affine< T > pow(const Affine< T > &a, const U &exp)
Calculate the power of an affine form.
Definition exponents.ipp:72
Taylor< float > TFloat
Typedef for a Taylor polynomial of floats.
Definition taylor.hpp:973
Taylor< double > TDouble
Typedef for a Taylor polynomial of doubles.
Definition taylor.hpp:976
Shared helpers for building the outer Taylor series of the elementary functions (exp,...
std::vector< T > reciprocal_outer_coeffs(T c, std::size_t order)
Outer-series coefficients of 1/x about c: (-1)^k / c^(k+1).
Definition series_detail.hpp:86
Tag type used to pass the truncation order to constructors.
Definition taylor.hpp:77
size_type value
The truncation order.
Definition taylor.hpp:79
Order(size_type v)
Constructs an Order with the given value.
Definition taylor.hpp:81
Components for compatibility with Eigen.
Convenience header for Taylor polynomial operations.