105 using Scalar = Scalar_;
107 using StorageIndex = int;
108 using Complex = std::complex<RealScalar>;
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;
130 template <
typename Derived>
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);
140 EIGEN_DEVICE_FUNC Index rows()
const {
return m_col.size(); }
141 EIGEN_DEVICE_FUNC Index cols()
const {
return m_col.size(); }
144 const GeneratorType&
column()
const {
return m_col; }
150 ComplexVector
symbol()
const {
return m_symbol.size() > 0 ? m_symbol : computeSymbol(); }
155 if (k < 0) k += rows();
156 return m_col.coeff(k);
164 const Index n = rows();
165 GeneratorType col(n);
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));
176 return Circulant(m_col.conjugate(), internal::structured_reverse_symbol(m_symbol).conjugate(),
177 internal::structured_reverse_symbol(m_prodSymbol).conjugate());
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());
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();
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);
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();
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);
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();
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);
249 template <
typename Rhs>
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));
269 internal::structured_fft_apply(x, sinv, n, b.derived(), Scalar(1));
280 const ComplexVector s =
symbol();
281 const RealVector mods = s.cwiseAbs();
282 return (!(mods.array() < internal::structured_rank_threshold(s, mods))).count();
290 const Index n = rows();
291 const ComplexVector sinv =
symbol().cwiseInverse();
292 GeneratorType col(n);
294 col = internal::structured_scalar_part_impl<Scalar>::run(sinv);
296 auto&& fft = internal::structured_fft_engine<RealScalar>();
298 fft.inv(ct, sinv, n);
299 col = internal::structured_scalar_part_impl<Scalar>::run(ct);
301 return Circulant(col, n > internal::structured_direct_threshold() ? sinv : ComplexVector(),
302 n > internal::structured_direct_threshold() ? computeProdSymbol(col) : ComplexVector());
314 const ComplexVector s =
symbol();
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));
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);
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]];
358 const Index n = rows();
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;
376 const Index n = rows();
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);
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);
400 const ComplexVector& s = m_prodSymbol.size() > 0 ? m_prodSymbol : m_symbol;
401 internal::structured_fft_apply(dst, s, n, rhs, alpha);
410 Circulant(
const GeneratorType& col,
const ComplexVector&
symbol,
const ComplexVector& prodSymbol)
411 : m_col(col), m_symbol(
symbol), m_prodSymbol(prodSymbol) {}
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>();
431 auto&& fft = internal::structured_fft_engine<RealScalar>();
432 fft.fwd(
symbol, embedding, p);
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();
444 const bool unitAlpha = alpha == ProductScalar(1);
445 if (n <= internal::structured_scalar_threshold()) {
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);
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);
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);
488 std::vector<Index> svdOrdering(ComplexVector& s, RealVector& mods)
const {
489 const Index n = rows();
491 EIGEN_IF_CONSTEXPR (!NumTraits<Scalar>::IsComplex) {
492 const Index pairs = (n - 1) / 2;
494 mods.head(n - pairs) = s.head(n - pairs).cwiseAbs();
495 mods.tail(pairs) = mods.segment(1, pairs).reverse();
499 return internal::structured_svd_permutation(mods);
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));
514 void fourierColumn(ComplexMatrix& F,
const ComplexVector& roots,
Index k,
Index dstCol)
const {
515 const Index n = rows();
517 for (
Index j = 0; j < n; ++j) {
518 F(j, dstCol) = roots[jk];
520 if (jk >= n) jk -= n;
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;
530 auto&& fft = internal::structured_fft_engine<RealScalar>();
536 ComplexVector m_symbol;
539 ComplexVector m_prodSymbol;