Eigen-Contrib  5.0.1-dev+master
 
Loading...
Searching...
No Matches
Toeplitz.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] R. M. Gray, "Toeplitz and Circulant Matrices: A Review", Foundations and
12// Trends in Communications and Information Theory, 2(3), 2006.
13// [2] G. H. Golub and C. F. Van Loan, "Matrix Computations", 4th ed., Johns
14// Hopkins University Press, 2013, chapter 4.8 (fast Toeplitz products via
15// circulant embedding and the FFT).
16
17#ifndef EIGEN_STRUCTURED_TOEPLITZ_H
18#define EIGEN_STRUCTURED_TOEPLITZ_H
19
20// IWYU pragma: private
21#include "./InternalHeaderCheck.h"
22
23namespace Eigen {
24
25template <typename Scalar_, int Rows_ = Dynamic, int Cols_ = Dynamic>
26class Toeplitz;
27
28namespace internal {
29
30template <typename Scalar_, int Rows_, int Cols_>
31struct traits<Toeplitz<Scalar_, Rows_, Cols_>> {
32 using Scalar = Scalar_;
33 using StorageKind = Dense;
34 using XprKind = MatrixXpr;
35 using StorageIndex = int;
36 static constexpr int RowsAtCompileTime = Rows_;
37 static constexpr int ColsAtCompileTime = Cols_;
38 static constexpr int MaxRowsAtCompileTime = Rows_;
39 static constexpr int MaxColsAtCompileTime = Cols_;
40 // Deliberately no NestByRefBit: transpose(), conjugate() and adjoint() return
41 // owning temporaries, so Product must nest the operator by value for a
42 // delayed-evaluated product expression to keep its left factor alive. The copy
43 // is O(m+n), negligible against the O(n log n) product evaluation.
44 static constexpr int Flags = 0;
45};
46
47template <typename Scalar_, int Rows_, int Cols_>
48struct evaluator_traits<Toeplitz<Scalar_, Rows_, Cols_>> {
49 using Kind = IndexBased;
50 using Shape = StructuredShape;
51};
52
53} // namespace internal
54
84template <typename Scalar_, int Rows_, int Cols_>
85class Toeplitz : public EigenBase<Toeplitz<Scalar_, Rows_, Cols_>> {
86 public:
87 using Scalar = Scalar_;
88 using RealScalar = typename NumTraits<Scalar>::Real;
89 using StorageIndex = int;
90 using Complex = std::complex<RealScalar>;
91 using ColGeneratorType = Matrix<Scalar, Rows_, 1>;
92 using RowGeneratorType = Matrix<Scalar, Cols_, 1>;
93 using ComplexVector = Matrix<Complex, Dynamic, 1>;
94
95 static constexpr int RowsAtCompileTime = Rows_;
96 static constexpr int ColsAtCompileTime = Cols_;
97 static constexpr int MaxRowsAtCompileTime = Rows_;
98 static constexpr int MaxColsAtCompileTime = Cols_;
99 static constexpr int SizeAtCompileTime = internal::size_at_compile_time(Rows_, Cols_);
100 static constexpr int MaxSizeAtCompileTime = SizeAtCompileTime;
101 static constexpr bool IsRowMajor = false;
102 // Deliberately no IsVectorAtCompileTime: Ref<const Toeplitz>'s default StrideType
103 // argument reads it, so its absence makes internal::is_ref_compatible SFINAE to
104 // false and keeps the iterative solvers on their matrix-free path.
105
115 template <typename ColDerived, typename RowDerived>
116 Toeplitz(const MatrixBase<ColDerived>& col, const MatrixBase<RowDerived>& row) : m_col(col), m_row(row) {
117 EIGEN_STATIC_ASSERT_VECTOR_ONLY(ColDerived)
118 EIGEN_STATIC_ASSERT_VECTOR_ONLY(RowDerived)
119 EIGEN_INTERNAL_ASSERT_NONEMPTY_MSG(m_col, "Toeplitz generators must be non-empty");
120 EIGEN_INTERNAL_ASSERT_NONEMPTY_MSG(m_row, "Toeplitz generators must be non-empty");
121 // Below the threshold every product takes the direct path and the symbol has
122 // no consumer, so skip the embedding altogether.
123 if (rows() > internal::structured_direct_threshold() || cols() > internal::structured_direct_threshold())
124 m_symbol = computeSymbol();
125 }
126
127 EIGEN_DEVICE_FUNC Index rows() const { return m_col.size(); }
128 EIGEN_DEVICE_FUNC Index cols() const { return m_row.size(); }
129
131 const ColGeneratorType& column() const { return m_col; }
133 const RowGeneratorType& row() const { return m_row; }
134
139 ComplexVector symbol() const { return m_symbol.size() > 0 ? m_symbol : computeSymbol(); }
140
142 Scalar coeff(Index row, Index col) const {
143 Index k = row - col;
144 return k >= 0 ? m_col.coeff(k) : m_row.coeff(-k);
145 }
146
152 Toeplitz<Scalar, Cols_, Rows_> transpose() const {
153 using TransposeType = Toeplitz<Scalar, Cols_, Rows_>;
154 const Index n = cols();
155 typename TransposeType::ColGeneratorType col(n);
156 col[0] = m_col[0];
157 if (n > 1) col.tail(n - 1) = m_row.tail(n - 1);
158 return TransposeType(col, m_col, internal::structured_reverse_symbol(m_symbol));
159 }
160
164 Toeplitz conjugate() const {
165 return Toeplitz(m_col.conjugate(), m_row.conjugate(), internal::structured_reverse_symbol(m_symbol).conjugate());
166 }
167
171 Toeplitz<Scalar, Cols_, Rows_> adjoint() const {
172 using AdjointType = Toeplitz<Scalar, Cols_, Rows_>;
173 const Index n = cols();
174 typename AdjointType::ColGeneratorType col(n);
175 col[0] = numext::conj(m_col[0]);
176 if (n > 1) col.tail(n - 1) = m_row.tail(n - 1).conjugate();
177 return AdjointType(col, m_col.conjugate(), m_symbol.conjugate());
178 }
179
184 template <typename Dest>
185 void evalTo(Dest& dst) const {
186 const Index m = rows(), n = cols();
187 EIGEN_IF_CONSTEXPR (Dest::IsRowMajor) {
188 for (Index i = 0; i < m; ++i) {
189 const Index h = numext::mini(i + 1, n);
190 dst.row(i).head(h) = m_col.segment(i - h + 1, h).reverse().transpose();
191 if (i + 1 < n) dst.row(i).tail(n - i - 1) = m_row.segment(1, n - i - 1).transpose();
192 }
193 return;
194 }
195 for (Index j = 0; j < n; ++j) {
196 const Index h = numext::mini(j, m);
197 dst.col(j).head(h) = m_row.segment(j - h + 1, h).reverse();
198 if (j < m) dst.col(j).tail(m - j) = m_col.head(m - j);
199 }
200 }
201
203 template <typename Dest>
204 void addTo(Dest& dst) const {
205 const Index m = rows(), n = cols();
206 EIGEN_IF_CONSTEXPR (Dest::IsRowMajor) {
207 for (Index i = 0; i < m; ++i) {
208 const Index h = numext::mini(i + 1, n);
209 dst.row(i).head(h) += m_col.segment(i - h + 1, h).reverse().transpose();
210 if (i + 1 < n) dst.row(i).tail(n - i - 1) += m_row.segment(1, n - i - 1).transpose();
211 }
212 return;
213 }
214 for (Index j = 0; j < n; ++j) {
215 const Index h = numext::mini(j, m);
216 dst.col(j).head(h) += m_row.segment(j - h + 1, h).reverse();
217 if (j < m) dst.col(j).tail(m - j) += m_col.head(m - j);
218 }
219 }
220
222 template <typename Dest>
223 void subTo(Dest& dst) const {
224 const Index m = rows(), n = cols();
225 EIGEN_IF_CONSTEXPR (Dest::IsRowMajor) {
226 for (Index i = 0; i < m; ++i) {
227 const Index h = numext::mini(i + 1, n);
228 dst.row(i).head(h) -= m_col.segment(i - h + 1, h).reverse().transpose();
229 if (i + 1 < n) dst.row(i).tail(n - i - 1) -= m_row.segment(1, n - i - 1).transpose();
230 }
231 return;
232 }
233 for (Index j = 0; j < n; ++j) {
234 const Index h = numext::mini(j, m);
235 dst.col(j).head(h) -= m_row.segment(j - h + 1, h).reverse();
236 if (j < m) dst.col(j).tail(m - j) -= m_col.head(m - j);
237 }
238 }
239
245 template <typename Rhs>
247 return Product<Toeplitz, Rhs>(*this, x.derived());
248 }
249
253 template <typename Dest, typename Rhs, typename ProductScalar>
254 void addProduct(Dest& dst, const Rhs& rhs, const ProductScalar& alpha) const {
255 const Index m = rows(), n = cols();
256 EIGEN_INTERNAL_ASSERT_PRODUCT_SHAPE_MSG(*this, rhs, "invalid product: dimensions do not match");
257 const bool small = m <= internal::structured_direct_threshold() && n <= internal::structured_direct_threshold();
258 if (small)
259 directProduct(dst, rhs, alpha);
260 else
261 internal::structured_fft_apply(dst, m_symbol, m, rhs, alpha);
262 }
263
264 private:
265 // Grants transpose() and adjoint() access to the private constructor of the
266 // dimension-swapped instantiation.
267 template <typename OtherScalar, int OtherRows, int OtherCols>
268 friend class Toeplitz;
269
274 Toeplitz(const ColGeneratorType& col, const RowGeneratorType& row, const ComplexVector& symbol)
275 : m_col(col), m_row(row), m_symbol(symbol) {}
276
280 template <typename Dest, typename Rhs, typename ProductScalar>
281 void directProductColumn(Dest& dst, const Rhs& rhs, Index k, const ProductScalar& alpha) const {
282 const Index m = rows(), n = cols();
283 // A unit alpha must not multiply: even the identity complex scalar (1,0)
284 // pollutes an (Inf,0) value with NaN through the 0*Inf cross term.
285 const bool unitAlpha = alpha == ProductScalar(1);
286 if (m <= internal::structured_scalar_threshold() && n <= internal::structured_scalar_threshold()) {
287 // Tiny sizes: a plain scalar loop beats the segment-based path below, whose
288 // per-segment setup dominates when segments hold only a few entries.
289 for (Index i = 0; i < m; ++i) {
290 ProductScalar acc(0);
291 for (Index j = 0; j < n; ++j) acc += coeff(i, j) * rhs.coeff(j, k);
292 dst.coeffRef(i, k) += unitAlpha ? acc : ProductScalar(alpha * acc);
293 }
294 return;
295 }
296
297 // Split each column at its diagonal into contiguous generator slices.
298 auto dstCol = dst.col(k);
299 for (Index j = 0; j < n; ++j) {
300 const ProductScalar xj = unitAlpha ? ProductScalar(rhs.coeff(j, k)) : ProductScalar(alpha * rhs.coeff(j, k));
301 const Index h = numext::mini(j, m);
302 dstCol.head(h) += xj * m_row.segment(j - h + 1, h).reverse();
303 if (j < m) dstCol.tail(m - j) += xj * m_col.head(m - j);
304 }
305 }
306
309 template <typename Dest, typename Rhs, typename ProductScalar>
310 void directProduct(Dest& dst, const Rhs& rhs, const ProductScalar& alpha) const {
311 for (Index k = 0; k < rhs.cols(); ++k) directProductColumn(dst, rhs, k, alpha);
312 }
313
315 ComplexVector computeSymbol() const {
316 const Index m = rows(), n = cols();
317 const Index p = internal::fft_next_good_size(m + n - 1);
318 ComplexVector embedding = ComplexVector::Zero(p);
319 embedding.head(m) = m_col.template cast<Complex>();
320 embedding.tail(n - 1) = m_row.tail(n - 1).reverse().template cast<Complex>();
321 if (p == 1) return embedding; // the DFT of a single sample is the identity
322 ComplexVector symbol(p);
323 auto&& fft = internal::structured_fft_engine<RealScalar>();
324 fft.fwd(symbol, embedding, p);
325 return symbol;
326 }
327
328 ColGeneratorType m_col;
329 RowGeneratorType m_row;
330 ComplexVector m_symbol;
331};
332
336template <typename ColDerived, typename RowDerived>
341
342namespace internal {
343
344template <typename Scalar_, int Rows_, int Cols_, typename Rhs, int ProductTag>
345struct generic_product_impl<Toeplitz<Scalar_, Rows_, Cols_>, Rhs, StructuredShape, DenseShape, ProductTag>
346 : structured_product_impl<Toeplitz<Scalar_, Rows_, Cols_>, Rhs> {};
347
348} // namespace internal
349
350#if EIGEN_COMP_CXXVER < 17
351template <typename Scalar_, int Rows_, int Cols_>
352constexpr int Toeplitz<Scalar_, Rows_, Cols_>::RowsAtCompileTime;
353template <typename Scalar_, int Rows_, int Cols_>
354constexpr int Toeplitz<Scalar_, Rows_, Cols_>::ColsAtCompileTime;
355template <typename Scalar_, int Rows_, int Cols_>
356constexpr int Toeplitz<Scalar_, Rows_, Cols_>::MaxRowsAtCompileTime;
357template <typename Scalar_, int Rows_, int Cols_>
358constexpr int Toeplitz<Scalar_, Rows_, Cols_>::MaxColsAtCompileTime;
359template <typename Scalar_, int Rows_, int Cols_>
360constexpr int Toeplitz<Scalar_, Rows_, Cols_>::SizeAtCompileTime;
361template <typename Scalar_, int Rows_, int Cols_>
362constexpr int Toeplitz<Scalar_, Rows_, Cols_>::MaxSizeAtCompileTime;
363template <typename Scalar_, int Rows_, int Cols_>
364constexpr bool Toeplitz<Scalar_, Rows_, Cols_>::IsRowMajor;
365#endif
366
367} // namespace Eigen
368
369#endif // EIGEN_STRUCTURED_TOEPLITZ_H
An m x n Toeplitz matrix represented by its first column and row.
Definition Toeplitz.h:85
Toeplitz< Scalar, Cols_, Rows_ > transpose() const
Definition Toeplitz.h:152
Scalar coeff(Index row, Index col) const
Definition Toeplitz.h:142
Toeplitz(const MatrixBase< ColDerived > &col, const MatrixBase< RowDerived > &row)
Definition Toeplitz.h:116
Toeplitz< Scalar, Cols_, Rows_ > adjoint() const
Definition Toeplitz.h:171
ComplexVector symbol() const
Definition Toeplitz.h:139
Product< Toeplitz, Rhs > operator*(const MatrixBase< Rhs > &x) const
Definition Toeplitz.h:246
Toeplitz conjugate() const
Definition Toeplitz.h:164
const ColGeneratorType & column() const
Definition Toeplitz.h:131
const RowGeneratorType & row() const
Definition Toeplitz.h:133
Toeplitz< typename ColDerived::Scalar, ColDerived::SizeAtCompileTime, RowDerived::SizeAtCompileTime > makeToeplitz(const MatrixBase< ColDerived > &col, const MatrixBase< RowDerived > &row)
Definition Toeplitz.h:337
Namespace containing all symbols from the Eigen library.