xtensor
Loading...
Searching...
No Matches
xfft.hpp
1#ifdef XTENSOR_USE_TBB
2#include <oneapi/tbb.h>
3#endif
4#include <stdexcept>
5
6#include <xtl/xcomplex.hpp>
7
8#include "../containers/xarray.hpp"
9#include "../core/xmath.hpp"
10#include "../generators/xbuilder.hpp"
11#include "../misc/xcomplex.hpp"
12#include "../views/xaxis_slice_iterator.hpp"
13#include "../views/xview.hpp"
14#include "./xtl_concepts.hpp"
15
16namespace xt
17{
18 namespace fft
19 {
20 namespace detail
21 {
22 template <xtl::complex_concept E>
23 inline auto radix2(E&& e)
24 {
25 using namespace xt::placeholders;
26 using namespace std::complex_literals;
27 using value_type = typename std::decay_t<E>::value_type;
28 using precision = typename value_type::value_type;
29 auto N = e.size();
30 const bool powerOfTwo = !(N == 0) && !(N & (N - 1));
31 // check for power of 2
32 if (!powerOfTwo || N == 0)
33 {
34 // TODO: Replace implementation with dft
35 XTENSOR_THROW(std::runtime_error, "FFT Implementation requires power of 2");
36 }
37 auto pi = xt::numeric_constants<precision>::PI;
39 if (N <= 1)
40 {
41 return ev;
42 }
43 else
44 {
45#ifdef XTENSOR_USE_TBB
48 oneapi::tbb::parallel_invoke(
49 [&]
50 {
51 even = radix2(xt::view(ev, xt::range(0, _, 2)));
52 },
53 [&]
54 {
55 odd = radix2(xt::view(ev, xt::range(1, _, 2)));
56 }
57 );
58#else
59 auto even = radix2(xt::view(ev, xt::range(0, _, 2)));
60 auto odd = radix2(xt::view(ev, xt::range(1, _, 2)));
61#endif
62
63 // N is a power of 2, so it is exactly representable as a double.
64 const auto N_dbl = static_cast<double>(N);
65 auto range = xt::arange<double>(N_dbl / 2);
66 auto exp = xt::exp(static_cast<value_type>(-2i) * pi * range / N_dbl);
67 auto t = exp * odd;
68 auto first_half = even + t;
69 auto second_half = even - t;
70 // TODO: should be a call to stack if performance was improved
71 auto spectrum = xt::xtensor<value_type, 1>::from_shape({N});
72 xt::view(spectrum, xt::range(0, N / 2)) = first_half;
73 xt::view(spectrum, xt::range(N / 2, N)) = second_half;
74 return spectrum;
75 }
76 }
77
78 template <typename E>
79 auto transform_bluestein(E&& data)
80 {
81 using value_type = typename std::decay_t<E>::value_type;
82 using precision = typename value_type::value_type;
83
84 // Find a power-of-2 convolution length m such that m >= n * 2 + 1
85 const std::size_t n = data.size();
86 size_t m = static_cast<size_t>(std::ceil(std::log2(n * 2 + 1)));
87 m = static_cast<size_t>(std::pow(2, m));
88
89 // Trignometric table
90 auto exp_table = xt::xtensor<std::complex<precision>, 1>::from_shape({n});
92 i %= (n * 2);
93
94 // The angles are computed in precision, the integer operands are converted to it.
95 auto angles = xt::eval(
96 xt::numeric_constants<precision>::PI * xt::cast<precision>(i) / static_cast<precision>(n)
97 );
98 auto j = std::complex<precision>(0, 1);
99 exp_table = xt::exp(-angles * j);
100
101 // Temporary vectors and preprocessing
102 auto av = xt::empty<std::complex<precision>>({m});
103 xt::view(av, xt::range(0, n)) = data * exp_table;
104
105
106 auto bv = xt::empty<std::complex<precision>>({m});
107 xt::view(bv, xt::range(0, n)) = ::xt::conj(exp_table);
108 xt::view(bv, xt::range(-n + 1, xt::placeholders::_)) = xt::view(
109 ::xt::conj(xt::flip(exp_table)),
110 xt::range(xt::placeholders::_, -1)
111 );
112
113 // Convolution
114 auto xv = radix2(av);
115 auto yv = radix2(bv);
116 auto spectrum_k = xv * yv;
117 auto complex_args = xt::conj(spectrum_k);
118 auto fft_res = radix2(complex_args);
119 // m is a power of 2, so it is exactly representable in floating point.
120 auto cv = xt::conj(fft_res) / static_cast<precision>(m);
121
122 return xt::eval(xt::view(cv, xt::range(0, n)) * exp_table);
123 }
124 } // namespace detail
125
132 template <class E>
133 inline auto fft(E&& e, std::ptrdiff_t axis = -1)
134 {
135 using value_type = typename std::decay<E>::type::value_type;
136 if (e.dimension() == 0)
137 {
138 XTENSOR_THROW(std::runtime_error, "Cannot take the FFT of a scalar expression");
139 }
140 if constexpr (xtl::is_complex<typename std::decay<E>::type::value_type>::value)
141 {
142 using precision = typename value_type::value_type;
143 const auto saxis = xt::normalize_axis(e.dimension(), axis);
144 const size_t N = e.shape(saxis);
145 const bool powerOfTwo = !(N == 0) && !(N & (N - 1));
147 auto begin = xt::axis_slice_begin(out, saxis);
148 auto end = xt::axis_slice_end(out, saxis);
149 for (auto iter = begin; iter != end; iter++)
150 {
151 if (powerOfTwo)
152 {
153 xt::noalias(*iter) = detail::radix2(*iter);
154 }
155 else
156 {
157 xt::noalias(*iter) = detail::transform_bluestein(*iter);
158 }
159 }
160 return out;
161 }
162 else
163 {
164 return fft(xt::cast<std::complex<value_type>>(e), axis);
165 }
166 }
167
168 template <class E>
169 inline auto ifft(E&& e, std::ptrdiff_t axis = -1)
170 {
171 if (e.dimension() == 0)
172 {
173 XTENSOR_THROW(std::runtime_error, "Cannot take the iFFT of a scalar expression");
174 }
175 if constexpr (xtl::is_complex<typename std::decay<E>::type::value_type>::value)
176 {
177 // check the length of the data on that axis
178 const std::size_t n = e.shape(xt::normalize_axis(e.dimension(), axis));
179 if (n == 0)
180 {
181 XTENSOR_THROW(std::runtime_error, "Cannot take the iFFT along an empty dimention");
182 }
183 auto complex_args = xt::conj(e);
184 auto fft_res = xt::fft::fft(complex_args, axis);
185 fft_res = xt::conj(fft_res);
186 return fft_res;
187 }
188 else
189 {
190 using value_type = typename std::decay<E>::type::value_type;
191 return ifft(xt::cast<std::complex<value_type>>(e), axis);
192 }
193 }
194
195 /*
196 * @brief performs a circular fft convolution xvec and yvec must
197 * be the same shape.
198 * @param xvec first array of the convolution
199 * @param yvec second array of the convolution
200 * @param axis axis along which to perform the convolution
201 */
202 template <typename E1, typename E2>
203 auto convolve(E1&& xvec, E2&& yvec, std::ptrdiff_t axis = -1)
204 {
205 // we could broadcast but that could get complicated???
206 if (xvec.dimension() != yvec.dimension())
207 {
208 XTENSOR_THROW(std::runtime_error, "Mismatched dimentions");
209 }
210
211 auto saxis = xt::normalize_axis(xvec.dimension(), axis);
212 if (xvec.shape(saxis) != yvec.shape(saxis))
213 {
214 XTENSOR_THROW(std::runtime_error, "Mismatched lengths along slice axis");
215 }
216
217 const std::size_t n = xvec.shape(saxis);
218
219 auto xv = fft(xvec, axis);
220 auto yv = fft(yvec, axis);
221
222 auto begin_x = xt::axis_slice_begin(xv, saxis);
223 auto end_x = xt::axis_slice_end(xv, saxis);
224 auto iter_y = xt::axis_slice_begin(yv, saxis);
225
226 for (auto iter = begin_x; iter != end_x; iter++)
227 {
228 (*iter) = (*iter_y++) * (*iter);
229 }
230
231 auto outvec = ifft(xv, axis);
232
233 // Scaling (because this FFT implementation omits it)
234 using precision = typename std::decay_t<decltype(outvec)>::value_type::value_type;
235 outvec = outvec / static_cast<precision>(n);
236
237 return outvec;
238 }
239
240 }
241} // namespace xt::fft
size_type size() const noexcept
Returns the number of element in the container.
auto cast(E &&e) noexcept -> detail::xfunction_type_t< typename detail::cast< R >::functor, E >
Element-wise static_cast.
auto exp(E &&e) noexcept -> detail::xfunction_type_t< math::exp_fun, E >
Natural exponential function.
Definition xmath.hpp:901
auto pow(E1 &&e1, E2 &&e2) noexcept -> detail::xfunction_type_t< math::pow_fun, E1, E2 >
Power function.
Definition xmath.hpp:1016
auto conj(E &&e) noexcept
Return an xt::xfunction evaluating to the complex conjugate of the given expression.
Definition xcomplex.hpp:207
auto eval(T &&t) -> std::enable_if_t< detail::is_container< std::decay_t< T > >::value, T && >
Force evaluation of xexpression.
Definition xeval.hpp:46
auto flip(E &&e)
Reverse the order of elements in an xexpression along every axis.
standard mathematical functions for xexpressions
auto range(A start_val, B stop_val)
Select a range from start_val to stop_val (excluded).
Definition xslice.hpp:737
auto arange(T start, T stop, S step=1) noexcept
Generates numbers evenly spaced within given half-open interval [start, stop).
Definition xbuilder.hpp:432
xarray_container< uvector< T, A >, L, xt::svector< typename uvector< T, A >::size_type, 4, SA, true > > xarray
Alias template on xarray_container with default parameters for data container type and shape / stride...
auto linspace(T start, T stop, std::size_t num_samples=50, bool endpoint=true) noexcept
Generates num_samples evenly spaced numbers over given interval.
Definition xbuilder.hpp:460
xtensor_container< uvector< T, A >, N, L > xtensor
Alias template on xtensor_container with default parameters for data container type.
auto axis_slice_begin(E &&e)
Returns an iterator to the first element of the expression for axis 0.
auto view(E &&e, S &&... slices)
Constructs and returns a view on the specified xexpression.
Definition xview.hpp:1816
auto axis_slice_end(E &&e)
Returns an iterator to the element following the last element of the expression for axis 0.
xarray< T, L > empty(const S &shape)
Create a xcontainer (xarray, xtensor or xtensor_fixed) with uninitialized values of with value_type T...
Definition xbuilder.hpp:89