Eigen-Contrib  5.0.1-dev+master
 
Loading...
Searching...
No Matches
Hankel.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] G. H. Golub and C. F. Van Loan, "Matrix Computations", 4th ed., Johns
12// Hopkins University Press, 2013, chapter 4.7 (Toeplitz, Hankel and
13// related systems) and chapter 4.8 (fast products via circulant embedding
14// and the FFT).
15// [2] R. H. Chan and X.-Q. Jin, "An Introduction to Iterative Toeplitz
16// Solvers", SIAM, 2007 (a Hankel matrix is a column-reversed Toeplitz
17// matrix, so its products and solves reduce to the Toeplitz machinery).
18
19#ifndef EIGEN_STRUCTURED_HANKEL_H
20#define EIGEN_STRUCTURED_HANKEL_H
21
22// IWYU pragma: private
23#include "./InternalHeaderCheck.h"
24
25namespace Eigen {
26
27template <typename Scalar_, int Rows_ = Dynamic, int Cols_ = Dynamic>
28class Hankel;
29
30namespace internal {
31
32template <typename Scalar_, int Rows_, int Cols_>
33struct traits<Hankel<Scalar_, Rows_, Cols_>> {
34 using Scalar = Scalar_;
35 using StorageKind = Dense;
36 using XprKind = MatrixXpr;
37 using StorageIndex = int;
38 static constexpr int RowsAtCompileTime = Rows_;
39 static constexpr int ColsAtCompileTime = Cols_;
40 static constexpr int MaxRowsAtCompileTime = Rows_;
41 static constexpr int MaxColsAtCompileTime = Cols_;
42 // Deliberately no NestByRefBit: transpose(), conjugate() and adjoint() return
43 // owning temporaries, so Product must nest the operator by value for a
44 // delayed-evaluated product expression to keep its left factor alive. The copy
45 // is O(n), negligible against the O(n log n) product evaluation.
46 static constexpr unsigned int Flags = 0;
47};
48
49template <typename Scalar_, int Rows_, int Cols_>
50struct evaluator_traits<Hankel<Scalar_, Rows_, Cols_>> {
51 using Kind = IndexBased;
52 using Shape = StructuredShape;
53};
54
55} // namespace internal
56
101template <typename Scalar_, int Rows_, int Cols_>
102class Hankel : public EigenBase<Hankel<Scalar_, Rows_, Cols_>> {
103 public:
104 using Scalar = Scalar_;
105 using RealScalar = typename NumTraits<Scalar>::Real;
106 using StorageIndex = int;
107 using Complex = std::complex<RealScalar>;
108 using ColGeneratorType = Matrix<Scalar, Rows_, 1>;
109 using RowGeneratorType = Matrix<Scalar, Cols_, 1>;
110 using ComplexVector = Matrix<Complex, Dynamic, 1>;
111
112 static constexpr int RowsAtCompileTime = Rows_;
113 static constexpr int ColsAtCompileTime = Cols_;
114 static constexpr int MaxRowsAtCompileTime = Rows_;
115 static constexpr int MaxColsAtCompileTime = Cols_;
116 static constexpr int SizeAtCompileTime = internal::size_at_compile_time(Rows_, Cols_);
117 static constexpr int MaxSizeAtCompileTime = SizeAtCompileTime;
118 static constexpr bool IsRowMajor = false;
119 // Deliberately no IsVectorAtCompileTime: Ref<const Hankel>'s default StrideType
120 // argument reads it, so its absence makes internal::is_ref_compatible SFINAE to
121 // false and keeps the iterative solvers on their matrix-free path.
122
124 static constexpr int GenSizeAtCompileTime = (Rows_ == Dynamic || Cols_ == Dynamic) ? Dynamic : (Rows_ + Cols_ - 1);
125 using GeneratorType = Matrix<Scalar, GenSizeAtCompileTime, 1>;
126
135 template <typename ColDerived, typename RowDerived>
137 : m_rows(col.size()), m_cols(row.size()) {
138 EIGEN_STATIC_ASSERT_VECTOR_ONLY(ColDerived)
139 EIGEN_STATIC_ASSERT_VECTOR_ONLY(RowDerived)
140 const Index m = col.size(), n = row.size();
141 EIGEN_INTERNAL_ASSERT_NONEMPTY_SIZE_MSG(col, m, "Hankel generators must be non-empty");
142 EIGEN_INTERNAL_ASSERT_NONEMPTY_SIZE_MSG(row, n, "Hankel generators must be non-empty");
143 m_h.resize(m + n - 1);
144 m_h.head(m) = col;
145 if (n > 1) m_h.tail(n - 1) = row.tail(n - 1);
146 if (m > 1 && n > 1 && (m > internal::structured_direct_threshold() || n > internal::structured_direct_threshold()))
147 m_symbol = computeSymbol();
148 }
149
150 EIGEN_DEVICE_FUNC Index rows() const { return m_rows.value(); }
151 EIGEN_DEVICE_FUNC Index cols() const { return m_cols.value(); }
152
155 const GeneratorType& generator() const { return m_h; }
156
158 ColGeneratorType column() const { return m_h.head(rows()); }
159
161 RowGeneratorType lastRow() const { return m_h.segment(rows() - 1, cols()); }
162
168 ComplexVector symbol() const { return m_symbol.size() > 0 ? m_symbol : computeSymbol(); }
169
171 Scalar coeff(Index row, Index col) const { return m_h.coeff(row + col); }
172
178 Hankel<Scalar, Cols_, Rows_> transpose() const {
179 return Hankel<Scalar, Cols_, Rows_>(m_h, cols(), rows(), transposedSymbol());
180 }
181
185 Hankel conjugate() const {
186 return Hankel(m_h.conjugate(), rows(), cols(), internal::structured_reverse_symbol(m_symbol).conjugate());
187 }
188
192 Hankel<Scalar, Cols_, Rows_> adjoint() const { return conjugate().transpose(); }
193
199 ColGeneratorType c = m_h.segment(cols() - 1, rows());
200 RowGeneratorType r = m_h.head(cols()).reverse();
202 }
203
207 static constexpr int SolveRowsAtCompileTime = Cols_ != Dynamic ? Cols_ : Rows_;
208
216 template <typename Rhs>
218 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(*this, "Hankel::solve requires a square matrix");
219 EIGEN_INTERNAL_ASSERT_SOLVER_RHS_MSG(*this, b, false, "right-hand side has the wrong number of rows");
221 eigen_assert(levinson.info() == Success &&
222 "Hankel::solve: the Levinson recursion broke down; "
223 "use LookAheadLevinson on toToeplitz() for diagnostics");
224 return levinson.solve(b).colwise().reverse();
225 }
226
230 template <typename Dest>
231 void evalTo(Dest& dst) const {
232 EIGEN_IF_CONSTEXPR (Dest::IsRowMajor) {
233 for (Index i = 0; i < rows(); ++i) dst.row(i) = m_h.segment(i, cols()).transpose();
234 return;
235 }
236 for (Index j = 0; j < cols(); ++j) dst.col(j) = m_h.segment(j, rows());
237 }
238
240 template <typename Dest>
241 void addTo(Dest& dst) const {
242 EIGEN_IF_CONSTEXPR (Dest::IsRowMajor) {
243 for (Index i = 0; i < rows(); ++i) dst.row(i) += m_h.segment(i, cols()).transpose();
244 return;
245 }
246 for (Index j = 0; j < cols(); ++j) dst.col(j) += m_h.segment(j, rows());
247 }
248
250 template <typename Dest>
251 void subTo(Dest& dst) const {
252 EIGEN_IF_CONSTEXPR (Dest::IsRowMajor) {
253 for (Index i = 0; i < rows(); ++i) dst.row(i) -= m_h.segment(i, cols()).transpose();
254 return;
255 }
256 for (Index j = 0; j < cols(); ++j) dst.col(j) -= m_h.segment(j, rows());
257 }
258
263 template <typename Rhs>
265 return Product<Hankel, Rhs>(*this, x.derived());
266 }
267
276 template <typename Dest, typename Rhs, typename ProductScalar>
277 void addProduct(Dest& dst, const Rhs& rhs, const ProductScalar& alpha) const {
278 const Index m = rows(), n = cols();
279 EIGEN_INTERNAL_ASSERT_PRODUCT_SHAPE_MSG(*this, rhs, "invalid product: dimensions do not match");
280 const bool small = m == 1 || n == 1 ||
281 (m <= internal::structured_direct_threshold() && n <= internal::structured_direct_threshold());
282 if (small) {
283 directProduct(dst, rhs, alpha);
284 return;
285 }
286 internal::structured_fft_apply(dst, m_symbol, m, rhs.colwise().reverse(), alpha);
287 }
288
289 private:
290 template <typename OtherScalar, int OtherRows, int OtherCols>
291 friend class Hankel;
292
297 Hankel(const GeneratorType& h, Index rows, Index cols, const ComplexVector& symbol)
298 : m_rows(rows), m_cols(cols), m_h(h), m_symbol(symbol) {}
299
304 template <typename Dest, typename Rhs, typename ProductScalar>
305 void directProductColumn(Dest& dst, const Rhs& rhs, Index k, const ProductScalar& alpha) const {
306 const Index m = rows(), n = cols();
307 // A unit alpha must not multiply: even the identity complex scalar (1,0)
308 // pollutes an (Inf,0) value with NaN through the 0*Inf cross term.
309 const bool unitAlpha = alpha == ProductScalar(1);
310
311 if (n == 1) {
312 // The runtime-sized head keeps other fixed-size shapes well-formed.
313 const ProductScalar xj = unitAlpha ? ProductScalar(rhs.coeff(0, k)) : ProductScalar(alpha * rhs.coeff(0, k));
314 dst.col(k) += xj * m_h.head(m);
315 return;
316 }
317
318 if (m == 1) {
319 const ProductScalar acc = m_h.head(n).cwiseProduct(rhs.col(k)).sum();
320 dst.coeffRef(0, k) += unitAlpha ? acc : ProductScalar(alpha * acc);
321 return;
322 }
323
324 if (m <= internal::structured_scalar_threshold() && n <= internal::structured_scalar_threshold()) {
325 // Tiny sizes: a plain scalar loop beats the segment-based path below, whose
326 // per-segment setup dominates when segments hold only a few entries.
327 for (Index i = 0; i < m; ++i) {
328 ProductScalar acc(0);
329 for (Index j = 0; j < n; ++j) acc += coeff(i, j) * rhs.coeff(j, k);
330 dst.coeffRef(i, k) += unitAlpha ? acc : ProductScalar(alpha * acc);
331 }
332 return;
333 }
334
335 // Column j is the contiguous, vectorizable slice h[j..j+m-1].
336 auto dstCol = dst.col(k);
337 for (Index j = 0; j < n; ++j) {
338 const ProductScalar xj = unitAlpha ? ProductScalar(rhs.coeff(j, k)) : ProductScalar(alpha * rhs.coeff(j, k));
339 dstCol += xj * m_h.segment(j, m);
340 }
341 }
342
345 template <typename Dest, typename Rhs, typename ProductScalar>
346 void directProduct(Dest& dst, const Rhs& rhs, const ProductScalar& alpha) const {
347 for (Index k = 0; k < rhs.cols(); ++k) directProductColumn(dst, rhs, k, alpha);
348 }
349
353 ComplexVector computeSymbol() const {
354 const Index m = rows(), n = cols();
355 const Index p = internal::fft_next_good_size(m + n - 1);
356 ComplexVector embedding = ComplexVector::Zero(p);
357 embedding.head(m) = m_h.tail(m).template cast<Complex>(); // h[n-1 .. m+n-2]
358 embedding.tail(n - 1) = m_h.head(n - 1).template cast<Complex>();
359 if (p == 1) return embedding; // the DFT of a single sample is the identity
360 ComplexVector symbol(p);
361 auto&& fft = internal::structured_fft_engine<RealScalar>();
362 fft.fwd(symbol, embedding, p);
363 return symbol;
364 }
365
371 ComplexVector transposedSymbol() const {
372 ComplexVector sym = m_symbol;
373 const Index p = sym.size();
374 if (p > 0 && rows() != cols()) {
375 Index s = (rows() - cols()) % p;
376 if (s < 0) s += p;
377 // Contiguous real buffers let sin/cos use packets; complex component views
378 // alone have stride two and would force scalar trigonometric evaluation.
379 Array<RealScalar, 64, 1> angles, values;
380 Matrix<Complex, 64, 1> phases;
381 Index fs = 0; // f * s mod p
382 for (Index f = 0; f < p;) {
383 const Index count = numext::mini<Index>(64, p - f);
384 for (Index i = 0; i < count; ++i) {
385 angles[i] = RealScalar(2 * EIGEN_PI) * RealScalar(fs) / RealScalar(p);
386 fs += s;
387 if (fs >= p) fs -= p;
388 }
389 values.head(count) = angles.head(count).cos();
390 phases.head(count).real() = values.head(count);
391 values.head(count) = angles.head(count).sin();
392 phases.head(count).imag() = values.head(count);
393 sym.segment(f, count).array() *= phases.head(count).array();
394 f += count;
395 }
396 }
397 return sym;
398 }
399
400 // Empty (compile-time constant) when the corresponding dimension is fixed; the
401 // dimensions cannot be recovered from m_h alone, whose length is rows()+cols()-1.
402 internal::variable_if_dynamic<Index, RowsAtCompileTime> m_rows;
403 internal::variable_if_dynamic<Index, ColsAtCompileTime> m_cols;
404 GeneratorType m_h;
405 ComplexVector m_symbol;
406};
407
411template <typename ColDerived, typename RowDerived>
416
417namespace internal {
418
419// Single product specialization covering every product tag; see the note in
420// Circulant.h.
421template <typename Scalar_, int Rows_, int Cols_, typename Rhs, int ProductTag>
422struct generic_product_impl<Hankel<Scalar_, Rows_, Cols_>, Rhs, StructuredShape, DenseShape, ProductTag>
423 : structured_product_impl<Hankel<Scalar_, Rows_, Cols_>, Rhs> {};
424
425} // namespace internal
426
427#if EIGEN_COMP_CXXVER < 17
428template <typename Scalar_, int Rows_, int Cols_>
429constexpr int Hankel<Scalar_, Rows_, Cols_>::RowsAtCompileTime;
430template <typename Scalar_, int Rows_, int Cols_>
431constexpr int Hankel<Scalar_, Rows_, Cols_>::ColsAtCompileTime;
432template <typename Scalar_, int Rows_, int Cols_>
433constexpr int Hankel<Scalar_, Rows_, Cols_>::MaxRowsAtCompileTime;
434template <typename Scalar_, int Rows_, int Cols_>
435constexpr int Hankel<Scalar_, Rows_, Cols_>::MaxColsAtCompileTime;
436template <typename Scalar_, int Rows_, int Cols_>
437constexpr int Hankel<Scalar_, Rows_, Cols_>::SizeAtCompileTime;
438template <typename Scalar_, int Rows_, int Cols_>
439constexpr int Hankel<Scalar_, Rows_, Cols_>::MaxSizeAtCompileTime;
440template <typename Scalar_, int Rows_, int Cols_>
441constexpr bool Hankel<Scalar_, Rows_, Cols_>::IsRowMajor;
442template <typename Scalar_, int Rows_, int Cols_>
443constexpr int Hankel<Scalar_, Rows_, Cols_>::GenSizeAtCompileTime;
444template <typename Scalar_, int Rows_, int Cols_>
445constexpr int Hankel<Scalar_, Rows_, Cols_>::SolveRowsAtCompileTime;
446#endif
447
448} // namespace Eigen
449
450#endif // EIGEN_STRUCTURED_HANKEL_H
constexpr FixedSegmentReturnType< N >::Type tail(Index n=N)
An m x n Hankel matrix represented by its first column and last row.
Definition Hankel.h:102
Scalar coeff(Index row, Index col) const
Definition Hankel.h:171
Hankel(const MatrixBase< ColDerived > &col, const MatrixBase< RowDerived > &row)
Definition Hankel.h:136
ColGeneratorType column() const
Definition Hankel.h:158
Matrix< Scalar, SolveRowsAtCompileTime, Rhs::ColsAtCompileTime > solve(const MatrixBase< Rhs > &b) const
Definition Hankel.h:217
Toeplitz< Scalar, Rows_, Cols_ > toToeplitz() const
Definition Hankel.h:198
ComplexVector symbol() const
Definition Hankel.h:168
Hankel< Scalar, Cols_, Rows_ > adjoint() const
Definition Hankel.h:192
RowGeneratorType lastRow() const
Definition Hankel.h:161
Hankel< Scalar, Cols_, Rows_ > transpose() const
Definition Hankel.h:178
Hankel conjugate() const
Definition Hankel.h:185
Product< Hankel, Rhs > operator*(const MatrixBase< Rhs > &x) const
Definition Hankel.h:264
const GeneratorType & generator() const
Definition Hankel.h:155
Look-ahead Levinson direct solver for general Toeplitz systems.
Definition LookAheadLevinson.h:87
ComputationInfo info() const
Definition LookAheadLevinson.h:162
const Solve< LookAheadLevinson, Rhs > solve(const MatrixBase< Rhs > &b) const
An m x n Toeplitz matrix represented by its first column and row.
Definition Toeplitz.h:85
Hankel< typename ColDerived::Scalar, ColDerived::SizeAtCompileTime, RowDerived::SizeAtCompileTime > makeHankel(const MatrixBase< ColDerived > &col, const MatrixBase< RowDerived > &row)
Definition Hankel.h:412
Namespace containing all symbols from the Eigen library.