Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
SelfAdjointEigenSolver.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2008-2010 Gael Guennebaud <gael.guennebaud@inria.fr>
5// Copyright (C) 2010 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_SELFADJOINTEIGENSOLVER_H
13#define EIGEN_SELFADJOINTEIGENSOLVER_H
14
15#include "./Tridiagonalization.h"
16
17// IWYU pragma: private
18#include "./InternalHeaderCheck.h"
19
20namespace Eigen {
21
22template <typename MatrixType_>
24
25namespace internal {
26template <typename SolverType, int Size, bool IsComplex, bool IsDirect = !IsComplex && (Size == 2 || Size == 3)>
27struct direct_selfadjoint_eigenvalues;
28
29template <bool PerBlockScaling, typename MatrixType, typename DiagType, typename SubDiagType>
30EIGEN_DEVICE_FUNC ComputationInfo computeFromTridiagonal_impl(DiagType& diag, SubDiagType& subdiag,
31 const Index maxIterations, bool computeEigenvectors,
32 MatrixType& eivec);
33} // namespace internal
34
83template <typename MatrixType_>
85 public:
86 using MatrixType = MatrixType_;
87 enum {
88 Size = MatrixType::RowsAtCompileTime,
89 ColsAtCompileTime = MatrixType::ColsAtCompileTime,
90 Options = internal::plain_object_options<MatrixType>::value,
91 MaxColsAtCompileTime = MatrixType::MaxColsAtCompileTime
92 };
93
95 using Scalar = typename MatrixType::Scalar;
96 using Index = Eigen::Index;
97
102
108 std::conditional_t<internal::is_ref<MatrixType>::value, MatrixType,
110
117 using RealScalar = typename NumTraits<Scalar>::Real;
118
119 friend struct internal::direct_selfadjoint_eigenvalues<SelfAdjointEigenSolver, Size, NumTraits<Scalar>::IsComplex>;
120
126 using VectorType = typename internal::plain_col_type<MatrixType, Scalar>::type;
127 using RealVectorType = typename internal::plain_col_type<MatrixType, RealScalar>::type;
128 using TridiagonalizationType = Tridiagonalization<MatrixType>;
129 using SubDiagonalType = typename TridiagonalizationType::SubDiagonalType;
130
141 EIGEN_DEVICE_FUNC SelfAdjointEigenSolver()
142 : m_eivec(),
143 m_workspace(),
144 m_eivalues(),
145 m_subdiag(),
146 m_hcoeffs(),
147 m_info(InvalidInput),
148 m_isInitialized(false),
149 m_eigenvectorsOk(false) {}
150
163 EIGEN_DEVICE_FUNC explicit SelfAdjointEigenSolver(Index size)
164 : m_eivec(size, size),
165 m_workspace(size),
166 m_eivalues(size),
167 m_subdiag(size > 1 ? size - 1 : 1),
168 m_hcoeffs(size > 1 ? size - 1 : 1),
169 m_isInitialized(false),
170 m_eigenvectorsOk(false) {}
171
188 template <typename InputType>
189 EIGEN_DEVICE_FUNC explicit SelfAdjointEigenSolver(const EigenBase<InputType>& matrix,
190 int options = ComputeEigenvectors)
191 : m_eivec(matrix.rows(), matrix.cols()),
192 m_workspace(matrix.cols()),
193 m_eivalues(matrix.cols()),
194 m_subdiag(matrix.rows() > 1 ? matrix.rows() - 1 : 1),
195 m_hcoeffs(matrix.cols() > 1 ? matrix.cols() - 1 : 1),
196 m_isInitialized(false),
197 m_eigenvectorsOk(false) {
198 compute(matrix.derived(), options);
199 }
200
213 template <typename InputType, bool IsRef = internal::is_ref<MatrixType>::value, std::enable_if_t<IsRef, int> = 0>
214 EIGEN_DEVICE_FUNC explicit SelfAdjointEigenSolver(EigenBase<InputType>& matrix, int options = ComputeEigenvectors)
215 : SelfAdjointEigenSolver(matrix, BindStorageTag()) {
216 m_eivec.template triangularView<StrictlyUpper>().setZero();
217 computeInPlace(options);
218 }
219
251 template <typename InputType>
252 EIGEN_DEVICE_FUNC SelfAdjointEigenSolver& compute(const EigenBase<InputType>& matrix,
253 int options = ComputeEigenvectors);
254
281 EIGEN_DEVICE_FUNC SelfAdjointEigenSolver& computeDirect(const MatrixType& matrix, int options = ComputeEigenvectors);
282
295 SelfAdjointEigenSolver& computeFromTridiagonal(const RealVectorType& diag, const SubDiagonalType& subdiag,
296 int options = ComputeEigenvectors);
297
321 EIGEN_DEVICE_FUNC const EigenvectorsType& eigenvectors() const {
322 eigen_assert(m_isInitialized && "SelfAdjointEigenSolver is not initialized.");
323 eigen_assert(m_eigenvectorsOk && "The eigenvectors have not been computed together with the eigenvalues.");
324 return m_eivec;
325 }
326
342 EIGEN_DEVICE_FUNC const RealVectorType& eigenvalues() const {
343 eigen_assert(m_isInitialized && "SelfAdjointEigenSolver is not initialized.");
344 return m_eivalues;
345 }
346
364 EIGEN_DEVICE_FUNC PlainMatrixType operatorSqrt() const {
365 eigen_assert(m_isInitialized && "SelfAdjointEigenSolver is not initialized.");
366 eigen_assert(m_eigenvectorsOk && "The eigenvectors have not been computed together with the eigenvalues.");
367 return m_eivec * m_eivalues.cwiseSqrt().asDiagonal() * m_eivec.adjoint();
368 }
369
380 EIGEN_DEVICE_FUNC PlainMatrixType operatorExp() const {
381 eigen_assert(m_isInitialized && "SelfAdjointEigenSolver is not initialized.");
382 eigen_assert(m_eigenvectorsOk && "The eigenvectors have not been computed together with the eigenvalues.");
383 return m_eivec * m_eivalues.array().exp().matrix().asDiagonal() * m_eivec.adjoint();
384 }
385
404 EIGEN_DEVICE_FUNC PlainMatrixType operatorInverseSqrt() const {
405 eigen_assert(m_isInitialized && "SelfAdjointEigenSolver is not initialized.");
406 eigen_assert(m_eigenvectorsOk && "The eigenvectors have not been computed together with the eigenvalues.");
407 return m_eivec * m_eivalues.cwiseInverse().cwiseSqrt().asDiagonal() * m_eivec.adjoint();
408 }
409
414 EIGEN_DEVICE_FUNC ComputationInfo info() const {
415 eigen_assert(m_isInitialized && "SelfAdjointEigenSolver is not initialized.");
416 return m_info;
417 }
418
424 static const int m_maxIterations = 30;
425
426 protected:
427 EIGEN_STATIC_ASSERT_NON_INTEGER(Scalar)
428
429
430 struct BindStorageTag {};
431
434 template <typename InputType>
435 EIGEN_DEVICE_FUNC SelfAdjointEigenSolver(EigenBase<InputType>& matrix, BindStorageTag)
436 : m_eivec(matrix.derived()),
437 m_workspace(matrix.cols()),
438 m_eivalues(matrix.cols()),
439 m_subdiag(matrix.rows() > 1 ? matrix.rows() - 1 : 1),
440 m_hcoeffs(matrix.cols() > 1 ? matrix.cols() - 1 : 1),
441 m_isInitialized(false),
442 m_eigenvectorsOk(false) {}
443
446 EIGEN_DEVICE_FUNC SelfAdjointEigenSolver& computeInPlace(int options);
447
448 EigenvectorsType m_eivec;
449 VectorType m_workspace;
450 RealVectorType m_eivalues;
451 typename TridiagonalizationType::SubDiagonalType m_subdiag;
452 typename TridiagonalizationType::CoeffVectorType m_hcoeffs;
453 ComputationInfo m_info;
454 bool m_isInitialized;
455 bool m_eigenvectorsOk;
456};
457
458namespace internal {
477template <typename RealScalar, typename Index, typename MatrixQType>
478EIGEN_DEVICE_FUNC static void tridiagonal_qr_step(RealScalar* diag, RealScalar* subdiag, Index start, Index end,
479 MatrixQType* matrixQ);
480} // namespace internal
481
482template <typename MatrixType>
483template <typename InputType>
485 const EigenBase<InputType>& a_matrix, int options) {
486 const InputType& matrix(a_matrix.derived());
487 EIGEN_INTERNAL_ASSERT_SQUARE(matrix);
488 m_eivec = matrix.template triangularView<Lower>();
489 return computeInPlace(options);
490}
491
492template <typename MatrixType>
493EIGEN_DEVICE_FUNC SelfAdjointEigenSolver<MatrixType>& SelfAdjointEigenSolver<MatrixType>::computeInPlace(int options) {
494 EIGEN_INTERNAL_ASSERT_SQUARE(m_eivec);
495 eigen_assert((options & ~(EigVecMask | GenEigMask)) == 0 && (options & EigVecMask) != EigVecMask &&
496 "invalid option parameter");
497 bool computeEigenvectors = (options & ComputeEigenvectors) == ComputeEigenvectors;
498 Index n = m_eivec.cols();
499 m_eivalues.resize(n, 1);
500
501 if (n <= 1) {
502 if (n == 1) m_eivalues.coeffRef(0, 0) = numext::real(m_eivec.coeff(0, 0));
503 if (computeEigenvectors) m_eivec.setOnes();
504 m_info = m_eivalues.allFinite() ? Success : NoConvergence;
505 m_isInitialized = true;
506 m_eigenvectorsOk = computeEigenvectors;
507 return *this;
508 }
509
510 // declare some aliases
511 RealVectorType& diag = m_eivalues;
512 EigenvectorsType& mat = m_eivec;
513
514 // A selfadjoint matrix has a real diagonal: ignore the imaginary part, as LAPACK's xLANHE and xHETRD do, so that
515 // it neither sets the scale below nor injects a NaN or Inf.
516 EIGEN_IF_CONSTEXPR (NumTraits<Scalar>::IsComplex) {
517 mat.diagonal() = mat.diagonal().real();
518 }
519
520 // Scale the matrix to O(1) to avoid overflow/underflow during tridiagonalization
521 // and subsequent QR iteration. Power-of-two factors avoid rounding representable scaled coefficients.
522 // Note: for block-diagonal matrices with widely separated scales, this
523 // can underflow small blocks. Users with such matrices should tridiagonalize separately
524 // and call computeFromTridiagonal(), which uses per-block scaling.
525 const RealScalar maxCoeff = internal::safe_scaling<RealScalar>::max_abs_component(mat);
526 if (!(numext::isfinite)(maxCoeff)) {
527 // Input contains Inf or NaN.
528 m_info = NoConvergence;
529 m_isInitialized = true;
530 m_eigenvectorsOk = false;
531 return *this;
532 }
533 const auto factors = internal::safe_scaling<RealScalar>::with_scaled(mat, maxCoeff, [&](const auto& scaled) {
534 mat.template triangularView<Lower>() = scaled.template triangularView<Lower>();
535 });
536 m_subdiag.resize(n - 1);
537 m_hcoeffs.resize(n - 1);
538 internal::tridiagonalization_inplace(mat, diag, m_subdiag, m_hcoeffs, m_workspace, computeEigenvectors);
539
540 m_info = internal::computeFromTridiagonal_impl<false>(diag, m_subdiag, m_maxIterations, computeEigenvectors, m_eivec);
541
542 // Scale back the eigenvalues.
543 internal::safe_scaling<RealScalar>::unscale_in_place(m_eivalues, maxCoeff, factors);
544
545 m_isInitialized = true;
546 m_eigenvectorsOk = computeEigenvectors;
547 return *this;
548}
549
550template <typename MatrixType>
552 const RealVectorType& diag, const SubDiagonalType& subdiag, int options) {
553 bool computeEigenvectors = (options & ComputeEigenvectors) == ComputeEigenvectors;
554
555 m_eivalues = diag;
556 m_subdiag = subdiag;
557
558 // Check for Inf/NaN in the input.
559 {
560 RealScalar scale = RealScalar(0);
561 if (m_eivalues.size() > 0) scale = m_eivalues.cwiseAbs().maxCoeff();
562 if (m_subdiag.size() > 0) scale = numext::maxi(scale, m_subdiag.cwiseAbs().maxCoeff());
563 if (!(numext::isfinite)(scale)) {
564 m_info = NoConvergence;
565 m_isInitialized = true;
566 m_eigenvectorsOk = false;
567 return *this;
568 }
569 }
570
571 if (computeEigenvectors) {
572 m_eivec.setIdentity(diag.size(), diag.size());
573 }
574 // Use per-deflation-block scaling (like LAPACK's DSTERF) to avoid losing
575 // precision when the tridiagonal entries span a wide range of magnitudes.
576 m_info =
577 internal::computeFromTridiagonal_impl<true>(m_eivalues, m_subdiag, m_maxIterations, computeEigenvectors, m_eivec);
578
579 m_isInitialized = true;
580 m_eigenvectorsOk = computeEigenvectors;
581 return *this;
582}
583
584namespace internal {
600template <bool PerBlockScaling, typename MatrixType, typename DiagType, typename SubDiagType>
601EIGEN_DEVICE_FUNC ComputationInfo computeFromTridiagonal_impl(DiagType& diag, SubDiagType& subdiag,
602 const Index maxIterations, bool computeEigenvectors,
603 MatrixType& eivec) {
604 ComputationInfo info;
605
606 Index n = diag.size();
607 Index end = n - 1;
608 Index start = 0;
609 Index iter = 0; // total number of iterations
610
611 using RealScalar = typename DiagType::RealScalar;
612 const RealScalar considerAsZero = (std::numeric_limits<RealScalar>::min)();
613 const RealScalar precision = NumTraits<RealScalar>::epsilon();
614 const RealScalar precision_inv = RealScalar(1) / precision;
615
616 // Helper lambda for the deflation test.
617 auto deflate = [&](Index lo, Index hi) {
618 for (Index i = lo; i < hi; ++i) {
619 const RealScalar absSubdiag = numext::abs(subdiag[i]);
620 if (absSubdiag < considerAsZero) {
621 subdiag[i] = RealScalar(0);
622 } else if (!PerBlockScaling) {
623 // Homogeneous in the global scale: both sides are linear in it, so prescaling cannot change which couplings
624 // are discarded (the previous test was quadratic on the left).
625 if (absSubdiag <= precision * numext::maxi(numext::abs(diag[i]), numext::abs(diag[i + 1]))) {
626 subdiag[i] = RealScalar(0);
627 }
628 } else {
629 const RealScalar scaled_subdiag = precision_inv * subdiag[i];
630 if (scaled_subdiag * scaled_subdiag <= (numext::abs(diag[i]) + numext::abs(diag[i + 1]))) {
631 subdiag[i] = RealScalar(0);
632 }
633 }
634 }
635 };
636
637 // For per-block scaling, track the currently scaled block and its scale factor.
638 // When the outer loop identifies a block outside the scaled region, unscale the old
639 // block and scale the new one. This keeps the same outer loop structure (one QR step
640 // per iteration) while ensuring each block is processed in scaled coordinates.
641 Index scaled_start = -1, scaled_end = -1;
642 RealScalar block_norm = RealScalar(0);
643 safe_scaling_factors<RealScalar> blockFactors;
644 const auto restore_block = [&]() {
645 if (scaled_start < 0) return;
646 auto diagonal = diag.segment(scaled_start, scaled_end - scaled_start + 1);
647 auto offDiagonal = subdiag.segment(scaled_start, scaled_end - scaled_start);
648 safe_scaling<RealScalar>::unscale_in_place(diagonal, block_norm, blockFactors);
649 safe_scaling<RealScalar>::unscale_in_place(offDiagonal, block_norm, blockFactors);
650 };
651
652 while (end > 0) {
653 deflate(start, end);
654
655 // Find the largest unreduced block at the end of the matrix.
656 while (end > 0 && numext::is_exactly_zero(subdiag[end - 1])) {
657 end--;
658 }
659 if (end <= 0) break;
660
661 // if we spent too many iterations, we give up
662 iter++;
663 if (iter > maxIterations * n) break;
664
665 start = end - 1;
666 while (start > 0 && !numext::is_exactly_zero(subdiag[start - 1])) start--;
667
668 if (PerBlockScaling) {
669 // Check if we've moved to a different block than the one currently scaled.
670 if (start != scaled_start || end != scaled_end) {
671 restore_block();
672 // Compute the norm and scale the new block to O(1).
673 block_norm = RealScalar(0);
674 for (Index i = start; i <= end; ++i) block_norm = numext::maxi(block_norm, numext::abs(diag[i]));
675 for (Index i = start; i < end; ++i) block_norm = numext::maxi(block_norm, numext::abs(subdiag[i]));
676 auto diagonal = diag.segment(start, end - start + 1);
677 auto offDiagonal = subdiag.segment(start, end - start);
678 blockFactors = safe_scaling<RealScalar>::scale_to(diagonal, diagonal, block_norm);
679 safe_scaling<RealScalar>::scale_to(offDiagonal, offDiagonal, block_norm, blockFactors);
680 scaled_start = start;
681 scaled_end = end;
682 }
683 }
684
685 internal::tridiagonal_qr_step(diag.data(), subdiag.data(), start, end,
686 computeEigenvectors ? &eivec : static_cast<MatrixType*>(nullptr));
687 }
688
689 // Unscale any remaining scaled block.
690 if (PerBlockScaling) restore_block();
691 if (iter <= maxIterations * n)
692 info = Success;
693 else
694 info = NoConvergence;
695
696 // Sort eigenvalues and corresponding vectors.
697 // TODO: make the sort optional and use a more efficient sorting algorithm.
698 if (info == Success) {
699 for (Index i = 0; i < n - 1; ++i) {
700 // Scalar argmin: the vectorized minCoeff path can return the wrong
701 // index on targets whose SIMD reduction flushes subnormals (32-bit ARM
702 // NEON always treats subnormal inputs to vminq_f32 as zero), which
703 // corrupts ordering when eigenvalues span the subnormal range.
704 Index k = i;
705 RealScalar min_val = diag[i];
706 for (Index j = i + 1; j < n; ++j) {
707 if (diag[j] < min_val) {
708 min_val = diag[j];
709 k = j;
710 }
711 }
712 if (k != i) {
713 numext::swap(diag[i], diag[k]);
714 if (computeEigenvectors) eivec.col(i).swap(eivec.col(k));
715 }
716 }
717 }
718 return info;
719}
720
721template <typename SolverType, int Size, bool IsComplex, bool IsDirect>
722struct direct_selfadjoint_eigenvalues {
723 EIGEN_DEVICE_FUNC static inline void run(SolverType& eig, const typename SolverType::MatrixType& A, int options) {
724 eig.compute(A, options);
725 }
726};
727
728template <typename SolverType, int Size>
729struct direct_selfadjoint_eigensolver_kernel;
730
731template <typename SolverType>
732struct direct_selfadjoint_eigensolver_kernel<SolverType, 3> {
733 using MatrixType = typename SolverType::MatrixType;
734 using VectorType = typename SolverType::RealVectorType;
735 using Scalar = typename SolverType::Scalar;
736 using EigenvectorsType = typename SolverType::EigenvectorsType;
737 using PlainMatrixType = typename SolverType::PlainMatrixType;
738
743 EIGEN_DEVICE_FUNC static inline void computeRoots(const MatrixType& m, VectorType& roots) {
744 const Scalar s_inv3 = Scalar(1) / Scalar(3);
745 const Scalar s_sqrt3 = numext::sqrt(Scalar(3));
746
747 // The characteristic equation is x^3 - c2*x^2 + c1*x - c0 = 0. The
748 // eigenvalues are the roots to this equation, all guaranteed to be
749 // real-valued, because the matrix is symmetric.
750 Scalar c0 = m(0, 0) * m(1, 1) * m(2, 2) + Scalar(2) * m(1, 0) * m(2, 0) * m(2, 1) - m(0, 0) * m(2, 1) * m(2, 1) -
751 m(1, 1) * m(2, 0) * m(2, 0) - m(2, 2) * m(1, 0) * m(1, 0);
752 Scalar c1 = m(0, 0) * m(1, 1) - m(1, 0) * m(1, 0) + m(0, 0) * m(2, 2) - m(2, 0) * m(2, 0) + m(1, 1) * m(2, 2) -
753 m(2, 1) * m(2, 1);
754 Scalar c2 = m(0, 0) + m(1, 1) + m(2, 2);
755
756 // Construct the parameters used in classifying the roots of the equation
757 // and in solving the equation for the roots in closed form.
758 Scalar c2_over_3 = c2 * s_inv3;
759 Scalar a_over_3 = (c2 * c2_over_3 - c1) * s_inv3;
760 a_over_3 = numext::maxi(a_over_3, Scalar(0));
761
762 Scalar half_b = Scalar(0.5) * (c0 + c2_over_3 * (Scalar(2) * c2_over_3 * c2_over_3 - c1));
763
764 Scalar q = a_over_3 * a_over_3 * a_over_3 - half_b * half_b;
765 q = numext::maxi(q, Scalar(0));
766
767 // Compute the eigenvalues by solving for the roots of the polynomial.
768 Scalar rho = numext::sqrt(a_over_3);
769 Scalar theta = numext::atan2(numext::sqrt(q), half_b) *
770 s_inv3; // since sqrt(q) > 0, atan2 is in [0, pi] and theta is in [0, pi/3]
771 Scalar cos_theta = numext::cos(theta);
772 Scalar sin_theta = numext::sin(theta);
773 // roots are already sorted, since cos is monotonically decreasing on [0, pi]
774 roots(0) = c2_over_3 - rho * (cos_theta + s_sqrt3 * sin_theta); // == 2*rho*cos(theta+2pi/3)
775 roots(1) = c2_over_3 - rho * (cos_theta - s_sqrt3 * sin_theta); // == 2*rho*cos(theta+ pi/3)
776 roots(2) = c2_over_3 + Scalar(2) * rho * cos_theta;
777 }
778
779 EIGEN_DEVICE_FUNC static inline bool extract_kernel(PlainMatrixType& mat, Ref<VectorType> res,
780 Ref<VectorType> representative) {
781 Index i0;
782 // Find non-zero column i0 (by construction, there must exist a non zero coefficient on the diagonal):
783 mat.diagonal().cwiseAbs().maxCoeff(&i0);
784 // mat.col(i0) is a good candidate for an orthogonal vector to the current eigenvector,
785 // so let's save it:
786 representative = mat.col(i0);
787 Scalar n0, n1;
788 VectorType c0, c1;
789 n0 = (c0 = representative.cross(mat.col((i0 + 1) % 3))).squaredNorm();
790 n1 = (c1 = representative.cross(mat.col((i0 + 2) % 3))).squaredNorm();
791 if (n0 > n1)
792 res = c0 / numext::sqrt(n0);
793 else
794 res = c1 / numext::sqrt(n1);
795
796 return true;
797 }
798
799 EIGEN_DEVICE_FUNC static void run(PlainMatrixType& scaledMat, VectorType& eivals, EigenvectorsType& eivecs,
800 bool computeEigenvectors, const Scalar& maxCoeff) {
801 // compute the eigenvalues
802 computeRoots(scaledMat, eivals);
803
804 // computeRoots produces theoretically sorted roots, but floating-point
805 // rounding in the trigonometric formulas can break the ordering.
806 // Enforce sorting with a fixed 3-element compare-swap network.
807 if (eivals(0) > eivals(1)) numext::swap(eivals(0), eivals(1));
808 if (eivals(1) > eivals(2)) numext::swap(eivals(1), eivals(2));
809 if (eivals(0) > eivals(1)) numext::swap(eivals(0), eivals(1));
810
811 // compute the eigenvectors
812 if (computeEigenvectors) {
813 if ((eivals(2) - eivals(0)) <= Eigen::NumTraits<Scalar>::epsilon() * maxCoeff) {
814 // All three eigenvalues are numerically the same
815 eivecs.setIdentity();
816 } else {
817 PlainMatrixType tmp;
818 tmp = scaledMat;
819
820 // Compute the eigenvector of the most distinct eigenvalue
821 Scalar d0 = eivals(2) - eivals(1);
822 Scalar d1 = eivals(1) - eivals(0);
823 Index k(0), l(2);
824 if (d0 > d1) {
825 numext::swap(k, l);
826 d0 = d1;
827 }
828
829 // Compute the eigenvector of index k
830 {
831 tmp.diagonal().array() -= eivals(k);
832 // By construction, 'tmp' is of rank 2, and its kernel corresponds to the respective eigenvector.
833 extract_kernel(tmp, eivecs.col(k), eivecs.col(l));
834 }
835
836 // Compute eigenvector of index l
837 if (d0 <= 2 * Eigen::NumTraits<Scalar>::epsilon() * d1) {
838 // If d0 is too small, then the two other eigenvalues are numerically the same,
839 // and thus we only have to ortho-normalize the near orthogonal vector we saved above.
840 eivecs.col(l) -= eivecs.col(k).dot(eivecs.col(l)) * eivecs.col(k);
841 eivecs.col(l).normalize();
842 } else {
843 tmp = scaledMat;
844 tmp.diagonal().array() -= eivals(l);
845
846 VectorType dummy;
847 extract_kernel(tmp, eivecs.col(l), dummy);
848 }
849
850 // Compute last eigenvector from the other two
851 eivecs.col(1) = eivecs.col(2).cross(eivecs.col(0)).normalized();
852 }
853 }
854 }
855};
856
857// 2x2 direct eigenvalues decomposition, code from Hauke Heibel
858template <typename SolverType>
859struct direct_selfadjoint_eigensolver_kernel<SolverType, 2> {
860 using MatrixType = typename SolverType::MatrixType;
861 using VectorType = typename SolverType::RealVectorType;
862 using Scalar = typename SolverType::Scalar;
863 using EigenvectorsType = typename SolverType::EigenvectorsType;
864 using PlainMatrixType = typename SolverType::PlainMatrixType;
865
866 EIGEN_DEVICE_FUNC static inline void computeRoots(const MatrixType& m, VectorType& roots) {
867 const Scalar t0 =
868 Scalar(0.5) * numext::sqrt<Scalar>(numext::abs2(m(0, 0) - m(1, 1)) + Scalar(4) * numext::abs2(m(1, 0)));
869 const Scalar t1 = Scalar(0.5) * (m(0, 0) + m(1, 1));
870 roots(0) = t1 - t0;
871 roots(1) = t1 + t0;
872 }
873
874 EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE static void run(PlainMatrixType& scaledMat, VectorType& eivals,
875 EigenvectorsType& eivecs, bool computeEigenvectors,
876 const Scalar&) {
877 // Compute the eigenvalues
878 computeRoots(scaledMat, eivals);
879
880 // compute the eigen vectors
881 if (computeEigenvectors) {
882 if ((eivals(1) - eivals(0)) <= numext::abs(eivals(1)) * Eigen::NumTraits<Scalar>::epsilon()) {
883 eivecs.setIdentity();
884 } else {
885 scaledMat.diagonal().array() -= eivals(1);
886 Scalar a2 = numext::abs2(scaledMat(0, 0));
887 Scalar c2 = numext::abs2(scaledMat(1, 1));
888 Scalar b2 = numext::abs2(scaledMat(1, 0));
889 if (a2 > c2) {
890 eivecs.col(1) << -scaledMat(1, 0), scaledMat(0, 0);
891 eivecs.col(1) /= numext::sqrt<Scalar>(a2 + b2);
892 } else {
893 eivecs.col(1) << -scaledMat(1, 1), scaledMat(1, 0);
894 eivecs.col(1) /= numext::sqrt<Scalar>(c2 + b2);
895 }
896
897 // The partner is already normalized; this rotation preserves its norm.
898 eivecs.col(0) << -eivecs(1, 1), eivecs(0, 1);
899 }
900 }
901 }
902};
903
904template <typename SolverType, int Size>
905struct direct_selfadjoint_eigenvalues<SolverType, Size, false, true> {
906 using MatrixType = typename SolverType::MatrixType;
907 using PlainMatrixType = typename SolverType::PlainMatrixType;
908 using Scalar = typename SolverType::Scalar;
909
910 // Only host-side long double limits need more range than double.
911 using Limit = std::conditional_t<std::is_same<Scalar, long double>::value, long double, double>;
912
913 EIGEN_DEVICE_FUNC static constexpr Limit power_of_two(int exponent) {
914 Limit result = 1;
915 for (; exponent > 0; --exponent) result *= 2;
916 for (; exponent < 0; ++exponent) result /= 2;
917 return result;
918 }
919
920 EIGEN_DEVICE_FUNC static bool safe_without_scaling(const Scalar& magnitude, true_type) {
921 // The quadratic/cubic kernels have degree 2/6. Reserve 12 exponent bits
922 // for intermediate growth and keep flushed terms below epsilon*mu^degree.
923 constexpr int degree = Size == 3 ? 6 : 2;
924 constexpr int lower = std::numeric_limits<Scalar>::min_exponent - 1 + std::numeric_limits<Scalar>::digits - 1 + 12;
925 constexpr int upper = std::numeric_limits<Scalar>::max_exponent - 1 - 12;
926 constexpr int minExponent = lower >= 0 ? (lower + degree - 1) / degree : lower / degree;
927 constexpr int maxExponent = upper >= 0 ? upper / degree : (upper - degree + 1) / degree;
928 constexpr Limit minimum = power_of_two(minExponent);
929 constexpr Limit maximum = power_of_two(maxExponent);
930 return magnitude >= Scalar(minimum) && magnitude <= Scalar(maximum);
931 }
932
933 EIGEN_DEVICE_FUNC static bool safe_without_scaling(const Scalar& magnitude, false_type) {
934 return magnitude >= Scalar(0.25) && magnitude <= Scalar(2) &&
935 NumTraits<Scalar>::epsilon() / Scalar(4096) >= (std::numeric_limits<Scalar>::min)();
936 }
937
938 EIGEN_DEVICE_FUNC EIGEN_DONT_INLINE static void run_scaled(SolverType& solver, const MatrixType& mat,
939 const Scalar& shift, Scalar centeredMax, int options) {
940 PlainMatrixType scaledMat = mat.template selfadjointView<Lower>();
941 scaledMat.diagonal().array() -= shift;
942 centeredMax = safe_scaling<Scalar>::recover_flushed_max_coeff(scaledMat, centeredMax);
943 const auto factors = safe_scaling<Scalar>::scale_to(scaledMat, scaledMat, centeredMax);
944 direct_selfadjoint_eigensolver_kernel<SolverType, Size>::run(scaledMat, solver.m_eivalues, solver.m_eivec,
946 scaledMat.cwiseAbs().maxCoeff());
947 safe_scaling<Scalar>::unscale_in_place(solver.m_eivalues, centeredMax, factors);
948 }
949
950 EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE static void run_centered(SolverType& solver, const MatrixType& mat,
951 int options) {
952 const bool computeEigenvectors = (options & ComputeEigenvectors) == ComputeEigenvectors;
953 PlainMatrixType scaledMat = mat.template selfadjointView<Lower>();
954 const Scalar first = scaledMat(0, 0);
955 Scalar shift = first;
956 for (Index i = 1; i < Size; ++i) shift += (scaledMat(i, i) - first) / Scalar(Size);
957 scaledMat.diagonal().array() -= shift;
958 // Centering can leave a much smaller matrix; normalize again for the cubic and cross-product formulas.
959 const Scalar centeredMax = scaledMat.cwiseAbs().maxCoeff();
960 if (safe_without_scaling(centeredMax, supports_power_of_two_scaling<Scalar>())) {
961 direct_selfadjoint_eigensolver_kernel<SolverType, Size>::run(scaledMat, solver.m_eivalues, solver.m_eivec,
962 computeEigenvectors, centeredMax);
963 } else {
964 run_scaled(solver, mat, shift, centeredMax, options);
965 }
966 solver.m_eivalues.array() += shift;
967 solver.m_info = Success;
968 solver.m_isInitialized = true;
969 solver.m_eigenvectorsOk = computeEigenvectors;
970 }
971
972 EIGEN_DEVICE_FUNC static void run_large(SolverType& solver, PlainMatrixType& scaledMat, int options, false_type) {
973 run_centered(solver, scaledMat, options);
974 }
975
976 EIGEN_DEVICE_FUNC static void run_large(SolverType& solver, PlainMatrixType& scaledMat, int options, true_type) {
977 // The cubic loses accuracy near repeated roots; at the exponent limit that error can overflow a finite result.
978 solver.compute(scaledMat, options);
979 }
980
981 EIGEN_DEVICE_FUNC EIGEN_DONT_INLINE static void run_prescaled(SolverType& solver, const MatrixType& mat,
982 const Scalar& maxCoeff, int options) {
983 PlainMatrixType scaledMat = mat.template selfadjointView<Lower>();
984 const Scalar recoveredMax = safe_scaling<Scalar>::recover_flushed_max_coeff(scaledMat, maxCoeff);
985 const auto inputFactors = safe_scaling<Scalar>::scale_to(scaledMat, scaledMat, recoveredMax);
986 if (maxCoeff > (NumTraits<Scalar>::highest() * Scalar(0.5)) / Scalar(Size)) {
987 run_large(solver, scaledMat, options,
988 bool_constant<(Size == 3 && supports_power_of_two_scaling<Scalar>::value)>());
989 } else {
990 run_centered(solver, scaledMat, options);
991 }
992 safe_scaling<Scalar>::unscale_in_place(solver.m_eivalues, recoveredMax, inputFactors);
993 }
994
995 EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE static void run(SolverType& solver, const MatrixType& mat, int options) {
996 EIGEN_INTERNAL_CHECK_SHAPE(mat.rows() == Size && mat.cols() == Size, YOU_MIXED_MATRICES_OF_DIFFERENT_SIZES,
997 internal::fixed_dimensions<MatrixType, Size, Size>);
998 eigen_assert((options & ~(EigVecMask | GenEigMask)) == 0 && (options & EigVecMask) != EigVecMask &&
999 "invalid option parameter");
1000 PlainMatrixType scaledMat = mat.template selfadjointView<Lower>();
1001 const Scalar maxCoeff = scaledMat.cwiseAbs().maxCoeff();
1002 // Bound centered coefficients by 2*M and eigenvalues by Size*M. Prescale tiny inputs before any FTZ-sensitive
1003 // subtraction, and large inputs before centering or restoring the centered eigenvalues could overflow.
1004 // Halve highest() first: IBM double-double division can overflow internally at the maximum value.
1005 if (EIGEN_PREDICT_FALSE(maxCoeff < (std::numeric_limits<Scalar>::min)() / NumTraits<Scalar>::epsilon() ||
1006 maxCoeff > (NumTraits<Scalar>::highest() * Scalar(0.5)) / Scalar(Size))) {
1007 run_prescaled(solver, mat, maxCoeff, options);
1008 } else {
1009 run_centered(solver, mat, options);
1010 }
1011 }
1012};
1013
1014} // namespace internal
1015
1016template <typename MatrixType>
1018 const MatrixType& matrix, int options) {
1019 internal::direct_selfadjoint_eigenvalues<SelfAdjointEigenSolver, Size, NumTraits<Scalar>::IsComplex>::run(
1020 *this, matrix, options);
1021 return *this;
1022}
1023
1024namespace internal {
1025
1026// Francis implicit QR step; the rotations accumulate into *matrixQ when it is non-null.
1027template <typename RealScalar, typename Index, typename MatrixQType>
1028EIGEN_DEVICE_FUNC static void tridiagonal_qr_step(RealScalar* diag, RealScalar* subdiag, Index start, Index end,
1029 MatrixQType* matrixQ) {
1030 // Wilkinson Shift.
1031 RealScalar td = (diag[end - 1] - diag[end]) * RealScalar(0.5);
1032 RealScalar e = subdiag[end - 1];
1033 RealScalar mu = diag[end];
1034 if (numext::is_exactly_zero(td)) {
1035 mu -= numext::abs(e);
1036 } else if (!numext::is_exactly_zero(e)) {
1037 const RealScalar e2 = numext::abs2(e);
1038 if (numext::is_exactly_zero(e2)) {
1039 // Scaling prevents e^2 and td^2 from overflowing, but e^2 can still underflow. A subdiagonal that survives
1040 // deflation satisfies (e/epsilon)^2 > 2*abs(td), so td/e remains bounded in this branch. LAPACK's xSTEQR uses
1041 // this dimensionless form; keeping td/e inside hypot prevents fast-math from reassociating the correction into
1042 // an underflowing e^2 expression.
1043 const RealScalar ratio = td / e;
1044 const RealScalar h = numext::hypot(ratio, RealScalar(1));
1045 mu -= e / (ratio + (ratio > RealScalar(0) ? h : -h));
1046 } else {
1047 const RealScalar h = numext::hypot(td, e);
1048 mu -= e2 / (td + (td > RealScalar(0) ? h : -h));
1049 }
1050 }
1051
1052 RealScalar x = diag[start] - mu;
1053 RealScalar z = subdiag[start];
1054 // If z ever becomes zero, the Givens rotation will be the identity and
1055 // z will stay zero for all future iterations.
1056 for (Index k = start; k < end && !numext::is_exactly_zero(z); ++k) {
1057 JacobiRotation<RealScalar> rot;
1058 rot.makeGivens(x, z);
1059
1060 // do T = G' T G. The two new diagonal entries and the new off-diagonal are all expressed below
1061 // as functions of the original difference diff = diag[k] - diag[k+1] and the original subdiag[k],
1062 // so capture diff and compute delta/subdiag[k] before overwriting the diagonal.
1063 const RealScalar diff = diag[k] - diag[k + 1];
1064
1065 // Update the 2x2 diagonal block by the symmetric change delta, applied with opposite signs to
1066 // diag[k] and diag[k+1]. A similarity leaves the trace invariant, so this preserves diag[k] +
1067 // diag[k+1] exactly. Forming the two new diagonal entries from independent explicit formulas
1068 // (diag[k] = c^2 d_k - 2 c s e_k + s^2 d_{k+1}, diag[k+1] = s^2 d_k + 2 c s e_k + c^2 d_{k+1})
1069 // instead lets the two roundings drift the trace a little on every rotation, an error that
1070 // accumulates over the O(n^2) rotations of a full solve and measurably degrades the eigenvalues.
1071 // Algebraically delta = s^2 (d_k - d_{k+1}) + 2 c s e_k, which is exactly d_k minus the formula above.
1072 const RealScalar delta = rot.s() * (rot.s() * diff + RealScalar(2) * rot.c() * subdiag[k]);
1073 // The exact (G' T G) off-diagonal, c*s*(d_k - d_{k+1}) + (c^2 - s^2)*e_k, written in the same diff
1074 // form rather than via the c*sdk - s*dkp1 temporaries.
1075 subdiag[k] = rot.c() * rot.s() * diff + (rot.c() * rot.c() - rot.s() * rot.s()) * subdiag[k];
1076 diag[k] -= delta;
1077 diag[k + 1] += delta;
1078
1079 if (k > start) subdiag[k - 1] = rot.c() * subdiag[k - 1] - rot.s() * z;
1080
1081 // "Chasing the bulge" to return to triangular form.
1082 x = subdiag[k];
1083 if (k < end - 1) {
1084 z = -rot.s() * subdiag[k + 1];
1085 subdiag[k + 1] = rot.c() * subdiag[k + 1];
1086 }
1087
1088 // apply the givens rotation to the unit matrix Q = Q * G
1089 if (matrixQ) {
1090 // Contiguous column-major storage is rotated through a dynamic-size map: the rotation kernel then dispatches
1091 // on the runtime alignment for fixed-size matrices too, and rounds as it always did. Other storage (a
1092 // row-major Ref<>) is rotated through the matrix type itself.
1093 EIGEN_IF_CONSTEXPR (!MatrixQType::IsRowMajor && int(MatrixQType::InnerStrideAtCompileTime) == 1) {
1094 using Scalar = typename MatrixQType::Scalar;
1095 Map<Matrix<Scalar, Dynamic, Dynamic, ColMajor>, Unaligned, OuterStride<>> q(
1096 matrixQ->data(), matrixQ->rows(), matrixQ->cols(), OuterStride<>(matrixQ->outerStride()));
1097 q.applyOnTheRight(k, k + 1, rot);
1098 } else {
1099 matrixQ->applyOnTheRight(k, k + 1, rot);
1100 }
1101 }
1102 }
1103}
1104
1105} // end namespace internal
1106
1107} // end namespace Eigen
1108
1109#endif // EIGEN_SELFADJOINTEIGENSOLVER_H
Computes eigenvalues and eigenvectors of the generalized selfadjoint eigen problem.
Definition GeneralizedSelfAdjointEigenSolver.h:53
The matrix class, also used for vectors and row-vectors.
Definition Matrix.h:188
Computes eigenvalues and eigenvectors of selfadjoint matrices.
Definition SelfAdjointEigenSolver.h:84
PlainMatrixType operatorExp() const
Computes the matrix exponential of the matrix.
Definition SelfAdjointEigenSolver.h:380
SelfAdjointEigenSolver & compute(const EigenBase< InputType > &matrix, int options=ComputeEigenvectors)
Computes eigendecomposition of given matrix.
SelfAdjointEigenSolver & computeFromTridiagonal(const RealVectorType &diag, const SubDiagonalType &subdiag, int options=ComputeEigenvectors)
Computes the eigen decomposition from a tridiagonal symmetric matrix.
Definition SelfAdjointEigenSolver.h:551
SelfAdjointEigenSolver(EigenBase< InputType > &matrix, int options=ComputeEigenvectors)
Constructor for inplace decomposition .
Definition SelfAdjointEigenSolver.h:214
typename MatrixType::Scalar Scalar
Scalar type for matrices of type MatrixType_.
Definition SelfAdjointEigenSolver.h:95
typename internal::plain_col_type< MatrixType, Scalar >::type VectorType
Type for vector of eigenvalues as returned by eigenvalues().
Definition SelfAdjointEigenSolver.h:126
SelfAdjointEigenSolver()
Default constructor for fixed-size matrices.
Definition SelfAdjointEigenSolver.h:141
ComputationInfo info() const
Reports whether previous computation was successful.
Definition SelfAdjointEigenSolver.h:414
Matrix< Scalar, Size, ColsAtCompileTime, Options, MatrixType::MaxRowsAtCompileTime, MaxColsAtCompileTime > PlainMatrixType
Plain matrix type with the shape and storage options of MatrixType_; MatrixType_ itself unless that i...
Definition SelfAdjointEigenSolver.h:100
PlainMatrixType operatorInverseSqrt() const
Computes the inverse square root of the matrix.
Definition SelfAdjointEigenSolver.h:404
std::conditional_t< internal::is_ref< MatrixType >::value, MatrixType, Matrix< Scalar, Size, Size, ColMajor, MaxColsAtCompileTime, MaxColsAtCompileTime > > EigenvectorsType
Type of the matrix returned by eigenvectors().
Definition SelfAdjointEigenSolver.h:107
typename NumTraits< Scalar >::Real RealScalar
Real scalar type for MatrixType_.
Definition SelfAdjointEigenSolver.h:117
PlainMatrixType operatorSqrt() const
Computes the positive-definite square root of the matrix.
Definition SelfAdjointEigenSolver.h:364
Eigen::Index Index
Definition SelfAdjointEigenSolver.h:96
SelfAdjointEigenSolver(Index size)
Constructor, pre-allocates memory for dynamic-size matrices.
Definition SelfAdjointEigenSolver.h:163
const RealVectorType & eigenvalues() const
Returns the eigenvalues of given matrix.
Definition SelfAdjointEigenSolver.h:342
static const int m_maxIterations
Maximum number of iterations.
Definition SelfAdjointEigenSolver.h:424
const EigenvectorsType & eigenvectors() const
Returns the eigenvectors of given matrix.
Definition SelfAdjointEigenSolver.h:321
SelfAdjointEigenSolver(const EigenBase< InputType > &matrix, int options=ComputeEigenvectors)
Constructor; computes eigendecomposition of given matrix.
Definition SelfAdjointEigenSolver.h:189
SelfAdjointEigenSolver & computeDirect(const MatrixType &matrix, int options=ComputeEigenvectors)
Computes eigendecomposition of given matrix primarily using a closed-form algorithm.
Definition SelfAdjointEigenSolver.h:1017
Tridiagonal decomposition of a selfadjoint matrix.
Definition Tridiagonalization.h:71
ComputationInfo
Definition Constants.h:455
@ Unaligned
Definition Constants.h:236
@ Success
Definition Constants.h:457
@ NoConvergence
Definition Constants.h:461
@ ComputeEigenvectors
Definition Constants.h:406
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