Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
EigenSolver.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2008 Gael Guennebaud <gael.guennebaud@inria.fr>
5// Copyright (C) 2010,2012 Jitse Niesen <jitse@maths.leeds.ac.uk>
6//
7// This Source Code Form is subject to the terms of the Mozilla
8// Public License v. 2.0. If a copy of the MPL was not distributed
9// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
10// SPDX-License-Identifier: MPL-2.0
11
12#ifndef EIGEN_EIGENSOLVER_H
13#define EIGEN_EIGENSOLVER_H
14
15#include "./RealSchur.h"
16
17// IWYU pragma: private
18#include "./InternalHeaderCheck.h"
19
20namespace Eigen {
21
68template <typename MatrixType_>
70 public:
72 using MatrixType = MatrixType_;
73
74 enum {
75 RowsAtCompileTime = MatrixType::RowsAtCompileTime,
76 ColsAtCompileTime = MatrixType::ColsAtCompileTime,
77 Options = internal::plain_object_options<MatrixType>::value,
78 MaxRowsAtCompileTime = MatrixType::MaxRowsAtCompileTime,
79 MaxColsAtCompileTime = MatrixType::MaxColsAtCompileTime
80 };
81
83 using Scalar = typename MatrixType::Scalar;
84 using RealScalar = typename NumTraits<Scalar>::Real;
85 using Index = Eigen::Index;
86
91
98 using ComplexScalar = internal::make_complex_t<Scalar>;
99
106
114
122 EigenSolver() : m_eivalues(), m_isInitialized(false), m_eigenvectorsOk(false), m_realSchur(), m_tmp() {}
123
130 explicit EigenSolver(Index size)
131 : m_eivalues(size), m_isInitialized(false), m_eigenvectorsOk(false), m_realSchur(size), m_tmp(size) {}
132
148 template <typename InputType>
149 explicit EigenSolver(const EigenBase<InputType>& matrix, bool computeEigenvectors = true)
150 : m_eivalues(matrix.cols()),
151 m_isInitialized(false),
152 m_eigenvectorsOk(false),
153 m_realSchur(matrix.derived(), computeEigenvectors),
154 m_tmp(matrix.cols()) {
155 check_template_parameters();
156 computeFromSchur(computeEigenvectors);
157 }
158
170 template <typename InputType>
171 explicit EigenSolver(EigenBase<InputType>& matrix, bool computeEigenvectors = true)
172 : m_eivalues(matrix.cols()),
173 m_isInitialized(false),
174 m_eigenvectorsOk(false),
175 m_realSchur(matrix.derived(), computeEigenvectors),
176 m_tmp(matrix.cols()) {
177 check_template_parameters();
178 computeFromSchur(computeEigenvectors);
179 }
180
202
222 eigen_assert(m_isInitialized && "EigenSolver is not initialized.");
223 eigen_assert(m_eigenvectorsOk && "The eigenvectors have not been computed together with the eigenvalues.");
224 return m_realSchur.m_matU;
225 }
226
246
266 eigen_assert(m_isInitialized && "EigenSolver is not initialized.");
267 return m_eivalues;
268 }
269
297 template <typename InputType>
298 EigenSolver& compute(const EigenBase<InputType>& matrix, bool computeEigenvectors = true);
299
304 eigen_assert(m_isInitialized && "EigenSolver is not initialized.");
305 return m_info;
306 }
307
310 m_realSchur.setMaxIterations(maxIters);
311 return *this;
312 }
313
315 Index getMaxIterations() const { return m_realSchur.getMaxIterations(); }
316
317 private:
318 EigenSolver& computeFromSchur(bool computeEigenvectors);
319 void doComputeEigenvectors();
320
321 protected:
322 static void check_template_parameters() {
323 EIGEN_STATIC_ASSERT_NON_INTEGER(Scalar);
324 EIGEN_STATIC_ASSERT(!NumTraits<Scalar>::IsComplex, NUMERIC_TYPE_MUST_BE_REAL);
325 }
326
327 EigenvalueType m_eivalues;
328 bool m_isInitialized;
329 bool m_eigenvectorsOk;
330 ComputationInfo m_info;
331 // Holds the Schur form T and U of the last matrix; computing the eigenvectors overwrites T with the eigenvectors
332 // of T and U with the pseudo-eigenvectors.
333 RealSchur<MatrixType> m_realSchur;
334
335 using ColumnVectorType = Matrix<Scalar, ColsAtCompileTime, 1, Options & ~RowMajor, MaxColsAtCompileTime, 1>;
336 ColumnVectorType m_tmp;
337};
338
339template <typename MatrixType>
341 eigen_assert(m_isInitialized && "EigenSolver is not initialized.");
342 const RealScalar precision = RealScalar(2) * NumTraits<RealScalar>::epsilon();
343 const Index n = m_eivalues.rows();
344 PlainMatrixType matD = PlainMatrixType::Zero(n, n);
345 Index i = 0;
346 for (; i < n - 1; ++i) {
347 RealScalar real = numext::real(m_eivalues.coeff(i));
348 RealScalar imag = numext::imag(m_eivalues.coeff(i));
349 matD.coeffRef(i, i) = real;
350 if (!internal::isMuchSmallerThan(imag, real, precision)) {
351 matD.coeffRef(i, i + 1) = imag;
352 matD.coeffRef(i + 1, i) = -imag;
353 matD.coeffRef(i + 1, i + 1) = real;
354 ++i;
355 }
356 }
357 if (i == n - 1) {
358 matD.coeffRef(i, i) = numext::real(m_eivalues.coeff(i));
359 }
360
361 return matD;
362}
363
364template <typename MatrixType>
366 eigen_assert(m_isInitialized && "EigenSolver is not initialized.");
367 eigen_assert(m_eigenvectorsOk && "The eigenvectors have not been computed together with the eigenvalues.");
368 const RealScalar precision = RealScalar(2) * NumTraits<RealScalar>::epsilon();
369 const PlainMatrixType& eivec = m_realSchur.m_matU;
370 Index n = eivec.cols();
371 EigenvectorsType matV(n, n);
372 for (Index j = 0; j < n; ++j) {
373 if (internal::isMuchSmallerThan(numext::imag(m_eivalues.coeff(j)), numext::real(m_eivalues.coeff(j)), precision) ||
374 j + 1 == n) {
375 // we have a real eigen value
376 matV.col(j) = eivec.col(j).template cast<ComplexScalar>();
377 matV.col(j).normalize();
378 } else {
379 // we have a pair of complex eigen values
380 for (Index i = 0; i < n; ++i) {
381 matV.coeffRef(i, j) = ComplexScalar(eivec.coeff(i, j), eivec.coeff(i, j + 1));
382 matV.coeffRef(i, j + 1) = ComplexScalar(eivec.coeff(i, j), -eivec.coeff(i, j + 1));
383 }
384 matV.col(j).normalize();
385 matV.col(j + 1).normalize();
386 ++j;
387 }
388 }
389 return matV;
390}
391
392template <typename MatrixType>
393template <typename InputType>
395 bool computeEigenvectors) {
396 check_template_parameters();
397 EIGEN_INTERNAL_ASSERT_SQUARE(matrix);
398
399 // Reduce to real Schur form.
400 m_realSchur.compute(matrix.derived(), computeEigenvectors);
401 return computeFromSchur(computeEigenvectors);
402}
403
406template <typename MatrixType>
407EigenSolver<MatrixType>& EigenSolver<MatrixType>::computeFromSchur(bool computeEigenvectors) {
408 m_info = m_realSchur.info();
409
410 if (m_info == Success) {
411 const MatrixType& matT = m_realSchur.m_matT;
412 const Index n = matT.cols();
413
414 // Compute eigenvalues from matT
415 m_eivalues.resize(n);
416 Index i = 0;
417 while (i < n) {
418 if (i == n - 1 || matT.coeff(i + 1, i) == Scalar(0)) {
419 m_eivalues.coeffRef(i) = matT.coeff(i, i);
420 if (!(numext::isfinite)(m_eivalues.coeffRef(i))) {
421 m_isInitialized = true;
422 m_eigenvectorsOk = false;
423 m_info = NumericalIssue;
424 return *this;
425 }
426 ++i;
427 } else {
428 Scalar p = Scalar(0.5) * (matT.coeff(i, i) - matT.coeff(i + 1, i + 1));
429 Scalar z;
430 // Compute z = sqrt(abs(p * p + matT.coeff(i+1, i) * matT.coeff(i, i+1)));
431 // without overflow
432 {
433 Scalar t0 = matT.coeff(i + 1, i);
434 Scalar t1 = matT.coeff(i, i + 1);
435 Scalar maxval = numext::maxi<Scalar>(numext::abs(p), numext::maxi<Scalar>(numext::abs(t0), numext::abs(t1)));
436 t0 /= maxval;
437 t1 /= maxval;
438 Scalar p0 = p / maxval;
439 z = maxval * numext::sqrt(numext::abs(p0 * p0 + t0 * t1));
440 }
441
442 m_eivalues.coeffRef(i) = ComplexScalar(matT.coeff(i + 1, i + 1) + p, z);
443 m_eivalues.coeffRef(i + 1) = ComplexScalar(matT.coeff(i + 1, i + 1) + p, -z);
444 if (!((numext::isfinite)(m_eivalues.coeffRef(i)) && (numext::isfinite)(m_eivalues.coeffRef(i + 1)))) {
445 m_isInitialized = true;
446 m_eigenvectorsOk = false;
447 m_info = NumericalIssue;
448 return *this;
449 }
450 i += 2;
451 }
452 }
453
454 // Compute eigenvectors.
455 if (computeEigenvectors) doComputeEigenvectors();
456 } else if (!m_realSchur.m_matT.allFinite()) {
457 // RealSchur reports both nonfinite input and iteration exhaustion as NoConvergence.
458 m_info = NumericalIssue;
459 }
460
461 m_isInitialized = true;
462 m_eigenvectorsOk = computeEigenvectors;
463
464 return *this;
465}
466
467template <typename MatrixType>
468void EigenSolver<MatrixType>::doComputeEigenvectors() {
469 // Back-substitution stores the eigenvectors of T over T itself; the back-transformation then turns U into the
470 // pseudo-eigenvectors in place, column by column from the last one.
471 MatrixType& matT = m_realSchur.m_matT;
472 PlainMatrixType& eivec = m_realSchur.m_matU;
473 const Index size = eivec.cols();
474 const Scalar eps = NumTraits<Scalar>::epsilon();
475
476 const Scalar norm = internal::hessenberg_abs_sum<Upper>(matT);
477
478 // Backsubstitute to find vectors of upper triangular form
479 if (norm == Scalar(0)) {
480 return;
481 }
482
483 for (Index n = size - 1; n >= 0; n--) {
484 Scalar p = m_eivalues.coeff(n).real();
485 Scalar q = m_eivalues.coeff(n).imag();
486
487 // Scalar vector
488 if (q == Scalar(0)) {
489 Scalar lastr(0), lastw(0);
490 Index l = n;
491
492 matT.coeffRef(n, n) = Scalar(1);
493 for (Index i = n - 1; i >= 0; i--) {
494 Scalar w = matT.coeff(i, i) - p;
495 Scalar r = matT.row(i).segment(l, n - l + 1).dot(matT.col(n).segment(l, n - l + 1));
496
497 if (m_eivalues.coeff(i).imag() < Scalar(0)) {
498 lastw = w;
499 lastr = r;
500 } else {
501 l = i;
502 if (m_eivalues.coeff(i).imag() == Scalar(0)) {
503 if (w != Scalar(0))
504 matT.coeffRef(i, n) = -r / w;
505 else
506 matT.coeffRef(i, n) = -r / (eps * norm);
507 } else // Solve real equations
508 {
509 Scalar x = matT.coeff(i, i + 1);
510 Scalar y = matT.coeff(i + 1, i);
511 Scalar denom = (m_eivalues.coeff(i).real() - p) * (m_eivalues.coeff(i).real() - p) +
512 m_eivalues.coeff(i).imag() * m_eivalues.coeff(i).imag();
513 Scalar t = (x * lastr - lastw * r) / denom;
514 matT.coeffRef(i, n) = t;
515 if (numext::abs(x) > numext::abs(lastw))
516 matT.coeffRef(i + 1, n) = (-r - w * t) / x;
517 else
518 matT.coeffRef(i + 1, n) = (-lastr - y * t) / lastw;
519 }
520
521 // Overflow control
522 Scalar t = numext::abs(matT.coeff(i, n));
523 if ((eps * t) * t > Scalar(1)) matT.col(n).tail(size - i) /= t;
524 }
525 }
526 } else if (q < Scalar(0) && n > 0) // Complex vector
527 {
528 Scalar lastra(0), lastsa(0), lastw(0);
529 Index l = n - 1;
530
531 // Last vector component imaginary so matrix is triangular
532 if (numext::abs(matT.coeff(n, n - 1)) > numext::abs(matT.coeff(n - 1, n))) {
533 matT.coeffRef(n - 1, n - 1) = q / matT.coeff(n, n - 1);
534 matT.coeffRef(n - 1, n) = -(matT.coeff(n, n) - p) / matT.coeff(n, n - 1);
535 } else {
536 ComplexScalar cc =
537 ComplexScalar(Scalar(0), -matT.coeff(n - 1, n)) / ComplexScalar(matT.coeff(n - 1, n - 1) - p, q);
538 matT.coeffRef(n - 1, n - 1) = numext::real(cc);
539 matT.coeffRef(n - 1, n) = numext::imag(cc);
540 }
541 matT.coeffRef(n, n - 1) = Scalar(0);
542 matT.coeffRef(n, n) = Scalar(1);
543 for (Index i = n - 2; i >= 0; i--) {
544 Scalar ra = matT.row(i).segment(l, n - l + 1).dot(matT.col(n - 1).segment(l, n - l + 1));
545 Scalar sa = matT.row(i).segment(l, n - l + 1).dot(matT.col(n).segment(l, n - l + 1));
546 Scalar w = matT.coeff(i, i) - p;
547
548 if (m_eivalues.coeff(i).imag() < Scalar(0)) {
549 lastw = w;
550 lastra = ra;
551 lastsa = sa;
552 } else {
553 l = i;
554 if (m_eivalues.coeff(i).imag() == RealScalar(0)) {
555 ComplexScalar cc = ComplexScalar(-ra, -sa) / ComplexScalar(w, q);
556 matT.coeffRef(i, n - 1) = numext::real(cc);
557 matT.coeffRef(i, n) = numext::imag(cc);
558 } else {
559 // Solve complex equations
560 Scalar x = matT.coeff(i, i + 1);
561 Scalar y = matT.coeff(i + 1, i);
562 Scalar vr = (m_eivalues.coeff(i).real() - p) * (m_eivalues.coeff(i).real() - p) +
563 m_eivalues.coeff(i).imag() * m_eivalues.coeff(i).imag() - q * q;
564 Scalar vi = (m_eivalues.coeff(i).real() - p) * Scalar(2) * q;
565 if ((vr == Scalar(0)) && (vi == Scalar(0)))
566 vr =
567 eps * norm * (numext::abs(w) + numext::abs(q) + numext::abs(x) + numext::abs(y) + numext::abs(lastw));
568
569 ComplexScalar cc = ComplexScalar(x * lastra - lastw * ra + q * sa, x * lastsa - lastw * sa - q * ra) /
570 ComplexScalar(vr, vi);
571 matT.coeffRef(i, n - 1) = numext::real(cc);
572 matT.coeffRef(i, n) = numext::imag(cc);
573 if (numext::abs(x) > (numext::abs(lastw) + numext::abs(q))) {
574 matT.coeffRef(i + 1, n - 1) = (-ra - w * matT.coeff(i, n - 1) + q * matT.coeff(i, n)) / x;
575 matT.coeffRef(i + 1, n) = (-sa - w * matT.coeff(i, n) - q * matT.coeff(i, n - 1)) / x;
576 } else {
577 cc = ComplexScalar(-lastra - y * matT.coeff(i, n - 1), -lastsa - y * matT.coeff(i, n)) /
578 ComplexScalar(lastw, q);
579 matT.coeffRef(i + 1, n - 1) = numext::real(cc);
580 matT.coeffRef(i + 1, n) = numext::imag(cc);
581 }
582 }
583
584 // Overflow control
585 Scalar t = numext::maxi<Scalar>(numext::abs(matT.coeff(i, n - 1)), numext::abs(matT.coeff(i, n)));
586 if ((eps * t) * t > Scalar(1)) matT.block(i, n - 1, size - i, 2) /= t;
587 }
588 }
589
590 // We handled a pair of complex conjugate eigenvalues, so need to skip them both
591 n--;
592 } else {
593 eigen_assert(0 && "Internal bug in EigenSolver (INF or NaN has not been detected)"); // this should not happen
594 }
595 }
596
597 // Back transformation to get eigenvectors of original matrix
598 for (Index j = size - 1; j >= 0; j--) {
599 m_tmp.noalias() = eivec.leftCols(j + 1) * matT.col(j).segment(0, j + 1);
600 eivec.col(j) = m_tmp;
601 }
602}
603
604} // end namespace Eigen
605
606#endif // EIGEN_EIGENSOLVER_H
Computes eigenvalues and eigenvectors of general matrices.
Definition EigenSolver.h:69
EigenSolver(const EigenBase< InputType > &matrix, bool computeEigenvectors=true)
Constructor; computes eigendecomposition of given matrix.
Definition EigenSolver.h:149
PlainMatrixType pseudoEigenvalueMatrix() const
Returns the block-diagonal matrix in the pseudo-eigendecomposition.
Definition EigenSolver.h:340
EigenSolver(EigenBase< InputType > &matrix, bool computeEigenvectors=true)
Constructor for inplace decomposition .
Definition EigenSolver.h:171
typename MatrixType::Scalar Scalar
Scalar type for matrices of type MatrixType.
Definition EigenSolver.h:83
EigenSolver(Index size)
Default constructor with memory preallocation.
Definition EigenSolver.h:130
Matrix< ComplexScalar, ColsAtCompileTime, 1, Options &~RowMajor, MaxColsAtCompileTime, 1 > EigenvalueType
Type for vector of eigenvalues as returned by eigenvalues().
Definition EigenSolver.h:105
ComputationInfo info() const
Definition EigenSolver.h:303
EigenvectorsType eigenvectors() const
Returns the eigenvectors of given matrix.
Definition EigenSolver.h:365
EigenSolver()
Default constructor.
Definition EigenSolver.h:122
EigenSolver & setMaxIterations(Index maxIters)
Sets the maximum number of iterations allowed.
Definition EigenSolver.h:309
const PlainMatrixType & pseudoEigenvectors() const
Returns the pseudo-eigenvectors of given matrix.
Definition EigenSolver.h:221
Index getMaxIterations() const
Returns the maximum number of iterations.
Definition EigenSolver.h:315
Matrix< ComplexScalar, RowsAtCompileTime, ColsAtCompileTime, Options, MaxRowsAtCompileTime, MaxColsAtCompileTime > EigenvectorsType
Type for matrix of eigenvectors as returned by eigenvectors().
Definition EigenSolver.h:112
EigenSolver & compute(const EigenBase< InputType > &matrix, bool computeEigenvectors=true)
Computes eigendecomposition of given matrix.
MatrixType_ MatrixType
Synonym for the template parameter MatrixType_.
Definition EigenSolver.h:72
internal::make_complex_t< Scalar > ComplexScalar
Complex scalar type for MatrixType.
Definition EigenSolver.h:98
const EigenvalueType & eigenvalues() const
Returns the eigenvalues of given matrix.
Definition EigenSolver.h:265
Eigen::Index Index
Definition EigenSolver.h:85
Matrix< Scalar, RowsAtCompileTime, ColsAtCompileTime, Options, MaxRowsAtCompileTime, MaxColsAtCompileTime > PlainMatrixType
Plain matrix type with the shape and storage options of MatrixType; MatrixType itself unless that is ...
Definition EigenSolver.h:89
The matrix class, also used for vectors and row-vectors.
Definition Matrix.h:188
constexpr Scalar & coeffRef(Index rowId, Index colId)
Definition PlainObjectBase.h:205
constexpr const Scalar & coeff(Index rowId, Index colId) const
Definition PlainObjectBase.h:187
ComputationInfo
Definition Constants.h:455
@ NumericalIssue
Definition Constants.h:459
@ Success
Definition Constants.h:457
Definition EigenBase.h:34
constexpr Derived & derived()
Definition EigenBase.h:50