diff options
Diffstat (limited to 'extern/Eigen3/Eigen/src/Eigenvalues')
13 files changed, 1244 insertions, 107 deletions
diff --git a/extern/Eigen3/Eigen/src/Eigenvalues/ComplexEigenSolver.h b/extern/Eigen3/Eigen/src/Eigenvalues/ComplexEigenSolver.h index c4b8a308cee..af434bc9bd6 100644 --- a/extern/Eigen3/Eigen/src/Eigenvalues/ComplexEigenSolver.h +++ b/extern/Eigen3/Eigen/src/Eigenvalues/ComplexEigenSolver.h @@ -3,7 +3,7 @@ // // Copyright (C) 2009 Claire Maurice // Copyright (C) 2009 Gael Guennebaud <gael.guennebaud@inria.fr> -// Copyright (C) 2010 Jitse Niesen <jitse@maths.leeds.ac.uk> +// Copyright (C) 2010,2012 Jitse Niesen <jitse@maths.leeds.ac.uk> // // This Source Code Form is subject to the terms of the Mozilla // Public License v. 2.0. If a copy of the MPL was not distributed @@ -220,6 +220,19 @@ template<typename _MatrixType> class ComplexEigenSolver return m_schur.info(); } + /** \brief Sets the maximum number of iterations allowed. */ + ComplexEigenSolver& setMaxIterations(Index maxIters) + { + m_schur.setMaxIterations(maxIters); + return *this; + } + + /** \brief Returns the maximum number of iterations. */ + Index getMaxIterations() + { + return m_schur.getMaxIterations(); + } + protected: EigenvectorType m_eivec; EigenvalueType m_eivalues; @@ -229,16 +242,17 @@ template<typename _MatrixType> class ComplexEigenSolver EigenvectorType m_matX; private: - void doComputeEigenvectors(RealScalar matrixnorm); + void doComputeEigenvectors(const RealScalar& matrixnorm); void sortEigenvalues(bool computeEigenvectors); }; template<typename MatrixType> -ComplexEigenSolver<MatrixType>& ComplexEigenSolver<MatrixType>::compute(const MatrixType& matrix, bool computeEigenvectors) +ComplexEigenSolver<MatrixType>& +ComplexEigenSolver<MatrixType>::compute(const MatrixType& matrix, bool computeEigenvectors) { // this code is inspired from Jampack - assert(matrix.cols() == matrix.rows()); + eigen_assert(matrix.cols() == matrix.rows()); // Do a complex Schur decomposition, A = U T U^* // The eigenvalues are on the diagonal of T. @@ -259,7 +273,7 @@ ComplexEigenSolver<MatrixType>& ComplexEigenSolver<MatrixType>::compute(const Ma template<typename MatrixType> -void ComplexEigenSolver<MatrixType>::doComputeEigenvectors(RealScalar matrixnorm) +void ComplexEigenSolver<MatrixType>::doComputeEigenvectors(const RealScalar& matrixnorm) { const Index n = m_eivalues.size(); @@ -280,7 +294,7 @@ void ComplexEigenSolver<MatrixType>::doComputeEigenvectors(RealScalar matrixnorm { // If the i-th and k-th eigenvalue are equal, then z equals 0. // Use a small value instead, to prevent division by zero. - internal::real_ref(z) = NumTraits<RealScalar>::epsilon() * matrixnorm; + numext::real_ref(z) = NumTraits<RealScalar>::epsilon() * matrixnorm; } m_matX.coeffRef(i,k) = m_matX.coeff(i,k) / z; } diff --git a/extern/Eigen3/Eigen/src/Eigenvalues/ComplexSchur.h b/extern/Eigen3/Eigen/src/Eigenvalues/ComplexSchur.h index 16a9a03d219..89e6cade334 100644 --- a/extern/Eigen3/Eigen/src/Eigenvalues/ComplexSchur.h +++ b/extern/Eigen3/Eigen/src/Eigenvalues/ComplexSchur.h @@ -3,7 +3,7 @@ // // Copyright (C) 2009 Claire Maurice // Copyright (C) 2009 Gael Guennebaud <gael.guennebaud@inria.fr> -// Copyright (C) 2010 Jitse Niesen <jitse@maths.leeds.ac.uk> +// Copyright (C) 2010,2012 Jitse Niesen <jitse@maths.leeds.ac.uk> // // This Source Code Form is subject to the terms of the Mozilla // Public License v. 2.0. If a copy of the MPL was not distributed @@ -96,7 +96,8 @@ template<typename _MatrixType> class ComplexSchur m_matU(size,size), m_hess(size), m_isInitialized(false), - m_matUisUptodate(false) + m_matUisUptodate(false), + m_maxIters(-1) {} /** \brief Constructor; computes Schur decomposition of given matrix. @@ -109,11 +110,12 @@ template<typename _MatrixType> class ComplexSchur * \sa matrixT() and matrixU() for examples. */ ComplexSchur(const MatrixType& matrix, bool computeU = true) - : m_matT(matrix.rows(),matrix.cols()), - m_matU(matrix.rows(),matrix.cols()), - m_hess(matrix.rows()), - m_isInitialized(false), - m_matUisUptodate(false) + : m_matT(matrix.rows(),matrix.cols()), + m_matU(matrix.rows(),matrix.cols()), + m_hess(matrix.rows()), + m_isInitialized(false), + m_matUisUptodate(false), + m_maxIters(-1) { compute(matrix, computeU); } @@ -166,6 +168,7 @@ template<typename _MatrixType> class ComplexSchur * * \param[in] matrix Square matrix whose Schur decomposition is to be computed. * \param[in] computeU If true, both T and U are computed; if false, only T is computed. + * \returns Reference to \c *this * * The Schur decomposition is computed by first reducing the @@ -180,8 +183,30 @@ template<typename _MatrixType> class ComplexSchur * * Example: \include ComplexSchur_compute.cpp * Output: \verbinclude ComplexSchur_compute.out + * + * \sa compute(const MatrixType&, bool, Index) */ ComplexSchur& compute(const MatrixType& matrix, bool computeU = true); + + /** \brief Compute Schur decomposition from a given Hessenberg matrix + * \param[in] matrixH Matrix in Hessenberg form H + * \param[in] matrixQ orthogonal matrix Q that transform a matrix A to H : A = Q H Q^T + * \param computeU Computes the matriX U of the Schur vectors + * \return Reference to \c *this + * + * This routine assumes that the matrix is already reduced in Hessenberg form matrixH + * using either the class HessenbergDecomposition or another mean. + * It computes the upper quasi-triangular matrix T of the Schur decomposition of H + * When computeU is true, this routine computes the matrix U such that + * A = U T U^T = (QZ) T (QZ)^T = Q H Q^T where A is the initial matrix + * + * NOTE Q is referenced if computeU is true; so, if the initial orthogonal matrix + * is not available, the user should give an identity matrix (Q.setIdentity()) + * + * \sa compute(const MatrixType&, bool) + */ + template<typename HessMatrixType, typename OrthMatrixType> + ComplexSchur& computeFromHessenberg(const HessMatrixType& matrixH, const OrthMatrixType& matrixQ, bool computeU=true); /** \brief Reports whether previous computation was successful. * @@ -189,15 +214,33 @@ template<typename _MatrixType> class ComplexSchur */ ComputationInfo info() const { - eigen_assert(m_isInitialized && "RealSchur is not initialized."); + eigen_assert(m_isInitialized && "ComplexSchur is not initialized."); return m_info; } - /** \brief Maximum number of iterations. + /** \brief Sets the maximum number of iterations allowed. * - * Maximum number of iterations allowed for an eigenvalue to converge. + * If not specified by the user, the maximum number of iterations is m_maxIterationsPerRow times the size + * of the matrix. */ - static const int m_maxIterations = 30; + ComplexSchur& setMaxIterations(Index maxIters) + { + m_maxIters = maxIters; + return *this; + } + + /** \brief Returns the maximum number of iterations. */ + Index getMaxIterations() + { + return m_maxIters; + } + + /** \brief Maximum number of iterations per row. + * + * If not otherwise specified, the maximum number of iterations is this number times the size of the + * matrix. It is currently set to 30. + */ + static const int m_maxIterationsPerRow = 30; protected: ComplexMatrixType m_matT, m_matU; @@ -205,6 +248,7 @@ template<typename _MatrixType> class ComplexSchur ComputationInfo m_info; bool m_isInitialized; bool m_matUisUptodate; + Index m_maxIters; private: bool subdiagonalEntryIsNeglegible(Index i); @@ -219,8 +263,8 @@ template<typename _MatrixType> class ComplexSchur template<typename MatrixType> inline bool ComplexSchur<MatrixType>::subdiagonalEntryIsNeglegible(Index i) { - RealScalar d = internal::norm1(m_matT.coeff(i,i)) + internal::norm1(m_matT.coeff(i+1,i+1)); - RealScalar sd = internal::norm1(m_matT.coeff(i+1,i)); + RealScalar d = numext::norm1(m_matT.coeff(i,i)) + numext::norm1(m_matT.coeff(i+1,i+1)); + RealScalar sd = numext::norm1(m_matT.coeff(i+1,i)); if (internal::isMuchSmallerThan(sd, d, NumTraits<RealScalar>::epsilon())) { m_matT.coeffRef(i+1,i) = ComplexScalar(0); @@ -234,10 +278,11 @@ inline bool ComplexSchur<MatrixType>::subdiagonalEntryIsNeglegible(Index i) template<typename MatrixType> typename ComplexSchur<MatrixType>::ComplexScalar ComplexSchur<MatrixType>::computeShift(Index iu, Index iter) { + using std::abs; if (iter == 10 || iter == 20) { // exceptional shift, taken from http://www.netlib.org/eispack/comqr.f - return internal::abs(internal::real(m_matT.coeff(iu,iu-1))) + internal::abs(internal::real(m_matT.coeff(iu-1,iu-2))); + return abs(numext::real(m_matT.coeff(iu,iu-1))) + abs(numext::real(m_matT.coeff(iu-1,iu-2))); } // compute the shift as one of the eigenvalues of t, the 2x2 @@ -254,13 +299,13 @@ typename ComplexSchur<MatrixType>::ComplexScalar ComplexSchur<MatrixType>::compu ComplexScalar eival1 = (trace + disc) / RealScalar(2); ComplexScalar eival2 = (trace - disc) / RealScalar(2); - if(internal::norm1(eival1) > internal::norm1(eival2)) + if(numext::norm1(eival1) > numext::norm1(eival2)) eival2 = det / eival1; else eival1 = det / eival2; // choose the eigenvalue closest to the bottom entry of the diagonal - if(internal::norm1(eival1-t.coeff(1,1)) < internal::norm1(eival2-t.coeff(1,1))) + if(numext::norm1(eival1-t.coeff(1,1)) < numext::norm1(eival2-t.coeff(1,1))) return normt * eival1; else return normt * eival2; @@ -284,10 +329,20 @@ ComplexSchur<MatrixType>& ComplexSchur<MatrixType>::compute(const MatrixType& ma } internal::complex_schur_reduce_to_hessenberg<MatrixType, NumTraits<Scalar>::IsComplex>::run(*this, matrix, computeU); - reduceToTriangularForm(computeU); + computeFromHessenberg(m_matT, m_matU, computeU); return *this; } +template<typename MatrixType> +template<typename HessMatrixType, typename OrthMatrixType> +ComplexSchur<MatrixType>& ComplexSchur<MatrixType>::computeFromHessenberg(const HessMatrixType& matrixH, const OrthMatrixType& matrixQ, bool computeU) +{ + m_matT = matrixH; + if(computeU) + m_matU = matrixQ; + reduceToTriangularForm(computeU); + return *this; +} namespace internal { /* Reduce given matrix to Hessenberg form */ @@ -309,7 +364,6 @@ struct complex_schur_reduce_to_hessenberg<MatrixType, false> static void run(ComplexSchur<MatrixType>& _this, const MatrixType& matrix, bool computeU) { typedef typename ComplexSchur<MatrixType>::ComplexScalar ComplexScalar; - typedef typename ComplexSchur<MatrixType>::ComplexMatrixType ComplexMatrixType; // Note: m_hess is over RealScalar; m_matT and m_matU is over ComplexScalar _this.m_hess.compute(matrix); @@ -329,6 +383,10 @@ struct complex_schur_reduce_to_hessenberg<MatrixType, false> template<typename MatrixType> void ComplexSchur<MatrixType>::reduceToTriangularForm(bool computeU) { + Index maxIters = m_maxIters; + if (maxIters == -1) + maxIters = m_maxIterationsPerRow * m_matT.rows(); + // The matrix m_matT is divided in three parts. // Rows 0,...,il-1 are decoupled from the rest because m_matT(il,il-1) is zero. // Rows il,...,iu is the part we are working on (the active submatrix). @@ -336,6 +394,7 @@ void ComplexSchur<MatrixType>::reduceToTriangularForm(bool computeU) Index iu = m_matT.cols() - 1; Index il; Index iter = 0; // number of iterations we are working on the (iu,iu) element + Index totalIter = 0; // number of iterations for whole matrix while(true) { @@ -350,9 +409,10 @@ void ComplexSchur<MatrixType>::reduceToTriangularForm(bool computeU) // if iu is zero then we are done; the whole matrix is triangularized if(iu==0) break; - // if we spent too many iterations on the current element, we give up + // if we spent too many iterations, we give up iter++; - if(iter > m_maxIterations * m_matT.cols()) break; + totalIter++; + if(totalIter > maxIters) break; // find il, the top row of the active submatrix il = iu-1; @@ -382,7 +442,7 @@ void ComplexSchur<MatrixType>::reduceToTriangularForm(bool computeU) } } - if(iter <= m_maxIterations * m_matT.cols()) + if(totalIter <= maxIters) m_info = Success; else m_info = NoConvergence; diff --git a/extern/Eigen3/Eigen/src/Eigenvalues/ComplexSchur_MKL.h b/extern/Eigen3/Eigen/src/Eigenvalues/ComplexSchur_MKL.h index aa18e696352..91496ae5bdb 100644 --- a/extern/Eigen3/Eigen/src/Eigenvalues/ComplexSchur_MKL.h +++ b/extern/Eigen3/Eigen/src/Eigenvalues/ComplexSchur_MKL.h @@ -40,7 +40,7 @@ namespace Eigen { /** \internal Specialization for the data types supported by MKL */ #define EIGEN_MKL_SCHUR_COMPLEX(EIGTYPE, MKLTYPE, MKLPREFIX, MKLPREFIX_U, EIGCOLROW, MKLCOLROW) \ -template<> inline\ +template<> inline \ ComplexSchur<Matrix<EIGTYPE, Dynamic, Dynamic, EIGCOLROW> >& \ ComplexSchur<Matrix<EIGTYPE, Dynamic, Dynamic, EIGCOLROW> >::compute(const Matrix<EIGTYPE, Dynamic, Dynamic, EIGCOLROW>& matrix, bool computeU) \ { \ @@ -49,7 +49,7 @@ ComplexSchur<Matrix<EIGTYPE, Dynamic, Dynamic, EIGCOLROW> >::compute(const Matri typedef MatrixType::RealScalar RealScalar; \ typedef std::complex<RealScalar> ComplexScalar; \ \ - assert(matrix.cols() == matrix.rows()); \ + eigen_assert(matrix.cols() == matrix.rows()); \ \ m_matUisUptodate = false; \ if(matrix.cols() == 1) \ diff --git a/extern/Eigen3/Eigen/src/Eigenvalues/EigenSolver.h b/extern/Eigen3/Eigen/src/Eigenvalues/EigenSolver.h index c16ff2b74e2..6e7150685a2 100644 --- a/extern/Eigen3/Eigen/src/Eigenvalues/EigenSolver.h +++ b/extern/Eigen3/Eigen/src/Eigenvalues/EigenSolver.h @@ -2,7 +2,7 @@ // for linear algebra. // // Copyright (C) 2008 Gael Guennebaud <gael.guennebaud@inria.fr> -// Copyright (C) 2010 Jitse Niesen <jitse@maths.leeds.ac.uk> +// Copyright (C) 2010,2012 Jitse Niesen <jitse@maths.leeds.ac.uk> // // This Source Code Form is subject to the terms of the Mozilla // Public License v. 2.0. If a copy of the MPL was not distributed @@ -281,6 +281,19 @@ template<typename _MatrixType> class EigenSolver return m_realSchur.info(); } + /** \brief Sets the maximum number of iterations allowed. */ + EigenSolver& setMaxIterations(Index maxIters) + { + m_realSchur.setMaxIterations(maxIters); + return *this; + } + + /** \brief Returns the maximum number of iterations. */ + Index getMaxIterations() + { + return m_realSchur.getMaxIterations(); + } + private: void doComputeEigenvectors(); @@ -304,12 +317,12 @@ MatrixType EigenSolver<MatrixType>::pseudoEigenvalueMatrix() const MatrixType matD = MatrixType::Zero(n,n); for (Index i=0; i<n; ++i) { - if (internal::isMuchSmallerThan(internal::imag(m_eivalues.coeff(i)), internal::real(m_eivalues.coeff(i)))) - matD.coeffRef(i,i) = internal::real(m_eivalues.coeff(i)); + if (internal::isMuchSmallerThan(numext::imag(m_eivalues.coeff(i)), numext::real(m_eivalues.coeff(i)))) + matD.coeffRef(i,i) = numext::real(m_eivalues.coeff(i)); else { - matD.template block<2,2>(i,i) << internal::real(m_eivalues.coeff(i)), internal::imag(m_eivalues.coeff(i)), - -internal::imag(m_eivalues.coeff(i)), internal::real(m_eivalues.coeff(i)); + matD.template block<2,2>(i,i) << numext::real(m_eivalues.coeff(i)), numext::imag(m_eivalues.coeff(i)), + -numext::imag(m_eivalues.coeff(i)), numext::real(m_eivalues.coeff(i)); ++i; } } @@ -325,7 +338,7 @@ typename EigenSolver<MatrixType>::EigenvectorsType EigenSolver<MatrixType>::eige EigenvectorsType matV(n,n); for (Index j=0; j<n; ++j) { - if (internal::isMuchSmallerThan(internal::imag(m_eivalues.coeff(j)), internal::real(m_eivalues.coeff(j))) || j+1==n) + if (internal::isMuchSmallerThan(numext::imag(m_eivalues.coeff(j)), numext::real(m_eivalues.coeff(j))) || j+1==n) { // we have a real eigen value matV.col(j) = m_eivec.col(j).template cast<ComplexScalar>(); @@ -348,12 +361,16 @@ typename EigenSolver<MatrixType>::EigenvectorsType EigenSolver<MatrixType>::eige } template<typename MatrixType> -EigenSolver<MatrixType>& EigenSolver<MatrixType>::compute(const MatrixType& matrix, bool computeEigenvectors) +EigenSolver<MatrixType>& +EigenSolver<MatrixType>::compute(const MatrixType& matrix, bool computeEigenvectors) { - assert(matrix.cols() == matrix.rows()); + using std::sqrt; + using std::abs; + eigen_assert(matrix.cols() == matrix.rows()); // Reduce to real Schur form. m_realSchur.compute(matrix, computeEigenvectors); + if (m_realSchur.info() == Success) { m_matT = m_realSchur.matrixT(); @@ -373,7 +390,7 @@ EigenSolver<MatrixType>& EigenSolver<MatrixType>::compute(const MatrixType& matr else { Scalar p = Scalar(0.5) * (m_matT.coeff(i, i) - m_matT.coeff(i+1, i+1)); - Scalar z = internal::sqrt(internal::abs(p * p + m_matT.coeff(i+1, i) * m_matT.coeff(i, i+1))); + Scalar z = sqrt(abs(p * p + m_matT.coeff(i+1, i) * m_matT.coeff(i, i+1))); m_eivalues.coeffRef(i) = ComplexScalar(m_matT.coeff(i+1, i+1) + p, z); m_eivalues.coeffRef(i+1) = ComplexScalar(m_matT.coeff(i+1, i+1) + p, -z); i += 2; @@ -393,10 +410,11 @@ EigenSolver<MatrixType>& EigenSolver<MatrixType>::compute(const MatrixType& matr // Complex scalar division. template<typename Scalar> -std::complex<Scalar> cdiv(Scalar xr, Scalar xi, Scalar yr, Scalar yi) +std::complex<Scalar> cdiv(const Scalar& xr, const Scalar& xi, const Scalar& yr, const Scalar& yi) { + using std::abs; Scalar r,d; - if (internal::abs(yr) > internal::abs(yi)) + if (abs(yr) > abs(yi)) { r = yi/yr; d = yr + r*yi; @@ -414,6 +432,7 @@ std::complex<Scalar> cdiv(Scalar xr, Scalar xi, Scalar yr, Scalar yi) template<typename MatrixType> void EigenSolver<MatrixType>::doComputeEigenvectors() { + using std::abs; const Index size = m_eivec.cols(); const Scalar eps = NumTraits<Scalar>::epsilon(); @@ -469,14 +488,14 @@ void EigenSolver<MatrixType>::doComputeEigenvectors() Scalar denom = (m_eivalues.coeff(i).real() - p) * (m_eivalues.coeff(i).real() - p) + m_eivalues.coeff(i).imag() * m_eivalues.coeff(i).imag(); Scalar t = (x * lastr - lastw * r) / denom; m_matT.coeffRef(i,n) = t; - if (internal::abs(x) > internal::abs(lastw)) + if (abs(x) > abs(lastw)) m_matT.coeffRef(i+1,n) = (-r - w * t) / x; else m_matT.coeffRef(i+1,n) = (-lastr - y * t) / lastw; } // Overflow control - Scalar t = internal::abs(m_matT.coeff(i,n)); + Scalar t = abs(m_matT.coeff(i,n)); if ((eps * t) * t > Scalar(1)) m_matT.col(n).tail(size-i) /= t; } @@ -488,7 +507,7 @@ void EigenSolver<MatrixType>::doComputeEigenvectors() Index l = n-1; // Last vector component imaginary so matrix is triangular - if (internal::abs(m_matT.coeff(n,n-1)) > internal::abs(m_matT.coeff(n-1,n))) + if (abs(m_matT.coeff(n,n-1)) > abs(m_matT.coeff(n-1,n))) { m_matT.coeffRef(n-1,n-1) = q / m_matT.coeff(n,n-1); m_matT.coeffRef(n-1,n) = -(m_matT.coeff(n,n) - p) / m_matT.coeff(n,n-1); @@ -496,8 +515,8 @@ void EigenSolver<MatrixType>::doComputeEigenvectors() else { std::complex<Scalar> cc = cdiv<Scalar>(0.0,-m_matT.coeff(n-1,n),m_matT.coeff(n-1,n-1)-p,q); - m_matT.coeffRef(n-1,n-1) = internal::real(cc); - m_matT.coeffRef(n-1,n) = internal::imag(cc); + m_matT.coeffRef(n-1,n-1) = numext::real(cc); + m_matT.coeffRef(n-1,n) = numext::imag(cc); } m_matT.coeffRef(n,n-1) = 0.0; m_matT.coeffRef(n,n) = 1.0; @@ -519,8 +538,8 @@ void EigenSolver<MatrixType>::doComputeEigenvectors() if (m_eivalues.coeff(i).imag() == RealScalar(0)) { std::complex<Scalar> cc = cdiv(-ra,-sa,w,q); - m_matT.coeffRef(i,n-1) = internal::real(cc); - m_matT.coeffRef(i,n) = internal::imag(cc); + m_matT.coeffRef(i,n-1) = numext::real(cc); + m_matT.coeffRef(i,n) = numext::imag(cc); } else { @@ -530,12 +549,12 @@ void EigenSolver<MatrixType>::doComputeEigenvectors() Scalar vr = (m_eivalues.coeff(i).real() - p) * (m_eivalues.coeff(i).real() - p) + m_eivalues.coeff(i).imag() * m_eivalues.coeff(i).imag() - q * q; Scalar vi = (m_eivalues.coeff(i).real() - p) * Scalar(2) * q; if ((vr == 0.0) && (vi == 0.0)) - vr = eps * norm * (internal::abs(w) + internal::abs(q) + internal::abs(x) + internal::abs(y) + internal::abs(lastw)); + vr = eps * norm * (abs(w) + abs(q) + abs(x) + abs(y) + abs(lastw)); - std::complex<Scalar> cc = cdiv(x*lastra-lastw*ra+q*sa,x*lastsa-lastw*sa-q*ra,vr,vi); - m_matT.coeffRef(i,n-1) = internal::real(cc); - m_matT.coeffRef(i,n) = internal::imag(cc); - if (internal::abs(x) > (internal::abs(lastw) + internal::abs(q))) + std::complex<Scalar> cc = cdiv(x*lastra-lastw*ra+q*sa,x*lastsa-lastw*sa-q*ra,vr,vi); + m_matT.coeffRef(i,n-1) = numext::real(cc); + m_matT.coeffRef(i,n) = numext::imag(cc); + if (abs(x) > (abs(lastw) + abs(q))) { m_matT.coeffRef(i+1,n-1) = (-ra - w * m_matT.coeff(i,n-1) + q * m_matT.coeff(i,n)) / x; m_matT.coeffRef(i+1,n) = (-sa - w * m_matT.coeff(i,n) - q * m_matT.coeff(i,n-1)) / x; @@ -543,14 +562,14 @@ void EigenSolver<MatrixType>::doComputeEigenvectors() else { cc = cdiv(-lastra-y*m_matT.coeff(i,n-1),-lastsa-y*m_matT.coeff(i,n),lastw,q); - m_matT.coeffRef(i+1,n-1) = internal::real(cc); - m_matT.coeffRef(i+1,n) = internal::imag(cc); + m_matT.coeffRef(i+1,n-1) = numext::real(cc); + m_matT.coeffRef(i+1,n) = numext::imag(cc); } } // Overflow control using std::max; - Scalar t = (max)(internal::abs(m_matT.coeff(i,n-1)),internal::abs(m_matT.coeff(i,n))); + Scalar t = (max)(abs(m_matT.coeff(i,n-1)),abs(m_matT.coeff(i,n))); if ((eps * t) * t > Scalar(1)) m_matT.block(i, n-1, size-i, 2) /= t; diff --git a/extern/Eigen3/Eigen/src/Eigenvalues/GeneralizedEigenSolver.h b/extern/Eigen3/Eigen/src/Eigenvalues/GeneralizedEigenSolver.h new file mode 100644 index 00000000000..dc240e13e13 --- /dev/null +++ b/extern/Eigen3/Eigen/src/Eigenvalues/GeneralizedEigenSolver.h @@ -0,0 +1,341 @@ +// This file is part of Eigen, a lightweight C++ template library +// for linear algebra. +// +// Copyright (C) 2012 Gael Guennebaud <gael.guennebaud@inria.fr> +// Copyright (C) 2010,2012 Jitse Niesen <jitse@maths.leeds.ac.uk> +// +// This Source Code Form is subject to the terms of the Mozilla +// Public License v. 2.0. If a copy of the MPL was not distributed +// with this file, You can obtain one at http://mozilla.org/MPL/2.0/. + +#ifndef EIGEN_GENERALIZEDEIGENSOLVER_H +#define EIGEN_GENERALIZEDEIGENSOLVER_H + +#include "./RealQZ.h" + +namespace Eigen { + +/** \eigenvalues_module \ingroup Eigenvalues_Module + * + * + * \class GeneralizedEigenSolver + * + * \brief Computes the generalized eigenvalues and eigenvectors of a pair of general matrices + * + * \tparam _MatrixType the type of the matrices of which we are computing the + * eigen-decomposition; this is expected to be an instantiation of the Matrix + * class template. Currently, only real matrices are supported. + * + * The generalized eigenvalues and eigenvectors of a matrix pair \f$ A \f$ and \f$ B \f$ are scalars + * \f$ \lambda \f$ and vectors \f$ v \f$ such that \f$ Av = \lambda Bv \f$. If + * \f$ D \f$ is a diagonal matrix with the eigenvalues on the diagonal, and + * \f$ V \f$ is a matrix with the eigenvectors as its columns, then \f$ A V = + * B V D \f$. The matrix \f$ V \f$ is almost always invertible, in which case we + * have \f$ A = B V D V^{-1} \f$. This is called the generalized eigen-decomposition. + * + * The generalized eigenvalues and eigenvectors of a matrix pair may be complex, even when the + * matrices are real. Moreover, the generalized eigenvalue might be infinite if the matrix B is + * singular. To workaround this difficulty, the eigenvalues are provided as a pair of complex \f$ \alpha \f$ + * and real \f$ \beta \f$ such that: \f$ \lambda_i = \alpha_i / \beta_i \f$. If \f$ \beta_i \f$ is (nearly) zero, + * then one can consider the well defined left eigenvalue \f$ \mu = \beta_i / \alpha_i\f$ such that: + * \f$ \mu_i A v_i = B v_i \f$, or even \f$ \mu_i u_i^T A = u_i^T B \f$ where \f$ u_i \f$ is + * called the left eigenvector. + * + * Call the function compute() to compute the generalized eigenvalues and eigenvectors of + * a given matrix pair. Alternatively, you can use the + * GeneralizedEigenSolver(const MatrixType&, const MatrixType&, bool) constructor which computes the + * eigenvalues and eigenvectors at construction time. Once the eigenvalue and + * eigenvectors are computed, they can be retrieved with the eigenvalues() and + * eigenvectors() functions. + * + * Here is an usage example of this class: + * Example: \include GeneralizedEigenSolver.cpp + * Output: \verbinclude GeneralizedEigenSolver.out + * + * \sa MatrixBase::eigenvalues(), class ComplexEigenSolver, class SelfAdjointEigenSolver + */ +template<typename _MatrixType> class GeneralizedEigenSolver +{ + public: + + /** \brief Synonym for the template parameter \p _MatrixType. */ + typedef _MatrixType MatrixType; + + enum { + RowsAtCompileTime = MatrixType::RowsAtCompileTime, + ColsAtCompileTime = MatrixType::ColsAtCompileTime, + Options = MatrixType::Options, + MaxRowsAtCompileTime = MatrixType::MaxRowsAtCompileTime, + MaxColsAtCompileTime = MatrixType::MaxColsAtCompileTime + }; + + /** \brief Scalar type for matrices of type #MatrixType. */ + typedef typename MatrixType::Scalar Scalar; + typedef typename NumTraits<Scalar>::Real RealScalar; + typedef typename MatrixType::Index Index; + + /** \brief Complex scalar type for #MatrixType. + * + * This is \c std::complex<Scalar> if #Scalar is real (e.g., + * \c float or \c double) and just \c Scalar if #Scalar is + * complex. + */ + typedef std::complex<RealScalar> ComplexScalar; + + /** \brief Type for vector of real scalar values eigenvalues as returned by betas(). + * + * This is a column vector with entries of type #Scalar. + * The length of the vector is the size of #MatrixType. + */ + typedef Matrix<Scalar, ColsAtCompileTime, 1, Options & ~RowMajor, MaxColsAtCompileTime, 1> VectorType; + + /** \brief Type for vector of complex scalar values eigenvalues as returned by betas(). + * + * This is a column vector with entries of type #ComplexScalar. + * The length of the vector is the size of #MatrixType. + */ + typedef Matrix<ComplexScalar, ColsAtCompileTime, 1, Options & ~RowMajor, MaxColsAtCompileTime, 1> ComplexVectorType; + + /** \brief Expression type for the eigenvalues as returned by eigenvalues(). + */ + typedef CwiseBinaryOp<internal::scalar_quotient_op<ComplexScalar,Scalar>,ComplexVectorType,VectorType> EigenvalueType; + + /** \brief Type for matrix of eigenvectors as returned by eigenvectors(). + * + * This is a square matrix with entries of type #ComplexScalar. + * The size is the same as the size of #MatrixType. + */ + typedef Matrix<ComplexScalar, RowsAtCompileTime, ColsAtCompileTime, Options, MaxRowsAtCompileTime, MaxColsAtCompileTime> EigenvectorsType; + + /** \brief Default constructor. + * + * The default constructor is useful in cases in which the user intends to + * perform decompositions via EigenSolver::compute(const MatrixType&, bool). + * + * \sa compute() for an example. + */ + GeneralizedEigenSolver() : m_eivec(), m_alphas(), m_betas(), m_isInitialized(false), m_realQZ(), m_matS(), m_tmp() {} + + /** \brief Default constructor with memory preallocation + * + * Like the default constructor but with preallocation of the internal data + * according to the specified problem \a size. + * \sa GeneralizedEigenSolver() + */ + GeneralizedEigenSolver(Index size) + : m_eivec(size, size), + m_alphas(size), + m_betas(size), + m_isInitialized(false), + m_eigenvectorsOk(false), + m_realQZ(size), + m_matS(size, size), + m_tmp(size) + {} + + /** \brief Constructor; computes the generalized eigendecomposition of given matrix pair. + * + * \param[in] A Square matrix whose eigendecomposition is to be computed. + * \param[in] B Square matrix whose eigendecomposition is to be computed. + * \param[in] computeEigenvectors If true, both the eigenvectors and the + * eigenvalues are computed; if false, only the eigenvalues are computed. + * + * This constructor calls compute() to compute the generalized eigenvalues + * and eigenvectors. + * + * \sa compute() + */ + GeneralizedEigenSolver(const MatrixType& A, const MatrixType& B, bool computeEigenvectors = true) + : m_eivec(A.rows(), A.cols()), + m_alphas(A.cols()), + m_betas(A.cols()), + m_isInitialized(false), + m_eigenvectorsOk(false), + m_realQZ(A.cols()), + m_matS(A.rows(), A.cols()), + m_tmp(A.cols()) + { + compute(A, B, computeEigenvectors); + } + + /* \brief Returns the computed generalized eigenvectors. + * + * \returns %Matrix whose columns are the (possibly complex) eigenvectors. + * + * \pre Either the constructor + * GeneralizedEigenSolver(const MatrixType&,const MatrixType&, bool) or the member function + * compute(const MatrixType&, const MatrixType& bool) has been called before, and + * \p computeEigenvectors was set to true (the default). + * + * Column \f$ k \f$ of the returned matrix is an eigenvector corresponding + * to eigenvalue number \f$ k \f$ as returned by eigenvalues(). The + * eigenvectors are normalized to have (Euclidean) norm equal to one. The + * matrix returned by this function is the matrix \f$ V \f$ in the + * generalized eigendecomposition \f$ A = B V D V^{-1} \f$, if it exists. + * + * \sa eigenvalues() + */ +// EigenvectorsType eigenvectors() const; + + /** \brief Returns an expression of the computed generalized eigenvalues. + * + * \returns An expression of the column vector containing the eigenvalues. + * + * It is a shortcut for \code this->alphas().cwiseQuotient(this->betas()); \endcode + * Not that betas might contain zeros. It is therefore not recommended to use this function, + * but rather directly deal with the alphas and betas vectors. + * + * \pre Either the constructor + * GeneralizedEigenSolver(const MatrixType&,const MatrixType&,bool) or the member function + * compute(const MatrixType&,const MatrixType&,bool) has been called before. + * + * The eigenvalues are repeated according to their algebraic multiplicity, + * so there are as many eigenvalues as rows in the matrix. The eigenvalues + * are not sorted in any particular order. + * + * \sa alphas(), betas(), eigenvectors() + */ + EigenvalueType eigenvalues() const + { + eigen_assert(m_isInitialized && "GeneralizedEigenSolver is not initialized."); + return EigenvalueType(m_alphas,m_betas); + } + + /** \returns A const reference to the vectors containing the alpha values + * + * This vector permits to reconstruct the j-th eigenvalues as alphas(i)/betas(j). + * + * \sa betas(), eigenvalues() */ + ComplexVectorType alphas() const + { + eigen_assert(m_isInitialized && "GeneralizedEigenSolver is not initialized."); + return m_alphas; + } + + /** \returns A const reference to the vectors containing the beta values + * + * This vector permits to reconstruct the j-th eigenvalues as alphas(i)/betas(j). + * + * \sa alphas(), eigenvalues() */ + VectorType betas() const + { + eigen_assert(m_isInitialized && "GeneralizedEigenSolver is not initialized."); + return m_betas; + } + + /** \brief Computes generalized eigendecomposition of given matrix. + * + * \param[in] A Square matrix whose eigendecomposition is to be computed. + * \param[in] B Square matrix whose eigendecomposition is to be computed. + * \param[in] computeEigenvectors If true, both the eigenvectors and the + * eigenvalues are computed; if false, only the eigenvalues are + * computed. + * \returns Reference to \c *this + * + * This function computes the eigenvalues of the real matrix \p matrix. + * The eigenvalues() function can be used to retrieve them. If + * \p computeEigenvectors is true, then the eigenvectors are also computed + * and can be retrieved by calling eigenvectors(). + * + * The matrix is first reduced to real generalized Schur form using the RealQZ + * class. The generalized Schur decomposition is then used to compute the eigenvalues + * and eigenvectors. + * + * The cost of the computation is dominated by the cost of the + * generalized Schur decomposition. + * + * This method reuses of the allocated data in the GeneralizedEigenSolver object. + */ + GeneralizedEigenSolver& compute(const MatrixType& A, const MatrixType& B, bool computeEigenvectors = true); + + ComputationInfo info() const + { + eigen_assert(m_isInitialized && "EigenSolver is not initialized."); + return m_realQZ.info(); + } + + /** Sets the maximal number of iterations allowed. + */ + GeneralizedEigenSolver& setMaxIterations(Index maxIters) + { + m_realQZ.setMaxIterations(maxIters); + return *this; + } + + protected: + MatrixType m_eivec; + ComplexVectorType m_alphas; + VectorType m_betas; + bool m_isInitialized; + bool m_eigenvectorsOk; + RealQZ<MatrixType> m_realQZ; + MatrixType m_matS; + + typedef Matrix<Scalar, ColsAtCompileTime, 1, Options & ~RowMajor, MaxColsAtCompileTime, 1> ColumnVectorType; + ColumnVectorType m_tmp; +}; + +//template<typename MatrixType> +//typename GeneralizedEigenSolver<MatrixType>::EigenvectorsType GeneralizedEigenSolver<MatrixType>::eigenvectors() const +//{ +// eigen_assert(m_isInitialized && "EigenSolver is not initialized."); +// eigen_assert(m_eigenvectorsOk && "The eigenvectors have not been computed together with the eigenvalues."); +// Index n = m_eivec.cols(); +// EigenvectorsType matV(n,n); +// // TODO +// return matV; +//} + +template<typename MatrixType> +GeneralizedEigenSolver<MatrixType>& +GeneralizedEigenSolver<MatrixType>::compute(const MatrixType& A, const MatrixType& B, bool computeEigenvectors) +{ + using std::sqrt; + using std::abs; + eigen_assert(A.cols() == A.rows() && B.cols() == A.rows() && B.cols() == B.rows()); + + // Reduce to generalized real Schur form: + // A = Q S Z and B = Q T Z + m_realQZ.compute(A, B, computeEigenvectors); + + if (m_realQZ.info() == Success) + { + m_matS = m_realQZ.matrixS(); + if (computeEigenvectors) + m_eivec = m_realQZ.matrixZ().transpose(); + + // Compute eigenvalues from matS + m_alphas.resize(A.cols()); + m_betas.resize(A.cols()); + Index i = 0; + while (i < A.cols()) + { + if (i == A.cols() - 1 || m_matS.coeff(i+1, i) == Scalar(0)) + { + m_alphas.coeffRef(i) = m_matS.coeff(i, i); + m_betas.coeffRef(i) = m_realQZ.matrixT().coeff(i,i); + ++i; + } + else + { + Scalar p = Scalar(0.5) * (m_matS.coeff(i, i) - m_matS.coeff(i+1, i+1)); + Scalar z = sqrt(abs(p * p + m_matS.coeff(i+1, i) * m_matS.coeff(i, i+1))); + m_alphas.coeffRef(i) = ComplexScalar(m_matS.coeff(i+1, i+1) + p, z); + m_alphas.coeffRef(i+1) = ComplexScalar(m_matS.coeff(i+1, i+1) + p, -z); + + m_betas.coeffRef(i) = m_realQZ.matrixT().coeff(i,i); + m_betas.coeffRef(i+1) = m_realQZ.matrixT().coeff(i,i); + i += 2; + } + } + } + + m_isInitialized = true; + m_eigenvectorsOk = false;//computeEigenvectors; + + return *this; +} + +} // end namespace Eigen + +#endif // EIGEN_GENERALIZEDEIGENSOLVER_H diff --git a/extern/Eigen3/Eigen/src/Eigenvalues/HessenbergDecomposition.h b/extern/Eigen3/Eigen/src/Eigenvalues/HessenbergDecomposition.h index b8378b08a09..3db0c0106c9 100644 --- a/extern/Eigen3/Eigen/src/Eigenvalues/HessenbergDecomposition.h +++ b/extern/Eigen3/Eigen/src/Eigenvalues/HessenbergDecomposition.h @@ -82,7 +82,7 @@ template<typename _MatrixType> class HessenbergDecomposition typedef Matrix<Scalar, SizeMinusOne, 1, Options & ~RowMajor, MaxSizeMinusOne, 1> CoeffVectorType; /** \brief Return type of matrixQ() */ - typedef typename HouseholderSequence<MatrixType,CoeffVectorType>::ConjugateReturnType HouseholderSequenceType; + typedef HouseholderSequence<MatrixType,typename internal::remove_all<typename CoeffVectorType::ConjugateReturnType>::type> HouseholderSequenceType; typedef internal::HessenbergDecompositionMatrixHReturnType<MatrixType> MatrixHReturnType; @@ -291,7 +291,7 @@ template<typename _MatrixType> class HessenbergDecomposition template<typename MatrixType> void HessenbergDecomposition<MatrixType>::_compute(MatrixType& matA, CoeffVectorType& hCoeffs, VectorType& temp) { - assert(matA.rows()==matA.cols()); + eigen_assert(matA.rows()==matA.cols()); Index n = matA.rows(); temp.resize(n); for (Index i = 0; i<n-1; ++i) @@ -313,7 +313,7 @@ void HessenbergDecomposition<MatrixType>::_compute(MatrixType& matA, CoeffVector // A = A H' matA.rightCols(remainingSize) - .applyHouseholderOnTheRight(matA.col(i).tail(remainingSize-1).conjugate(), internal::conj(h), &temp.coeffRef(0)); + .applyHouseholderOnTheRight(matA.col(i).tail(remainingSize-1).conjugate(), numext::conj(h), &temp.coeffRef(0)); } } diff --git a/extern/Eigen3/Eigen/src/Eigenvalues/MatrixBaseEigenvalues.h b/extern/Eigen3/Eigen/src/Eigenvalues/MatrixBaseEigenvalues.h index 6af481c75f6..4fec8af0a3e 100644 --- a/extern/Eigen3/Eigen/src/Eigenvalues/MatrixBaseEigenvalues.h +++ b/extern/Eigen3/Eigen/src/Eigenvalues/MatrixBaseEigenvalues.h @@ -121,10 +121,11 @@ template<typename Derived> inline typename MatrixBase<Derived>::RealScalar MatrixBase<Derived>::operatorNorm() const { + using std::sqrt; typename Derived::PlainObject m_eval(derived()); // FIXME if it is really guaranteed that the eigenvalues are already sorted, // then we don't need to compute a maxCoeff() here, comparing the 1st and last ones is enough. - return internal::sqrt((m_eval*m_eval.adjoint()) + return sqrt((m_eval*m_eval.adjoint()) .eval() .template selfadjointView<Lower>() .eigenvalues() diff --git a/extern/Eigen3/Eigen/src/Eigenvalues/RealQZ.h b/extern/Eigen3/Eigen/src/Eigenvalues/RealQZ.h new file mode 100644 index 00000000000..5706eeebe91 --- /dev/null +++ b/extern/Eigen3/Eigen/src/Eigenvalues/RealQZ.h @@ -0,0 +1,624 @@ +// This file is part of Eigen, a lightweight C++ template library +// for linear algebra. +// +// Copyright (C) 2012 Alexey Korepanov <kaikaikai@yandex.ru> +// +// This Source Code Form is subject to the terms of the Mozilla +// Public License v. 2.0. If a copy of the MPL was not distributed +// with this file, You can obtain one at http://mozilla.org/MPL/2.0/. + +#ifndef EIGEN_REAL_QZ_H +#define EIGEN_REAL_QZ_H + +namespace Eigen { + + /** \eigenvalues_module \ingroup Eigenvalues_Module + * + * + * \class RealQZ + * + * \brief Performs a real QZ decomposition of a pair of square matrices + * + * \tparam _MatrixType the type of the matrix of which we are computing the + * real QZ decomposition; this is expected to be an instantiation of the + * Matrix class template. + * + * Given a real square matrices A and B, this class computes the real QZ + * decomposition: \f$ A = Q S Z \f$, \f$ B = Q T Z \f$ where Q and Z are + * real orthogonal matrixes, T is upper-triangular matrix, and S is upper + * quasi-triangular matrix. An orthogonal matrix is a matrix whose + * inverse is equal to its transpose, \f$ U^{-1} = U^T \f$. A quasi-triangular + * matrix is a block-triangular matrix whose diagonal consists of 1-by-1 + * blocks and 2-by-2 blocks where further reduction is impossible due to + * complex eigenvalues. + * + * The eigenvalues of the pencil \f$ A - z B \f$ can be obtained from + * 1x1 and 2x2 blocks on the diagonals of S and T. + * + * Call the function compute() to compute the real QZ decomposition of a + * given pair of matrices. Alternatively, you can use the + * RealQZ(const MatrixType& B, const MatrixType& B, bool computeQZ) + * constructor which computes the real QZ decomposition at construction + * time. Once the decomposition is computed, you can use the matrixS(), + * matrixT(), matrixQ() and matrixZ() functions to retrieve the matrices + * S, T, Q and Z in the decomposition. If computeQZ==false, some time + * is saved by not computing matrices Q and Z. + * + * Example: \include RealQZ_compute.cpp + * Output: \include RealQZ_compute.out + * + * \note The implementation is based on the algorithm in "Matrix Computations" + * by Gene H. Golub and Charles F. Van Loan, and a paper "An algorithm for + * generalized eigenvalue problems" by C.B.Moler and G.W.Stewart. + * + * \sa class RealSchur, class ComplexSchur, class EigenSolver, class ComplexEigenSolver + */ + + template<typename _MatrixType> class RealQZ + { + public: + typedef _MatrixType MatrixType; + enum { + RowsAtCompileTime = MatrixType::RowsAtCompileTime, + ColsAtCompileTime = MatrixType::ColsAtCompileTime, + Options = MatrixType::Options, + MaxRowsAtCompileTime = MatrixType::MaxRowsAtCompileTime, + MaxColsAtCompileTime = MatrixType::MaxColsAtCompileTime + }; + typedef typename MatrixType::Scalar Scalar; + typedef std::complex<typename NumTraits<Scalar>::Real> ComplexScalar; + typedef typename MatrixType::Index Index; + + typedef Matrix<ComplexScalar, ColsAtCompileTime, 1, Options & ~RowMajor, MaxColsAtCompileTime, 1> EigenvalueType; + typedef Matrix<Scalar, ColsAtCompileTime, 1, Options & ~RowMajor, MaxColsAtCompileTime, 1> ColumnVectorType; + + /** \brief Default constructor. + * + * \param [in] size Positive integer, size of the matrix whose QZ decomposition will be computed. + * + * The default constructor is useful in cases in which the user intends to + * perform decompositions via compute(). The \p size parameter is only + * used as a hint. It is not an error to give a wrong \p size, but it may + * impair performance. + * + * \sa compute() for an example. + */ + RealQZ(Index size = RowsAtCompileTime==Dynamic ? 1 : RowsAtCompileTime) : + m_S(size, size), + m_T(size, size), + m_Q(size, size), + m_Z(size, size), + m_workspace(size*2), + m_maxIters(400), + m_isInitialized(false) + { } + + /** \brief Constructor; computes real QZ decomposition of given matrices + * + * \param[in] A Matrix A. + * \param[in] B Matrix B. + * \param[in] computeQZ If false, A and Z are not computed. + * + * This constructor calls compute() to compute the QZ decomposition. + */ + RealQZ(const MatrixType& A, const MatrixType& B, bool computeQZ = true) : + m_S(A.rows(),A.cols()), + m_T(A.rows(),A.cols()), + m_Q(A.rows(),A.cols()), + m_Z(A.rows(),A.cols()), + m_workspace(A.rows()*2), + m_maxIters(400), + m_isInitialized(false) { + compute(A, B, computeQZ); + } + + /** \brief Returns matrix Q in the QZ decomposition. + * + * \returns A const reference to the matrix Q. + */ + const MatrixType& matrixQ() const { + eigen_assert(m_isInitialized && "RealQZ is not initialized."); + eigen_assert(m_computeQZ && "The matrices Q and Z have not been computed during the QZ decomposition."); + return m_Q; + } + + /** \brief Returns matrix Z in the QZ decomposition. + * + * \returns A const reference to the matrix Z. + */ + const MatrixType& matrixZ() const { + eigen_assert(m_isInitialized && "RealQZ is not initialized."); + eigen_assert(m_computeQZ && "The matrices Q and Z have not been computed during the QZ decomposition."); + return m_Z; + } + + /** \brief Returns matrix S in the QZ decomposition. + * + * \returns A const reference to the matrix S. + */ + const MatrixType& matrixS() const { + eigen_assert(m_isInitialized && "RealQZ is not initialized."); + return m_S; + } + + /** \brief Returns matrix S in the QZ decomposition. + * + * \returns A const reference to the matrix S. + */ + const MatrixType& matrixT() const { + eigen_assert(m_isInitialized && "RealQZ is not initialized."); + return m_T; + } + + /** \brief Computes QZ decomposition of given matrix. + * + * \param[in] A Matrix A. + * \param[in] B Matrix B. + * \param[in] computeQZ If false, A and Z are not computed. + * \returns Reference to \c *this + */ + RealQZ& compute(const MatrixType& A, const MatrixType& B, bool computeQZ = true); + + /** \brief Reports whether previous computation was successful. + * + * \returns \c Success if computation was succesful, \c NoConvergence otherwise. + */ + ComputationInfo info() const + { + eigen_assert(m_isInitialized && "RealQZ is not initialized."); + return m_info; + } + + /** \brief Returns number of performed QR-like iterations. + */ + Index iterations() const + { + eigen_assert(m_isInitialized && "RealQZ is not initialized."); + return m_global_iter; + } + + /** Sets the maximal number of iterations allowed to converge to one eigenvalue + * or decouple the problem. + */ + RealQZ& setMaxIterations(Index maxIters) + { + m_maxIters = maxIters; + return *this; + } + + private: + + MatrixType m_S, m_T, m_Q, m_Z; + Matrix<Scalar,Dynamic,1> m_workspace; + ComputationInfo m_info; + Index m_maxIters; + bool m_isInitialized; + bool m_computeQZ; + Scalar m_normOfT, m_normOfS; + Index m_global_iter; + + typedef Matrix<Scalar,3,1> Vector3s; + typedef Matrix<Scalar,2,1> Vector2s; + typedef Matrix<Scalar,2,2> Matrix2s; + typedef JacobiRotation<Scalar> JRs; + + void hessenbergTriangular(); + void computeNorms(); + Index findSmallSubdiagEntry(Index iu); + Index findSmallDiagEntry(Index f, Index l); + void splitOffTwoRows(Index i); + void pushDownZero(Index z, Index f, Index l); + void step(Index f, Index l, Index iter); + + }; // RealQZ + + /** \internal Reduces S and T to upper Hessenberg - triangular form */ + template<typename MatrixType> + void RealQZ<MatrixType>::hessenbergTriangular() + { + + const Index dim = m_S.cols(); + + // perform QR decomposition of T, overwrite T with R, save Q + HouseholderQR<MatrixType> qrT(m_T); + m_T = qrT.matrixQR(); + m_T.template triangularView<StrictlyLower>().setZero(); + m_Q = qrT.householderQ(); + // overwrite S with Q* S + m_S.applyOnTheLeft(m_Q.adjoint()); + // init Z as Identity + if (m_computeQZ) + m_Z = MatrixType::Identity(dim,dim); + // reduce S to upper Hessenberg with Givens rotations + for (Index j=0; j<=dim-3; j++) { + for (Index i=dim-1; i>=j+2; i--) { + JRs G; + // kill S(i,j) + if(m_S.coeff(i,j) != 0) + { + G.makeGivens(m_S.coeff(i-1,j), m_S.coeff(i,j), &m_S.coeffRef(i-1, j)); + m_S.coeffRef(i,j) = Scalar(0.0); + m_S.rightCols(dim-j-1).applyOnTheLeft(i-1,i,G.adjoint()); + m_T.rightCols(dim-i+1).applyOnTheLeft(i-1,i,G.adjoint()); + } + // update Q + if (m_computeQZ) + m_Q.applyOnTheRight(i-1,i,G); + // kill T(i,i-1) + if(m_T.coeff(i,i-1)!=Scalar(0)) + { + G.makeGivens(m_T.coeff(i,i), m_T.coeff(i,i-1), &m_T.coeffRef(i,i)); + m_T.coeffRef(i,i-1) = Scalar(0.0); + m_S.applyOnTheRight(i,i-1,G); + m_T.topRows(i).applyOnTheRight(i,i-1,G); + } + // update Z + if (m_computeQZ) + m_Z.applyOnTheLeft(i,i-1,G.adjoint()); + } + } + } + + /** \internal Computes vector L1 norms of S and T when in Hessenberg-Triangular form already */ + template<typename MatrixType> + inline void RealQZ<MatrixType>::computeNorms() + { + const Index size = m_S.cols(); + m_normOfS = Scalar(0.0); + m_normOfT = Scalar(0.0); + for (Index j = 0; j < size; ++j) + { + m_normOfS += m_S.col(j).segment(0, (std::min)(size,j+2)).cwiseAbs().sum(); + m_normOfT += m_T.row(j).segment(j, size - j).cwiseAbs().sum(); + } + } + + + /** \internal Look for single small sub-diagonal element S(res, res-1) and return res (or 0) */ + template<typename MatrixType> + inline typename MatrixType::Index RealQZ<MatrixType>::findSmallSubdiagEntry(Index iu) + { + using std::abs; + Index res = iu; + while (res > 0) + { + Scalar s = abs(m_S.coeff(res-1,res-1)) + abs(m_S.coeff(res,res)); + if (s == Scalar(0.0)) + s = m_normOfS; + if (abs(m_S.coeff(res,res-1)) < NumTraits<Scalar>::epsilon() * s) + break; + res--; + } + return res; + } + + /** \internal Look for single small diagonal element T(res, res) for res between f and l, and return res (or f-1) */ + template<typename MatrixType> + inline typename MatrixType::Index RealQZ<MatrixType>::findSmallDiagEntry(Index f, Index l) + { + using std::abs; + Index res = l; + while (res >= f) { + if (abs(m_T.coeff(res,res)) <= NumTraits<Scalar>::epsilon() * m_normOfT) + break; + res--; + } + return res; + } + + /** \internal decouple 2x2 diagonal block in rows i, i+1 if eigenvalues are real */ + template<typename MatrixType> + inline void RealQZ<MatrixType>::splitOffTwoRows(Index i) + { + using std::abs; + using std::sqrt; + const Index dim=m_S.cols(); + if (abs(m_S.coeff(i+1,i)==Scalar(0))) + return; + Index z = findSmallDiagEntry(i,i+1); + if (z==i-1) + { + // block of (S T^{-1}) + Matrix2s STi = m_T.template block<2,2>(i,i).template triangularView<Upper>(). + template solve<OnTheRight>(m_S.template block<2,2>(i,i)); + Scalar p = Scalar(0.5)*(STi(0,0)-STi(1,1)); + Scalar q = p*p + STi(1,0)*STi(0,1); + if (q>=0) { + Scalar z = sqrt(q); + // one QR-like iteration for ABi - lambda I + // is enough - when we know exact eigenvalue in advance, + // convergence is immediate + JRs G; + if (p>=0) + G.makeGivens(p + z, STi(1,0)); + else + G.makeGivens(p - z, STi(1,0)); + m_S.rightCols(dim-i).applyOnTheLeft(i,i+1,G.adjoint()); + m_T.rightCols(dim-i).applyOnTheLeft(i,i+1,G.adjoint()); + // update Q + if (m_computeQZ) + m_Q.applyOnTheRight(i,i+1,G); + + G.makeGivens(m_T.coeff(i+1,i+1), m_T.coeff(i+1,i)); + m_S.topRows(i+2).applyOnTheRight(i+1,i,G); + m_T.topRows(i+2).applyOnTheRight(i+1,i,G); + // update Z + if (m_computeQZ) + m_Z.applyOnTheLeft(i+1,i,G.adjoint()); + + m_S.coeffRef(i+1,i) = Scalar(0.0); + m_T.coeffRef(i+1,i) = Scalar(0.0); + } + } + else + { + pushDownZero(z,i,i+1); + } + } + + /** \internal use zero in T(z,z) to zero S(l,l-1), working in block f..l */ + template<typename MatrixType> + inline void RealQZ<MatrixType>::pushDownZero(Index z, Index f, Index l) + { + JRs G; + const Index dim = m_S.cols(); + for (Index zz=z; zz<l; zz++) + { + // push 0 down + Index firstColS = zz>f ? (zz-1) : zz; + G.makeGivens(m_T.coeff(zz, zz+1), m_T.coeff(zz+1, zz+1)); + m_S.rightCols(dim-firstColS).applyOnTheLeft(zz,zz+1,G.adjoint()); + m_T.rightCols(dim-zz).applyOnTheLeft(zz,zz+1,G.adjoint()); + m_T.coeffRef(zz+1,zz+1) = Scalar(0.0); + // update Q + if (m_computeQZ) + m_Q.applyOnTheRight(zz,zz+1,G); + // kill S(zz+1, zz-1) + if (zz>f) + { + G.makeGivens(m_S.coeff(zz+1, zz), m_S.coeff(zz+1,zz-1)); + m_S.topRows(zz+2).applyOnTheRight(zz, zz-1,G); + m_T.topRows(zz+1).applyOnTheRight(zz, zz-1,G); + m_S.coeffRef(zz+1,zz-1) = Scalar(0.0); + // update Z + if (m_computeQZ) + m_Z.applyOnTheLeft(zz,zz-1,G.adjoint()); + } + } + // finally kill S(l,l-1) + G.makeGivens(m_S.coeff(l,l), m_S.coeff(l,l-1)); + m_S.applyOnTheRight(l,l-1,G); + m_T.applyOnTheRight(l,l-1,G); + m_S.coeffRef(l,l-1)=Scalar(0.0); + // update Z + if (m_computeQZ) + m_Z.applyOnTheLeft(l,l-1,G.adjoint()); + } + + /** \internal QR-like iterative step for block f..l */ + template<typename MatrixType> + inline void RealQZ<MatrixType>::step(Index f, Index l, Index iter) + { + using std::abs; + const Index dim = m_S.cols(); + + // x, y, z + Scalar x, y, z; + if (iter==10) + { + // Wilkinson ad hoc shift + const Scalar + a11=m_S.coeff(f+0,f+0), a12=m_S.coeff(f+0,f+1), + a21=m_S.coeff(f+1,f+0), a22=m_S.coeff(f+1,f+1), a32=m_S.coeff(f+2,f+1), + b12=m_T.coeff(f+0,f+1), + b11i=Scalar(1.0)/m_T.coeff(f+0,f+0), + b22i=Scalar(1.0)/m_T.coeff(f+1,f+1), + a87=m_S.coeff(l-1,l-2), + a98=m_S.coeff(l-0,l-1), + b77i=Scalar(1.0)/m_T.coeff(l-2,l-2), + b88i=Scalar(1.0)/m_T.coeff(l-1,l-1); + Scalar ss = abs(a87*b77i) + abs(a98*b88i), + lpl = Scalar(1.5)*ss, + ll = ss*ss; + x = ll + a11*a11*b11i*b11i - lpl*a11*b11i + a12*a21*b11i*b22i + - a11*a21*b12*b11i*b11i*b22i; + y = a11*a21*b11i*b11i - lpl*a21*b11i + a21*a22*b11i*b22i + - a21*a21*b12*b11i*b11i*b22i; + z = a21*a32*b11i*b22i; + } + else if (iter==16) + { + // another exceptional shift + x = m_S.coeff(f,f)/m_T.coeff(f,f)-m_S.coeff(l,l)/m_T.coeff(l,l) + m_S.coeff(l,l-1)*m_T.coeff(l-1,l) / + (m_T.coeff(l-1,l-1)*m_T.coeff(l,l)); + y = m_S.coeff(f+1,f)/m_T.coeff(f,f); + z = 0; + } + else if (iter>23 && !(iter%8)) + { + // extremely exceptional shift + x = internal::random<Scalar>(-1.0,1.0); + y = internal::random<Scalar>(-1.0,1.0); + z = internal::random<Scalar>(-1.0,1.0); + } + else + { + // Compute the shifts: (x,y,z,0...) = (AB^-1 - l1 I) (AB^-1 - l2 I) e1 + // where l1 and l2 are the eigenvalues of the 2x2 matrix C = U V^-1 where + // U and V are 2x2 bottom right sub matrices of A and B. Thus: + // = AB^-1AB^-1 + l1 l2 I - (l1+l2)(AB^-1) + // = AB^-1AB^-1 + det(M) - tr(M)(AB^-1) + // Since we are only interested in having x, y, z with a correct ratio, we have: + const Scalar + a11 = m_S.coeff(f,f), a12 = m_S.coeff(f,f+1), + a21 = m_S.coeff(f+1,f), a22 = m_S.coeff(f+1,f+1), + a32 = m_S.coeff(f+2,f+1), + + a88 = m_S.coeff(l-1,l-1), a89 = m_S.coeff(l-1,l), + a98 = m_S.coeff(l,l-1), a99 = m_S.coeff(l,l), + + b11 = m_T.coeff(f,f), b12 = m_T.coeff(f,f+1), + b22 = m_T.coeff(f+1,f+1), + + b88 = m_T.coeff(l-1,l-1), b89 = m_T.coeff(l-1,l), + b99 = m_T.coeff(l,l); + + x = ( (a88/b88 - a11/b11)*(a99/b99 - a11/b11) - (a89/b99)*(a98/b88) + (a98/b88)*(b89/b99)*(a11/b11) ) * (b11/a21) + + a12/b22 - (a11/b11)*(b12/b22); + y = (a22/b22-a11/b11) - (a21/b11)*(b12/b22) - (a88/b88-a11/b11) - (a99/b99-a11/b11) + (a98/b88)*(b89/b99); + z = a32/b22; + } + + JRs G; + + for (Index k=f; k<=l-2; k++) + { + // variables for Householder reflections + Vector2s essential2; + Scalar tau, beta; + + Vector3s hr(x,y,z); + + // Q_k to annihilate S(k+1,k-1) and S(k+2,k-1) + hr.makeHouseholderInPlace(tau, beta); + essential2 = hr.template bottomRows<2>(); + Index fc=(std::max)(k-1,Index(0)); // first col to update + m_S.template middleRows<3>(k).rightCols(dim-fc).applyHouseholderOnTheLeft(essential2, tau, m_workspace.data()); + m_T.template middleRows<3>(k).rightCols(dim-fc).applyHouseholderOnTheLeft(essential2, tau, m_workspace.data()); + if (m_computeQZ) + m_Q.template middleCols<3>(k).applyHouseholderOnTheRight(essential2, tau, m_workspace.data()); + if (k>f) + m_S.coeffRef(k+2,k-1) = m_S.coeffRef(k+1,k-1) = Scalar(0.0); + + // Z_{k1} to annihilate T(k+2,k+1) and T(k+2,k) + hr << m_T.coeff(k+2,k+2),m_T.coeff(k+2,k),m_T.coeff(k+2,k+1); + hr.makeHouseholderInPlace(tau, beta); + essential2 = hr.template bottomRows<2>(); + { + Index lr = (std::min)(k+4,dim); // last row to update + Map<Matrix<Scalar,Dynamic,1> > tmp(m_workspace.data(),lr); + // S + tmp = m_S.template middleCols<2>(k).topRows(lr) * essential2; + tmp += m_S.col(k+2).head(lr); + m_S.col(k+2).head(lr) -= tau*tmp; + m_S.template middleCols<2>(k).topRows(lr) -= (tau*tmp) * essential2.adjoint(); + // T + tmp = m_T.template middleCols<2>(k).topRows(lr) * essential2; + tmp += m_T.col(k+2).head(lr); + m_T.col(k+2).head(lr) -= tau*tmp; + m_T.template middleCols<2>(k).topRows(lr) -= (tau*tmp) * essential2.adjoint(); + } + if (m_computeQZ) + { + // Z + Map<Matrix<Scalar,1,Dynamic> > tmp(m_workspace.data(),dim); + tmp = essential2.adjoint()*(m_Z.template middleRows<2>(k)); + tmp += m_Z.row(k+2); + m_Z.row(k+2) -= tau*tmp; + m_Z.template middleRows<2>(k) -= essential2 * (tau*tmp); + } + m_T.coeffRef(k+2,k) = m_T.coeffRef(k+2,k+1) = Scalar(0.0); + + // Z_{k2} to annihilate T(k+1,k) + G.makeGivens(m_T.coeff(k+1,k+1), m_T.coeff(k+1,k)); + m_S.applyOnTheRight(k+1,k,G); + m_T.applyOnTheRight(k+1,k,G); + // update Z + if (m_computeQZ) + m_Z.applyOnTheLeft(k+1,k,G.adjoint()); + m_T.coeffRef(k+1,k) = Scalar(0.0); + + // update x,y,z + x = m_S.coeff(k+1,k); + y = m_S.coeff(k+2,k); + if (k < l-2) + z = m_S.coeff(k+3,k); + } // loop over k + + // Q_{n-1} to annihilate y = S(l,l-2) + G.makeGivens(x,y); + m_S.applyOnTheLeft(l-1,l,G.adjoint()); + m_T.applyOnTheLeft(l-1,l,G.adjoint()); + if (m_computeQZ) + m_Q.applyOnTheRight(l-1,l,G); + m_S.coeffRef(l,l-2) = Scalar(0.0); + + // Z_{n-1} to annihilate T(l,l-1) + G.makeGivens(m_T.coeff(l,l),m_T.coeff(l,l-1)); + m_S.applyOnTheRight(l,l-1,G); + m_T.applyOnTheRight(l,l-1,G); + if (m_computeQZ) + m_Z.applyOnTheLeft(l,l-1,G.adjoint()); + m_T.coeffRef(l,l-1) = Scalar(0.0); + } + + + template<typename MatrixType> + RealQZ<MatrixType>& RealQZ<MatrixType>::compute(const MatrixType& A_in, const MatrixType& B_in, bool computeQZ) + { + + const Index dim = A_in.cols(); + + eigen_assert (A_in.rows()==dim && A_in.cols()==dim + && B_in.rows()==dim && B_in.cols()==dim + && "Need square matrices of the same dimension"); + + m_isInitialized = true; + m_computeQZ = computeQZ; + m_S = A_in; m_T = B_in; + m_workspace.resize(dim*2); + m_global_iter = 0; + + // entrance point: hessenberg triangular decomposition + hessenbergTriangular(); + // compute L1 vector norms of T, S into m_normOfS, m_normOfT + computeNorms(); + + Index l = dim-1, + f, + local_iter = 0; + + while (l>0 && local_iter<m_maxIters) + { + f = findSmallSubdiagEntry(l); + // now rows and columns f..l (including) decouple from the rest of the problem + if (f>0) m_S.coeffRef(f,f-1) = Scalar(0.0); + if (f == l) // One root found + { + l--; + local_iter = 0; + } + else if (f == l-1) // Two roots found + { + splitOffTwoRows(f); + l -= 2; + local_iter = 0; + } + else // No convergence yet + { + // if there's zero on diagonal of T, we can isolate an eigenvalue with Givens rotations + Index z = findSmallDiagEntry(f,l); + if (z>=f) + { + // zero found + pushDownZero(z,f,l); + } + else + { + // We are sure now that S.block(f,f, l-f+1,l-f+1) is underuced upper-Hessenberg + // and T.block(f,f, l-f+1,l-f+1) is invertible uper-triangular, which allows to + // apply a QR-like iteration to rows and columns f..l. + step(f,l, local_iter); + local_iter++; + m_global_iter++; + } + } + } + // check if we converged before reaching iterations limit + m_info = (local_iter<m_maxIters) ? Success : NoConvergence; + return *this; + } // end compute + +} // end namespace Eigen + +#endif //EIGEN_REAL_QZ diff --git a/extern/Eigen3/Eigen/src/Eigenvalues/RealSchur.h b/extern/Eigen3/Eigen/src/Eigenvalues/RealSchur.h index 781692eccd3..64d13634141 100644 --- a/extern/Eigen3/Eigen/src/Eigenvalues/RealSchur.h +++ b/extern/Eigen3/Eigen/src/Eigenvalues/RealSchur.h @@ -2,7 +2,7 @@ // for linear algebra. // // Copyright (C) 2008 Gael Guennebaud <gael.guennebaud@inria.fr> -// Copyright (C) 2010 Jitse Niesen <jitse@maths.leeds.ac.uk> +// Copyright (C) 2010,2012 Jitse Niesen <jitse@maths.leeds.ac.uk> // // This Source Code Form is subject to the terms of the Mozilla // Public License v. 2.0. If a copy of the MPL was not distributed @@ -86,7 +86,8 @@ template<typename _MatrixType> class RealSchur m_workspaceVector(size), m_hess(size), m_isInitialized(false), - m_matUisUptodate(false) + m_matUisUptodate(false), + m_maxIters(-1) { } /** \brief Constructor; computes real Schur decomposition of given matrix. @@ -105,7 +106,8 @@ template<typename _MatrixType> class RealSchur m_workspaceVector(matrix.rows()), m_hess(matrix.rows()), m_isInitialized(false), - m_matUisUptodate(false) + m_matUisUptodate(false), + m_maxIters(-1) { compute(matrix, computeU); } @@ -160,9 +162,30 @@ template<typename _MatrixType> class RealSchur * * Example: \include RealSchur_compute.cpp * Output: \verbinclude RealSchur_compute.out + * + * \sa compute(const MatrixType&, bool, Index) */ RealSchur& compute(const MatrixType& matrix, bool computeU = true); + /** \brief Computes Schur decomposition of a Hessenberg matrix H = Z T Z^T + * \param[in] matrixH Matrix in Hessenberg form H + * \param[in] matrixQ orthogonal matrix Q that transform a matrix A to H : A = Q H Q^T + * \param computeU Computes the matriX U of the Schur vectors + * \return Reference to \c *this + * + * This routine assumes that the matrix is already reduced in Hessenberg form matrixH + * using either the class HessenbergDecomposition or another mean. + * It computes the upper quasi-triangular matrix T of the Schur decomposition of H + * When computeU is true, this routine computes the matrix U such that + * A = U T U^T = (QZ) T (QZ)^T = Q H Q^T where A is the initial matrix + * + * NOTE Q is referenced if computeU is true; so, if the initial orthogonal matrix + * is not available, the user should give an identity matrix (Q.setIdentity()) + * + * \sa compute(const MatrixType&, bool) + */ + template<typename HessMatrixType, typename OrthMatrixType> + RealSchur& computeFromHessenberg(const HessMatrixType& matrixH, const OrthMatrixType& matrixQ, bool computeU); /** \brief Reports whether previous computation was successful. * * \returns \c Success if computation was succesful, \c NoConvergence otherwise. @@ -173,11 +196,29 @@ template<typename _MatrixType> class RealSchur return m_info; } - /** \brief Maximum number of iterations. + /** \brief Sets the maximum number of iterations allowed. + * + * If not specified by the user, the maximum number of iterations is m_maxIterationsPerRow times the size + * of the matrix. + */ + RealSchur& setMaxIterations(Index maxIters) + { + m_maxIters = maxIters; + return *this; + } + + /** \brief Returns the maximum number of iterations. */ + Index getMaxIterations() + { + return m_maxIters; + } + + /** \brief Maximum number of iterations per row. * - * Maximum number of iterations allowed for an eigenvalue to converge. + * If not otherwise specified, the maximum number of iterations is this number times the size of the + * matrix. It is currently set to 40. */ - static const int m_maxIterations = 40; + static const int m_maxIterationsPerRow = 40; private: @@ -188,12 +229,13 @@ template<typename _MatrixType> class RealSchur ComputationInfo m_info; bool m_isInitialized; bool m_matUisUptodate; + Index m_maxIters; typedef Matrix<Scalar,3,1> Vector3s; Scalar computeNormOfT(); - Index findSmallSubdiagEntry(Index iu, Scalar norm); - void splitOffTwoRows(Index iu, bool computeU, Scalar exshift); + Index findSmallSubdiagEntry(Index iu, const Scalar& norm); + void splitOffTwoRows(Index iu, bool computeU, const Scalar& exshift); void computeShift(Index iu, Index iter, Scalar& exshift, Vector3s& shiftInfo); void initFrancisQRStep(Index il, Index iu, const Vector3s& shiftInfo, Index& im, Vector3s& firstHouseholderVector); void performFrancisQRStep(Index il, Index im, Index iu, bool computeU, const Vector3s& firstHouseholderVector, Scalar* workspace); @@ -203,15 +245,30 @@ template<typename _MatrixType> class RealSchur template<typename MatrixType> RealSchur<MatrixType>& RealSchur<MatrixType>::compute(const MatrixType& matrix, bool computeU) { - assert(matrix.cols() == matrix.rows()); + eigen_assert(matrix.cols() == matrix.rows()); + Index maxIters = m_maxIters; + if (maxIters == -1) + maxIters = m_maxIterationsPerRow * matrix.rows(); // Step 1. Reduce to Hessenberg form m_hess.compute(matrix); - m_matT = m_hess.matrixH(); - if (computeU) - m_matU = m_hess.matrixQ(); // Step 2. Reduce to real Schur form + computeFromHessenberg(m_hess.matrixH(), m_hess.matrixQ(), computeU); + + return *this; +} +template<typename MatrixType> +template<typename HessMatrixType, typename OrthMatrixType> +RealSchur<MatrixType>& RealSchur<MatrixType>::computeFromHessenberg(const HessMatrixType& matrixH, const OrthMatrixType& matrixQ, bool computeU) +{ + m_matT = matrixH; + if(computeU) + m_matU = matrixQ; + + Index maxIters = m_maxIters; + if (maxIters == -1) + maxIters = m_maxIterationsPerRow * matrixH.rows(); m_workspaceVector.resize(m_matT.cols()); Scalar* workspace = &m_workspaceVector.coeffRef(0); @@ -220,8 +277,9 @@ RealSchur<MatrixType>& RealSchur<MatrixType>::compute(const MatrixType& matrix, // Rows il,...,iu is the part we are working on (the active window). // Rows iu+1,...,end are already brought in triangular form. Index iu = m_matT.cols() - 1; - Index iter = 0; // iteration count - Scalar exshift(0); // sum of exceptional shifts + Index iter = 0; // iteration count for current eigenvalue + Index totalIter = 0; // iteration count for whole matrix + Scalar exshift(0); // sum of exceptional shifts Scalar norm = computeNormOfT(); if(norm!=0) @@ -251,14 +309,15 @@ RealSchur<MatrixType>& RealSchur<MatrixType>::compute(const MatrixType& matrix, Vector3s firstHouseholderVector(0,0,0), shiftInfo; computeShift(iu, iter, exshift, shiftInfo); iter = iter + 1; - if (iter > m_maxIterations * m_matT.cols()) break; + totalIter = totalIter + 1; + if (totalIter > maxIters) break; Index im; initFrancisQRStep(il, iu, shiftInfo, im, firstHouseholderVector); performFrancisQRStep(il, im, iu, computeU, firstHouseholderVector, workspace); } } } - if(iter <= m_maxIterations * m_matT.cols()) + if(totalIter <= maxIters) m_info = Success; else m_info = NoConvergence; @@ -278,21 +337,22 @@ inline typename MatrixType::Scalar RealSchur<MatrixType>::computeNormOfT() // + m_matT.bottomLeftCorner(size-1,size-1).diagonal().cwiseAbs().sum(); Scalar norm(0); for (Index j = 0; j < size; ++j) - norm += m_matT.row(j).segment((std::max)(j-1,Index(0)), size-(std::max)(j-1,Index(0))).cwiseAbs().sum(); + norm += m_matT.col(j).segment(0, (std::min)(size,j+2)).cwiseAbs().sum(); return norm; } /** \internal Look for single small sub-diagonal element and returns its index */ template<typename MatrixType> -inline typename MatrixType::Index RealSchur<MatrixType>::findSmallSubdiagEntry(Index iu, Scalar norm) +inline typename MatrixType::Index RealSchur<MatrixType>::findSmallSubdiagEntry(Index iu, const Scalar& norm) { + using std::abs; Index res = iu; while (res > 0) { - Scalar s = internal::abs(m_matT.coeff(res-1,res-1)) + internal::abs(m_matT.coeff(res,res)); + Scalar s = abs(m_matT.coeff(res-1,res-1)) + abs(m_matT.coeff(res,res)); if (s == 0.0) s = norm; - if (internal::abs(m_matT.coeff(res,res-1)) < NumTraits<Scalar>::epsilon() * s) + if (abs(m_matT.coeff(res,res-1)) < NumTraits<Scalar>::epsilon() * s) break; res--; } @@ -301,8 +361,10 @@ inline typename MatrixType::Index RealSchur<MatrixType>::findSmallSubdiagEntry(I /** \internal Update T given that rows iu-1 and iu decouple from the rest. */ template<typename MatrixType> -inline void RealSchur<MatrixType>::splitOffTwoRows(Index iu, bool computeU, Scalar exshift) +inline void RealSchur<MatrixType>::splitOffTwoRows(Index iu, bool computeU, const Scalar& exshift) { + using std::sqrt; + using std::abs; const Index size = m_matT.cols(); // The eigenvalues of the 2x2 matrix [a b; c d] are @@ -314,7 +376,7 @@ inline void RealSchur<MatrixType>::splitOffTwoRows(Index iu, bool computeU, Scal if (q >= Scalar(0)) // Two real eigenvalues { - Scalar z = internal::sqrt(internal::abs(q)); + Scalar z = sqrt(abs(q)); JacobiRotation<Scalar> rot; if (p >= Scalar(0)) rot.makeGivens(p + z, m_matT.coeff(iu, iu-1)); @@ -336,6 +398,8 @@ inline void RealSchur<MatrixType>::splitOffTwoRows(Index iu, bool computeU, Scal template<typename MatrixType> inline void RealSchur<MatrixType>::computeShift(Index iu, Index iter, Scalar& exshift, Vector3s& shiftInfo) { + using std::sqrt; + using std::abs; shiftInfo.coeffRef(0) = m_matT.coeff(iu,iu); shiftInfo.coeffRef(1) = m_matT.coeff(iu-1,iu-1); shiftInfo.coeffRef(2) = m_matT.coeff(iu,iu-1) * m_matT.coeff(iu-1,iu); @@ -346,7 +410,7 @@ inline void RealSchur<MatrixType>::computeShift(Index iu, Index iter, Scalar& ex exshift += shiftInfo.coeff(0); for (Index i = 0; i <= iu; ++i) m_matT.coeffRef(i,i) -= shiftInfo.coeff(0); - Scalar s = internal::abs(m_matT.coeff(iu,iu-1)) + internal::abs(m_matT.coeff(iu-1,iu-2)); + Scalar s = abs(m_matT.coeff(iu,iu-1)) + abs(m_matT.coeff(iu-1,iu-2)); shiftInfo.coeffRef(0) = Scalar(0.75) * s; shiftInfo.coeffRef(1) = Scalar(0.75) * s; shiftInfo.coeffRef(2) = Scalar(-0.4375) * s * s; @@ -359,7 +423,7 @@ inline void RealSchur<MatrixType>::computeShift(Index iu, Index iter, Scalar& ex s = s * s + shiftInfo.coeff(2); if (s > Scalar(0)) { - s = internal::sqrt(s); + s = sqrt(s); if (shiftInfo.coeff(1) < shiftInfo.coeff(0)) s = -s; s = s + (shiftInfo.coeff(1) - shiftInfo.coeff(0)) / Scalar(2.0); @@ -376,6 +440,7 @@ inline void RealSchur<MatrixType>::computeShift(Index iu, Index iter, Scalar& ex template<typename MatrixType> inline void RealSchur<MatrixType>::initFrancisQRStep(Index il, Index iu, const Vector3s& shiftInfo, Index& im, Vector3s& firstHouseholderVector) { + using std::abs; Vector3s& v = firstHouseholderVector; // alias to save typing for (im = iu-2; im >= il; --im) @@ -389,9 +454,9 @@ inline void RealSchur<MatrixType>::initFrancisQRStep(Index il, Index iu, const V if (im == il) { break; } - const Scalar lhs = m_matT.coeff(im,im-1) * (internal::abs(v.coeff(1)) + internal::abs(v.coeff(2))); - const Scalar rhs = v.coeff(0) * (internal::abs(m_matT.coeff(im-1,im-1)) + internal::abs(Tmm) + internal::abs(m_matT.coeff(im+1,im+1))); - if (internal::abs(lhs) < NumTraits<Scalar>::epsilon() * rhs) + const Scalar lhs = m_matT.coeff(im,im-1) * (abs(v.coeff(1)) + abs(v.coeff(2))); + const Scalar rhs = v.coeff(0) * (abs(m_matT.coeff(im-1,im-1)) + abs(Tmm) + abs(m_matT.coeff(im+1,im+1))); + if (abs(lhs) < NumTraits<Scalar>::epsilon() * rhs) { break; } @@ -402,8 +467,8 @@ inline void RealSchur<MatrixType>::initFrancisQRStep(Index il, Index iu, const V template<typename MatrixType> inline void RealSchur<MatrixType>::performFrancisQRStep(Index il, Index im, Index iu, bool computeU, const Vector3s& firstHouseholderVector, Scalar* workspace) { - assert(im >= il); - assert(im <= iu-2); + eigen_assert(im >= il); + eigen_assert(im <= iu-2); const Index size = m_matT.cols(); diff --git a/extern/Eigen3/Eigen/src/Eigenvalues/RealSchur_MKL.h b/extern/Eigen3/Eigen/src/Eigenvalues/RealSchur_MKL.h index 960ec3c764a..ad973646028 100644 --- a/extern/Eigen3/Eigen/src/Eigenvalues/RealSchur_MKL.h +++ b/extern/Eigen3/Eigen/src/Eigenvalues/RealSchur_MKL.h @@ -48,7 +48,7 @@ RealSchur<Matrix<EIGTYPE, Dynamic, Dynamic, EIGCOLROW> >::compute(const Matrix<E typedef MatrixType::Scalar Scalar; \ typedef MatrixType::RealScalar RealScalar; \ \ - assert(matrix.cols() == matrix.rows()); \ + eigen_assert(matrix.cols() == matrix.rows()); \ \ lapack_int n = matrix.cols(), sdim, info; \ lapack_int lda = matrix.outerStride(); \ diff --git a/extern/Eigen3/Eigen/src/Eigenvalues/SelfAdjointEigenSolver.h b/extern/Eigen3/Eigen/src/Eigenvalues/SelfAdjointEigenSolver.h index acc5576feb1..3993046a88e 100644 --- a/extern/Eigen3/Eigen/src/Eigenvalues/SelfAdjointEigenSolver.h +++ b/extern/Eigen3/Eigen/src/Eigenvalues/SelfAdjointEigenSolver.h @@ -384,6 +384,7 @@ template<typename MatrixType> SelfAdjointEigenSolver<MatrixType>& SelfAdjointEigenSolver<MatrixType> ::compute(const MatrixType& matrix, int options) { + using std::abs; eigen_assert(matrix.cols() == matrix.rows()); eigen_assert((options&~(EigVecMask|GenEigMask))==0 && (options&EigVecMask)!=EigVecMask @@ -394,7 +395,7 @@ SelfAdjointEigenSolver<MatrixType>& SelfAdjointEigenSolver<MatrixType> if(n==1) { - m_eivalues.coeffRef(0,0) = internal::real(matrix.coeff(0,0)); + m_eivalues.coeffRef(0,0) = numext::real(matrix.coeff(0,0)); if(computeEigenvectors) m_eivec.setOnes(n,n); m_info = Success; @@ -408,9 +409,10 @@ SelfAdjointEigenSolver<MatrixType>& SelfAdjointEigenSolver<MatrixType> MatrixType& mat = m_eivec; // map the matrix coefficients to [-1:1] to avoid over- and underflow. - RealScalar scale = matrix.cwiseAbs().maxCoeff(); + mat = matrix.template triangularView<Lower>(); + RealScalar scale = mat.cwiseAbs().maxCoeff(); if(scale==RealScalar(0)) scale = RealScalar(1); - mat = matrix / scale; + mat.template triangularView<Lower>() /= scale; m_subdiag.resize(n-1); internal::tridiagonalization_inplace(mat, diag, m_subdiag, computeEigenvectors); @@ -421,7 +423,7 @@ SelfAdjointEigenSolver<MatrixType>& SelfAdjointEigenSolver<MatrixType> while (end>0) { for (Index i = start; i<end; ++i) - if (internal::isMuchSmallerThan(internal::abs(m_subdiag[i]),(internal::abs(diag[i])+internal::abs(diag[i+1])))) + if (internal::isMuchSmallerThan(abs(m_subdiag[i]),(abs(diag[i])+abs(diag[i+1])))) m_subdiag[i] = 0; // find the largest unreduced block @@ -667,7 +669,7 @@ template<typename SolverType> struct direct_selfadjoint_eigenvalues<SolverType,2 static inline void computeRoots(const MatrixType& m, VectorType& roots) { using std::sqrt; - const Scalar t0 = Scalar(0.5) * sqrt( abs2(m(0,0)-m(1,1)) + Scalar(4)*m(1,0)*m(1,0)); + const Scalar t0 = Scalar(0.5) * sqrt( numext::abs2(m(0,0)-m(1,1)) + Scalar(4)*m(1,0)*m(1,0)); const Scalar t1 = Scalar(0.5) * (m(0,0) + m(1,1)); roots(0) = t1 - t0; roots(1) = t1 + t0; @@ -675,6 +677,7 @@ template<typename SolverType> struct direct_selfadjoint_eigenvalues<SolverType,2 static inline void run(SolverType& solver, const MatrixType& mat, int options) { + using std::sqrt; eigen_assert(mat.cols() == 2 && mat.cols() == mat.rows()); eigen_assert((options&~(EigVecMask|GenEigMask))==0 && (options&EigVecMask)!=EigVecMask @@ -696,9 +699,9 @@ template<typename SolverType> struct direct_selfadjoint_eigenvalues<SolverType,2 if(computeEigenvectors) { scaledMat.diagonal().array () -= eivals(1); - Scalar a2 = abs2(scaledMat(0,0)); - Scalar c2 = abs2(scaledMat(1,1)); - Scalar b2 = abs2(scaledMat(1,0)); + Scalar a2 = numext::abs2(scaledMat(0,0)); + Scalar c2 = numext::abs2(scaledMat(1,1)); + Scalar b2 = numext::abs2(scaledMat(1,0)); if(a2>c2) { eivecs.col(1) << -scaledMat(1,0), scaledMat(0,0); @@ -736,14 +739,24 @@ namespace internal { template<int StorageOrder,typename RealScalar, typename Scalar, typename Index> static void tridiagonal_qr_step(RealScalar* diag, RealScalar* subdiag, Index start, Index end, Scalar* matrixQ, Index n) { + using std::abs; RealScalar td = (diag[end-1] - diag[end])*RealScalar(0.5); RealScalar e = subdiag[end-1]; // Note that thanks to scaling, e^2 or td^2 cannot overflow, however they can still // underflow thus leading to inf/NaN values when using the following commented code: -// RealScalar e2 = abs2(subdiag[end-1]); +// RealScalar e2 = numext::abs2(subdiag[end-1]); // RealScalar mu = diag[end] - e2 / (td + (td>0 ? 1 : -1) * sqrt(td*td + e2)); // This explain the following, somewhat more complicated, version: - RealScalar mu = diag[end] - (e / (td + (td>0 ? 1 : -1))) * (e / hypot(td,e)); + RealScalar mu = diag[end]; + if(td==0) + mu -= abs(e); + else + { + RealScalar e2 = numext::abs2(subdiag[end-1]); + RealScalar h = numext::hypot(td,e); + if(e2==0) mu -= (e / (td + (td>0 ? 1 : -1))) * (e / h); + else mu -= e2 / (td + (td>0 ? h : -h)); + } RealScalar x = diag[start] - mu; RealScalar z = subdiag[start]; diff --git a/extern/Eigen3/Eigen/src/Eigenvalues/SelfAdjointEigenSolver_MKL.h b/extern/Eigen3/Eigen/src/Eigenvalues/SelfAdjointEigenSolver_MKL.h index 9380956b5f9..17c0dadd23e 100644 --- a/extern/Eigen3/Eigen/src/Eigenvalues/SelfAdjointEigenSolver_MKL.h +++ b/extern/Eigen3/Eigen/src/Eigenvalues/SelfAdjointEigenSolver_MKL.h @@ -40,7 +40,7 @@ namespace Eigen { /** \internal Specialization for the data types supported by MKL */ #define EIGEN_MKL_EIG_SELFADJ(EIGTYPE, MKLTYPE, MKLRTYPE, MKLNAME, EIGCOLROW, MKLCOLROW ) \ -template<> inline\ +template<> inline \ SelfAdjointEigenSolver<Matrix<EIGTYPE, Dynamic, Dynamic, EIGCOLROW> >& \ SelfAdjointEigenSolver<Matrix<EIGTYPE, Dynamic, Dynamic, EIGCOLROW> >::compute(const Matrix<EIGTYPE, Dynamic, Dynamic, EIGCOLROW>& matrix, int options) \ { \ @@ -56,7 +56,7 @@ SelfAdjointEigenSolver<Matrix<EIGTYPE, Dynamic, Dynamic, EIGCOLROW> >::compute(c \ if(n==1) \ { \ - m_eivalues.coeffRef(0,0) = internal::real(matrix.coeff(0,0)); \ + m_eivalues.coeffRef(0,0) = numext::real(matrix.coeff(0,0)); \ if(computeEigenvectors) m_eivec.setOnes(n,n); \ m_info = Success; \ m_isInitialized = true; \ diff --git a/extern/Eigen3/Eigen/src/Eigenvalues/Tridiagonalization.h b/extern/Eigen3/Eigen/src/Eigenvalues/Tridiagonalization.h index c34b7b3b801..192278d685d 100644 --- a/extern/Eigen3/Eigen/src/Eigenvalues/Tridiagonalization.h +++ b/extern/Eigen3/Eigen/src/Eigenvalues/Tridiagonalization.h @@ -96,7 +96,7 @@ template<typename _MatrixType> class Tridiagonalization >::type SubDiagonalReturnType; /** \brief Return type of matrixQ() */ - typedef typename HouseholderSequence<MatrixType,CoeffVectorType>::ConjugateReturnType HouseholderSequenceType; + typedef HouseholderSequence<MatrixType,typename internal::remove_all<typename CoeffVectorType::ConjugateReturnType>::type> HouseholderSequenceType; /** \brief Default constructor. * @@ -345,6 +345,7 @@ namespace internal { template<typename MatrixType, typename CoeffVectorType> void tridiagonalization_inplace(MatrixType& matA, CoeffVectorType& hCoeffs) { + using numext::conj; typedef typename MatrixType::Index Index; typedef typename MatrixType::Scalar Scalar; typedef typename MatrixType::RealScalar RealScalar; @@ -425,8 +426,6 @@ struct tridiagonalization_inplace_selector; template<typename MatrixType, typename DiagonalType, typename SubDiagonalType> void tridiagonalization_inplace(MatrixType& mat, DiagonalType& diag, SubDiagonalType& subdiag, bool extractQ) { - typedef typename MatrixType::Index Index; - //Index n = mat.rows(); eigen_assert(mat.cols()==mat.rows() && diag.size()==mat.rows() && subdiag.size()==mat.rows()-1); tridiagonalization_inplace_selector<MatrixType>::run(mat, diag, subdiag, extractQ); } @@ -467,8 +466,9 @@ struct tridiagonalization_inplace_selector<MatrixType,3,false> template<typename DiagonalType, typename SubDiagonalType> static void run(MatrixType& mat, DiagonalType& diag, SubDiagonalType& subdiag, bool extractQ) { + using std::sqrt; diag[0] = mat(0,0); - RealScalar v1norm2 = abs2(mat(2,0)); + RealScalar v1norm2 = numext::abs2(mat(2,0)); if(v1norm2 == RealScalar(0)) { diag[1] = mat(1,1); @@ -480,7 +480,7 @@ struct tridiagonalization_inplace_selector<MatrixType,3,false> } else { - RealScalar beta = sqrt(abs2(mat(1,0)) + v1norm2); + RealScalar beta = sqrt(numext::abs2(mat(1,0)) + v1norm2); RealScalar invBeta = RealScalar(1)/beta; Scalar m01 = mat(1,0) * invBeta; Scalar m02 = mat(2,0) * invBeta; @@ -510,7 +510,7 @@ struct tridiagonalization_inplace_selector<MatrixType,1,IsComplex> template<typename DiagonalType, typename SubDiagonalType> static void run(MatrixType& mat, DiagonalType& diag, SubDiagonalType&, bool extractQ) { - diag(0,0) = real(mat(0,0)); + diag(0,0) = numext::real(mat(0,0)); if(extractQ) mat(0,0) = Scalar(1); } |