Eigen-Contrib  5.0.1-dev+master
 
Loading...
Searching...
No Matches
Circulant.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] P. J. Davis, "Circulant Matrices", Wiley, 1979. Diagonalization of a
12// circulant matrix by the DFT and the closed-form eigenstructure used by
13// eigenvalues()/eigenvectors(); the SVD and pseudo-inverse below follow
14// from it by taking moduli/phases of the eigenvalues.
15// [2] R. M. Gray, "Toeplitz and Circulant Matrices: A Review", Foundations and
16// Trends in Communications and Information Theory, 2(3), 2006.
17// [3] G. H. Golub and C. F. Van Loan, "Matrix Computations", 4th ed., Johns
18// Hopkins University Press, 2013, chapter 4.8 (circulant systems and
19// FFT-based products) and chapter 5.4 (numerical rank conventions).
20// [4] J. J. Dongarra, J. R. Bunch, C. B. Moler and G. W. Stewart, "LINPACK
21// Users' Guide", SIAM, 1979. determinant()'s balanced accumulation follows
22// the convention of its xGEDI routines, which return determinants as a
23// (fraction, exponent) pair to avoid spurious overflow/underflow.
24// [5] P. H. Sterbenz, "Floating-Point Computation", Prentice-Hall, 1974.
25// Scaling by a power of two is exact, the property the balanced
26// accumulation relies on.
27
28#ifndef EIGEN_STRUCTURED_CIRCULANT_H
29#define EIGEN_STRUCTURED_CIRCULANT_H
30
31// IWYU pragma: private
32#include "./InternalHeaderCheck.h"
33
34namespace Eigen {
35
36template <typename Scalar_, int Size_ = Dynamic>
37class Circulant;
38
39namespace internal {
40
41template <typename Scalar_, int Size_>
42struct traits<Circulant<Scalar_, Size_>> {
43 using Scalar = Scalar_;
44 using StorageKind = Dense;
45 using XprKind = MatrixXpr;
46 using StorageIndex = int;
47 static constexpr int RowsAtCompileTime = Size_;
48 static constexpr int ColsAtCompileTime = Size_;
49 static constexpr int MaxRowsAtCompileTime = Size_;
50 static constexpr int MaxColsAtCompileTime = Size_;
51 // Deliberately no NestByRefBit: transpose(), conjugate() and adjoint() return
52 // owning temporaries, so Product must nest the operator by value for a
53 // delayed-evaluated product expression to keep its left factor alive. The copy
54 // is O(n), negligible against the O(n log n) product evaluation.
55 static constexpr int Flags = 0;
56};
57
58template <typename Scalar_, int Size_>
59struct evaluator_traits<Circulant<Scalar_, Size_>> {
60 using Kind = IndexBased;
61 using Shape = StructuredShape;
62};
63
64} // namespace internal
65
102template <typename Scalar_, int Size_>
103class Circulant : public EigenBase<Circulant<Scalar_, Size_>> {
104 public:
105 using Scalar = Scalar_;
106 using RealScalar = typename NumTraits<Scalar>::Real;
107 using StorageIndex = int;
108 using Complex = std::complex<RealScalar>;
109 using GeneratorType = Matrix<Scalar, Size_, 1>;
110 using ComplexVector = Matrix<Complex, Dynamic, 1>;
111 using RealVector = Matrix<RealScalar, Size_, 1>;
112 using ComplexMatrix = Matrix<Complex, Size_, Size_>;
113
114 static constexpr int RowsAtCompileTime = Size_;
115 static constexpr int ColsAtCompileTime = Size_;
116 static constexpr int MaxRowsAtCompileTime = Size_;
117 static constexpr int MaxColsAtCompileTime = Size_;
118 static constexpr int SizeAtCompileTime = internal::size_at_compile_time(Size_, Size_);
119 static constexpr int MaxSizeAtCompileTime = SizeAtCompileTime;
120 static constexpr bool IsRowMajor = false;
121 // Deliberately no IsVectorAtCompileTime: Ref<const Circulant>'s default StrideType
122 // argument reads it, so its absence makes internal::is_ref_compatible SFINAE to
123 // false and keeps the iterative solvers on their matrix-free path.
124
130 template <typename Derived>
131 explicit Circulant(const MatrixBase<Derived>& col) : m_col(col) {
132 EIGEN_STATIC_ASSERT_VECTOR_ONLY(Derived)
133 EIGEN_INTERNAL_ASSERT_NONEMPTY_MSG(m_col, "Circulant generator must be non-empty");
134 if (m_col.size() > internal::structured_direct_threshold()) {
135 m_symbol = computeSymbol();
136 m_prodSymbol = computeProdSymbol(m_col);
137 }
138 }
139
140 EIGEN_DEVICE_FUNC Index rows() const { return m_col.size(); }
141 EIGEN_DEVICE_FUNC Index cols() const { return m_col.size(); }
142
144 const GeneratorType& column() const { return m_col; }
145
150 ComplexVector symbol() const { return m_symbol.size() > 0 ? m_symbol : computeSymbol(); }
151
153 Scalar coeff(Index row, Index col) const {
154 Index k = row - col;
155 if (k < 0) k += rows();
156 return m_col.coeff(k);
157 }
158
164 const Index n = rows();
165 GeneratorType col(n);
166 col[0] = m_col[0];
167 if (n > 1) col.tail(n - 1) = m_col.tail(n - 1).reverse();
168 return Circulant(col, internal::structured_reverse_symbol(m_symbol),
169 internal::structured_reverse_symbol(m_prodSymbol));
170 }
171
176 return Circulant(m_col.conjugate(), internal::structured_reverse_symbol(m_symbol).conjugate(),
177 internal::structured_reverse_symbol(m_prodSymbol).conjugate());
178 }
179
185 const Index n = rows();
186 GeneratorType col(n);
187 col[0] = numext::conj(m_col[0]);
188 if (n > 1) col.tail(n - 1) = m_col.tail(n - 1).reverse().conjugate();
189 return Circulant(col, m_symbol.conjugate(), m_prodSymbol.conjugate());
190 }
191
195 template <typename Dest>
196 void evalTo(Dest& dst) const {
197 const Index n = rows();
198 EIGEN_IF_CONSTEXPR (Dest::IsRowMajor) {
199 for (Index i = 0; i < n; ++i) {
200 dst.row(i).head(i + 1) = m_col.head(i + 1).reverse().transpose();
201 dst.row(i).tail(n - i - 1) = m_col.tail(n - i - 1).reverse().transpose();
202 }
203 return;
204 }
205 for (Index j = 0; j < n; ++j) {
206 dst.col(j).head(j) = m_col.tail(j);
207 dst.col(j).tail(n - j) = m_col.head(n - j);
208 }
209 }
210
212 template <typename Dest>
213 void addTo(Dest& dst) const {
214 const Index n = rows();
215 EIGEN_IF_CONSTEXPR (Dest::IsRowMajor) {
216 for (Index i = 0; i < n; ++i) {
217 dst.row(i).head(i + 1) += m_col.head(i + 1).reverse().transpose();
218 dst.row(i).tail(n - i - 1) += m_col.tail(n - i - 1).reverse().transpose();
219 }
220 return;
221 }
222 for (Index j = 0; j < n; ++j) {
223 dst.col(j).head(j) += m_col.tail(j);
224 dst.col(j).tail(n - j) += m_col.head(n - j);
225 }
226 }
227
229 template <typename Dest>
230 void subTo(Dest& dst) const {
231 const Index n = rows();
232 EIGEN_IF_CONSTEXPR (Dest::IsRowMajor) {
233 for (Index i = 0; i < n; ++i) {
234 dst.row(i).head(i + 1) -= m_col.head(i + 1).reverse().transpose();
235 dst.row(i).tail(n - i - 1) -= m_col.tail(n - i - 1).reverse().transpose();
236 }
237 return;
238 }
239 for (Index j = 0; j < n; ++j) {
240 dst.col(j).head(j) -= m_col.tail(j);
241 dst.col(j).tail(n - j) -= m_col.head(n - j);
242 }
243 }
244
249 template <typename Rhs>
251 return Product<Circulant, Rhs>(*this, x.derived());
252 }
253
260 template <typename Rhs>
262 EIGEN_INTERNAL_ASSERT_SOLVER_RHS_MSG(*this, b, false, "right-hand side has the wrong number of rows");
263 const Index n = rows();
264 const ComplexVector s = symbol();
265 const RealVector mods = s.cwiseAbs();
266 const ComplexVector sinv = internal::structured_pinv_symbol(s, mods, internal::structured_rank_threshold(s, mods));
268 x.setZero();
269 internal::structured_fft_apply(x, sinv, n, b.derived(), Scalar(1));
270 return x;
271 }
272
279 Index rank() const {
280 const ComplexVector s = symbol();
281 const RealVector mods = s.cwiseAbs();
282 return (!(mods.array() < internal::structured_rank_threshold(s, mods))).count(); // NaN entries count as non-zero
283 }
284
290 const Index n = rows();
291 const ComplexVector sinv = symbol().cwiseInverse();
292 GeneratorType col(n);
293 if (n == 1) {
294 col = internal::structured_scalar_part_impl<Scalar>::run(sinv);
295 } else {
296 auto&& fft = internal::structured_fft_engine<RealScalar>();
297 ComplexVector ct(n);
298 fft.inv(ct, sinv, n);
299 col = internal::structured_scalar_part_impl<Scalar>::run(ct);
300 }
301 return Circulant(col, n > internal::structured_direct_threshold() ? sinv : ComplexVector(),
302 n > internal::structured_direct_threshold() ? computeProdSymbol(col) : ComplexVector());
303 }
304
313 Scalar determinant() const {
314 const ComplexVector s = symbol();
315 Complex det(1);
316 Index exponent = 0;
317 for (Index k = 0; k < s.size(); ++k)
318 det = internal::balance_exponent(Complex(det * internal::balance_exponent(s[k], exponent)), exponent);
319 return internal::structured_scalar_part_impl<Scalar>::run_scalar(internal::apply_exponent(det, exponent));
320 }
321
326 ComplexVector eigenvalues() const { return symbol(); }
327
332 ComplexMatrix eigenvectors() const {
333 const Index n = rows();
334 const ComplexVector roots = fourierRoots();
335 ComplexMatrix F(n, n);
336 for (Index k = 0; k < n; ++k) fourierColumn(F, roots, k, k);
337 return F;
338 }
339
345 RealVector singularValues() const {
346 ComplexVector s;
347 RealVector mods;
348 const std::vector<Index> perm = svdOrdering(s, mods);
349 RealVector sv(s.size());
350 for (Index t = 0; t < s.size(); ++t) sv[t] = mods[perm[t]];
351 return sv;
352 }
353
357 ComplexMatrix matrixU() const {
358 const Index n = rows();
359 ComplexVector s;
360 RealVector mods;
361 const std::vector<Index> perm = svdOrdering(s, mods);
362 const ComplexVector roots = fourierRoots();
363 ComplexMatrix U(n, n);
364 for (Index t = 0; t < n; ++t) {
365 fourierColumn(U, roots, perm[t], t);
366 const RealScalar a = mods[perm[t]];
367 if (a > RealScalar(0)) U.col(t) *= s[perm[t]] / a;
368 }
369 return U;
370 }
371
375 ComplexMatrix matrixV() const {
376 const Index n = rows();
377 ComplexVector s;
378 RealVector mods;
379 const std::vector<Index> perm = svdOrdering(s, mods);
380 const ComplexVector roots = fourierRoots();
381 ComplexMatrix V(n, n);
382 for (Index t = 0; t < n; ++t) fourierColumn(V, roots, perm[t], t);
383 return V;
384 }
385
389 template <typename Dest, typename Rhs, typename ProductScalar>
390 void addProduct(Dest& dst, const Rhs& rhs, const ProductScalar& alpha) const {
391 const Index n = rows();
392 EIGEN_INTERNAL_ASSERT_PRODUCT_SHAPE_MSG(*this, rhs, "invalid product: dimensions do not match");
393 if (n <= internal::structured_direct_threshold()) {
394 directProduct(dst, rhs, alpha);
395 return;
396 }
397 // Products use the padded embedding symbol when the operator size is not
398 // 5-smooth (see computeProdSymbol()); the exact-size transform of such a
399 // size runs through kissfft's quadratic generic butterfly.
400 const ComplexVector& s = m_prodSymbol.size() > 0 ? m_prodSymbol : m_symbol;
401 internal::structured_fft_apply(dst, s, n, rhs, alpha);
402 }
403
404 private:
410 Circulant(const GeneratorType& col, const ComplexVector& symbol, const ComplexVector& prodSymbol)
411 : m_col(col), m_symbol(symbol), m_prodSymbol(prodSymbol) {}
412
423 static ComplexVector computeProdSymbol(const GeneratorType& col) {
424 const Index n = col.size();
425 if (internal::fft_next_good_size(n) == n) return ComplexVector();
426 const Index p = internal::fft_next_good_size(2 * n - 1);
427 ComplexVector embedding = ComplexVector::Zero(p);
428 embedding.head(n) = col.template cast<Complex>();
429 embedding.tail(n - 1) = col.tail(n - 1).template cast<Complex>();
430 ComplexVector symbol(p);
431 auto&& fft = internal::structured_fft_engine<RealScalar>();
432 fft.fwd(symbol, embedding, p);
433 return symbol;
434 }
435
439 template <typename Dest, typename Rhs, typename ProductScalar>
440 void directProductColumn(Dest& dst, const Rhs& rhs, Index k, const ProductScalar& alpha) const {
441 const Index n = rows();
442 // A unit alpha must not multiply: even the identity complex scalar (1,0)
443 // pollutes an (Inf,0) value with NaN through the 0*Inf cross term.
444 const bool unitAlpha = alpha == ProductScalar(1);
445 if (n <= internal::structured_scalar_threshold()) {
446 // Tiny sizes: a plain scalar loop beats the segment-based path below, whose
447 // per-segment setup dominates when segments hold only a few entries.
448 for (Index i = 0; i < n; ++i) {
449 ProductScalar acc(0);
450 for (Index j = 0; j < n; ++j) acc += coeff(i, j) * rhs.coeff(j, k);
451 dst.coeffRef(i, k) += unitAlpha ? acc : ProductScalar(alpha * acc);
452 }
453 return;
454 }
455
456 // Column j is c rotated downward by j; split it into two contiguous segments.
457 auto dstCol = dst.col(k);
458 for (Index j = 0; j < n; ++j) {
459 const ProductScalar xj = unitAlpha ? ProductScalar(rhs.coeff(j, k)) : ProductScalar(alpha * rhs.coeff(j, k));
460 dstCol.head(j) += xj * m_col.tail(j);
461 dstCol.tail(n - j) += xj * m_col.head(n - j);
462 }
463 }
464
467 template <typename Dest, typename Rhs, typename ProductScalar>
468 void directProduct(Dest& dst, const Rhs& rhs, const ProductScalar& alpha) const {
469 for (Index k = 0; k < rhs.cols(); ++k) directProductColumn(dst, rhs, k, alpha);
470 }
471
488 std::vector<Index> svdOrdering(ComplexVector& s, RealVector& mods) const {
489 const Index n = rows();
490 s = symbol();
491 EIGEN_IF_CONSTEXPR (!NumTraits<Scalar>::IsComplex) {
492 const Index pairs = (n - 1) / 2;
493 mods.resize(n);
494 mods.head(n - pairs) = s.head(n - pairs).cwiseAbs();
495 mods.tail(pairs) = mods.segment(1, pairs).reverse();
496 } else {
497 mods = s.cwiseAbs();
498 }
499 return internal::structured_svd_permutation(mods);
500 }
501
502 // Cache the n distinct roots once per Fourier matrix, preserving polar()'s
503 // bounded arguments and rounding while avoiding n^2 trigonometric evaluations.
504 ComplexVector fourierRoots() const {
505 const Index n = rows();
506 const RealScalar scale = RealScalar(1) / numext::sqrt(RealScalar(n));
507 ComplexVector roots(n);
508 for (Index j = 0; j < n; ++j)
509 roots[j] = std::polar(scale, RealScalar(2 * EIGEN_PI) * RealScalar(j) / RealScalar(n));
510 return roots;
511 }
512
513 // Column k uses roots[j*k mod n]; incremental modular indexing avoids j*k overflow.
514 void fourierColumn(ComplexMatrix& F, const ComplexVector& roots, Index k, Index dstCol) const {
515 const Index n = rows();
516 Index jk = 0;
517 for (Index j = 0; j < n; ++j) {
518 F(j, dstCol) = roots[jk];
519 jk += k;
520 if (jk >= n) jk -= n;
521 }
522 }
523
525 ComplexVector computeSymbol() const {
526 const Index n = m_col.size();
527 const ComplexVector cc = m_col.template cast<Complex>();
528 if (n == 1) return cc; // the DFT of a single sample is the identity
529 ComplexVector symbol(n);
530 auto&& fft = internal::structured_fft_engine<RealScalar>();
531 fft.fwd(symbol, cc, n);
532 return symbol;
533 }
534
535 GeneratorType m_col;
536 ComplexVector m_symbol;
537 // The padded embedding symbol products use when the size is not 5-smooth;
538 // empty otherwise. See computeProdSymbol().
539 ComplexVector m_prodSymbol;
540};
541
545template <typename Derived>
549
550namespace internal {
551
552// StructuredShape avoids ambiguity with the stock dense product specializations.
553template <typename Scalar_, int Size_, typename Rhs, int ProductTag>
554struct generic_product_impl<Circulant<Scalar_, Size_>, Rhs, StructuredShape, DenseShape, ProductTag>
555 : structured_product_impl<Circulant<Scalar_, Size_>, Rhs> {};
556
557} // namespace internal
558
559#if EIGEN_COMP_CXXVER < 17
560template <typename Scalar_, int Size_>
561constexpr int Circulant<Scalar_, Size_>::RowsAtCompileTime;
562template <typename Scalar_, int Size_>
563constexpr int Circulant<Scalar_, Size_>::ColsAtCompileTime;
564template <typename Scalar_, int Size_>
565constexpr int Circulant<Scalar_, Size_>::MaxRowsAtCompileTime;
566template <typename Scalar_, int Size_>
567constexpr int Circulant<Scalar_, Size_>::MaxColsAtCompileTime;
568template <typename Scalar_, int Size_>
569constexpr int Circulant<Scalar_, Size_>::SizeAtCompileTime;
570template <typename Scalar_, int Size_>
571constexpr int Circulant<Scalar_, Size_>::MaxSizeAtCompileTime;
572template <typename Scalar_, int Size_>
573constexpr bool Circulant<Scalar_, Size_>::IsRowMajor;
574#endif
575
576} // namespace Eigen
577
578#endif // EIGEN_STRUCTURED_CIRCULANT_H
An n x n circulant matrix represented by its first column.
Definition Circulant.h:103
Circulant(const MatrixBase< Derived > &col)
Definition Circulant.h:131
ComplexVector eigenvalues() const
Definition Circulant.h:326
const GeneratorType & column() const
Definition Circulant.h:144
Circulant transpose() const
Definition Circulant.h:163
ComplexMatrix matrixV() const
Definition Circulant.h:375
Index rank() const
Definition Circulant.h:279
Circulant conjugate() const
Definition Circulant.h:175
Circulant inverse() const
Definition Circulant.h:289
ComplexVector symbol() const
Definition Circulant.h:150
Circulant adjoint() const
Definition Circulant.h:184
Scalar coeff(Index row, Index col) const
Definition Circulant.h:153
ComplexMatrix eigenvectors() const
Definition Circulant.h:332
ComplexMatrix matrixU() const
Definition Circulant.h:357
Matrix< Scalar, Size_, Rhs::ColsAtCompileTime > solve(const MatrixBase< Rhs > &b) const
Definition Circulant.h:261
Scalar determinant() const
Definition Circulant.h:313
Product< Circulant, Rhs > operator*(const MatrixBase< Rhs > &x) const
Definition Circulant.h:250
RealVector singularValues() const
Definition Circulant.h:345
Derived & setZero(Index rows, Index cols)
Circulant< typename Derived::Scalar, Derived::SizeAtCompileTime > makeCirculant(const MatrixBase< Derived > &col)
Definition Circulant.h:546
Namespace containing all symbols from the Eigen library.