Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
ComplexSchur.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2009 Claire Maurice
5// Copyright (C) 2009 Gael Guennebaud <gael.guennebaud@inria.fr>
6// Copyright (C) 2010,2012 Jitse Niesen <jitse@maths.leeds.ac.uk>
7//
8// This Source Code Form is subject to the terms of the Mozilla
9// Public License v. 2.0. If a copy of the MPL was not distributed
10// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
11// SPDX-License-Identifier: MPL-2.0
12
13#ifndef EIGEN_COMPLEX_SCHUR_H
14#define EIGEN_COMPLEX_SCHUR_H
15
16#include "./HessenbergDecomposition.h"
17
18// IWYU pragma: private
19#include "./InternalHeaderCheck.h"
20
21namespace Eigen {
22
23namespace internal {
24template <typename MatrixType, bool IsComplex>
25struct complex_schur_reduce_to_hessenberg;
26}
27
28template <typename MatrixType_>
30
59template <typename MatrixType_>
61 public:
62 using MatrixType = MatrixType_;
63 enum {
64 RowsAtCompileTime = MatrixType::RowsAtCompileTime,
65 ColsAtCompileTime = MatrixType::ColsAtCompileTime,
66 Options = internal::plain_object_options<MatrixType>::value,
67 MaxRowsAtCompileTime = MatrixType::MaxRowsAtCompileTime,
68 MaxColsAtCompileTime = MatrixType::MaxColsAtCompileTime
69 };
70
72 using Scalar = typename MatrixType::Scalar;
73 using RealScalar = typename NumTraits<Scalar>::Real;
74 using Index = Eigen::Index;
75
82 using ComplexScalar = internal::make_complex_t<Scalar>;
83
91
96 using MatrixTType = std::conditional_t<internal::is_ref<MatrixType>::value, MatrixType, ComplexMatrixType>;
97
109 explicit ComplexSchur(Index size = RowsAtCompileTime == Dynamic ? 1 : RowsAtCompileTime)
110 : m_matT(size, size),
111 m_matU(size, size),
112 m_hess(size),
113 m_isInitialized(false),
114 m_matUisUptodate(false),
115 m_maxIters(-1) {}
116
126 template <typename InputType>
127 explicit ComplexSchur(const EigenBase<InputType>& matrix, bool computeU = true)
128 : m_matT(matrix.rows(), matrix.cols()),
129 m_matU(matrix.rows(), matrix.cols()),
130 m_hess(matrix.rows()),
131 m_isInitialized(false),
132 m_matUisUptodate(false),
133 m_maxIters(-1) {
134 compute(matrix.derived(), computeU);
135 }
136
146 template <typename InputType, bool IsRef = internal::is_ref<MatrixType>::value, std::enable_if_t<IsRef, int> = 0>
147 explicit ComplexSchur(EigenBase<InputType>& matrix, bool computeU = true)
148 : m_matT(matrix.derived()),
149 m_matU(matrix.rows(), matrix.cols()),
150 m_hess(matrix.rows()),
151 m_isInitialized(false),
152 m_matUisUptodate(false),
153 m_maxIters(-1) {
154 computeInPlace(computeU);
155 }
156
171 const ComplexMatrixType& matrixU() const {
172 eigen_assert(m_isInitialized && "ComplexSchur is not initialized.");
173 eigen_assert(m_matUisUptodate && "The matrix U has not been computed during the ComplexSchur decomposition.");
174 return m_matU;
175 }
176
194 const MatrixTType& matrixT() const {
195 eigen_assert(m_isInitialized && "ComplexSchur is not initialized.");
196 return m_matT;
197 }
198
220 template <typename InputType>
221 ComplexSchur& compute(const EigenBase<InputType>& matrix, bool computeU = true);
222
240 template <typename HessMatrixType, typename OrthMatrixType>
241 ComplexSchur& computeFromHessenberg(const HessMatrixType& matrixH, const OrthMatrixType& matrixQ,
242 bool computeU = true);
243
249 eigen_assert(m_isInitialized && "ComplexSchur is not initialized.");
250 return m_info;
251 }
252
259 m_maxIters = maxIters;
260 return *this;
261 }
262
264 Index getMaxIterations() const { return m_maxIters; }
265
271 static const int m_maxIterationsPerRow = 30;
272
273 protected:
274 EIGEN_STATIC_ASSERT(NumTraits<Scalar>::IsComplex || !internal::is_ref<MatrixType>::value,
275 INPLACE_COMPLEXSCHUR_REQUIRES_A_COMPLEX_MATRIX_TYPE)
276
277 MatrixTType m_matT;
278 ComplexMatrixType m_matU;
279 internal::complex_schur_reduce_to_hessenberg<MatrixType, NumTraits<Scalar>::IsComplex> m_hess;
280 ComputationInfo m_info;
281 bool m_isInitialized;
282 bool m_matUisUptodate;
283 Index m_maxIters;
284
285 private:
286 // ComplexEigenSolver computes the eigenvectors of T within this storage.
287 friend class ComplexEigenSolver<MatrixType>;
288
289 ComplexSchur& computeInPlace(bool computeU);
290 bool subdiagonalEntryIsNeglegible(Index i);
291 ComplexScalar computeShift(Index iu, Index iter);
292 void reduceToTriangularForm(bool computeU);
293 friend struct internal::complex_schur_reduce_to_hessenberg<MatrixType, NumTraits<Scalar>::IsComplex>;
294};
295
299template <typename MatrixType>
300inline bool ComplexSchur<MatrixType>::subdiagonalEntryIsNeglegible(Index i) {
301 RealScalar d = numext::norm1(m_matT.coeff(i, i)) + numext::norm1(m_matT.coeff(i + 1, i + 1));
302 RealScalar sd = numext::norm1(m_matT.coeff(i + 1, i));
303 if (internal::isMuchSmallerThan(sd, d, NumTraits<RealScalar>::epsilon())) {
304 m_matT.coeffRef(i + 1, i) = ComplexScalar(0);
305 return true;
306 }
307 return false;
308}
309
311template <typename MatrixType>
312typename ComplexSchur<MatrixType>::ComplexScalar ComplexSchur<MatrixType>::computeShift(Index iu, Index iter) {
313 if ((iter == 10 || iter == 20) && iu > 1) {
314 // exceptional shift, taken from http://www.netlib.org/eispack/comqr.f
315 return ComplexSchur<MatrixType>::ComplexScalar(numext::abs(numext::real(m_matT.coeff(iu, iu - 1))) +
316 numext::abs(numext::real(m_matT.coeff(iu - 1, iu - 2))));
317 }
318
319 // compute the shift as one of the eigenvalues of t, the 2x2
320 // diagonal block on the bottom of the active submatrix
321 Matrix<ComplexScalar, 2, 2> t = m_matT.template block<2, 2>(iu - 1, iu - 1);
322 const RealScalar normt = t.cwiseAbs().sum();
323 const auto factors = internal::safe_scaling<RealScalar>::scale_to(t, t, normt);
324
325 ComplexScalar b = t.coeff(0, 1) * t.coeff(1, 0);
326 ComplexScalar c = t.coeff(0, 0) - t.coeff(1, 1);
327 ComplexScalar disc = numext::sqrt(c * c + RealScalar(4) * b);
328 ComplexScalar det = t.coeff(0, 0) * t.coeff(1, 1) - b;
329 ComplexScalar trace = t.coeff(0, 0) + t.coeff(1, 1);
330 ComplexScalar eival1 = (trace + disc) / RealScalar(2);
331 ComplexScalar eival2 = (trace - disc) / RealScalar(2);
332 RealScalar eival1_norm = numext::norm1(eival1);
333 RealScalar eival2_norm = numext::norm1(eival2);
334 // A division by zero can only occur if eival1==eival2==0.
335 // In this case, det==0, and all we have to do is checking that eival2_norm!=0
336 if (eival1_norm > eival2_norm)
337 eival2 = det / eival1;
338 else if (!numext::is_exactly_zero(eival2_norm))
339 eival1 = det / eival2;
340
341 // choose the eigenvalue closest to the bottom entry of the diagonal
342 ComplexScalar shift = numext::norm1(eival1 - t.coeff(1, 1)) < numext::norm1(eival2 - t.coeff(1, 1)) ? eival1 : eival2;
343 internal::safe_scaling<RealScalar>::unscale_in_place(shift, factors);
344 return shift;
345}
346
347template <typename MatrixType>
348template <typename InputType>
349ComplexSchur<MatrixType>& ComplexSchur<MatrixType>::compute(const EigenBase<InputType>& matrix, bool computeU) {
350 m_matUisUptodate = false;
351 EIGEN_INTERNAL_ASSERT_SQUARE(matrix);
352
353 if (matrix.cols() <= 1) {
354 m_matT = matrix.derived().template cast<ComplexScalar>();
355 if (computeU) m_matU = ComplexMatrixType::Identity(matrix.rows(), matrix.cols());
356 m_info = Success;
357 m_isInitialized = true;
358 m_matUisUptodate = computeU;
359 return *this;
360 }
361
362 // Reduce to Hessenberg form at unit scale, as RealSchur does: HessenbergDecomposition treats a subdiagonal tail
363 // whose squared norm underflows as already zero, so an unscaled matrix near the bottom of the exponent range loses
364 // its whole subdiagonal. For binary scalars the scale is the power of two just below the largest real or imaginary
365 // part, clamped so that it and its reciprocal are normal; the modulus of a finite coefficient can overflow. When
366 // maxCoeff < min/eps, both steps round through integer significands, which FTZ/DAZ and ARMv7 NEON cannot flush. A
367 // scale above one underflows coefficients more than the exponent range below the largest one, a perturbation bounded
368 // by the smallest subnormal relative to that largest coefficient. maxCoeff propagates NaN; a zero or non-finite
369 // maxCoeff carries no usable exponent and is left unscaled.
370 const RealScalar maxCoeff = internal::safe_scaling<RealScalar>::max_abs_component(matrix.derived());
371 const internal::safe_scaling_factors<RealScalar> factors = internal::safe_scaling<RealScalar>::with_scaled(
372 matrix.derived(), maxCoeff, [&](const auto& scaled) { m_hess.run(*this, scaled, computeU); });
373 computeFromHessenberg(m_matT, m_matU, computeU);
374 // m_matU is unitary either way; only the triangular factor carries the scale.
375 internal::safe_scaling<RealScalar>::unscale_in_place(m_matT, maxCoeff, factors);
376 return *this;
377}
378
380template <typename MatrixType>
382 m_matUisUptodate = false;
383 EIGEN_INTERNAL_ASSERT_SQUARE(m_matT);
384
385 if (m_matT.cols() <= 1) {
386 if (computeU) m_matU = ComplexMatrixType::Identity(m_matT.rows(), m_matT.cols());
387 m_info = Success;
388 m_isInitialized = true;
389 m_matUisUptodate = computeU;
390 return *this;
391 }
392
393 const RealScalar maxCoeff = internal::safe_scaling<RealScalar>::max_abs_component(m_matT);
394 const internal::safe_scaling_factors<RealScalar> factors =
395 internal::safe_scaling<RealScalar>::scale_in_place(m_matT, maxCoeff);
396 m_hess.runInPlace(*this, computeU);
397 computeFromHessenberg(m_matT, m_matU, computeU);
398 internal::safe_scaling<RealScalar>::unscale_in_place(m_matT, maxCoeff, factors);
399 return *this;
400}
401
402template <typename MatrixType>
403template <typename HessMatrixType, typename OrthMatrixType>
405 const OrthMatrixType& matrixQ,
406 bool computeU) {
407 if (!internal::is_same_dense(m_matT, matrixH)) m_matT = matrixH;
408 if (computeU && !internal::is_same_dense(m_matU, matrixQ)) m_matU = matrixQ;
409 reduceToTriangularForm(computeU);
410 return *this;
411}
412namespace internal {
413
414/* Reduce given matrix to Hessenberg form, and hold the workspace this takes. */
415template <typename MatrixType, bool IsComplex>
416struct complex_schur_reduce_to_hessenberg {
417 // this is the implementation for the case IsComplex = true: the reduction runs in place in m_matT.
418 using Schur = ComplexSchur<MatrixType>;
419 using Scalar = typename Schur::ComplexScalar;
420 using CoeffVectorType = Matrix<Scalar, Schur::RowsAtCompileTime == Dynamic ? Dynamic : Schur::RowsAtCompileTime - 1,
421 1, Schur::Options & ~RowMajor,
422 Schur::MaxRowsAtCompileTime == Dynamic ? Dynamic : Schur::MaxRowsAtCompileTime - 1, 1>;
423 using WorkspaceType =
424 Matrix<Scalar, Schur::ColsAtCompileTime, 1, Schur::Options & ~RowMajor, Schur::MaxColsAtCompileTime, 1>;
425
426 explicit complex_schur_reduce_to_hessenberg(Index size) : m_workspace(size) {
427 if (size > 1) m_hCoeffs.resize(size - 1);
428 }
429
430 template <typename InputType>
431 void run(Schur& _this, const InputType& matrix, bool computeU) {
432 _this.m_matT = matrix;
433 runInPlace(_this, computeU);
434 }
435
436 void runInPlace(Schur& _this, bool computeU) {
437 hessenberg_decomposition_inplace(_this.m_matT, m_hCoeffs, m_workspace, _this.m_matU, computeU);
438 }
439
440 CoeffVectorType m_hCoeffs;
441 WorkspaceType m_workspace;
442};
443
444template <typename MatrixType>
445struct complex_schur_reduce_to_hessenberg<MatrixType, false> {
446 using Schur = ComplexSchur<MatrixType>;
447
448 explicit complex_schur_reduce_to_hessenberg(Index size) : m_hess(size) {}
449
450 template <typename InputType>
451 void run(Schur& _this, const InputType& matrix, bool computeU) {
452 using ComplexScalar = typename Schur::ComplexScalar;
453
454 // Note: m_hess is over RealScalar; m_matT and m_matU is over ComplexScalar
455 m_hess.compute(matrix);
456 _this.m_matT = m_hess.matrixH().template cast<ComplexScalar>();
457 if (computeU) {
458 // TODO: this temporary allocation could potentially be avoided.
459 MatrixType Q = m_hess.matrixQ();
460 _this.m_matU = Q.template cast<ComplexScalar>();
461 }
462 }
463
464 HessenbergDecomposition<MatrixType> m_hess;
465};
466
467} // end namespace internal
468
469// Reduce the Hessenberg matrix m_matT to triangular form by QR iteration.
470template <typename MatrixType>
472 Index maxIters = m_maxIters;
473 if (maxIters == -1) maxIters = m_maxIterationsPerRow * m_matT.rows();
474
475 // The matrix m_matT is divided in three parts.
476 // Rows 0,...,il-1 are decoupled from the rest because m_matT(il,il-1) is zero.
477 // Rows il,...,iu is the part we are working on (the active submatrix).
478 // Rows iu+1,...,end are already brought in triangular form.
479 Index iu = m_matT.cols() - 1;
480 Index il;
481 Index iter = 0; // number of iterations we are working on the (iu,iu) element
482 Index totalIter = 0; // number of iterations for whole matrix
483
484 while (true) {
485 // find iu, the bottom row of the active submatrix
486 while (iu > 0) {
487 if (!subdiagonalEntryIsNeglegible(iu - 1)) break;
488 iter = 0;
489 --iu;
490 }
491
492 // if iu is zero then we are done; the whole matrix is triangularized
493 if (iu == 0) break;
494
495 // if we spent too many iterations, we give up
496 iter++;
497 totalIter++;
498 if (totalIter > maxIters) break;
499
500 // find il, the top row of the active submatrix
501 il = iu - 1;
502 while (il > 0 && !subdiagonalEntryIsNeglegible(il - 1)) {
503 --il;
504 }
505
506 /* perform the QR step using Givens rotations. The first rotation
507 creates a bulge; the (il+2,il) element becomes nonzero. This
508 bulge is chased down to the bottom of the active submatrix. */
509
510 ComplexScalar shift = computeShift(iu, iter);
511 JacobiRotation<ComplexScalar> rot;
512 rot.makeGivens(m_matT.coeff(il, il) - shift, m_matT.coeff(il + 1, il));
513 m_matT.rightCols(m_matT.cols() - il).applyOnTheLeft(il, il + 1, rot.adjoint());
514 m_matT.topRows((std::min)(il + 2, iu) + 1).applyOnTheRight(il, il + 1, rot);
515 if (computeU) m_matU.applyOnTheRight(il, il + 1, rot);
516
517 for (Index i = il + 1; i < iu; i++) {
518 rot.makeGivens(m_matT.coeffRef(i, i - 1), m_matT.coeffRef(i + 1, i - 1), &m_matT.coeffRef(i, i - 1));
519 m_matT.coeffRef(i + 1, i - 1) = ComplexScalar(0);
520 m_matT.rightCols(m_matT.cols() - i).applyOnTheLeft(i, i + 1, rot.adjoint());
521 m_matT.topRows((std::min)(i + 2, iu) + 1).applyOnTheRight(i, i + 1, rot);
522 if (computeU) m_matU.applyOnTheRight(i, i + 1, rot);
523 }
524 }
525
526 if (totalIter <= maxIters)
527 m_info = Success;
528 else
529 m_info = NoConvergence;
530
531 m_isInitialized = true;
532 m_matUisUptodate = computeU;
533}
534
535} // end namespace Eigen
536
537#endif // EIGEN_COMPLEX_SCHUR_H
Computes eigenvalues and eigenvectors of general complex matrices.
Definition ComplexEigenSolver.h:50
ComputationInfo info() const
Reports whether previous computation was successful.
Definition ComplexSchur.h:248
Eigen::Index Index
Definition ComplexSchur.h:74
std::conditional_t< internal::is_ref< MatrixType >::value, MatrixType, ComplexMatrixType > MatrixTType
Type of the matrix returned by matrixT().
Definition ComplexSchur.h:96
ComplexSchur(Index size=RowsAtCompileTime==Dynamic ? 1 :RowsAtCompileTime)
Default constructor.
Definition ComplexSchur.h:109
const MatrixTType & matrixT() const
Returns the triangular matrix in the Schur decomposition.
Definition ComplexSchur.h:194
Matrix< ComplexScalar, RowsAtCompileTime, ColsAtCompileTime, Options, MaxRowsAtCompileTime, MaxColsAtCompileTime > ComplexMatrixType
Type for the matrices in the Schur decomposition.
Definition ComplexSchur.h:89
typename MatrixType::Scalar Scalar
Scalar type for matrices of type MatrixType_.
Definition ComplexSchur.h:72
ComplexSchur & computeFromHessenberg(const HessMatrixType &matrixH, const OrthMatrixType &matrixQ, bool computeU=true)
Compute Schur decomposition from a given Hessenberg matrix.
Index getMaxIterations() const
Returns the maximum number of iterations.
Definition ComplexSchur.h:264
static const int m_maxIterationsPerRow
Definition ComplexSchur.h:271
internal::make_complex_t< Scalar > ComplexScalar
Complex scalar type for MatrixType_.
Definition ComplexSchur.h:82
ComplexSchur(const EigenBase< InputType > &matrix, bool computeU=true)
Constructor; computes Schur decomposition of given matrix.
Definition ComplexSchur.h:127
ComplexSchur(EigenBase< InputType > &matrix, bool computeU=true)
Constructor for inplace decomposition .
Definition ComplexSchur.h:147
ComplexSchur & compute(const EigenBase< InputType > &matrix, bool computeU=true)
Computes Schur decomposition of given matrix.
ComplexSchur & setMaxIterations(Index maxIters)
Sets the maximum number of iterations allowed.
Definition ComplexSchur.h:258
const ComplexMatrixType & matrixU() const
Returns the unitary matrix in the Schur decomposition.
Definition ComplexSchur.h:171
The matrix class, also used for vectors and row-vectors.
Definition Matrix.h:188
ComputationInfo
Definition Constants.h:455
@ Success
Definition Constants.h:457
@ NoConvergence
Definition Constants.h:461
Definition EigenBase.h:34
constexpr Derived & derived()
Definition EigenBase.h:50
Holds information about the various numeric (i.e. scalar) types allowed by Eigen.
Definition NumTraits.h:267