12#ifndef EIGEN_REAL_SCHUR_H
13#define EIGEN_REAL_SCHUR_H
15#include "./HessenbergDecomposition.h"
18#include "./InternalHeaderCheck.h"
22template <
typename MatrixType_>
61template <
typename MatrixType_>
64 using MatrixType = MatrixType_;
66 RowsAtCompileTime = MatrixType::RowsAtCompileTime,
67 ColsAtCompileTime = MatrixType::ColsAtCompileTime,
68 Options = internal::plain_object_options<MatrixType>::value,
69 MaxRowsAtCompileTime = MatrixType::MaxRowsAtCompileTime,
70 MaxColsAtCompileTime = MatrixType::MaxColsAtCompileTime
72 using Scalar =
typename MatrixType::Scalar;
73 using ComplexScalar = internal::make_complex_t<Scalar>;
95 explicit RealSchur(
Index size = RowsAtCompileTime == Dynamic ? 1 : RowsAtCompileTime)
98 m_workspaceVector(size),
99 m_isInitialized(false),
100 m_matUisUptodate(false),
102 if (size > 1) m_hCoeffs.resize(size - 1);
115 template <
typename InputType>
117 : m_matT(matrix.rows(), matrix.cols()),
118 m_matU(matrix.rows(), matrix.cols()),
119 m_workspaceVector(matrix.rows()),
120 m_isInitialized(false),
121 m_matUisUptodate(false),
143 template <typename InputType, bool IsRef = internal::is_ref<MatrixType>::value, std::enable_if_t<IsRef, int> = 0>
145 : m_matT(matrix.derived()),
146 m_matU(matrix.rows(), matrix.cols()),
147 m_workspaceVector(matrix.rows()),
148 m_isInitialized(false),
149 m_matUisUptodate(false),
166 eigen_assert(m_isInitialized &&
"RealSchur is not initialized.");
167 eigen_assert(m_matUisUptodate &&
"The matrix U has not been computed during the RealSchur decomposition.");
182 eigen_assert(m_isInitialized &&
"RealSchur is not initialized.");
210 template <
typename InputType>
235 template <
typename HessMatrixType,
typename OrthMatrixType>
242 eigen_assert(m_isInitialized &&
"RealSchur is not initialized.");
252 m_maxIters = maxIters;
270 using CoeffVectorType =
271 Matrix<Scalar, RowsAtCompileTime == Dynamic ? Dynamic : RowsAtCompileTime - 1, 1, Options &
~RowMajor,
272 MaxRowsAtCompileTime == Dynamic ? Dynamic : MaxRowsAtCompileTime - 1, 1>;
276 ColumnVectorType m_workspaceVector;
277 CoeffVectorType m_hCoeffs;
279 bool m_isInitialized;
280 bool m_matUisUptodate;
283 template <
typename TMatrix>
284 EIGEN_DONT_INLINE
RealSchur& computeFromHessenbergInPlace(TMatrix& matT,
bool computeU);
289 bool usePaddedWorkspace(
Index size)
const;
290 template <
typename TMatrix>
291 RealSchur& computeInPlace(TMatrix& matT,
bool computeU);
292 template <
typename TMatrix>
293 Scalar computeNormOfT(TMatrix& matT);
294 template <
typename TMatrix>
295 Index findSmallSubdiagEntry(TMatrix& matT,
Index iu,
const Scalar& considerAsZero);
296 template <
typename TMatrix>
297 void splitOffTwoRows(TMatrix& matT,
Index iu,
bool computeU,
const Scalar& exshift);
298 template <
typename TMatrix>
299 void computeShift(TMatrix& matT,
Index iu,
Index iter, Scalar& exshift, Vector3s& shiftInfo);
300 template <
typename TMatrix>
301 void initFrancisQRStep(TMatrix& matT,
Index il,
Index iu,
const Vector3s& shiftInfo,
Index& im,
302 Vector3s& firstHouseholderVector);
303 template <
typename TMatrix>
304 void performFrancisQRStep(TMatrix& matT,
Index il,
Index im,
Index iu,
bool computeU,
305 const Vector3s& firstHouseholderVector, Scalar* workspace);
308template <
typename MatrixType>
309template <
typename InputType>
311 EIGEN_INTERNAL_ASSERT_SQUARE(matrix);
312 const Index size = matrix.
rows();
313 if (usePaddedWorkspace(size)) {
314 WorkspaceMatrix storage(size + (MatrixType::IsRowMajor ? 0 : 1), size + (MatrixType::IsRowMajor ? 1 : 0));
315 auto matT = storage.topLeftCorner(size, size);
317 computeInPlace(matT, computeU);
319 if (!internal::is_same_dense(m_matT, matrix.
derived())) m_matT = matrix.
derived();
320 computeInPlace(m_matT, computeU);
325template <
typename MatrixType>
326bool RealSchur<MatrixType>::usePaddedWorkspace(Index size)
const {
329 const Index stride = internal::is_ref<MatrixType>::value ? m_matT.outerStride() : size;
330 bool usePadding = size >= 128 && (stride *
sizeof(Scalar)) % 1024 == 0;
331#ifdef EIGEN_NO_MALLOC
333#elif defined(EIGEN_RUNTIME_NO_MALLOC)
334 usePadding = usePadding && internal::is_malloc_allowed() && internal::is_free_allowed();
340template <
typename MatrixType>
341template <
typename TMatrix>
343 const Scalar considerAsZero = (std::numeric_limits<Scalar>::min)();
344 const Index n = matT.rows();
345 EIGEN_INTERNAL_ASSERT_SQUARE(matT);
347 const Scalar maxCoeff = n == 0 ? Scalar(0) : matT.cwiseAbs().template maxCoeff<
PropagateNaN>();
348 if (!(numext::isfinite)(maxCoeff)) {
349 if (!internal::is_same_dense(m_matT, matT)) m_matT = matT;
351 m_isInitialized =
true;
352 m_matUisUptodate =
false;
355 if (maxCoeff < considerAsZero) {
359 if (computeU) m_matU.setIdentity(n, n);
361 m_isInitialized =
true;
362 m_matUisUptodate = computeU;
365 const auto factors = internal::safe_scaling<Scalar>::scale_in_place(matT, maxCoeff);
368 internal::hessenberg_decomposition_inplace(matT, m_hCoeffs, m_workspaceVector, m_matU, computeU);
371 computeFromHessenbergInPlace(matT, computeU);
374 if (internal::is_same_dense(m_matT, matT))
375 internal::safe_scaling<Scalar>::unscale_in_place(matT, maxCoeff, factors);
377 internal::safe_scaling<Scalar>::unscale_to(m_matT, matT, maxCoeff, factors);
381template <
typename MatrixType>
382template <
typename HessMatrixType,
typename OrthMatrixType>
384 const OrthMatrixType& matrixQ,
bool computeU) {
385 const Index size = matrixH.rows();
386 m_workspaceVector.resize(size);
387 if (usePaddedWorkspace(size)) {
388 WorkspaceMatrix storage(size + (MatrixType::IsRowMajor ? 0 : 1), size + (MatrixType::IsRowMajor ? 1 : 0));
389 auto matT = storage.topLeftCorner(size, size);
391 if (computeU && !internal::is_same_dense(m_matU, matrixQ)) m_matU = matrixQ;
392 computeFromHessenbergInPlace(matT, computeU);
395 if (!internal::is_same_dense(m_matT, matrixH)) m_matT = matrixH;
396 if (computeU && !internal::is_same_dense(m_matU, matrixQ)) m_matU = matrixQ;
397 computeFromHessenbergInPlace(m_matT, computeU);
402template <
typename MatrixType>
403template <
typename TMatrix>
404RealSchur<MatrixType>& RealSchur<MatrixType>::computeFromHessenbergInPlace(TMatrix& matT,
bool computeU) {
405 Index maxIters = m_maxIters;
406 if (maxIters == -1) maxIters = m_maxIterationsPerRow * matT.rows();
407 Scalar* workspace = &m_workspaceVector.coeffRef(0);
413 Index iu = matT.cols() - 1;
417 Scalar norm = computeNormOfT(matT);
420 Scalar considerAsZero =
421 numext::maxi<Scalar>(norm * numext::abs2(NumTraits<Scalar>::epsilon()), (std::numeric_limits<Scalar>::min)());
423 if (!numext::is_exactly_zero(norm)) {
425 Index il = findSmallSubdiagEntry(matT, iu, considerAsZero);
430 matT.coeffRef(iu, iu) = matT.coeff(iu, iu) + exshift;
431 if (iu > 0) matT.coeffRef(iu, iu - 1) = Scalar(0);
434 }
else if (il == iu - 1)
436 splitOffTwoRows(matT, iu, computeU, exshift);
443 Vector3s firstHouseholderVector = Vector3s::Zero(), shiftInfo;
444 computeShift(matT, iu, iter, exshift, shiftInfo);
446 totalIter = totalIter + 1;
447 if (totalIter > maxIters)
break;
449 initFrancisQRStep(matT, il, iu, shiftInfo, im, firstHouseholderVector);
450 performFrancisQRStep(matT, il, im, iu, computeU, firstHouseholderVector, workspace);
454 if (totalIter <= maxIters)
459 m_isInitialized =
true;
460 m_matUisUptodate = computeU;
465template <
typename MatrixType>
466template <
typename TMatrix>
467inline typename MatrixType::Scalar RealSchur<MatrixType>::computeNormOfT(TMatrix& matT) {
468 return internal::hessenberg_abs_sum<Upper>(matT);
472template <
typename MatrixType>
473template <
typename TMatrix>
474inline Index RealSchur<MatrixType>::findSmallSubdiagEntry(TMatrix& matT, Index iu,
const Scalar& considerAsZero) {
477 Scalar s = numext::abs(matT.coeff(res - 1, res - 1)) + numext::abs(matT.coeff(res, res));
479 s = numext::maxi<Scalar>(s * NumTraits<Scalar>::epsilon(), considerAsZero);
481 if (numext::abs(matT.coeff(res, res - 1)) <= s)
break;
491#if EIGEN_GNUC_STRICT_AT_LEAST(10, 0, 0) && EIGEN_GNUC_STRICT_LESS_THAN(12, 0, 0) && defined(__AVX__)
492#define EIGEN_REALSCHUR_SPLIT_INLINE EIGEN_DONT_INLINE __attribute__((optimize("no-gcse-after-reload")))
494#define EIGEN_REALSCHUR_SPLIT_INLINE inline
498template <
typename MatrixType>
499template <
typename TMatrix>
500EIGEN_REALSCHUR_SPLIT_INLINE
void RealSchur<MatrixType>::splitOffTwoRows(TMatrix& matT, Index iu,
bool computeU,
501 const Scalar& exshift) {
502 const Index size = matT.cols();
506 Scalar p = Scalar(0.5) * (matT.coeff(iu - 1, iu - 1) - matT.coeff(iu, iu));
507 Scalar q = p * p + matT.coeff(iu, iu - 1) * matT.coeff(iu - 1, iu);
508 matT.coeffRef(iu, iu) += exshift;
509 matT.coeffRef(iu - 1, iu - 1) += exshift;
513 Scalar z = numext::sqrt(numext::abs(q));
516 rot.
makeGivens(p + z, matT.coeff(iu, iu - 1));
518 rot.makeGivens(p - z, matT.coeff(iu, iu - 1));
520 matT.rightCols(size - iu + 1).applyOnTheLeft(iu - 1, iu, rot.adjoint());
521 matT.topRows(iu + 1).applyOnTheRight(iu - 1, iu, rot);
522 matT.coeffRef(iu, iu - 1) = Scalar(0);
523 if (computeU) m_matU.applyOnTheRight(iu - 1, iu, rot);
526 if (iu > 1) matT.coeffRef(iu - 1, iu - 2) = Scalar(0);
529#undef EIGEN_REALSCHUR_SPLIT_INLINE
532template <
typename MatrixType>
533template <
typename TMatrix>
534inline void RealSchur<MatrixType>::computeShift(TMatrix& matT, Index iu, Index iter, Scalar& exshift,
535 Vector3s& shiftInfo) {
536 shiftInfo.coeffRef(0) = matT.coeff(iu, iu);
537 shiftInfo.coeffRef(1) = matT.coeff(iu - 1, iu - 1);
538 shiftInfo.coeffRef(2) = matT.coeff(iu, iu - 1) * matT.coeff(iu - 1, iu);
541 if (iter > 0 && iter % 16 == 0) {
543 if (iter % 32 != 0) {
544 exshift += shiftInfo.coeff(0);
545 matT.diagonal().head(iu + 1).array() -= shiftInfo.coeff(0);
546 Scalar s = numext::abs(matT.coeff(iu, iu - 1)) + numext::abs(matT.coeff(iu - 1, iu - 2));
547 shiftInfo.coeffRef(0) = Scalar(0.75) * s;
548 shiftInfo.coeffRef(1) = Scalar(0.75) * s;
549 shiftInfo.coeffRef(2) = Scalar(-0.4375) * s * s;
552 Scalar s = (shiftInfo.coeff(1) - shiftInfo.coeff(0)) / Scalar(2.0);
553 s = s * s + shiftInfo.coeff(2);
556 if (shiftInfo.coeff(1) < shiftInfo.coeff(0)) s = -s;
557 s = s + (shiftInfo.coeff(1) - shiftInfo.coeff(0)) / Scalar(2.0);
558 s = shiftInfo.coeff(0) - shiftInfo.coeff(2) / s;
560 matT.diagonal().head(iu + 1).array() -= s;
561 shiftInfo.setConstant(Scalar(0.964));
568template <
typename MatrixType>
569template <
typename TMatrix>
570inline void RealSchur<MatrixType>::initFrancisQRStep(TMatrix& matT, Index il, Index iu,
const Vector3s& shiftInfo,
571 Index& im, Vector3s& firstHouseholderVector) {
572 Vector3s& v = firstHouseholderVector;
574 for (im = iu - 2; im >= il; --im) {
575 const Scalar Tmm = matT.coeff(im, im);
576 const Scalar r = shiftInfo.coeff(0) - Tmm;
577 const Scalar s = shiftInfo.coeff(1) - Tmm;
578 v.coeffRef(0) = (r * s - shiftInfo.coeff(2)) / matT.coeff(im + 1, im) + matT.coeff(im, im + 1);
579 v.coeffRef(1) = matT.coeff(im + 1, im + 1) - Tmm - r - s;
580 v.coeffRef(2) = matT.coeff(im + 2, im + 1);
584 const Scalar lhs = matT.coeff(im, im - 1) * (numext::abs(v.coeff(1)) + numext::abs(v.coeff(2)));
585 const Scalar rhs = v.coeff(0) * (numext::abs(matT.coeff(im - 1, im - 1)) + numext::abs(Tmm) +
586 numext::abs(matT.coeff(im + 1, im + 1)));
587 if (numext::abs(lhs) < NumTraits<Scalar>::epsilon() * rhs)
break;
592template <
typename MatrixType>
593template <
typename TMatrix>
594inline void RealSchur<MatrixType>::performFrancisQRStep(TMatrix& matT, Index il, Index im, Index iu,
bool computeU,
595 const Vector3s& firstHouseholderVector, Scalar* workspace) {
596 eigen_assert(im >= il);
597 eigen_assert(im <= iu - 2);
599 const Index size = matT.cols();
605 constexpr Index WindowSize = 32;
606 constexpr bool deferLeft = !TMatrix::IsRowMajor && int(TMatrix::InnerStrideAtCompileTime) == 1;
607 Index windowK[WindowSize];
608 Scalar windowTau[WindowSize];
611 for (Index k0 = im; k0 <= iu - 2; k0 += WindowSize) {
612 const Index k1 = (std::min)(k0 + WindowSize, iu - 1);
613 const Index nearEnd = deferLeft ? (std::min)(size, k1 + 2) : size;
614 Index numDeferred = 0;
615 for (Index k = k0; k < k1; ++k) {
616 bool firstIteration = (k == im);
620 v = firstHouseholderVector;
622 v = matT.template block<3, 1>(k, k - 1);
626 v.makeHouseholder(ess, tau, beta);
628 if (!numext::is_exactly_zero(beta))
630 if (firstIteration && k > il)
631 matT.coeffRef(k, k - 1) = -matT.coeff(k, k - 1);
632 else if (!firstIteration)
633 matT.coeffRef(k, k - 1) = beta;
636 matT.block(k, k, 3, nearEnd - k).applyHouseholderOnTheLeft(ess, tau, workspace);
637 matT.block(0, k, (std::min)(iu, k + 3) + 1, 3).applyHouseholderOnTheRight(ess, tau, workspace);
638 if (computeU) m_matU.block(0, k, size, 3).applyHouseholderOnTheRight(ess, tau, workspace);
641 if (nearEnd < size && !numext::is_exactly_zero(tau)) {
642 windowK[numDeferred] = k;
643 windowTau[numDeferred] = tau;
644 windowEss[numDeferred] = ess;
651 constexpr Index ColumnGroup = 16;
652 for (Index j0 = nearEnd; j0 < size && numDeferred > 0; j0 += ColumnGroup) {
653 const Index j1 = (std::min)(j0 + ColumnGroup, size);
654 for (Index r = 0; r < numDeferred; ++r) {
655 const Index k = windowK[r];
656 const Scalar e0 = windowEss[r].coeff(0), e1 = windowEss[r].coeff(1), tau = windowTau[r];
657 for (Index j = j0; j < j1; ++j) {
659 Scalar* x = &matT.coeffRef(k, j);
660 const Scalar tmp = tau * ((e0 * x[1] + e1 * x[2]) + x[0]);
672 v.makeHouseholder(ess, tau, beta);
674 if (!numext::is_exactly_zero(beta))
676 matT.coeffRef(iu - 1, iu - 2) = beta;
677 matT.block(iu - 1, iu - 1, 2, size - iu + 1).applyHouseholderOnTheLeft(ess, tau, workspace);
678 matT.block(0, iu - 1, iu + 1, 2).applyHouseholderOnTheRight(ess, tau, workspace);
679 if (computeU) m_matU.block(0, iu - 1, size, 2).applyHouseholderOnTheRight(ess, tau, workspace);
683 for (Index i = im + 2; i <= iu; ++i) {
684 matT.coeffRef(i, i - 2) = Scalar(0);
685 if (i > im + 2) matT.coeffRef(i, i - 3) = Scalar(0);
Computes eigenvalues and eigenvectors of general matrices.
Definition EigenSolver.h:69
Rotation given by a cosine-sine pair.
Definition Jacobi.h:39
void makeGivens(const Scalar &p, const Scalar &q, Scalar *r=0)
Definition Jacobi.h:157
The matrix class, also used for vectors and row-vectors.
Definition Matrix.h:188
Performs a real Schur decomposition of a square matrix.
Definition RealSchur.h:62
Matrix< Scalar, RowsAtCompileTime, ColsAtCompileTime, Options, MaxRowsAtCompileTime, MaxColsAtCompileTime > MatrixUType
Type of the matrix returned by matrixU(): a plain matrix with the shape and storage options of Matrix...
Definition RealSchur.h:81
ComputationInfo info() const
Reports whether previous computation was successful.
Definition RealSchur.h:241
Eigen::Index Index
Definition RealSchur.h:74
RealSchur(Index size=RowsAtCompileTime==Dynamic ? 1 :RowsAtCompileTime)
Default constructor.
Definition RealSchur.h:95
RealSchur(EigenBase< InputType > &matrix, bool computeU=true)
Constructor for inplace decomposition .
Definition RealSchur.h:144
RealSchur(const EigenBase< InputType > &matrix, bool computeU=true)
Constructor; computes real Schur decomposition of given matrix.
Definition RealSchur.h:116
static const int m_maxIterationsPerRow
Maximum number of iterations per row.
Definition RealSchur.h:264
RealSchur & compute(const EigenBase< InputType > &matrix, bool computeU=true)
Computes Schur decomposition of given matrix.
Index getMaxIterations() const
Returns the maximum number of iterations.
Definition RealSchur.h:257
RealSchur & setMaxIterations(Index maxIters)
Sets the maximum number of iterations allowed.
Definition RealSchur.h:251
RealSchur & computeFromHessenberg(const HessMatrixType &matrixH, const OrthMatrixType &matrixQ, bool computeU)
Computes Schur decomposition of a Hessenberg matrix H = Z T Z^T.
const MatrixUType & matrixU() const
Returns the orthogonal matrix in the Schur decomposition.
Definition RealSchur.h:165
const MatrixType & matrixT() const
Returns the quasi-triangular matrix in the Schur decomposition.
Definition RealSchur.h:181
ComputationInfo
Definition Constants.h:455
@ PropagateNaN
Definition Constants.h:343
@ Success
Definition Constants.h:457
@ NoConvergence
Definition Constants.h:461
@ RowMajor
Definition Constants.h:321
Definition EigenBase.h:34
constexpr Derived & derived()
Definition EigenBase.h:50
constexpr Index rows() const noexcept
Definition EigenBase.h:60