Eigen-Contrib  5.0.1-dev+master
 
Loading...
Searching...
No Matches
StructuredMatrixUtils.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// This Source Code Form is subject to the terms of the Mozilla
5// Public License v. 2.0. If a copy of the MPL was not distributed
6// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
7// SPDX-FileCopyrightText: The Eigen Authors
8// SPDX-License-Identifier: MPL-2.0
9
10// References:
11// [1] N. J. Higham, "Accuracy and Stability of Numerical Algorithms", 2nd ed.,
12// SIAM, 2002, chapter 27. Avoiding spurious overflow by rescaling with
13// powers of two, the technique behind structured_exponent_bound() and the
14// balanced determinant accumulations.
15// [2] P. H. Sterbenz, "Floating-Point Computation", Prentice-Hall, 1974.
16// Scaling by a power of two is exact, so the balanced accumulations
17// introduce no roundoff of their own.
18
19#ifndef EIGEN_STRUCTURED_MATRIX_UTILS_H
20#define EIGEN_STRUCTURED_MATRIX_UTILS_H
21
22// IWYU pragma: private
23#include "./InternalHeaderCheck.h"
24
25namespace Eigen {
26
27namespace internal {
28
29// A distinct shape routes assignment through evalTo/addTo/subTo and lets one
30// product specialization cover every product tag without colliding with DenseShape.
31struct StructuredShape {};
32
33// Below this dimension the FFT setup costs more than a plain O(n^2) evaluation,
34// so the structured operators fall back to a direct segment-based product.
35constexpr Index structured_direct_threshold() { return 32; }
36
37// Below this dimension even the segment-based direct product loses to a plain
38// scalar loop: the per-segment setup dominates when the average segment holds
39// fewer than a couple of packets (measured crossover on AVX2 hardware).
40constexpr Index structured_scalar_threshold() { return 16; }
41
42// Numerical scale exponents are independent of Eigen's configurable dimension
43// index. A 32-bit Index can overflow while accumulating O(n^2) factor
44// exponents for dimensions that are otherwise practical.
45using structured_exponent_type = numext::int64_t;
46
53template <typename RealVectorType>
54std::vector<Index> structured_svd_permutation(const RealVectorType& mods) {
55 using RealScalar = typename RealVectorType::Scalar;
56 std::vector<Index> perm;
57 perm.reserve(static_cast<std::size_t>(mods.size()));
58 for (Index k = 0; k < mods.size(); ++k) perm.push_back(k);
59 std::stable_sort(perm.begin(), perm.end(), [&mods](Index a, Index b) {
60 const RealScalar ka = mods[a], kb = mods[b];
61 // isgreater is quiet for NaNs; the second clause implements NaN-last ordering.
62 return std::isgreater(ka, kb) || (!(numext::isnan)(ka) && (numext::isnan)(kb));
63 });
64 return perm;
65}
66
81#ifndef EIGEN_AVOID_THREAD_LOCAL
82template <typename RealScalar>
83FFT<RealScalar>& structured_fft_engine() {
84 static thread_local FFT<RealScalar> fft;
85 return fft;
86}
87#else
88template <typename RealScalar>
89FFT<RealScalar> structured_fft_engine() {
90 return FFT<RealScalar>();
91}
92#endif
93
102inline Index fft_next_good_size(Index n) {
103 if (n < 1) return 1;
104 for (Index m = n;; ++m) {
105 Index r = m;
106 while (r % 2 == 0) r /= 2;
107 while (r % 3 == 0) r /= 3;
108 while (r % 5 == 0) r /= 5;
109 if (r == 1) return m;
110 }
111}
112
118template <typename Scalar, bool IsComplex = NumTraits<Scalar>::IsComplex>
119struct structured_scalar_part_impl {
120 template <typename Xpr>
121 static const Xpr& run(const Xpr& xpr) {
122 return xpr;
123 }
124 static const Scalar& run_scalar(const Scalar& x) { return x; }
125};
126
127template <typename Scalar>
128struct structured_scalar_part_impl<Scalar, false> {
129 template <typename Xpr>
130 static typename Xpr::RealReturnType run(const Xpr& xpr) {
131 return xpr.real();
132 }
133 static Scalar run_scalar(const std::complex<Scalar>& x) { return numext::real(x); }
134};
135
153template <typename Xpr>
154bool structured_exponent_bound_finite(const Xpr& x, int& e) {
155 using ScalarTraits = NumTraits<typename Xpr::Scalar>;
156 using RealScalar = typename ScalarTraits::Real;
157 // maxCoeff() asserts on an empty input, and a degenerate operand -- a rank-0
158 // factor, a solve with no right-hand sides -- reaches here legitimately.
159 // An empty operand bounds nothing, so its exponent bound is 0.
160 e = 0;
161 if (x.size() == 0) return true;
162 RealScalar m;
163 if (ScalarTraits::IsComplex)
164 // realView() reduces over both components in one pass, vectorized for
165 // direct-access storage; the strided real()/imag() views never vectorize.
166 m = x.realView().cwiseAbs().maxCoeff();
167 else
168 m = x.cwiseAbs().maxCoeff();
169 // A SIMD unit that flushes subnormal inputs (ARMv7 NEON, Arm FZ, DAZ) reads
170 // an all-subnormal operand as zero; the rescan recovers the largest component
171 // from its representation.
172 m = safe_scaling<RealScalar>::recover_flushed_max_coeff(x, m);
173 e = 0;
174 if (!(numext::isfinite)(m)) return false;
175 if (!numext::is_exactly_zero_no_flush(m)) {
176 e = frexp_exponent_preserving_subnormals(m);
177 if (ScalarTraits::IsComplex) ++e;
178 }
179 return true;
180}
181
184template <typename Xpr>
185int structured_exponent_bound(const Xpr& x) {
186 int e;
187 structured_exponent_bound_finite(x, e);
188 return e;
189}
190
191// The packet form of M *= 2^e. ldexp saturates entrywise for every e without
192// forming a possibly unrepresentable 2^e; for std::complex storage, realView()
193// exposes both components to the real ldexp packets.
194template <typename Xpr, std::enable_if_t<!NumTraits<typename Xpr::Scalar>::IsComplex, bool> = true>
195void structured_ldexp_entries_packet(Xpr& M, int e) {
196 M.array() = M.array().ldexp(e);
197}
198
199template <typename Xpr, std::enable_if_t<complex_array_access<typename Xpr::Scalar>::value, bool> = true>
200void structured_ldexp_entries_packet(Xpr& M, int e) {
201 M.realView().array() = M.realView().array().ldexp(e);
202}
203
204template <typename Xpr, std::enable_if_t<NumTraits<typename Xpr::Scalar>::IsComplex &&
205 !complex_array_access<typename Xpr::Scalar>::value,
206 bool> = true>
207void structured_ldexp_entries_packet(Xpr& M, int e) {
208 using Scalar = typename Xpr::Scalar;
209 M = M.unaryExpr([e](const Scalar& z) { return apply_exponent(z, Index(e)); });
210}
211
212template <typename Xpr>
213void structured_ldexp_entries_impl(Xpr& M, int e, int, std::false_type) {
214 structured_ldexp_entries_packet(M, e);
215}
216
217template <typename Xpr>
218void structured_ldexp_entries_impl(Xpr& M, int e, int bound, std::true_type) {
219 using Scalar = typename Xpr::Scalar;
220 using RealScalar = typename NumTraits<Scalar>::Real;
221 // The largest component is at least 2^(componentBound - 1): a complex bound
222 // carries one extra bit for the modulus. The input holds no significant
223 // subnormal when componentBound - 1 >= recovery, and neither does the result
224 // when componentBound - 1 + e >= recovery.
225 const int componentBound = bound - (NumTraits<Scalar>::IsComplex ? 1 : 0);
226 const int recovery = safe_scaling<RealScalar>::subnormal_recovery_exponent();
227 if (componentBound - 1 >= recovery && componentBound - 1 + e >= recovery)
228 structured_ldexp_entries_packet(M, e);
229 else
230 M = M.unaryExpr(scale_by_exponent_op<RealScalar>(e));
231}
232
243template <typename Xpr>
244void structured_ldexp_entries(Xpr& M, int e, int bound) {
245 if (e == 0) return;
246 using Scalar = typename Xpr::Scalar;
247 using RealScalar = typename NumTraits<Scalar>::Real;
248 structured_ldexp_entries_impl(M, e, bound,
249 bool_constant<use_subnormal_preserving_scaling<RealScalar, Scalar>::value>());
250}
251
255template <typename Xpr>
256void structured_ldexp_entries(Xpr& M, int e) {
257 if (e == 0) return;
258 structured_ldexp_entries(M, e, structured_exponent_bound(M));
259}
260
261template <typename Xpr>
262void structured_ldexp_entries_exact_impl(Xpr& M, int e, std::false_type) {
263 structured_ldexp_entries_packet(M, e);
264}
265template <typename Xpr>
266void structured_ldexp_entries_exact_impl(Xpr& M, int e, std::true_type) {
267 using RealScalar = typename NumTraits<typename Xpr::Scalar>::Real;
268 M = M.unaryExpr(scale_by_exponent_op<RealScalar>(e));
269}
270
276template <typename Xpr>
277void structured_ldexp_entries_exact(Xpr& M, int e) {
278 if (e == 0) return;
279 using Scalar = typename Xpr::Scalar;
280 using RealScalar = typename NumTraits<Scalar>::Real;
281 structured_ldexp_entries_exact_impl(M, e,
282 bool_constant<use_subnormal_preserving_scaling<RealScalar, Scalar>::value>());
283}
284
290template <typename ComplexVectorType>
291ComplexVectorType structured_reverse_symbol(const ComplexVectorType& symbol) {
292 const Index p = symbol.size();
293 ComplexVectorType reversed(p);
294 if (p > 0) {
295 reversed[0] = symbol[0];
296 reversed.tail(p - 1) = symbol.tail(p - 1).reverse();
297 }
298 return reversed;
299}
300
311template <typename Scalar, typename Dest, typename Rhs>
312void structured_fft_apply(Dest& dst, const Matrix<std::complex<typename NumTraits<Scalar>::Real>, Dynamic, 1>& symbol,
313 Index outSize, const Rhs& rhs, const Scalar& alpha) {
314 using RealScalar = typename NumTraits<Scalar>::Real;
315 using Complex = std::complex<RealScalar>;
316 using ComplexVector = Matrix<Complex, Dynamic, 1>;
317
318 const Index p = symbol.size();
319 eigen_assert(rhs.rows() <= p && outSize <= p);
320 if (p == 1) {
321 // The length-one DFT is the identity and is unsupported by kissfft.
322 dst.row(0) += alpha * structured_scalar_part_impl<Scalar>::run(Complex(symbol.coeff(0)) *
323 rhs.row(0).template cast<Complex>());
324 return;
325 }
326
327 auto&& fft = structured_fft_engine<RealScalar>();
328 ComplexVector xt = ComplexVector::Zero(p);
329 ComplexVector xf(p), yt(p);
330 for (Index k = 0; k < rhs.cols(); ++k) {
331 xt.head(rhs.rows()) = rhs.col(k).template cast<Complex>();
332 fft.fwd(xf, xt, p);
333 xf.array() *= symbol.array();
334 fft.inv(yt, xf, p);
335 dst.col(k) += alpha * structured_scalar_part_impl<Scalar>::run(yt.head(outSize));
336 }
337}
338
345template <typename SymbolType, typename ModsType, typename RealScalar>
346SymbolType structured_pinv_symbol(const SymbolType& symbol, const ModsType& mods, const RealScalar& tol) {
347 using Complex = typename SymbolType::Scalar;
348 const auto w = (mods.array() < tol).select(RealScalar(0), mods.array().inverse()).template cast<Complex>().eval();
349 return (symbol.array().conjugate() * w * w).matrix();
350}
351
357template <typename SymbolType, typename ModsType>
358typename ModsType::Scalar structured_rank_threshold(const SymbolType& symbol, const ModsType& mods) {
359 using RealScalar = typename ModsType::Scalar;
360 const RealScalar factor = RealScalar(mods.size()) * NumTraits<RealScalar>::epsilon();
361 RealScalar tol = factor * mods.maxCoeff();
362 if (!(numext::isfinite)(tol)) tol = (RealScalar(2) * factor) * (symbol * RealScalar(0.5)).cwiseAbs().maxCoeff();
363 return numext::maxi(tol, (std::numeric_limits<RealScalar>::min)());
364}
365
377template <typename Op, typename Rhs>
378struct structured_product_impl : generic_product_impl_base<Op, Rhs, structured_product_impl<Op, Rhs>> {
379 using Scalar = typename Product<Op, Rhs>::Scalar;
380
381 template <typename Dest>
382 static void evalTo(Dest& dst, const Op& lhs, const Rhs& rhs) {
383 dst.setZero();
384 scaleAndAddTo(dst, lhs, rhs, Scalar(1));
385 }
386
387 template <typename Dest>
388 static void scaleAndAddTo(Dest& dst, const Op& lhs, const Rhs& rhs, const Scalar& alpha) {
389 using RhsNested = typename nested_eval<Rhs, Op::RowsAtCompileTime>::type;
390 RhsNested actualRhs(rhs);
391 lhs.addProduct(dst, actualRhs, alpha);
392 }
393};
394
395} // namespace internal
396
397} // namespace Eigen
398
399#endif // EIGEN_STRUCTURED_MATRIX_UTILS_H
Namespace containing all symbols from the Eigen library.