Debian Codegraph @

third-party/boost-math/include/boost/math/special_functions/daubechies_wavelet.hpp

raw
1 /*
2 * Copyright Nick Thompson, 2020
3 * Use, modification and distribution are subject to the
4 * Boost Software License, Version 1.0. (See accompanying file
5 * LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 */
7
8 #ifndef BOOST_MATH_SPECIAL_DAUBECHIES_WAVELET_HPP
9 #define BOOST_MATH_SPECIAL_DAUBECHIES_WAVELET_HPP
10 #include <vector>
11 #include <array>
12 #include <cmath>
13 #include <thread>
14 #include <future>
15 #include <iostream>
16 #include <boost/math/constants/constants.hpp>
17 #include <boost/math/special_functions/detail/daubechies_scaling_integer_grid.hpp>
18 #include <boost/math/special_functions/daubechies_scaling.hpp>
19 #include <boost/math/filters/daubechies.hpp>
20 #include <boost/math/interpolators/detail/cubic_hermite_detail.hpp>
21 #include <boost/math/interpolators/detail/quintic_hermite_detail.hpp>
22 #include <boost/math/interpolators/detail/septic_hermite_detail.hpp>
23
24 #include <boost/math/tools/is_standalone.hpp>
25 #ifndef BOOST_MATH_STANDALONE
26 #include <boost/config.hpp>
27 #ifdef BOOST_MATH_NO_CXX17_IF_CONSTEXPR
28 #error "The header <boost/math/norms.hpp> can only be used in C++17 and later."
29 #endif
30 #endif
31
32 namespace boost::math {
33
34 template<class Real, int p, int order>
35 std::vector<Real> daubechies_wavelet_dyadic_grid(int64_t j_max)
36 {
37 if (j_max == 0)
38 {
39 throw std::domain_error("The wavelet dyadic grid is refined from the scaling integer grid, so its minimum amount of data is half integer widths.");
40 }
41 auto phijk = daubechies_scaling_dyadic_grid<Real, p, order>(j_max - 1);
42 //psi_j[l] = psi(-p+1 + l/2^j) = \sum_{k=0}^{2p-1} (-1)^k c_k \phi(1-2p+k + l/2^{j-1})
43 //For derivatives just map c_k -> 2^order c_k.
44 auto d = boost::math::filters::daubechies_scaling_filter<Real, p>();
45 Real scale = boost::math::constants::root_two<Real>() * (1 << order);
46 for (size_t i = 0; i < d.size(); ++i)
47 {
48 d[i] *= scale;
49 if (!(i & 1))
50 {
51 d[i] = -d[i];
52 }
53 }
54
55 std::vector<Real> v(2 * p + (2 * p - 1) * ((int64_t(1) << j_max) - 1), std::numeric_limits<Real>::quiet_NaN());
56 v[0] = 0;
57 v[v.size() - 1] = 0;
58
59 for (int64_t l = 1; l < static_cast<int64_t>(v.size() - 1); ++l)
60 {
61 Real term = 0;
62 for (int64_t k = 0; k < static_cast<int64_t>(d.size()); ++k)
63 {
64 int64_t idx = (int64_t(1) << (j_max - 1)) * (1 - 2 * p + k) + l;
65 if (idx < 0 || idx >= static_cast<int64_t>(phijk.size()))
66 {
67 continue;
68 }
69 term += d[k] * phijk[idx];
70 }
71 v[l] = term;
72 }
73
74 return v;
75 }
76
77
78 template<class Real, int p>
79 class daubechies_wavelet {
80 //
81 // Some type manipulation so we know the type of the interpolator, and the vector type it requires:
82 //
83 using vector_type = std::vector < std::array < Real, p < 6 ? 2 : p < 10 ? 3 : 4>>;
84 //
85 // List our interpolators:
86 //
87 using interpolator_list = std::tuple<
88 detail::null_interpolator, detail::matched_holder_aos<vector_type>, detail::linear_interpolation_aos<vector_type>,
89 interpolators::detail::cardinal_cubic_hermite_detail_aos<vector_type>, interpolators::detail::cardinal_quintic_hermite_detail_aos<vector_type>,
90 interpolators::detail::cardinal_septic_hermite_detail_aos<vector_type> > ;
91 //
92 // Select the one we need:
93 //
94 using interpolator_type = std::tuple_element_t<
95 p == 1 ? 0 :
96 p == 2 ? 1 :
97 p == 3 ? 2 :
98 p <= 5 ? 3 :
99 p <= 9 ? 4 : 5, interpolator_list>;
100 public:
101 explicit daubechies_wavelet(int grid_refinements = -1)
102 {
103 static_assert(p < 20, "Daubechies wavelets are only implemented for p < 20.");
104 static_assert(p > 0, "Daubechies wavelets must have at least 1 vanishing moment.");
105 if (grid_refinements == 0)
106 {
107 throw std::domain_error("The wavelet requires at least 1 grid refinement.");
108 }
109 if constexpr (p == 1)
110 {
111 return;
112 }
113 else
114 {
115 if (grid_refinements < 0)
116 {
117 if constexpr (std::is_same_v<Real, float>)
118 {
119 if (grid_refinements == -2)
120 {
121 // Control absolute error:
122 // p= 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19
123 std::array<int, 20> r{ -1, -1, 18, 19, 16, 11, 8, 7, 7, 7, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3 };
124 grid_refinements = r[p];
125 }
126 else
127 {
128 // Control relative error:
129 // p= 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19
130 std::array<int, 20> r{ -1, -1, 21, 21, 21, 17, 16, 15, 14, 13, 12, 11, 11, 11, 11, 11, 11, 11, 11, 11 };
131 grid_refinements = r[p];
132 }
133 }
134 else if constexpr (std::is_same_v<Real, double>)
135 {
136 // p= 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19
137 std::array<int, 20> r{ -1, -1, 21, 21, 21, 21, 21, 21, 21, 21, 20, 20, 19, 18, 18, 18, 18, 18, 18, 18 };
138 grid_refinements = r[p];
139 }
140 else
141 {
142 grid_refinements = 21;
143 }
144 }
145
146 // Compute the refined grid:
147 // In fact for float precision I know the grid must be computed in double precision and then cast back down, or else parts of the support are systematically inaccurate.
148 std::future<std::vector<Real>> t0 = std::async(std::launch::async, [&grid_refinements]() {
149 // Computing in higher precision and downcasting is essential for 1ULP evaluation in float precision:
150 auto v = daubechies_wavelet_dyadic_grid<typename detail::daubechies_eval_type<Real>::type, p, 0>(grid_refinements);
151 return detail::daubechies_eval_type<Real>::vector_cast(v);
152 });
153 // Compute the derivative of the refined grid:
154 std::future<std::vector<Real>> t1 = std::async(std::launch::async, [&grid_refinements]() {
155 auto v = daubechies_wavelet_dyadic_grid<typename detail::daubechies_eval_type<Real>::type, p, 1>(grid_refinements);
156 return detail::daubechies_eval_type<Real>::vector_cast(v);
157 });
158
159 // if necessary, compute the second and third derivative:
160 std::vector<Real> d2ydx2;
161 std::vector<Real> d3ydx3;
162 if constexpr (p >= 6) {
163 std::future<std::vector<Real>> t3 = std::async(std::launch::async, [&grid_refinements]() {
164 auto v = daubechies_wavelet_dyadic_grid<typename detail::daubechies_eval_type<Real>::type, p, 2>(grid_refinements);
165 return detail::daubechies_eval_type<Real>::vector_cast(v);
166 });
167
168 if constexpr (p >= 10) {
169 std::future<std::vector<Real>> t4 = std::async(std::launch::async, [&grid_refinements]() {
170 auto v = daubechies_wavelet_dyadic_grid<typename detail::daubechies_eval_type<Real>::type, p, 3>(grid_refinements);
171 return detail::daubechies_eval_type<Real>::vector_cast(v);
172 });
173 d3ydx3 = t4.get();
174 }
175 d2ydx2 = t3.get();
176 }
177
178
179 auto y = t0.get();
180 auto dydx = t1.get();
181
182 if constexpr (p >= 2)
183 {
184 vector_type data(y.size());
185 for (size_t i = 0; i < y.size(); ++i)
186 {
187 data[i][0] = y[i];
188 data[i][1] = dydx[i];
189 if constexpr (p >= 6)
190 data[i][2] = d2ydx2[i];
191 if constexpr (p >= 10)
192 data[i][3] = d3ydx3[i];
193 }
194 if constexpr (p <= 3)
195 m_interpolator = std::make_shared<interpolator_type>(std::move(data), grid_refinements, Real(-p + 1));
196 else
197 m_interpolator = std::make_shared<interpolator_type>(std::move(data), Real(-p + 1), Real(1) / (1 << grid_refinements));
198 }
199 else
200 m_interpolator = std::make_shared<detail::null_interpolator>();
201 }
202 }
203
204
205 inline Real operator()(Real x) const
206 {
207 if (x <= -p + 1 || x >= p)
208 {
209 return 0;
210 }
211
212 if constexpr (p == 1)
213 {
214 if (x < Real(1) / Real(2))
215 {
216 return 1;
217 }
218 else if (x == Real(1) / Real(2))
219 {
220 return 0;
221 }
222 return -1;
223 }
224 else
225 {
226 return (*m_interpolator)(x);
227 }
228 }
229
230 inline Real prime(Real x) const
231 {
232 static_assert(p > 2, "The 3-vanishing moment Daubechies wavelet is the first which is continuously differentiable.");
233 if (x <= -p + 1 || x >= p)
234 {
235 return 0;
236 }
237 return m_interpolator->prime(x);
238 }
239
240 inline Real double_prime(Real x) const
241 {
242 static_assert(p >= 6, "Second derivatives of Daubechies wavelets require at least 6 vanishing moments.");
243 if (x <= -p + 1 || x >= p)
244 {
245 return Real(0);
246 }
247 return m_interpolator->double_prime(x);
248 }
249
250 std::pair<Real, Real> support() const
251 {
252 return std::make_pair(Real(-p + 1), Real(p));
253 }
254
255 int64_t bytes() const
256 {
257 return m_interpolator->bytes() + sizeof(*this);
258 }
259
260 private:
261 std::shared_ptr<interpolator_type> m_interpolator;
262 };
263
264 }
265
266 #endif // BOOST_MATH_SPECIAL_DAUBECHIES_WAVELET_HPP