diff options
author | 2014-09-21 14:02:51 +0300 | |
---|---|---|
committer | 2014-09-21 14:02:51 +0300 | |
commit | 60e093a9dce2f8d4c0f3b2ea3e0386d5f01bff8d (patch) | |
tree | 05442eeff0bcfe7fe85ce59cf5fa72aa06ee2a07 /unsupported/Eigen | |
parent | 56408504e4e3fa5f9c59d9edac14ca1ba1255e5a (diff) | |
parent | 03dd4dd91a5d8963f56eebe3b9d2eb924bc06e02 (diff) |
Merged eigen/eigen into default
Diffstat (limited to 'unsupported/Eigen')
27 files changed, 479 insertions, 1586 deletions
diff --git a/unsupported/Eigen/AlignedVector3 b/unsupported/Eigen/AlignedVector3 index 7b45e6cce..35493e87b 100644 --- a/unsupported/Eigen/AlignedVector3 +++ b/unsupported/Eigen/AlignedVector3 @@ -57,6 +57,10 @@ template<typename _Scalar> class AlignedVector3 inline Index rows() const { return 3; } inline Index cols() const { return 1; } + + Scalar* data() { return m_coeffs.data(); } + const Scalar* data() const { return m_coeffs.data(); } + Index innerStride() const { return 1; } inline const Scalar& coeff(Index row, Index col) const { return m_coeffs.coeff(row, col); } @@ -181,8 +185,28 @@ template<typename _Scalar> class AlignedVector3 { return m_coeffs.template head<3>().isApprox(other,eps); } + + CoeffType& coeffs() { return m_coeffs; } + const CoeffType& coeffs() const { return m_coeffs; } }; +namespace internal { + +template<typename Scalar> +struct evaluator<AlignedVector3<Scalar> > + : evaluator<Matrix<Scalar,4,1> >::type +{ + typedef AlignedVector3<Scalar> XprType; + typedef typename evaluator<Matrix<Scalar,4,1> >::type Base; + + typedef evaluator type; + typedef evaluator nestedType; + + evaluator(const XprType &m) : Base(m.coeffs()) {} +}; + +} + //@} } diff --git a/unsupported/Eigen/BDCSVD b/unsupported/Eigen/BDCSVD new file mode 100644 index 000000000..44649dbd0 --- /dev/null +++ b/unsupported/Eigen/BDCSVD @@ -0,0 +1,26 @@ +#ifndef EIGEN_BDCSVD_MODULE_H +#define EIGEN_BDCSVD_MODULE_H + +#include <Eigen/SVD> + +#include "../../Eigen/src/Core/util/DisableStupidWarnings.h" + +/** \defgroup BDCSVD_Module BDCSVD module + * + * + * + * This module provides Divide & Conquer SVD decomposition for matrices (both real and complex). + * This decomposition is accessible via the following MatrixBase method: + * - MatrixBase::bdcSvd() + * + * \code + * #include <Eigen/BDCSVD> + * \endcode + */ + +#include "src/BDCSVD/BDCSVD.h" + +#include "../../Eigen/src/Core/util/ReenableStupidWarnings.h" + +#endif // EIGEN_BDCSVD_MODULE_H +/* vim: set filetype=cpp et sw=2 ts=2 ai: */ diff --git a/unsupported/Eigen/IterativeSolvers b/unsupported/Eigen/IterativeSolvers index aa15403db..ff0d59b6e 100644 --- a/unsupported/Eigen/IterativeSolvers +++ b/unsupported/Eigen/IterativeSolvers @@ -24,9 +24,6 @@ */ //@{ -#include "../../Eigen/src/misc/Solve.h" -#include "../../Eigen/src/misc/SparseSolve.h" - #ifndef EIGEN_MPL2_ONLY #include "src/IterativeSolvers/IterationController.h" #include "src/IterativeSolvers/ConstrainedConjGrad.h" diff --git a/unsupported/Eigen/MPRealSupport b/unsupported/Eigen/MPRealSupport index 632de3854..8e42965a3 100644 --- a/unsupported/Eigen/MPRealSupport +++ b/unsupported/Eigen/MPRealSupport @@ -159,10 +159,10 @@ int main() { if(rows==0 || cols==0 || depth==0) return; - + mpreal acc1(0,mpfr_get_prec(blockA[0].mpfr_srcptr())), tmp (0,mpfr_get_prec(blockA[0].mpfr_srcptr())); - + if(strideA==-1) strideA = depth; if(strideB==-1) strideB = depth; diff --git a/unsupported/Eigen/MatrixFunctions b/unsupported/Eigen/MatrixFunctions index 0b12aaffb..0320606c1 100644 --- a/unsupported/Eigen/MatrixFunctions +++ b/unsupported/Eigen/MatrixFunctions @@ -82,7 +82,9 @@ const MatrixFunctionReturnValue<Derived> MatrixBase<Derived>::cos() const \param[in] M a square matrix. \returns expression representing \f$ \cos(M) \f$. -This function calls \ref matrixbase_matrixfunction "matrixFunction()" with StdStemFunctions::cos(). +This function computes the matrix cosine. Use ArrayBase::cos() for computing the entry-wise cosine. + +The implementation calls \ref matrixbase_matrixfunction "matrixFunction()" with StdStemFunctions::cos(). \sa \ref matrixbase_sin "sin()" for an example. @@ -123,6 +125,9 @@ differential equations: the solution of \f$ y' = My \f$ with the initial condition \f$ y(0) = y_0 \f$ is given by \f$ y(t) = \exp(M) y_0 \f$. +The matrix exponential is different from applying the exp function to all the entries in the matrix. +Use ArrayBase::exp() if you want to do the latter. + The cost of the computation is approximately \f$ 20 n^3 \f$ for matrices of size \f$ n \f$. The number 20 depends weakly on the norm of the matrix. @@ -177,6 +182,9 @@ the scalar logarithm, the equation \f$ \exp(X) = M \f$ may have multiple solutions; this function returns a matrix whose eigenvalues have imaginary part in the interval \f$ (-\pi,\pi] \f$. +The matrix logarithm is different from applying the log function to all the entries in the matrix. +Use ArrayBase::log() if you want to do the latter. + In the real case, the matrix \f$ M \f$ should be invertible and it should have no eigenvalues which are real and negative (pairs of complex conjugate eigenvalues are allowed). In the complex case, it @@ -232,7 +240,8 @@ const MatrixPowerReturnValue<Derived> MatrixBase<Derived>::pow(RealScalar p) con The matrix power \f$ M^p \f$ is defined as \f$ \exp(p \log(M)) \f$, where exp denotes the matrix exponential, and log denotes the matrix -logarithm. +logarithm. This is different from raising all the entries in the matrix +to the p-th power. Use ArrayBase::pow() if you want to do the latter. If \p p is complex, the scalar type of \p M should be the type of \p p . \f$ M^p \f$ simply evaluates into \f$ \exp(p \log(M)) \f$. @@ -391,7 +400,9 @@ const MatrixFunctionReturnValue<Derived> MatrixBase<Derived>::sin() const \param[in] M a square matrix. \returns expression representing \f$ \sin(M) \f$. -This function calls \ref matrixbase_matrixfunction "matrixFunction()" with StdStemFunctions::sin(). +This function computes the matrix sine. Use ArrayBase::sin() for computing the entry-wise sine. + +The implementation calls \ref matrixbase_matrixfunction "matrixFunction()" with StdStemFunctions::sin(). Example: \include MatrixSine.cpp Output: \verbinclude MatrixSine.out @@ -428,7 +439,9 @@ const MatrixSquareRootReturnValue<Derived> MatrixBase<Derived>::sqrt() const The matrix square root of \f$ M \f$ is the matrix \f$ M^{1/2} \f$ whose square is the original matrix; so if \f$ S = M^{1/2} \f$ then -\f$ S^2 = M \f$. +\f$ S^2 = M \f$. This is different from taking the square root of all +the entries in the matrix; use ArrayBase::sqrt() if you want to do the +latter. In the <b>real case</b>, the matrix \f$ M \f$ should be invertible and it should have no eigenvalues which are real and negative (pairs of diff --git a/unsupported/Eigen/SVD b/unsupported/Eigen/SVD deleted file mode 100644 index 900a8aa60..000000000 --- a/unsupported/Eigen/SVD +++ /dev/null @@ -1,35 +0,0 @@ -#ifndef EIGEN_SVD_MODULE_H -#define EIGEN_SVD_MODULE_H - -#include <Eigen/QR> -#include <Eigen/Householder> -#include <Eigen/Jacobi> - -#include "../../Eigen/src/Core/util/DisableStupidWarnings.h" - -/** \defgroup SVD_Module SVD module - * - * - * - * This module provides SVD decomposition for matrices (both real and complex). - * This decomposition is accessible via the following MatrixBase method: - * - MatrixBase::jacobiSvd() - * - * \code - * #include <Eigen/SVD> - * \endcode - */ - -#include "../../Eigen/src/misc/Solve.h" -#include "../../Eigen/src/SVD/UpperBidiagonalization.h" -#include "src/SVD/SVDBase.h" -#include "src/SVD/JacobiSVD.h" -#include "src/SVD/BDCSVD.h" -#if defined(EIGEN_USE_LAPACKE) && !defined(EIGEN_USE_LAPACKE_STRICT) -#include "../../Eigen/src/SVD/JacobiSVD_MKL.h" -#endif - -#include "../../Eigen/src/Core/util/ReenableStupidWarnings.h" - -#endif // EIGEN_SVD_MODULE_H -/* vim: set filetype=cpp et sw=2 ts=2 ai: */ diff --git a/unsupported/Eigen/SparseExtra b/unsupported/Eigen/SparseExtra index b5597902a..819cffa27 100644 --- a/unsupported/Eigen/SparseExtra +++ b/unsupported/Eigen/SparseExtra @@ -37,9 +37,6 @@ */ -#include "../../Eigen/src/misc/Solve.h" -#include "../../Eigen/src/misc/SparseSolve.h" - #include "src/SparseExtra/DynamicSparseMatrix.h" #include "src/SparseExtra/BlockOfDynamicSparseMatrix.h" #include "src/SparseExtra/RandomSetter.h" diff --git a/unsupported/Eigen/src/SVD/BDCSVD.h b/unsupported/Eigen/src/BDCSVD/BDCSVD.h index 80006fd60..0167872af 100644 --- a/unsupported/Eigen/src/SVD/BDCSVD.h +++ b/unsupported/Eigen/src/BDCSVD/BDCSVD.h @@ -19,11 +19,21 @@ #ifndef EIGEN_BDCSVD_H #define EIGEN_BDCSVD_H -#define EPSILON 0.0000000000000001 +namespace Eigen { -#define ALGOSWAP 16 +template<typename _MatrixType> class BDCSVD; -namespace Eigen { +namespace internal { + +template<typename _MatrixType> +struct traits<BDCSVD<_MatrixType> > +{ + typedef _MatrixType MatrixType; +}; + +} // end namespace internal + + /** \ingroup SVD_Module * * @@ -36,13 +46,15 @@ namespace Eigen { * It should be used to speed up the calcul of SVD for big matrices. */ template<typename _MatrixType> -class BDCSVD : public SVDBase<_MatrixType> +class BDCSVD : public SVDBase<BDCSVD<_MatrixType> > { - typedef SVDBase<_MatrixType> Base; + typedef SVDBase<BDCSVD> Base; public: using Base::rows; using Base::cols; + using Base::computeU; + using Base::computeV; typedef _MatrixType MatrixType; typedef typename MatrixType::Scalar Scalar; @@ -58,15 +70,10 @@ public: MatrixOptions = MatrixType::Options }; - typedef Matrix<Scalar, RowsAtCompileTime, RowsAtCompileTime, - MatrixOptions, MaxRowsAtCompileTime, MaxRowsAtCompileTime> - MatrixUType; - typedef Matrix<Scalar, ColsAtCompileTime, ColsAtCompileTime, - MatrixOptions, MaxColsAtCompileTime, MaxColsAtCompileTime> - MatrixVType; - typedef typename internal::plain_diag_type<MatrixType, RealScalar>::type SingularValuesType; - typedef typename internal::plain_row_type<MatrixType>::type RowType; - typedef typename internal::plain_col_type<MatrixType>::type ColType; + typedef typename Base::MatrixUType MatrixUType; + typedef typename Base::MatrixVType MatrixVType; + typedef typename Base::SingularValuesType SingularValuesType; + typedef Matrix<Scalar, Dynamic, Dynamic> MatrixX; typedef Matrix<RealScalar, Dynamic, Dynamic> MatrixXr; typedef Matrix<RealScalar, Dynamic, 1> VectorType; @@ -77,9 +84,7 @@ public: * The default constructor is useful in cases in which the user intends to * perform decompositions via BDCSVD::compute(const MatrixType&). */ - BDCSVD() - : SVDBase<_MatrixType>::SVDBase(), - algoswap(ALGOSWAP), m_numIters(0) + BDCSVD() : m_algoswap(16), m_numIters(0) {} @@ -90,8 +95,7 @@ public: * \sa BDCSVD() */ BDCSVD(Index rows, Index cols, unsigned int computationOptions = 0) - : SVDBase<_MatrixType>::SVDBase(), - algoswap(ALGOSWAP), m_numIters(0) + : m_algoswap(16), m_numIters(0) { allocate(rows, cols, computationOptions); } @@ -107,8 +111,7 @@ public: * available with the (non - default) FullPivHouseholderQR preconditioner. */ BDCSVD(const MatrixType& matrix, unsigned int computationOptions = 0) - : SVDBase<_MatrixType>::SVDBase(), - algoswap(ALGOSWAP), m_numIters(0) + : m_algoswap(16), m_numIters(0) { compute(matrix, computationOptions); } @@ -116,6 +119,7 @@ public: ~BDCSVD() { } + /** \brief Method performing the decomposition of given matrix using custom options. * * \param matrix the matrix to decompose @@ -126,7 +130,7 @@ public: * Thin unitaries are only available if your matrix type has a Dynamic number of columns (for example MatrixXf). They also are not * available with the (non - default) FullPivHouseholderQR preconditioner. */ - SVDBase<MatrixType>& compute(const MatrixType& matrix, unsigned int computationOptions); + BDCSVD& compute(const MatrixType& matrix, unsigned int computationOptions); /** \brief Method performing the decomposition of given matrix using current options. * @@ -134,7 +138,7 @@ public: * * This method uses the current \a computationOptions, as already passed to the constructor or to compute(const MatrixType&, unsigned int). */ - SVDBase<MatrixType>& compute(const MatrixType& matrix) + BDCSVD& compute(const MatrixType& matrix) { return compute(matrix, this->m_computationOptions); } @@ -142,58 +146,7 @@ public: void setSwitchSize(int s) { eigen_assert(s>3 && "BDCSVD the size of the algo switch has to be greater than 3"); - algoswap = s; - } - - - /** \returns a (least squares) solution of \f$ A x = b \f$ using the current SVD decomposition of A. - * - * \param b the right - hand - side of the equation to solve. - * - * \note Solving requires both U and V to be computed. Thin U and V are enough, there is no need for full U or V. - * - * \note SVD solving is implicitly least - squares. Thus, this method serves both purposes of exact solving and least - squares solving. - * In other words, the returned solution is guaranteed to minimize the Euclidean norm \f$ \Vert A x - b \Vert \f$. - */ - template<typename Rhs> - inline const internal::solve_retval<BDCSVD, Rhs> - solve(const MatrixBase<Rhs>& b) const - { - eigen_assert(this->m_isInitialized && "BDCSVD is not initialized."); - eigen_assert(SVDBase<_MatrixType>::computeU() && SVDBase<_MatrixType>::computeV() && - "BDCSVD::solve() requires both unitaries U and V to be computed (thin unitaries suffice)."); - return internal::solve_retval<BDCSVD, Rhs>(*this, b.derived()); - } - - - const MatrixUType& matrixU() const - { - eigen_assert(this->m_isInitialized && "SVD is not initialized."); - if (isTranspose){ - eigen_assert(this->computeV() && "This SVD decomposition didn't compute U. Did you ask for it?"); - return this->m_matrixV; - } - else - { - eigen_assert(this->computeU() && "This SVD decomposition didn't compute U. Did you ask for it?"); - return this->m_matrixU; - } - - } - - - const MatrixVType& matrixV() const - { - eigen_assert(this->m_isInitialized && "SVD is not initialized."); - if (isTranspose){ - eigen_assert(this->computeU() && "This SVD decomposition didn't compute V. Did you ask for it?"); - return this->m_matrixU; - } - else - { - eigen_assert(this->computeV() && "This SVD decomposition didn't compute V. Did you ask for it?"); - return this->m_matrixV; - } + m_algoswap = s; } private: @@ -209,15 +162,27 @@ private: void deflation43(Index firstCol, Index shift, Index i, Index size); void deflation44(Index firstColu , Index firstColm, Index firstRowW, Index firstColW, Index i, Index j, Index size); void deflation(Index firstCol, Index lastCol, Index k, Index firstRowW, Index firstColW, Index shift); - void copyUV(const typename internal::UpperBidiagonalization<MatrixX>::HouseholderUSequenceType& householderU, - const typename internal::UpperBidiagonalization<MatrixX>::HouseholderVSequenceType& householderV); + template<typename HouseholderU, typename HouseholderV, typename NaiveU, typename NaiveV> + void copyUV(const HouseholderU &householderU, const HouseholderV &householderV, const NaiveU &naiveU, const NaiveV &naivev); + static void structured_update(Block<MatrixXr,Dynamic,Dynamic> A, const MatrixXr &B, Index n1); protected: MatrixXr m_naiveU, m_naiveV; MatrixXr m_computed; - Index nRec; - int algoswap; - bool isTranspose, compU, compV; + Index m_nRec; + int m_algoswap; + bool m_isTranspose, m_compU, m_compV; + + using Base::m_singularValues; + using Base::m_diagSize; + using Base::m_computeFullU; + using Base::m_computeFullV; + using Base::m_computeThinU; + using Base::m_computeThinV; + using Base::m_matrixU; + using Base::m_matrixV; + using Base::m_isInitialized; + using Base::m_nonzeroSingularValues; public: int m_numIters; @@ -228,117 +193,147 @@ public: template<typename MatrixType> void BDCSVD<MatrixType>::allocate(Index rows, Index cols, unsigned int computationOptions) { - isTranspose = (cols > rows); - if (SVDBase<MatrixType>::allocate(rows, cols, computationOptions)) return; - m_computed = MatrixXr::Zero(this->m_diagSize + 1, this->m_diagSize ); - if (isTranspose){ - compU = this->computeU(); - compV = this->computeV(); - } - else - { - compV = this->computeU(); - compU = this->computeV(); - } - if (compU) m_naiveU = MatrixXr::Zero(this->m_diagSize + 1, this->m_diagSize + 1 ); - else m_naiveU = MatrixXr::Zero(2, this->m_diagSize + 1 ); + m_isTranspose = (cols > rows); + if (Base::allocate(rows, cols, computationOptions)) + return; - if (compV) m_naiveV = MatrixXr::Zero(this->m_diagSize, this->m_diagSize); + m_computed = MatrixXr::Zero(m_diagSize + 1, m_diagSize ); + m_compU = computeV(); + m_compV = computeU(); + if (m_isTranspose) + std::swap(m_compU, m_compV); - - //should be changed for a cleaner implementation - if (isTranspose){ - bool aux; - if (this->computeU()||this->computeV()){ - aux = this->m_computeFullU; - this->m_computeFullU = this->m_computeFullV; - this->m_computeFullV = aux; - aux = this->m_computeThinU; - this->m_computeThinU = this->m_computeThinV; - this->m_computeThinV = aux; - } - } + if (m_compU) m_naiveU = MatrixXr::Zero(m_diagSize + 1, m_diagSize + 1 ); + else m_naiveU = MatrixXr::Zero(2, m_diagSize + 1 ); + + if (m_compV) m_naiveV = MatrixXr::Zero(m_diagSize, m_diagSize); }// end allocate // Methode which compute the BDCSVD for the int template<> -SVDBase<Matrix<int, Dynamic, Dynamic> >& -BDCSVD<Matrix<int, Dynamic, Dynamic> >::compute(const MatrixType& matrix, unsigned int computationOptions) { +BDCSVD<Matrix<int, Dynamic, Dynamic> >& BDCSVD<Matrix<int, Dynamic, Dynamic> >::compute(const MatrixType& matrix, unsigned int computationOptions) +{ allocate(matrix.rows(), matrix.cols(), computationOptions); - this->m_nonzeroSingularValues = 0; + m_nonzeroSingularValues = 0; m_computed = Matrix<int, Dynamic, Dynamic>::Zero(rows(), cols()); - for (int i=0; i<this->m_diagSize; i++) { - this->m_singularValues.coeffRef(i) = 0; - } - if (this->m_computeFullU) this->m_matrixU = Matrix<int, Dynamic, Dynamic>::Zero(rows(), rows()); - if (this->m_computeFullV) this->m_matrixV = Matrix<int, Dynamic, Dynamic>::Zero(cols(), cols()); - this->m_isInitialized = true; + + m_singularValues.head(m_diagSize).setZero(); + + if (m_computeFullU) m_matrixU.setZero(rows(), rows()); + if (m_computeFullV) m_matrixV.setZero(cols(), cols()); + m_isInitialized = true; return *this; } // Methode which compute the BDCSVD template<typename MatrixType> -SVDBase<MatrixType>& -BDCSVD<MatrixType>::compute(const MatrixType& matrix, unsigned int computationOptions) +BDCSVD<MatrixType>& BDCSVD<MatrixType>::compute(const MatrixType& matrix, unsigned int computationOptions) { allocate(matrix.rows(), matrix.cols(), computationOptions); using std::abs; - //**** step 1 Bidiagonalization isTranspose = (matrix.cols()>matrix.rows()) ; + //**** step 1 Bidiagonalization m_isTranspose = (matrix.cols()>matrix.rows()) ; MatrixType copy; - if (isTranspose) copy = matrix.adjoint(); - else copy = matrix; + if (m_isTranspose) copy = matrix.adjoint(); + else copy = matrix; internal::UpperBidiagonalization<MatrixX> bid(copy); //**** step 2 Divide - m_computed.topRows(this->m_diagSize) = bid.bidiagonal().toDenseMatrix().transpose(); + m_naiveU.setZero(); + m_naiveV.setZero(); + m_computed.topRows(m_diagSize) = bid.bidiagonal().toDenseMatrix().transpose(); m_computed.template bottomRows<1>().setZero(); - divide(0, this->m_diagSize - 1, 0, 0, 0); + divide(0, m_diagSize - 1, 0, 0, 0); //**** step 3 copy - for (int i=0; i<this->m_diagSize; i++) { + for (int i=0; i<m_diagSize; i++) + { RealScalar a = abs(m_computed.coeff(i, i)); - this->m_singularValues.coeffRef(i) = a; - if (a == 0){ - this->m_nonzeroSingularValues = i; - this->m_singularValues.tail(this->m_diagSize - i - 1).setZero(); + m_singularValues.coeffRef(i) = a; + if (a == 0) + { + m_nonzeroSingularValues = i; + m_singularValues.tail(m_diagSize - i - 1).setZero(); break; } - else if (i == this->m_diagSize - 1) + else if (i == m_diagSize - 1) { - this->m_nonzeroSingularValues = i + 1; + m_nonzeroSingularValues = i + 1; break; } } - copyUV(bid.householderU(), bid.householderV()); - this->m_isInitialized = true; + if(m_isTranspose) copyUV(bid.householderV(), bid.householderU(), m_naiveV, m_naiveU); + else copyUV(bid.householderU(), bid.householderV(), m_naiveU, m_naiveV); + m_isInitialized = true; return *this; }// end compute template<typename MatrixType> -void BDCSVD<MatrixType>::copyUV(const typename internal::UpperBidiagonalization<MatrixX>::HouseholderUSequenceType& householderU, - const typename internal::UpperBidiagonalization<MatrixX>::HouseholderVSequenceType& householderV) +template<typename HouseholderU, typename HouseholderV, typename NaiveU, typename NaiveV> +void BDCSVD<MatrixType>::copyUV(const HouseholderU &householderU, const HouseholderV &householderV, const NaiveU &naiveU, const NaiveV &naiveV) { // Note exchange of U and V: m_matrixU is set from m_naiveV and vice versa - if (this->computeU()){ - Index Ucols = this->m_computeThinU ? this->m_nonzeroSingularValues : householderU.cols(); - this->m_matrixU = MatrixX::Identity(householderU.cols(), Ucols); - Index blockCols = this->m_computeThinU ? this->m_nonzeroSingularValues : this->m_diagSize; - this->m_matrixU.block(0, 0, this->m_diagSize, blockCols) = - m_naiveV.template cast<Scalar>().block(0, 0, this->m_diagSize, blockCols); - this->m_matrixU = householderU * this->m_matrixU; + if (computeU()) + { + Index Ucols = m_computeThinU ? m_nonzeroSingularValues : householderU.cols(); + m_matrixU = MatrixX::Identity(householderU.cols(), Ucols); + Index blockCols = m_computeThinU ? m_nonzeroSingularValues : m_diagSize; + m_matrixU.topLeftCorner(m_diagSize, blockCols) = naiveV.template cast<Scalar>().topLeftCorner(m_diagSize, blockCols); + householderU.applyThisOnTheLeft(m_matrixU); + } + if (computeV()) + { + Index Vcols = m_computeThinV ? m_nonzeroSingularValues : householderV.cols(); + m_matrixV = MatrixX::Identity(householderV.cols(), Vcols); + Index blockCols = m_computeThinV ? m_nonzeroSingularValues : m_diagSize; + m_matrixV.topLeftCorner(m_diagSize, blockCols) = naiveU.template cast<Scalar>().topLeftCorner(m_diagSize, blockCols); + householderV.applyThisOnTheLeft(m_matrixV); } - if (this->computeV()){ - Index Vcols = this->m_computeThinV ? this->m_nonzeroSingularValues : householderV.cols(); - this->m_matrixV = MatrixX::Identity(householderV.cols(), Vcols); - Index blockCols = this->m_computeThinV ? this->m_nonzeroSingularValues : this->m_diagSize; - this->m_matrixV.block(0, 0, this->m_diagSize, blockCols) = - m_naiveU.template cast<Scalar>().block(0, 0, this->m_diagSize, blockCols); - this->m_matrixV = householderV * this->m_matrixV; +} + +/** \internal + * Performs A = A * B exploiting the special structure of the matrix A. Splitting A as: + * A = [A1] + * [A2] + * such that A1.rows()==n1, then we assume that at least half of the columns of A1 and A2 are zeros. + * We can thus pack them prior to the the matrix product. However, this is only worth the effort if the matrix is large + * enough. + */ +template<typename MatrixType> +void BDCSVD<MatrixType>::structured_update(Block<MatrixXr,Dynamic,Dynamic> A, const MatrixXr &B, Index n1) +{ + Index n = A.rows(); + if(n>100) + { + // If the matrices are large enough, let's exploit the sparse strucure of A by + // splitting it in half (wrt n1), and packing the non-zero columns. + DenseIndex n2 = n - n1; + MatrixXr A1(n1,n), A2(n2,n), B1(n,n), B2(n,n); + Index k1=0, k2=0; + for(Index j=0; j<n; ++j) + { + if( (A.col(j).head(n1).array()!=0).any() ) + { + A1.col(k1) = A.col(j).head(n1); + B1.row(k1) = B.row(j); + ++k1; + } + if( (A.col(j).tail(n2).array()!=0).any() ) + { + A2.col(k2) = A.col(j).tail(n2); + B2.row(k2) = B.row(j); + ++k2; + } + } + + A.topRows(n1).noalias() = A1.leftCols(k1) * B1.topRows(k1); + A.bottomRows(n2).noalias() = A2.leftCols(k2) * B2.topRows(k2); } + else + A *= B; // FIXME this requires a temporary } // The divide algorithm is done "in place", we are always working on subsets of the same matrix. The divide methods takes as argument the @@ -352,8 +347,7 @@ void BDCSVD<MatrixType>::copyUV(const typename internal::UpperBidiagonalization< //@param shift : Each time one takes the left submatrix, one must add 1 to the shift. Why? Because! We actually want the last column of the U submatrix // to become the first column (*coeff) and to shift all the other columns to the right. There are more details on the reference paper. template<typename MatrixType> -void BDCSVD<MatrixType>::divide (Index firstCol, Index lastCol, Index firstRowW, - Index firstColW, Index shift) +void BDCSVD<MatrixType>::divide (Index firstCol, Index lastCol, Index firstRowW, Index firstColW, Index shift) { // requires nbRows = nbCols + 1; using std::pow; @@ -365,24 +359,22 @@ void BDCSVD<MatrixType>::divide (Index firstCol, Index lastCol, Index firstRowW, RealScalar betaK; RealScalar r0; RealScalar lambda, phi, c0, s0; - MatrixXr l, f; + VectorType l, f; // We use the other algorithm which is more efficient for small // matrices. - if (n < algoswap){ - JacobiSVD<MatrixXr> b(m_computed.block(firstCol, firstCol, n + 1, n), - ComputeFullU | (ComputeFullV * compV)) ; - if (compU) m_naiveU.block(firstCol, firstCol, n + 1, n + 1).real() << b.matrixU(); + if (n < m_algoswap) + { + JacobiSVD<MatrixXr> b(m_computed.block(firstCol, firstCol, n + 1, n), ComputeFullU | (m_compV ? ComputeFullV : 0)) ; + if (m_compU) + m_naiveU.block(firstCol, firstCol, n + 1, n + 1).real() = b.matrixU(); else { - m_naiveU.row(0).segment(firstCol, n + 1).real() << b.matrixU().row(0); - m_naiveU.row(1).segment(firstCol, n + 1).real() << b.matrixU().row(n); + m_naiveU.row(0).segment(firstCol, n + 1).real() = b.matrixU().row(0); + m_naiveU.row(1).segment(firstCol, n + 1).real() = b.matrixU().row(n); } - if (compV) m_naiveV.block(firstRowW, firstColW, n, n).real() << b.matrixV(); + if (m_compV) m_naiveV.block(firstRowW, firstColW, n, n).real() = b.matrixV(); m_computed.block(firstCol + shift, firstCol + shift, n + 1, n).setZero(); - for (int i=0; i<n; i++) - { - m_computed(firstCol + shift + i, firstCol + shift +i) = b.singularValues().coeffRef(i); - } + m_computed.diagonal().segment(firstCol + shift, n) = b.singularValues().head(n); return; } // We use the divide and conquer algorithm @@ -393,7 +385,7 @@ void BDCSVD<MatrixType>::divide (Index firstCol, Index lastCol, Index firstRowW, // right submatrix before the left one. divide(k + 1 + firstCol, lastCol, k + 1 + firstRowW, k + 1 + firstColW, shift); divide(firstCol, k - 1 + firstCol, firstRowW, firstColW + 1, shift + 1); - if (compU) + if (m_compU) { lambda = m_naiveU(firstCol + k, firstCol + k); phi = m_naiveU(firstCol + k + 1, lastCol + 1); @@ -403,9 +395,8 @@ void BDCSVD<MatrixType>::divide (Index firstCol, Index lastCol, Index firstRowW, lambda = m_naiveU(1, firstCol + k); phi = m_naiveU(0, lastCol + 1); } - r0 = sqrt((abs(alphaK * lambda) * abs(alphaK * lambda)) - + abs(betaK * phi) * abs(betaK * phi)); - if (compU) + r0 = sqrt((abs(alphaK * lambda) * abs(alphaK * lambda)) + abs(betaK * phi) * abs(betaK * phi)); + if (m_compU) { l = m_naiveU.row(firstCol + k).segment(firstCol, k); f = m_naiveU.row(firstCol + k + 1).segment(firstCol + k + 1, n - k - 1); @@ -415,7 +406,7 @@ void BDCSVD<MatrixType>::divide (Index firstCol, Index lastCol, Index firstRowW, l = m_naiveU.row(1).segment(firstCol, k); f = m_naiveU.row(0).segment(firstCol + k + 1, n - k - 1); } - if (compV) m_naiveV(firstRowW+k, firstColW) = 1; + if (m_compV) m_naiveV(firstRowW+k, firstColW) = 1; if (r0 == 0) { c0 = 1; @@ -426,32 +417,27 @@ void BDCSVD<MatrixType>::divide (Index firstCol, Index lastCol, Index firstRowW, c0 = alphaK * lambda / r0; s0 = betaK * phi / r0; } - if (compU) + if (m_compU) { MatrixXr q1 (m_naiveU.col(firstCol + k).segment(firstCol, k + 1)); // we shiftW Q1 to the right for (Index i = firstCol + k - 1; i >= firstCol; i--) - { - m_naiveU.col(i + 1).segment(firstCol, k + 1) << m_naiveU.col(i).segment(firstCol, k + 1); - } + m_naiveU.col(i + 1).segment(firstCol, k + 1) = m_naiveU.col(i).segment(firstCol, k + 1); // we shift q1 at the left with a factor c0 - m_naiveU.col(firstCol).segment( firstCol, k + 1) << (q1 * c0); + m_naiveU.col(firstCol).segment( firstCol, k + 1) = (q1 * c0); // last column = q1 * - s0 - m_naiveU.col(lastCol + 1).segment(firstCol, k + 1) << (q1 * ( - s0)); + m_naiveU.col(lastCol + 1).segment(firstCol, k + 1) = (q1 * ( - s0)); // first column = q2 * s0 - m_naiveU.col(firstCol).segment(firstCol + k + 1, n - k) << - m_naiveU.col(lastCol + 1).segment(firstCol + k + 1, n - k) *s0; + m_naiveU.col(firstCol).segment(firstCol + k + 1, n - k) = m_naiveU.col(lastCol + 1).segment(firstCol + k + 1, n - k) * s0; // q2 *= c0 - m_naiveU.col(lastCol + 1).segment(firstCol + k + 1, n - k) *= c0; + m_naiveU.col(lastCol + 1).segment(firstCol + k + 1, n - k) *= c0; } else { RealScalar q1 = (m_naiveU(0, firstCol + k)); // we shift Q1 to the right for (Index i = firstCol + k - 1; i >= firstCol; i--) - { m_naiveU(0, i + 1) = m_naiveU(0, i); - } // we shift q1 at the left with a factor c0 m_naiveU(0, firstCol) = (q1 * c0); // last column = q1 * - s0 @@ -464,9 +450,8 @@ void BDCSVD<MatrixType>::divide (Index firstCol, Index lastCol, Index firstRowW, m_naiveU.row(0).segment(firstCol + k + 1, n - k - 1).setZero(); } m_computed(firstCol + shift, firstCol + shift) = r0; - m_computed.col(firstCol + shift).segment(firstCol + shift + 1, k) << alphaK * l.transpose().real(); - m_computed.col(firstCol + shift).segment(firstCol + shift + k + 1, n - k - 1) << betaK * f.transpose().real(); - + m_computed.col(firstCol + shift).segment(firstCol + shift + 1, k) = alphaK * l.transpose().real(); + m_computed.col(firstCol + shift).segment(firstCol + shift + k + 1, n - k - 1) = betaK * f.transpose().real(); // Second part: try to deflate singular values in combined matrix deflation(firstCol, lastCol, k, firstRowW, firstColW, shift); @@ -475,9 +460,12 @@ void BDCSVD<MatrixType>::divide (Index firstCol, Index lastCol, Index firstRowW, MatrixXr UofSVD, VofSVD; VectorType singVals; computeSVDofM(firstCol + shift, n, UofSVD, singVals, VofSVD); - if (compU) m_naiveU.block(firstCol, firstCol, n + 1, n + 1) *= UofSVD; - else m_naiveU.block(0, firstCol, 2, n + 1) *= UofSVD; - if (compV) m_naiveV.block(firstRowW, firstColW, n, n) *= VofSVD; + + if (m_compU) structured_update(m_naiveU.block(firstCol, firstCol, n + 1, n + 1), UofSVD, (n+2)/2); + else m_naiveU.middleCols(firstCol, n + 1) *= UofSVD; // FIXME this requires a temporary, and exploit that there are 2 rows at compile time + + if (m_compV) structured_update(m_naiveV.block(firstRowW, firstColW, n, n), VofSVD, (n+1)/2); + m_computed.block(firstCol + shift, firstCol + shift, n, n).setZero(); m_computed.block(firstCol + shift, firstCol + shift, n, n).diagonal() = singVals; }// end divide @@ -485,7 +473,7 @@ void BDCSVD<MatrixType>::divide (Index firstCol, Index lastCol, Index firstRowW, // Compute SVD of m_computed.block(firstCol, firstCol, n + 1, n); this block only has non-zeros in // the first column and on the diagonal and has undergone deflation, so diagonal is in increasing // order except for possibly the (0,0) entry. The computed SVD is stored U, singVals and V, except -// that if compV is false, then V is not computed. Singular values are sorted in decreasing order. +// that if m_compV is false, then V is not computed. Singular values are sorted in decreasing order. // // TODO Opportunities for optimization: better root finding algo, better stopping criterion, better // handling of round-off errors, be consistent in ordering @@ -493,26 +481,28 @@ template <typename MatrixType> void BDCSVD<MatrixType>::computeSVDofM(Index firstCol, Index n, MatrixXr& U, VectorType& singVals, MatrixXr& V) { // TODO Get rid of these copies (?) - ArrayXr col0 = m_computed.block(firstCol, firstCol, n, 1); + // FIXME at least preallocate them + ArrayXr col0 = m_computed.col(firstCol).segment(firstCol, n); ArrayXr diag = m_computed.block(firstCol, firstCol, n, n).diagonal(); diag(0) = 0; // compute singular values and vectors (in decreasing order) singVals.resize(n); U.resize(n+1, n+1); - if (compV) V.resize(n, n); + if (m_compV) V.resize(n, n); if (col0.hasNaN() || diag.hasNaN()) return; ArrayXr shifts(n), mus(n), zhat(n); + computeSingVals(col0, diag, singVals, shifts, mus); perturbCol0(col0, diag, singVals, shifts, mus, zhat); computeSingVecs(zhat, diag, singVals, shifts, mus, U, V); // Reverse order so that singular values in increased order singVals.reverseInPlace(); - U.leftCols(n) = U.leftCols(n).rowwise().reverse().eval(); - if (compV) V = V.rowwise().reverse().eval(); + U.leftCols(n) = U.leftCols(n).rowwise().reverse().eval(); // FIXME this requires a temporary + if (m_compV) V = V.rowwise().reverse().eval(); // FIXME this requires a temporary } template <typename MatrixType> @@ -521,10 +511,13 @@ void BDCSVD<MatrixType>::computeSingVals(const ArrayXr& col0, const ArrayXr& dia { using std::abs; using std::swap; + using std::max; Index n = col0.size(); - for (Index k = 0; k < n; ++k) { - if (col0(k) == 0) { + for (Index k = 0; k < n; ++k) + { + if (col0(k) == 0) + { // entry is deflated, so singular value is on diagonal singVals(k) = diag(k); mus(k) = 0; @@ -540,27 +533,29 @@ void BDCSVD<MatrixType>::computeSingVals(const ArrayXr& col0, const ArrayXr& dia RealScalar mid = left + (right-left) / 2; RealScalar fMid = 1 + (col0.square() / ((diag + mid) * (diag - mid))).sum(); - RealScalar shift; - if (k == n-1 || fMid > 0) shift = left; - else shift = right; + RealScalar shift = (k == n-1 || fMid > 0) ? left : right; // measure everything relative to shift ArrayXr diagShifted = diag - shift; // initial guess RealScalar muPrev, muCur; - if (shift == left) { + if (shift == left) + { muPrev = (right - left) * 0.1; if (k == n-1) muCur = right - left; - else muCur = (right - left) * 0.5; - } else { + else muCur = (right - left) * 0.5; + } + else + { muPrev = -(right - left) * 0.1; muCur = -(right - left) * 0.5; } RealScalar fPrev = 1 + (col0.square() / ((diagShifted - muPrev) * (diag + shift + muPrev))).sum(); RealScalar fCur = 1 + (col0.square() / ((diagShifted - muCur) * (diag + shift + muCur))).sum(); - if (abs(fPrev) < abs(fCur)) { + if (abs(fPrev) < abs(fCur)) + { swap(fPrev, fCur); swap(muPrev, muCur); } @@ -568,7 +563,8 @@ void BDCSVD<MatrixType>::computeSingVals(const ArrayXr& col0, const ArrayXr& dia // rational interpolation: fit a function of the form a / mu + b through the two previous // iterates and use its zero to compute the next iterate bool useBisection = false; - while (abs(muCur - muPrev) > 8 * NumTraits<RealScalar>::epsilon() * (std::max)(abs(muCur), abs(muPrev)) && fCur != fPrev && !useBisection) { + while (abs(muCur - muPrev) > 8 * NumTraits<RealScalar>::epsilon() * (max)(abs(muCur), abs(muPrev)) && fCur != fPrev && !useBisection) + { ++m_numIters; RealScalar a = (fCur - fPrev) / (1/muCur - 1/muPrev); @@ -584,13 +580,17 @@ void BDCSVD<MatrixType>::computeSingVals(const ArrayXr& col0, const ArrayXr& dia } // fall back on bisection method if rational interpolation did not work - if (useBisection) { + if (useBisection) + { RealScalar leftShifted, rightShifted; - if (shift == left) { + if (shift == left) + { leftShifted = 1e-30; if (k == 0) rightShifted = right - left; - else rightShifted = (right - left) * 0.6; // theoretically we can take 0.5, but let's be safe - } else { + else rightShifted = (right - left) * 0.6; // theoretically we can take 0.5, but let's be safe + } + else + { leftShifted = -(right - left) * 0.6; rightShifted = -1e-30; } @@ -599,13 +599,17 @@ void BDCSVD<MatrixType>::computeSingVals(const ArrayXr& col0, const ArrayXr& dia RealScalar fRight = 1 + (col0.square() / ((diagShifted - rightShifted) * (diag + shift + rightShifted))).sum(); assert(fLeft * fRight < 0); - while (rightShifted - leftShifted > 2 * NumTraits<RealScalar>::epsilon() * (std::max)(abs(leftShifted), abs(rightShifted))) { + while (rightShifted - leftShifted > 2 * NumTraits<RealScalar>::epsilon() * (max)(abs(leftShifted), abs(rightShifted))) + { RealScalar midShifted = (leftShifted + rightShifted) / 2; RealScalar fMid = 1 + (col0.square() / ((diagShifted - midShifted) * (diag + shift + midShifted))).sum(); - if (fLeft * fMid < 0) { + if (fLeft * fMid < 0) + { rightShifted = midShifted; fRight = fMid; - } else { + } + else + { leftShifted = midShifted; fLeft = fMid; } @@ -632,13 +636,15 @@ void BDCSVD<MatrixType>::perturbCol0 (const ArrayXr& col0, const ArrayXr& diag, const VectorType& singVals, const ArrayXr& shifts, const ArrayXr& mus, ArrayXr& zhat) { + using std::sqrt; Index n = col0.size(); - for (Index k = 0; k < n; ++k) { + for (Index k = 0; k < n; ++k) + { if (col0(k) == 0) zhat(k) = 0; - else { + else + { // see equation (3.6) - using std::sqrt; RealScalar tmp = sqrt( (singVals(n-1) + diag(k)) * (mus(n-1) + (shifts(n-1) - diag(k))) @@ -664,16 +670,21 @@ void BDCSVD<MatrixType>::computeSingVecs const ArrayXr& shifts, const ArrayXr& mus, MatrixXr& U, MatrixXr& V) { Index n = zhat.size(); - for (Index k = 0; k < n; ++k) { - if (zhat(k) == 0) { + for (Index k = 0; k < n; ++k) + { + if (zhat(k) == 0) + { U.col(k) = VectorType::Unit(n+1, k); - if (compV) V.col(k) = VectorType::Unit(n, k); - } else { + if (m_compV) V.col(k) = VectorType::Unit(n, k); + } + else + { U.col(k).head(n) = zhat / (((diag - shifts(k)) - mus(k)) * (diag + singVals[k])); U(n,k) = 0; U.col(k).normalize(); - if (compV) { + if (m_compV) + { V.col(k).tail(n-1) = (diag * zhat / (((diag - shifts(k)) - mus(k)) * (diag + singVals[k]))).tail(n-1); V(0,k) = -1; V.col(k).normalize(); @@ -688,15 +699,17 @@ void BDCSVD<MatrixType>::computeSingVecs // i >= 1, di almost null and zi non null. // We use a rotation to zero out zi applied to the left of M template <typename MatrixType> -void BDCSVD<MatrixType>::deflation43(Index firstCol, Index shift, Index i, Index size){ +void BDCSVD<MatrixType>::deflation43(Index firstCol, Index shift, Index i, Index size) +{ using std::abs; using std::sqrt; using std::pow; RealScalar c = m_computed(firstCol + shift, firstCol + shift); RealScalar s = m_computed(i, firstCol + shift); RealScalar r = sqrt(pow(abs(c), 2) + pow(abs(s), 2)); - if (r == 0){ - m_computed(i, i)=0; + if (r == 0) + { + m_computed(i, i) = 0; return; } c/=r; @@ -704,7 +717,8 @@ void BDCSVD<MatrixType>::deflation43(Index firstCol, Index shift, Index i, Index m_computed(firstCol + shift, firstCol + shift) = r; m_computed(i, firstCol + shift) = 0; m_computed(i, i) = 0; - if (compU){ + if (m_compU) + { m_naiveU.col(firstCol).segment(firstCol,size) = c * m_naiveU.col(firstCol).segment(firstCol, size) - s * m_naiveU.col(i).segment(firstCol, size) ; @@ -720,7 +734,8 @@ void BDCSVD<MatrixType>::deflation43(Index firstCol, Index shift, Index i, Index // i,j >= 1, i != j and |di - dj| < epsilon * norm2(M) // We apply two rotations to have zj = 0; template <typename MatrixType> -void BDCSVD<MatrixType>::deflation44(Index firstColu , Index firstColm, Index firstRowW, Index firstColW, Index i, Index j, Index size){ +void BDCSVD<MatrixType>::deflation44(Index firstColu , Index firstColm, Index firstRowW, Index firstColW, Index i, Index j, Index size) +{ using std::abs; using std::sqrt; using std::conj; @@ -728,7 +743,8 @@ void BDCSVD<MatrixType>::deflation44(Index firstColu , Index firstColm, Index fi RealScalar c = m_computed(firstColm, firstColm + j - 1); RealScalar s = m_computed(firstColm, firstColm + i - 1); RealScalar r = sqrt(pow(abs(c), 2) + pow(abs(s), 2)); - if (r==0){ + if (r==0) + { m_computed(firstColm + i, firstColm + i) = m_computed(firstColm + j, firstColm + j); return; } @@ -737,7 +753,8 @@ void BDCSVD<MatrixType>::deflation44(Index firstColu , Index firstColm, Index fi m_computed(firstColm + i, firstColm) = r; m_computed(firstColm + i, firstColm + i) = m_computed(firstColm + j, firstColm + j); m_computed(firstColm + j, firstColm) = 0; - if (compU){ + if (m_compU) + { m_naiveU.col(firstColu + i).segment(firstColu, size) = c * m_naiveU.col(firstColu + i).segment(firstColu, size) - s * m_naiveU.col(firstColu + j).segment(firstColu, size) ; @@ -746,7 +763,8 @@ void BDCSVD<MatrixType>::deflation44(Index firstColu , Index firstColm, Index fi (c + s*s/c) * m_naiveU.col(firstColu + j).segment(firstColu, size) + (s/c) * m_naiveU.col(firstColu + i).segment(firstColu, size); } - if (compV){ + if (m_compV) + { m_naiveV.col(firstColW + i).segment(firstRowW, size - 1) = c * m_naiveV.col(firstColW + i).segment(firstRowW, size - 1) + s * m_naiveV.col(firstColW + j).segment(firstRowW, size - 1) ; @@ -760,72 +778,56 @@ void BDCSVD<MatrixType>::deflation44(Index firstColu , Index firstColm, Index fi // acts on block from (firstCol+shift, firstCol+shift) to (lastCol+shift, lastCol+shift) [inclusive] template <typename MatrixType> -void BDCSVD<MatrixType>::deflation(Index firstCol, Index lastCol, Index k, Index firstRowW, Index firstColW, Index shift){ +void BDCSVD<MatrixType>::deflation(Index firstCol, Index lastCol, Index k, Index firstRowW, Index firstColW, Index shift) +{ //condition 4.1 using std::sqrt; + using std::abs; const Index length = lastCol + 1 - firstCol; RealScalar norm1 = m_computed.block(firstCol+shift, firstCol+shift, length, 1).squaredNorm(); RealScalar norm2 = m_computed.block(firstCol+shift, firstCol+shift, length, length).diagonal().squaredNorm(); - RealScalar EPS = 10 * NumTraits<RealScalar>::epsilon() * sqrt(norm1 + norm2); - if (m_computed(firstCol + shift, firstCol + shift) < EPS){ - m_computed(firstCol + shift, firstCol + shift) = EPS; - } + RealScalar epsilon = 10 * NumTraits<RealScalar>::epsilon() * sqrt(norm1 + norm2); + if (m_computed(firstCol + shift, firstCol + shift) < epsilon) + m_computed(firstCol + shift, firstCol + shift) = epsilon; //condition 4.2 - for (Index i=firstCol + shift + 1;i<=lastCol + shift;i++){ - if (std::abs(m_computed(i, firstCol + shift)) < EPS){ + for (Index i=firstCol + shift + 1;i<=lastCol + shift;i++) + if (abs(m_computed(i, firstCol + shift)) < epsilon) m_computed(i, firstCol + shift) = 0; - } - } //condition 4.3 - for (Index i=firstCol + shift + 1;i<=lastCol + shift; i++){ - if (m_computed(i, i) < EPS){ + for (Index i=firstCol + shift + 1;i<=lastCol + shift; i++) + if (m_computed(i, i) < epsilon) deflation43(firstCol, shift, i, length); - } - } //condition 4.4 Index i=firstCol + shift + 1, j=firstCol + shift + k + 1; //we stock the final place of each line - Index *permutation = new Index[length]; + Index *permutation = new Index[length]; // FIXME avoid repeated dynamic memory allocation - for (Index p =1; p < length; p++) { - if (i> firstCol + shift + k){ - permutation[p] = j; - j++; - } else if (j> lastCol + shift) - { - permutation[p] = i; - i++; - } - else - { - if (m_computed(i, i) < m_computed(j, j)){ - permutation[p] = j; - j++; - } - else - { - permutation[p] = i; - i++; - } - } + for (Index p =1; p < length; p++) + { + if (i> firstCol + shift + k) permutation[p] = j++; + else if (j> lastCol + shift) permutation[p] = i++; + else if (m_computed(i, i) < m_computed(j, j)) permutation[p] = j++; + else permutation[p] = i++; } //we do the permutation RealScalar aux; //we stock the current index of each col //and the column of each index - Index *realInd = new Index[length]; - Index *realCol = new Index[length]; - for (int pos = 0; pos< length; pos++){ + Index *realInd = new Index[length]; // FIXME avoid repeated dynamic memory allocation + Index *realCol = new Index[length]; // FIXME avoid repeated dynamic memory allocation + for (int pos = 0; pos< length; pos++) + { realCol[pos] = pos + firstCol + shift; realInd[pos] = pos; } const Index Zero = firstCol + shift; VectorType temp; - for (int i = 1; i < length - 1; i++){ + for (int i = 1; i < length - 1; i++) + { const Index I = i + Zero; const Index realI = realInd[i]; const Index j = permutation[length - i] - Zero; @@ -842,25 +844,25 @@ void BDCSVD<MatrixType>::deflation(Index firstCol, Index lastCol, Index k, Index m_computed(J, Zero) = aux; // change columns - if (compU) { + if (m_compU) + { temp = m_naiveU.col(I - shift).segment(firstCol, length + 1); - m_naiveU.col(I - shift).segment(firstCol, length + 1) << - m_naiveU.col(J - shift).segment(firstCol, length + 1); - m_naiveU.col(J - shift).segment(firstCol, length + 1) << temp; + m_naiveU.col(I - shift).segment(firstCol, length + 1) = m_naiveU.col(J - shift).segment(firstCol, length + 1); + m_naiveU.col(J - shift).segment(firstCol, length + 1) = temp; } else { temp = m_naiveU.col(I - shift).segment(0, 2); - m_naiveU.col(I - shift).segment(0, 2) << - m_naiveU.col(J - shift).segment(0, 2); - m_naiveU.col(J - shift).segment(0, 2) << temp; + m_naiveU.col(I - shift).template head<2>() = m_naiveU.col(J - shift).segment(0, 2); + m_naiveU.col(J - shift).template head<2>() = temp; } - if (compV) { + if (m_compV) + { const Index CWI = I + firstColW - Zero; const Index CWJ = J + firstColW - Zero; temp = m_naiveV.col(CWI).segment(firstRowW, length); - m_naiveV.col(CWI).segment(firstRowW, length) << m_naiveV.col(CWJ).segment(firstRowW, length); - m_naiveV.col(CWJ).segment(firstRowW, length) << temp; + m_naiveV.col(CWI).segment(firstRowW, length) = m_naiveV.col(CWJ).segment(firstRowW, length); + m_naiveV.col(CWJ).segment(firstRowW, length) = temp; } //update real pos @@ -869,53 +871,16 @@ void BDCSVD<MatrixType>::deflation(Index firstCol, Index lastCol, Index k, Index realInd[J - Zero] = realI; realInd[I - Zero] = j; } - for (Index i = firstCol + shift + 1; i<lastCol + shift;i++){ - if ((m_computed(i + 1, i + 1) - m_computed(i, i)) < EPS){ - deflation44(firstCol , - firstCol + shift, - firstRowW, - firstColW, - i - Zero, - i + 1 - Zero, - length); - } - } - delete [] permutation; - delete [] realInd; - delete [] realCol; + for (Index i = firstCol + shift + 1; i<lastCol + shift;i++) + if ((m_computed(i + 1, i + 1) - m_computed(i, i)) < epsilon) + deflation44(firstCol, firstCol + shift, firstRowW, firstColW, i - Zero, i + 1 - Zero, length); + + delete[] permutation; + delete[] realInd; + delete[] realCol; }//end deflation -namespace internal{ - -template<typename _MatrixType, typename Rhs> -struct solve_retval<BDCSVD<_MatrixType>, Rhs> - : solve_retval_base<BDCSVD<_MatrixType>, Rhs> -{ - typedef BDCSVD<_MatrixType> BDCSVDType; - EIGEN_MAKE_SOLVE_HELPERS(BDCSVDType, Rhs) - - template<typename Dest> void evalTo(Dest& dst) const - { - eigen_assert(rhs().rows() == dec().rows()); - // A = U S V^* - // So A^{ - 1} = V S^{ - 1} U^* - Index diagSize = (std::min)(dec().rows(), dec().cols()); - typename BDCSVDType::SingularValuesType invertedSingVals(diagSize); - Index nonzeroSingVals = dec().nonzeroSingularValues(); - invertedSingVals.head(nonzeroSingVals) = dec().singularValues().head(nonzeroSingVals).array().inverse(); - invertedSingVals.tail(diagSize - nonzeroSingVals).setZero(); - - dst = dec().matrixV().leftCols(diagSize) - * invertedSingVals.asDiagonal() - * dec().matrixU().leftCols(diagSize).adjoint() - * rhs(); - return; - } -}; - -} //end namespace internal - /** \svd_module * * \return the singular value decomposition of \c *this computed by diff --git a/unsupported/Eigen/src/BDCSVD/CMakeLists.txt b/unsupported/Eigen/src/BDCSVD/CMakeLists.txt new file mode 100644 index 000000000..73b89ea18 --- /dev/null +++ b/unsupported/Eigen/src/BDCSVD/CMakeLists.txt @@ -0,0 +1,6 @@ +FILE(GLOB Eigen_BDCSVD_SRCS "*.h") + +INSTALL(FILES + ${Eigen_BDCSVD_SRCS} + DESTINATION ${INCLUDE_INSTALL_DIR}unsupported/Eigen/src/BDCSVD COMPONENT Devel + ) diff --git a/unsupported/Eigen/src/SVD/TODOBdcsvd.txt b/unsupported/Eigen/src/BDCSVD/TODOBdcsvd.txt index 0bc9a46e6..0bc9a46e6 100644 --- a/unsupported/Eigen/src/SVD/TODOBdcsvd.txt +++ b/unsupported/Eigen/src/BDCSVD/TODOBdcsvd.txt diff --git a/unsupported/Eigen/src/SVD/doneInBDCSVD.txt b/unsupported/Eigen/src/BDCSVD/doneInBDCSVD.txt index 8563ddab8..8563ddab8 100644 --- a/unsupported/Eigen/src/SVD/doneInBDCSVD.txt +++ b/unsupported/Eigen/src/BDCSVD/doneInBDCSVD.txt diff --git a/unsupported/Eigen/src/CMakeLists.txt b/unsupported/Eigen/src/CMakeLists.txt index 8eb2808e3..654a2327f 100644 --- a/unsupported/Eigen/src/CMakeLists.txt +++ b/unsupported/Eigen/src/CMakeLists.txt @@ -12,3 +12,4 @@ ADD_SUBDIRECTORY(Skyline) ADD_SUBDIRECTORY(SparseExtra) ADD_SUBDIRECTORY(KroneckerProduct) ADD_SUBDIRECTORY(Splines) +ADD_SUBDIRECTORY(BDCSVD) diff --git a/unsupported/Eigen/src/IterativeSolvers/DGMRES.h b/unsupported/Eigen/src/IterativeSolvers/DGMRES.h index 9fcc8a8d9..0e1b7d977 100644 --- a/unsupported/Eigen/src/IterativeSolvers/DGMRES.h +++ b/unsupported/Eigen/src/IterativeSolvers/DGMRES.h @@ -108,6 +108,7 @@ class DGMRES : public IterativeSolverBase<DGMRES<_MatrixType,_Preconditioner> > using Base::m_isInitialized; using Base::m_tolerance; public: + using Base::_solve_impl; typedef _MatrixType MatrixType; typedef typename MatrixType::Scalar Scalar; typedef typename MatrixType::Index Index; @@ -138,25 +139,9 @@ class DGMRES : public IterativeSolverBase<DGMRES<_MatrixType,_Preconditioner> > ~DGMRES() {} - /** \returns the solution x of \f$ A x = b \f$ using the current decomposition of A - * \a x0 as an initial solution. - * - * \sa compute() - */ - template<typename Rhs,typename Guess> - inline const internal::solve_retval_with_guess<DGMRES, Rhs, Guess> - solveWithGuess(const MatrixBase<Rhs>& b, const Guess& x0) const - { - eigen_assert(m_isInitialized && "DGMRES is not initialized."); - eigen_assert(Base::rows()==b.rows() - && "DGMRES::solve(): invalid number of rows of the right hand side matrix b"); - return internal::solve_retval_with_guess - <DGMRES, Rhs, Guess>(*this, b.derived(), x0); - } - /** \internal */ template<typename Rhs,typename Dest> - void _solveWithGuess(const Rhs& b, Dest& x) const + void _solve_with_guess_impl(const Rhs& b, Dest& x) const { bool failed = false; for(int j=0; j<b.cols(); ++j) @@ -175,10 +160,10 @@ class DGMRES : public IterativeSolverBase<DGMRES<_MatrixType,_Preconditioner> > /** \internal */ template<typename Rhs,typename Dest> - void _solve(const Rhs& b, Dest& x) const + void _solve_impl(const Rhs& b, MatrixBase<Dest>& x) const { x = b; - _solveWithGuess(b,x); + _solve_with_guess_impl(b,x.derived()); } /** * Get the restart value @@ -522,21 +507,5 @@ int DGMRES<_MatrixType, _Preconditioner>::dgmresApplyDeflation(const RhsType &x, return 0; } -namespace internal { - - template<typename _MatrixType, typename _Preconditioner, typename Rhs> -struct solve_retval<DGMRES<_MatrixType, _Preconditioner>, Rhs> - : solve_retval_base<DGMRES<_MatrixType, _Preconditioner>, Rhs> -{ - typedef DGMRES<_MatrixType, _Preconditioner> Dec; - EIGEN_MAKE_SOLVE_HELPERS(Dec,Rhs) - - template<typename Dest> void evalTo(Dest& dst) const - { - dec()._solve(rhs(),dst); - } -}; -} // end namespace internal - } // end namespace Eigen #endif diff --git a/unsupported/Eigen/src/IterativeSolvers/GMRES.h b/unsupported/Eigen/src/IterativeSolvers/GMRES.h index 67498705b..cd15ce0bf 100644 --- a/unsupported/Eigen/src/IterativeSolvers/GMRES.h +++ b/unsupported/Eigen/src/IterativeSolvers/GMRES.h @@ -281,6 +281,7 @@ private: int m_restart; public: + using Base::_solve_impl; typedef _MatrixType MatrixType; typedef typename MatrixType::Scalar Scalar; typedef typename MatrixType::Index Index; @@ -315,25 +316,9 @@ public: */ void set_restart(const int restart) { m_restart=restart; } - /** \returns the solution x of \f$ A x = b \f$ using the current decomposition of A - * \a x0 as an initial solution. - * - * \sa compute() - */ - template<typename Rhs,typename Guess> - inline const internal::solve_retval_with_guess<GMRES, Rhs, Guess> - solveWithGuess(const MatrixBase<Rhs>& b, const Guess& x0) const - { - eigen_assert(m_isInitialized && "GMRES is not initialized."); - eigen_assert(Base::rows()==b.rows() - && "GMRES::solve(): invalid number of rows of the right hand side matrix b"); - return internal::solve_retval_with_guess - <GMRES, Rhs, Guess>(*this, b.derived(), x0); - } - /** \internal */ template<typename Rhs,typename Dest> - void _solveWithGuess(const Rhs& b, Dest& x) const + void _solve_with_guess_impl(const Rhs& b, Dest& x) const { bool failed = false; for(int j=0; j<b.cols(); ++j) @@ -353,35 +338,17 @@ public: /** \internal */ template<typename Rhs,typename Dest> - void _solve(const Rhs& b, Dest& x) const + void _solve_impl(const Rhs& b, MatrixBase<Dest> &x) const { x = b; if(x.squaredNorm() == 0) return; // Check Zero right hand side - _solveWithGuess(b,x); + _solve_with_guess_impl(b,x.derived()); } protected: }; - -namespace internal { - - template<typename _MatrixType, typename _Preconditioner, typename Rhs> -struct solve_retval<GMRES<_MatrixType, _Preconditioner>, Rhs> - : solve_retval_base<GMRES<_MatrixType, _Preconditioner>, Rhs> -{ - typedef GMRES<_MatrixType, _Preconditioner> Dec; - EIGEN_MAKE_SOLVE_HELPERS(Dec,Rhs) - - template<typename Dest> void evalTo(Dest& dst) const - { - dec()._solve(rhs(),dst); - } -}; - -} // end namespace internal - } // end namespace Eigen #endif // EIGEN_GMRES_H diff --git a/unsupported/Eigen/src/IterativeSolvers/IncompleteCholesky.h b/unsupported/Eigen/src/IterativeSolvers/IncompleteCholesky.h index 661c1f2e0..dd43de6b3 100644 --- a/unsupported/Eigen/src/IterativeSolvers/IncompleteCholesky.h +++ b/unsupported/Eigen/src/IterativeSolvers/IncompleteCholesky.h @@ -27,8 +27,11 @@ namespace Eigen { */ template <typename Scalar, int _UpLo = Lower, typename _OrderingType = NaturalOrdering<int> > -class IncompleteCholesky : internal::noncopyable +class IncompleteCholesky : public SparseSolverBase<IncompleteCholesky<Scalar,_UpLo,_OrderingType> > { + protected: + typedef SparseSolverBase<IncompleteCholesky<Scalar,_UpLo,_OrderingType> > Base; + using Base::m_isInitialized; public: typedef SparseMatrix<Scalar,ColMajor> MatrixType; typedef _OrderingType OrderingType; @@ -89,7 +92,7 @@ class IncompleteCholesky : internal::noncopyable } template<typename Rhs, typename Dest> - void _solve(const Rhs& b, Dest& x) const + void _solve_impl(const Rhs& b, Dest& x) const { eigen_assert(m_factorizationIsOk && "factorize() should be called first"); if (m_perm.rows() == b.rows()) @@ -103,22 +106,13 @@ class IncompleteCholesky : internal::noncopyable x = m_perm * x; x = m_scal.asDiagonal() * x; } - template<typename Rhs> inline const internal::solve_retval<IncompleteCholesky, Rhs> - solve(const MatrixBase<Rhs>& b) const - { - eigen_assert(m_factorizationIsOk && "IncompleteLLT did not succeed"); - eigen_assert(m_isInitialized && "IncompleteLLT is not initialized."); - eigen_assert(cols()==b.rows() - && "IncompleteLLT::solve(): invalid number of rows of the right hand side matrix b"); - return internal::solve_retval<IncompleteCholesky, Rhs>(*this, b.derived()); - } + protected: SparseMatrix<Scalar,ColMajor> m_L; // The lower part stored in CSC ScalarType m_scal; // The vector for scaling the matrix Scalar m_shift; //The initial shift parameter bool m_analysisIsOk; bool m_factorizationIsOk; - bool m_isInitialized; ComputationInfo m_info; PermutationType m_perm; @@ -256,22 +250,6 @@ inline void IncompleteCholesky<Scalar,_UpLo, OrderingType>::updateList(const Idx listCol[rowIdx(jk)].push_back(col); } } -namespace internal { - -template<typename _Scalar, int _UpLo, typename OrderingType, typename Rhs> -struct solve_retval<IncompleteCholesky<_Scalar, _UpLo, OrderingType>, Rhs> - : solve_retval_base<IncompleteCholesky<_Scalar, _UpLo, OrderingType>, Rhs> -{ - typedef IncompleteCholesky<_Scalar, _UpLo, OrderingType> Dec; - EIGEN_MAKE_SOLVE_HELPERS(Dec,Rhs) - - template<typename Dest> void evalTo(Dest& dst) const - { - dec()._solve(rhs(),dst); - } -}; - -} // end namespace internal } // end namespace Eigen diff --git a/unsupported/Eigen/src/IterativeSolvers/IncompleteLU.h b/unsupported/Eigen/src/IterativeSolvers/IncompleteLU.h index 67e780181..7d08c3515 100644 --- a/unsupported/Eigen/src/IterativeSolvers/IncompleteLU.h +++ b/unsupported/Eigen/src/IterativeSolvers/IncompleteLU.h @@ -13,8 +13,12 @@ namespace Eigen { template <typename _Scalar> -class IncompleteLU +class IncompleteLU : public SparseSolverBase<IncompleteLU<_Scalar> > { + protected: + typedef SparseSolverBase<IncompleteLU<_Scalar> > Base; + using Base::m_isInitialized; + typedef _Scalar Scalar; typedef Matrix<Scalar,Dynamic,1> Vector; typedef typename Vector::Index Index; @@ -23,10 +27,10 @@ class IncompleteLU public: typedef Matrix<Scalar,Dynamic,Dynamic> MatrixType; - IncompleteLU() : m_isInitialized(false) {} + IncompleteLU() {} template<typename MatrixType> - IncompleteLU(const MatrixType& mat) : m_isInitialized(false) + IncompleteLU(const MatrixType& mat) { compute(mat); } @@ -71,43 +75,16 @@ class IncompleteLU } template<typename Rhs, typename Dest> - void _solve(const Rhs& b, Dest& x) const + void _solve_impl(const Rhs& b, Dest& x) const { x = m_lu.template triangularView<UnitLower>().solve(b); x = m_lu.template triangularView<Upper>().solve(x); } - template<typename Rhs> inline const internal::solve_retval<IncompleteLU, Rhs> - solve(const MatrixBase<Rhs>& b) const - { - eigen_assert(m_isInitialized && "IncompleteLU is not initialized."); - eigen_assert(cols()==b.rows() - && "IncompleteLU::solve(): invalid number of rows of the right hand side matrix b"); - return internal::solve_retval<IncompleteLU, Rhs>(*this, b.derived()); - } - protected: FactorType m_lu; - bool m_isInitialized; -}; - -namespace internal { - -template<typename _MatrixType, typename Rhs> -struct solve_retval<IncompleteLU<_MatrixType>, Rhs> - : solve_retval_base<IncompleteLU<_MatrixType>, Rhs> -{ - typedef IncompleteLU<_MatrixType> Dec; - EIGEN_MAKE_SOLVE_HELPERS(Dec,Rhs) - - template<typename Dest> void evalTo(Dest& dst) const - { - dec()._solve(rhs(),dst); - } }; -} // end namespace internal - } // end namespace Eigen #endif // EIGEN_INCOMPLETE_LU_H diff --git a/unsupported/Eigen/src/IterativeSolvers/MINRES.h b/unsupported/Eigen/src/IterativeSolvers/MINRES.h index 98f9ecc17..aaf42c78a 100644 --- a/unsupported/Eigen/src/IterativeSolvers/MINRES.h +++ b/unsupported/Eigen/src/IterativeSolvers/MINRES.h @@ -2,7 +2,7 @@ // for linear algebra. // // Copyright (C) 2012 Giacomo Po <gpo@ucla.edu> -// Copyright (C) 2011 Gael Guennebaud <gael.guennebaud@inria.fr> +// Copyright (C) 2011-2014 Gael Guennebaud <gael.guennebaud@inria.fr> // // 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 @@ -217,6 +217,7 @@ namespace Eigen { using Base::m_info; using Base::m_isInitialized; public: + using Base::_solve_impl; typedef _MatrixType MatrixType; typedef typename MatrixType::Scalar Scalar; typedef typename MatrixType::Index Index; @@ -244,26 +245,10 @@ namespace Eigen { /** Destructor. */ ~MINRES(){} - - /** \returns the solution x of \f$ A x = b \f$ using the current decomposition of A - * \a x0 as an initial solution. - * - * \sa compute() - */ - template<typename Rhs,typename Guess> - inline const internal::solve_retval_with_guess<MINRES, Rhs, Guess> - solveWithGuess(const MatrixBase<Rhs>& b, const Guess& x0) const - { - eigen_assert(m_isInitialized && "MINRES is not initialized."); - eigen_assert(Base::rows()==b.rows() - && "MINRES::solve(): invalid number of rows of the right hand side matrix b"); - return internal::solve_retval_with_guess - <MINRES, Rhs, Guess>(*this, b.derived(), x0); - } - + /** \internal */ template<typename Rhs,typename Dest> - void _solveWithGuess(const Rhs& b, Dest& x) const + void _solve_with_guess_impl(const Rhs& b, Dest& x) const { m_iterations = Base::maxIterations(); m_error = Base::m_tolerance; @@ -284,33 +269,16 @@ namespace Eigen { /** \internal */ template<typename Rhs,typename Dest> - void _solve(const Rhs& b, Dest& x) const + void _solve_impl(const Rhs& b, MatrixBase<Dest> &x) const { x.setZero(); - _solveWithGuess(b,x); + _solve_with_guess_impl(b,x.derived()); } protected: }; - - namespace internal { - - template<typename _MatrixType, int _UpLo, typename _Preconditioner, typename Rhs> - struct solve_retval<MINRES<_MatrixType,_UpLo,_Preconditioner>, Rhs> - : solve_retval_base<MINRES<_MatrixType,_UpLo,_Preconditioner>, Rhs> - { - typedef MINRES<_MatrixType,_UpLo,_Preconditioner> Dec; - EIGEN_MAKE_SOLVE_HELPERS(Dec,Rhs) - - template<typename Dest> void evalTo(Dest& dst) const - { - dec()._solve(rhs(),dst); - } - }; - - } // end namespace internal - + } // end namespace Eigen #endif // EIGEN_MINRES_H diff --git a/unsupported/Eigen/src/KroneckerProduct/KroneckerTensorProduct.h b/unsupported/Eigen/src/KroneckerProduct/KroneckerTensorProduct.h index b8f2cba17..72e25db19 100644 --- a/unsupported/Eigen/src/KroneckerProduct/KroneckerTensorProduct.h +++ b/unsupported/Eigen/src/KroneckerProduct/KroneckerTensorProduct.h @@ -154,16 +154,41 @@ void KroneckerProductSparse<Lhs,Rhs>::evalTo(Dest& dst) const dst.resize(this->rows(), this->cols()); dst.resizeNonZeros(0); + // 1 - evaluate the operands if needed: + typedef typename internal::nested_eval<Lhs,10>::type Lhs1; + typedef typename internal::remove_all<Lhs1>::type Lhs1Cleaned; + const Lhs1 lhs1(m_A); + typedef typename internal::nested_eval<Rhs,10>::type Rhs1; + typedef typename internal::remove_all<Rhs1>::type Rhs1Cleaned; + const Rhs1 rhs1(m_B); + + // 2 - construct a SparseView for dense operands + typedef typename internal::conditional<internal::is_same<typename internal::traits<Lhs1Cleaned>::StorageKind,Sparse>::value, Lhs1, SparseView<const Lhs1Cleaned> >::type Lhs2; + typedef typename internal::remove_all<Lhs2>::type Lhs2Cleaned; + const Lhs2 lhs2(lhs1); + typedef typename internal::conditional<internal::is_same<typename internal::traits<Rhs1Cleaned>::StorageKind,Sparse>::value, Rhs1, SparseView<const Rhs1Cleaned> >::type Rhs2; + typedef typename internal::remove_all<Rhs2>::type Rhs2Cleaned; + const Rhs2 rhs2(rhs1); + + // 3 - construct respective evaluators + typedef typename internal::evaluator<Lhs2Cleaned>::type LhsEval; + LhsEval lhsEval(lhs2); + typedef typename internal::evaluator<Rhs2Cleaned>::type RhsEval; + RhsEval rhsEval(rhs2); + + typedef typename LhsEval::InnerIterator LhsInnerIterator; + typedef typename RhsEval::InnerIterator RhsInnerIterator; + // compute number of non-zeros per innervectors of dst { VectorXi nnzA = VectorXi::Zero(Dest::IsRowMajor ? m_A.rows() : m_A.cols()); for (Index kA=0; kA < m_A.outerSize(); ++kA) - for (typename Lhs::InnerIterator itA(m_A,kA); itA; ++itA) + for (LhsInnerIterator itA(lhsEval,kA); itA; ++itA) nnzA(Dest::IsRowMajor ? itA.row() : itA.col())++; VectorXi nnzB = VectorXi::Zero(Dest::IsRowMajor ? m_B.rows() : m_B.cols()); for (Index kB=0; kB < m_B.outerSize(); ++kB) - for (typename Rhs::InnerIterator itB(m_B,kB); itB; ++itB) + for (RhsInnerIterator itB(rhsEval,kB); itB; ++itB) nnzB(Dest::IsRowMajor ? itB.row() : itB.col())++; Matrix<int,Dynamic,Dynamic,ColMajor> nnzAB = nnzB * nnzA.transpose(); @@ -174,9 +199,9 @@ void KroneckerProductSparse<Lhs,Rhs>::evalTo(Dest& dst) const { for (Index kB=0; kB < m_B.outerSize(); ++kB) { - for (typename Lhs::InnerIterator itA(m_A,kA); itA; ++itA) + for (LhsInnerIterator itA(lhsEval,kA); itA; ++itA) { - for (typename Rhs::InnerIterator itB(m_B,kB); itB; ++itB) + for (RhsInnerIterator itB(rhsEval,kB); itB; ++itB) { const Index i = itA.row() * Br + itB.row(), j = itA.col() * Bc + itB.col(); @@ -201,8 +226,7 @@ struct traits<KroneckerProduct<_Lhs,_Rhs> > Rows = size_at_compile_time<traits<Lhs>::RowsAtCompileTime, traits<Rhs>::RowsAtCompileTime>::ret, Cols = size_at_compile_time<traits<Lhs>::ColsAtCompileTime, traits<Rhs>::ColsAtCompileTime>::ret, MaxRows = size_at_compile_time<traits<Lhs>::MaxRowsAtCompileTime, traits<Rhs>::MaxRowsAtCompileTime>::ret, - MaxCols = size_at_compile_time<traits<Lhs>::MaxColsAtCompileTime, traits<Rhs>::MaxColsAtCompileTime>::ret, - CoeffReadCost = Lhs::CoeffReadCost + Rhs::CoeffReadCost + NumTraits<Scalar>::MulCost + MaxCols = size_at_compile_time<traits<Lhs>::MaxColsAtCompileTime, traits<Rhs>::MaxColsAtCompileTime>::ret }; typedef Matrix<Scalar,Rows,Cols> ReturnType; @@ -215,7 +239,7 @@ struct traits<KroneckerProductSparse<_Lhs,_Rhs> > typedef typename remove_all<_Lhs>::type Lhs; typedef typename remove_all<_Rhs>::type Rhs; typedef typename scalar_product_traits<typename Lhs::Scalar, typename Rhs::Scalar>::ReturnType Scalar; - typedef typename promote_storage_type<typename traits<Lhs>::StorageKind, typename traits<Rhs>::StorageKind>::ret StorageKind; + typedef typename cwise_promote_storage_type<typename traits<Lhs>::StorageKind, typename traits<Rhs>::StorageKind, scalar_product_op<typename Lhs::Scalar, typename Rhs::Scalar> >::ret StorageKind; typedef typename promote_index_type<typename Lhs::Index, typename Rhs::Index>::type Index; enum { diff --git a/unsupported/Eigen/src/MatrixFunctions/MatrixExponential.h b/unsupported/Eigen/src/MatrixFunctions/MatrixExponential.h index 160120d03..9e0545660 100644 --- a/unsupported/Eigen/src/MatrixFunctions/MatrixExponential.h +++ b/unsupported/Eigen/src/MatrixFunctions/MatrixExponential.h @@ -392,14 +392,15 @@ template<typename Derived> struct MatrixExponentialReturnValue template <typename ResultType> inline void evalTo(ResultType& result) const { - internal::matrix_exp_compute(m_src, result); + const typename internal::nested_eval<Derived, 10>::type tmp(m_src); + internal::matrix_exp_compute(tmp, result); } Index rows() const { return m_src.rows(); } Index cols() const { return m_src.cols(); } protected: - const typename internal::nested<Derived, 10>::type m_src; + const typename internal::nested<Derived>::type m_src; }; namespace internal { diff --git a/unsupported/Eigen/src/MatrixFunctions/MatrixFunction.h b/unsupported/Eigen/src/MatrixFunctions/MatrixFunction.h index a35c11be5..b68aae5e8 100644 --- a/unsupported/Eigen/src/MatrixFunctions/MatrixFunction.h +++ b/unsupported/Eigen/src/MatrixFunctions/MatrixFunction.h @@ -485,7 +485,7 @@ template<typename Derived> class MatrixFunctionReturnValue typedef typename internal::stem_function<Scalar>::type StemFunction; protected: - typedef typename internal::nested<Derived, 10>::type DerivedNested; + typedef typename internal::nested<Derived>::type DerivedNested; public: @@ -503,18 +503,19 @@ template<typename Derived> class MatrixFunctionReturnValue template <typename ResultType> inline void evalTo(ResultType& result) const { - typedef typename internal::remove_all<DerivedNested>::type DerivedNestedClean; - typedef internal::traits<DerivedNestedClean> Traits; + typedef typename internal::nested_eval<Derived, 10>::type NestedEvalType; + typedef typename internal::remove_all<NestedEvalType>::type NestedEvalTypeClean; + typedef internal::traits<NestedEvalTypeClean> Traits; static const int RowsAtCompileTime = Traits::RowsAtCompileTime; static const int ColsAtCompileTime = Traits::ColsAtCompileTime; - static const int Options = DerivedNestedClean::Options; + static const int Options = NestedEvalTypeClean::Options; typedef std::complex<typename NumTraits<Scalar>::Real> ComplexScalar; typedef Matrix<ComplexScalar, Dynamic, Dynamic, Options, RowsAtCompileTime, ColsAtCompileTime> DynMatrixType; typedef internal::MatrixFunctionAtomic<DynMatrixType> AtomicType; AtomicType atomic(m_f); - internal::matrix_function_compute<DerivedNestedClean>::run(m_A, atomic, result); + internal::matrix_function_compute<NestedEvalTypeClean>::run(m_A, atomic, result); } Index rows() const { return m_A.rows(); } diff --git a/unsupported/Eigen/src/MatrixFunctions/MatrixLogarithm.h b/unsupported/Eigen/src/MatrixFunctions/MatrixLogarithm.h index d46ccc145..42b60b9b1 100644 --- a/unsupported/Eigen/src/MatrixFunctions/MatrixLogarithm.h +++ b/unsupported/Eigen/src/MatrixFunctions/MatrixLogarithm.h @@ -310,7 +310,7 @@ public: typedef typename Derived::Index Index; protected: - typedef typename internal::nested<Derived, 10>::type DerivedNested; + typedef typename internal::nested<Derived>::type DerivedNested; public: @@ -327,17 +327,18 @@ public: template <typename ResultType> inline void evalTo(ResultType& result) const { - typedef typename internal::remove_all<DerivedNested>::type DerivedNestedClean; - typedef internal::traits<DerivedNestedClean> Traits; + typedef typename internal::nested_eval<Derived, 10>::type DerivedEvalType; + typedef typename internal::remove_all<DerivedEvalType>::type DerivedEvalTypeClean; + typedef internal::traits<DerivedEvalTypeClean> Traits; static const int RowsAtCompileTime = Traits::RowsAtCompileTime; static const int ColsAtCompileTime = Traits::ColsAtCompileTime; - static const int Options = DerivedNestedClean::Options; + static const int Options = DerivedEvalTypeClean::Options; typedef std::complex<typename NumTraits<Scalar>::Real> ComplexScalar; typedef Matrix<ComplexScalar, Dynamic, Dynamic, Options, RowsAtCompileTime, ColsAtCompileTime> DynMatrixType; typedef internal::MatrixLogarithmAtomic<DynMatrixType> AtomicType; AtomicType atomic; - internal::matrix_function_compute<DerivedNestedClean>::run(m_A, atomic, result); + internal::matrix_function_compute<DerivedEvalTypeClean>::run(m_A, atomic, result); } Index rows() const { return m_A.rows(); } diff --git a/unsupported/Eigen/src/MatrixFunctions/MatrixSquareRoot.h b/unsupported/Eigen/src/MatrixFunctions/MatrixSquareRoot.h index 8ca4f4864..3a4d6eb3f 100644 --- a/unsupported/Eigen/src/MatrixFunctions/MatrixSquareRoot.h +++ b/unsupported/Eigen/src/MatrixFunctions/MatrixSquareRoot.h @@ -320,7 +320,7 @@ template<typename Derived> class MatrixSquareRootReturnValue { protected: typedef typename Derived::Index Index; - typedef typename internal::nested<Derived, 10>::type DerivedNested; + typedef typename internal::nested<Derived>::type DerivedNested; public: /** \brief Constructor. @@ -338,8 +338,10 @@ template<typename Derived> class MatrixSquareRootReturnValue template <typename ResultType> inline void evalTo(ResultType& result) const { - typedef typename internal::remove_all<DerivedNested>::type DerivedNestedClean; - internal::matrix_sqrt_compute<DerivedNestedClean>::run(m_src, result); + typedef typename internal::nested_eval<Derived, 10>::type DerivedEvalType; + typedef typename internal::remove_all<DerivedEvalType>::type DerivedEvalTypeClean; + DerivedEvalType tmp(m_src); + internal::matrix_sqrt_compute<DerivedEvalTypeClean>::run(tmp, result); } Index rows() const { return m_src.rows(); } diff --git a/unsupported/Eigen/src/NonLinearOptimization/LevenbergMarquardt.h b/unsupported/Eigen/src/NonLinearOptimization/LevenbergMarquardt.h index ecb8dccf4..69106ddc5 100644 --- a/unsupported/Eigen/src/NonLinearOptimization/LevenbergMarquardt.h +++ b/unsupported/Eigen/src/NonLinearOptimization/LevenbergMarquardt.h @@ -45,18 +45,24 @@ namespace LevenbergMarquardtSpace { template<typename FunctorType, typename Scalar=double> class LevenbergMarquardt { + static Scalar sqrt_epsilon() + { + using std::sqrt; + return sqrt(NumTraits<Scalar>::epsilon()); + } + public: LevenbergMarquardt(FunctorType &_functor) : functor(_functor) { nfev = njev = iter = 0; fnorm = gnorm = 0.; useExternalScaling=false; } typedef DenseIndex Index; - + struct Parameters { Parameters() : factor(Scalar(100.)) , maxfev(400) - , ftol(sqrt_(NumTraits<Scalar>::epsilon())) - , xtol(sqrt_(NumTraits<Scalar>::epsilon())) + , ftol(sqrt_epsilon()) + , xtol(sqrt_epsilon()) , gtol(Scalar(0.)) , epsfcn(Scalar(0.)) {} Scalar factor; @@ -72,7 +78,7 @@ public: LevenbergMarquardtSpace::Status lmder1( FVectorType &x, - const Scalar tol = sqrt_(NumTraits<Scalar>::epsilon()) + const Scalar tol = sqrt_epsilon() ); LevenbergMarquardtSpace::Status minimize(FVectorType &x); @@ -83,12 +89,12 @@ public: FunctorType &functor, FVectorType &x, Index *nfev, - const Scalar tol = sqrt_(NumTraits<Scalar>::epsilon()) + const Scalar tol = sqrt_epsilon() ); LevenbergMarquardtSpace::Status lmstr1( FVectorType &x, - const Scalar tol = sqrt_(NumTraits<Scalar>::epsilon()) + const Scalar tol = sqrt_epsilon() ); LevenbergMarquardtSpace::Status minimizeOptimumStorage(FVectorType &x); @@ -109,7 +115,6 @@ public: Scalar lm_param(void) { return par; } private: - static Scalar sqrt_(const Scalar& x) { using std::sqrt; return sqrt(x); } FunctorType &functor; Index n; diff --git a/unsupported/Eigen/src/SVD/CMakeLists.txt b/unsupported/Eigen/src/SVD/CMakeLists.txt deleted file mode 100644 index b40baf092..000000000 --- a/unsupported/Eigen/src/SVD/CMakeLists.txt +++ /dev/null @@ -1,6 +0,0 @@ -FILE(GLOB Eigen_SVD_SRCS "*.h") - -INSTALL(FILES - ${Eigen_SVD_SRCS} - DESTINATION ${INCLUDE_INSTALL_DIR}unsupported/Eigen/src/SVD COMPONENT Devel - ) diff --git a/unsupported/Eigen/src/SVD/JacobiSVD.h b/unsupported/Eigen/src/SVD/JacobiSVD.h deleted file mode 100644 index 02fac409e..000000000 --- a/unsupported/Eigen/src/SVD/JacobiSVD.h +++ /dev/null @@ -1,782 +0,0 @@ -// This file is part of Eigen, a lightweight C++ template library -// for linear algebra. -// -// Copyright (C) 2009-2010 Benoit Jacob <jacob.benoit.1@gmail.com> -// -// 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_JACOBISVD_H -#define EIGEN_JACOBISVD_H - -namespace Eigen { - -namespace internal { -// forward declaration (needed by ICC) -// the empty body is required by MSVC -template<typename MatrixType, int QRPreconditioner, - bool IsComplex = NumTraits<typename MatrixType::Scalar>::IsComplex> -struct svd_precondition_2x2_block_to_be_real {}; - -/*** QR preconditioners (R-SVD) - *** - *** Their role is to reduce the problem of computing the SVD to the case of a square matrix. - *** This approach, known as R-SVD, is an optimization for rectangular-enough matrices, and is a requirement for - *** JacobiSVD which by itself is only able to work on square matrices. - ***/ - -enum { PreconditionIfMoreColsThanRows, PreconditionIfMoreRowsThanCols }; - -template<typename MatrixType, int QRPreconditioner, int Case> -struct qr_preconditioner_should_do_anything -{ - enum { a = MatrixType::RowsAtCompileTime != Dynamic && - MatrixType::ColsAtCompileTime != Dynamic && - MatrixType::ColsAtCompileTime <= MatrixType::RowsAtCompileTime, - b = MatrixType::RowsAtCompileTime != Dynamic && - MatrixType::ColsAtCompileTime != Dynamic && - MatrixType::RowsAtCompileTime <= MatrixType::ColsAtCompileTime, - ret = !( (QRPreconditioner == NoQRPreconditioner) || - (Case == PreconditionIfMoreColsThanRows && bool(a)) || - (Case == PreconditionIfMoreRowsThanCols && bool(b)) ) - }; -}; - -template<typename MatrixType, int QRPreconditioner, int Case, - bool DoAnything = qr_preconditioner_should_do_anything<MatrixType, QRPreconditioner, Case>::ret -> struct qr_preconditioner_impl {}; - -template<typename MatrixType, int QRPreconditioner, int Case> -class qr_preconditioner_impl<MatrixType, QRPreconditioner, Case, false> -{ -public: - typedef typename MatrixType::Index Index; - void allocate(const JacobiSVD<MatrixType, QRPreconditioner>&) {} - bool run(JacobiSVD<MatrixType, QRPreconditioner>&, const MatrixType&) - { - return false; - } -}; - -/*** preconditioner using FullPivHouseholderQR ***/ - -template<typename MatrixType> -class qr_preconditioner_impl<MatrixType, FullPivHouseholderQRPreconditioner, PreconditionIfMoreRowsThanCols, true> -{ -public: - typedef typename MatrixType::Index Index; - typedef typename MatrixType::Scalar Scalar; - enum - { - RowsAtCompileTime = MatrixType::RowsAtCompileTime, - MaxRowsAtCompileTime = MatrixType::MaxRowsAtCompileTime - }; - typedef Matrix<Scalar, 1, RowsAtCompileTime, RowMajor, 1, MaxRowsAtCompileTime> WorkspaceType; - - void allocate(const JacobiSVD<MatrixType, FullPivHouseholderQRPreconditioner>& svd) - { - if (svd.rows() != m_qr.rows() || svd.cols() != m_qr.cols()) - { - m_qr.~QRType(); - ::new (&m_qr) QRType(svd.rows(), svd.cols()); - } - if (svd.m_computeFullU) m_workspace.resize(svd.rows()); - } - - bool run(JacobiSVD<MatrixType, FullPivHouseholderQRPreconditioner>& svd, const MatrixType& matrix) - { - if(matrix.rows() > matrix.cols()) - { - m_qr.compute(matrix); - svd.m_workMatrix = m_qr.matrixQR().block(0,0,matrix.cols(),matrix.cols()).template triangularView<Upper>(); - if(svd.m_computeFullU) m_qr.matrixQ().evalTo(svd.m_matrixU, m_workspace); - if(svd.computeV()) svd.m_matrixV = m_qr.colsPermutation(); - return true; - } - return false; - } -private: - typedef FullPivHouseholderQR<MatrixType> QRType; - QRType m_qr; - WorkspaceType m_workspace; -}; - -template<typename MatrixType> -class qr_preconditioner_impl<MatrixType, FullPivHouseholderQRPreconditioner, PreconditionIfMoreColsThanRows, true> -{ -public: - typedef typename MatrixType::Index Index; - typedef typename MatrixType::Scalar Scalar; - enum - { - RowsAtCompileTime = MatrixType::RowsAtCompileTime, - ColsAtCompileTime = MatrixType::ColsAtCompileTime, - MaxRowsAtCompileTime = MatrixType::MaxRowsAtCompileTime, - MaxColsAtCompileTime = MatrixType::MaxColsAtCompileTime, - Options = MatrixType::Options - }; - typedef Matrix<Scalar, ColsAtCompileTime, RowsAtCompileTime, Options, MaxColsAtCompileTime, MaxRowsAtCompileTime> - TransposeTypeWithSameStorageOrder; - - void allocate(const JacobiSVD<MatrixType, FullPivHouseholderQRPreconditioner>& svd) - { - if (svd.cols() != m_qr.rows() || svd.rows() != m_qr.cols()) - { - m_qr.~QRType(); - ::new (&m_qr) QRType(svd.cols(), svd.rows()); - } - m_adjoint.resize(svd.cols(), svd.rows()); - if (svd.m_computeFullV) m_workspace.resize(svd.cols()); - } - - bool run(JacobiSVD<MatrixType, FullPivHouseholderQRPreconditioner>& svd, const MatrixType& matrix) - { - if(matrix.cols() > matrix.rows()) - { - m_adjoint = matrix.adjoint(); - m_qr.compute(m_adjoint); - svd.m_workMatrix = m_qr.matrixQR().block(0,0,matrix.rows(),matrix.rows()).template triangularView<Upper>().adjoint(); - if(svd.m_computeFullV) m_qr.matrixQ().evalTo(svd.m_matrixV, m_workspace); - if(svd.computeU()) svd.m_matrixU = m_qr.colsPermutation(); - return true; - } - else return false; - } -private: - typedef FullPivHouseholderQR<TransposeTypeWithSameStorageOrder> QRType; - QRType m_qr; - TransposeTypeWithSameStorageOrder m_adjoint; - typename internal::plain_row_type<MatrixType>::type m_workspace; -}; - -/*** preconditioner using ColPivHouseholderQR ***/ - -template<typename MatrixType> -class qr_preconditioner_impl<MatrixType, ColPivHouseholderQRPreconditioner, PreconditionIfMoreRowsThanCols, true> -{ -public: - typedef typename MatrixType::Index Index; - - void allocate(const JacobiSVD<MatrixType, ColPivHouseholderQRPreconditioner>& svd) - { - if (svd.rows() != m_qr.rows() || svd.cols() != m_qr.cols()) - { - m_qr.~QRType(); - ::new (&m_qr) QRType(svd.rows(), svd.cols()); - } - if (svd.m_computeFullU) m_workspace.resize(svd.rows()); - else if (svd.m_computeThinU) m_workspace.resize(svd.cols()); - } - - bool run(JacobiSVD<MatrixType, ColPivHouseholderQRPreconditioner>& svd, const MatrixType& matrix) - { - if(matrix.rows() > matrix.cols()) - { - m_qr.compute(matrix); - svd.m_workMatrix = m_qr.matrixQR().block(0,0,matrix.cols(),matrix.cols()).template triangularView<Upper>(); - if(svd.m_computeFullU) m_qr.householderQ().evalTo(svd.m_matrixU, m_workspace); - else if(svd.m_computeThinU) - { - svd.m_matrixU.setIdentity(matrix.rows(), matrix.cols()); - m_qr.householderQ().applyThisOnTheLeft(svd.m_matrixU, m_workspace); - } - if(svd.computeV()) svd.m_matrixV = m_qr.colsPermutation(); - return true; - } - return false; - } - -private: - typedef ColPivHouseholderQR<MatrixType> QRType; - QRType m_qr; - typename internal::plain_col_type<MatrixType>::type m_workspace; -}; - -template<typename MatrixType> -class qr_preconditioner_impl<MatrixType, ColPivHouseholderQRPreconditioner, PreconditionIfMoreColsThanRows, true> -{ -public: - typedef typename MatrixType::Index Index; - typedef typename MatrixType::Scalar Scalar; - enum - { - RowsAtCompileTime = MatrixType::RowsAtCompileTime, - ColsAtCompileTime = MatrixType::ColsAtCompileTime, - MaxRowsAtCompileTime = MatrixType::MaxRowsAtCompileTime, - MaxColsAtCompileTime = MatrixType::MaxColsAtCompileTime, - Options = MatrixType::Options - }; - - typedef Matrix<Scalar, ColsAtCompileTime, RowsAtCompileTime, Options, MaxColsAtCompileTime, MaxRowsAtCompileTime> - TransposeTypeWithSameStorageOrder; - - void allocate(const JacobiSVD<MatrixType, ColPivHouseholderQRPreconditioner>& svd) - { - if (svd.cols() != m_qr.rows() || svd.rows() != m_qr.cols()) - { - m_qr.~QRType(); - ::new (&m_qr) QRType(svd.cols(), svd.rows()); - } - if (svd.m_computeFullV) m_workspace.resize(svd.cols()); - else if (svd.m_computeThinV) m_workspace.resize(svd.rows()); - m_adjoint.resize(svd.cols(), svd.rows()); - } - - bool run(JacobiSVD<MatrixType, ColPivHouseholderQRPreconditioner>& svd, const MatrixType& matrix) - { - if(matrix.cols() > matrix.rows()) - { - m_adjoint = matrix.adjoint(); - m_qr.compute(m_adjoint); - - svd.m_workMatrix = m_qr.matrixQR().block(0,0,matrix.rows(),matrix.rows()).template triangularView<Upper>().adjoint(); - if(svd.m_computeFullV) m_qr.householderQ().evalTo(svd.m_matrixV, m_workspace); - else if(svd.m_computeThinV) - { - svd.m_matrixV.setIdentity(matrix.cols(), matrix.rows()); - m_qr.householderQ().applyThisOnTheLeft(svd.m_matrixV, m_workspace); - } - if(svd.computeU()) svd.m_matrixU = m_qr.colsPermutation(); - return true; - } - else return false; - } - -private: - typedef ColPivHouseholderQR<TransposeTypeWithSameStorageOrder> QRType; - QRType m_qr; - TransposeTypeWithSameStorageOrder m_adjoint; - typename internal::plain_row_type<MatrixType>::type m_workspace; -}; - -/*** preconditioner using HouseholderQR ***/ - -template<typename MatrixType> -class qr_preconditioner_impl<MatrixType, HouseholderQRPreconditioner, PreconditionIfMoreRowsThanCols, true> -{ -public: - typedef typename MatrixType::Index Index; - - void allocate(const JacobiSVD<MatrixType, HouseholderQRPreconditioner>& svd) - { - if (svd.rows() != m_qr.rows() || svd.cols() != m_qr.cols()) - { - m_qr.~QRType(); - ::new (&m_qr) QRType(svd.rows(), svd.cols()); - } - if (svd.m_computeFullU) m_workspace.resize(svd.rows()); - else if (svd.m_computeThinU) m_workspace.resize(svd.cols()); - } - - bool run(JacobiSVD<MatrixType, HouseholderQRPreconditioner>& svd, const MatrixType& matrix) - { - if(matrix.rows() > matrix.cols()) - { - m_qr.compute(matrix); - svd.m_workMatrix = m_qr.matrixQR().block(0,0,matrix.cols(),matrix.cols()).template triangularView<Upper>(); - if(svd.m_computeFullU) m_qr.householderQ().evalTo(svd.m_matrixU, m_workspace); - else if(svd.m_computeThinU) - { - svd.m_matrixU.setIdentity(matrix.rows(), matrix.cols()); - m_qr.householderQ().applyThisOnTheLeft(svd.m_matrixU, m_workspace); - } - if(svd.computeV()) svd.m_matrixV.setIdentity(matrix.cols(), matrix.cols()); - return true; - } - return false; - } -private: - typedef HouseholderQR<MatrixType> QRType; - QRType m_qr; - typename internal::plain_col_type<MatrixType>::type m_workspace; -}; - -template<typename MatrixType> -class qr_preconditioner_impl<MatrixType, HouseholderQRPreconditioner, PreconditionIfMoreColsThanRows, true> -{ -public: - typedef typename MatrixType::Index Index; - typedef typename MatrixType::Scalar Scalar; - enum - { - RowsAtCompileTime = MatrixType::RowsAtCompileTime, - ColsAtCompileTime = MatrixType::ColsAtCompileTime, - MaxRowsAtCompileTime = MatrixType::MaxRowsAtCompileTime, - MaxColsAtCompileTime = MatrixType::MaxColsAtCompileTime, - Options = MatrixType::Options - }; - - typedef Matrix<Scalar, ColsAtCompileTime, RowsAtCompileTime, Options, MaxColsAtCompileTime, MaxRowsAtCompileTime> - TransposeTypeWithSameStorageOrder; - - void allocate(const JacobiSVD<MatrixType, HouseholderQRPreconditioner>& svd) - { - if (svd.cols() != m_qr.rows() || svd.rows() != m_qr.cols()) - { - m_qr.~QRType(); - ::new (&m_qr) QRType(svd.cols(), svd.rows()); - } - if (svd.m_computeFullV) m_workspace.resize(svd.cols()); - else if (svd.m_computeThinV) m_workspace.resize(svd.rows()); - m_adjoint.resize(svd.cols(), svd.rows()); - } - - bool run(JacobiSVD<MatrixType, HouseholderQRPreconditioner>& svd, const MatrixType& matrix) - { - if(matrix.cols() > matrix.rows()) - { - m_adjoint = matrix.adjoint(); - m_qr.compute(m_adjoint); - - svd.m_workMatrix = m_qr.matrixQR().block(0,0,matrix.rows(),matrix.rows()).template triangularView<Upper>().adjoint(); - if(svd.m_computeFullV) m_qr.householderQ().evalTo(svd.m_matrixV, m_workspace); - else if(svd.m_computeThinV) - { - svd.m_matrixV.setIdentity(matrix.cols(), matrix.rows()); - m_qr.householderQ().applyThisOnTheLeft(svd.m_matrixV, m_workspace); - } - if(svd.computeU()) svd.m_matrixU.setIdentity(matrix.rows(), matrix.rows()); - return true; - } - else return false; - } - -private: - typedef HouseholderQR<TransposeTypeWithSameStorageOrder> QRType; - QRType m_qr; - TransposeTypeWithSameStorageOrder m_adjoint; - typename internal::plain_row_type<MatrixType>::type m_workspace; -}; - -/*** 2x2 SVD implementation - *** - *** JacobiSVD consists in performing a series of 2x2 SVD subproblems - ***/ - -template<typename MatrixType, int QRPreconditioner> -struct svd_precondition_2x2_block_to_be_real<MatrixType, QRPreconditioner, false> -{ - typedef JacobiSVD<MatrixType, QRPreconditioner> SVD; - typedef typename SVD::Index Index; - static void run(typename SVD::WorkMatrixType&, SVD&, Index, Index) {} -}; - -template<typename MatrixType, int QRPreconditioner> -struct svd_precondition_2x2_block_to_be_real<MatrixType, QRPreconditioner, true> -{ - typedef JacobiSVD<MatrixType, QRPreconditioner> SVD; - typedef typename MatrixType::Scalar Scalar; - typedef typename MatrixType::RealScalar RealScalar; - typedef typename SVD::Index Index; - static void run(typename SVD::WorkMatrixType& work_matrix, SVD& svd, Index p, Index q) - { - using std::sqrt; - Scalar z; - JacobiRotation<Scalar> rot; - RealScalar n = sqrt(numext::abs2(work_matrix.coeff(p,p)) + numext::abs2(work_matrix.coeff(q,p))); - if(n==0) - { - z = abs(work_matrix.coeff(p,q)) / work_matrix.coeff(p,q); - work_matrix.row(p) *= z; - if(svd.computeU()) svd.m_matrixU.col(p) *= conj(z); - z = abs(work_matrix.coeff(q,q)) / work_matrix.coeff(q,q); - work_matrix.row(q) *= z; - if(svd.computeU()) svd.m_matrixU.col(q) *= conj(z); - } - else - { - rot.c() = conj(work_matrix.coeff(p,p)) / n; - rot.s() = work_matrix.coeff(q,p) / n; - work_matrix.applyOnTheLeft(p,q,rot); - if(svd.computeU()) svd.m_matrixU.applyOnTheRight(p,q,rot.adjoint()); - if(work_matrix.coeff(p,q) != Scalar(0)) - { - Scalar z = abs(work_matrix.coeff(p,q)) / work_matrix.coeff(p,q); - work_matrix.col(q) *= z; - if(svd.computeV()) svd.m_matrixV.col(q) *= z; - } - if(work_matrix.coeff(q,q) != Scalar(0)) - { - z = abs(work_matrix.coeff(q,q)) / work_matrix.coeff(q,q); - work_matrix.row(q) *= z; - if(svd.computeU()) svd.m_matrixU.col(q) *= conj(z); - } - } - } -}; - -template<typename MatrixType, typename RealScalar, typename Index> -void real_2x2_jacobi_svd(const MatrixType& matrix, Index p, Index q, - JacobiRotation<RealScalar> *j_left, - JacobiRotation<RealScalar> *j_right) -{ - using std::sqrt; - Matrix<RealScalar,2,2> m; - m << numext::real(matrix.coeff(p,p)), numext::real(matrix.coeff(p,q)), - numext::real(matrix.coeff(q,p)), numext::real(matrix.coeff(q,q)); - JacobiRotation<RealScalar> rot1; - RealScalar t = m.coeff(0,0) + m.coeff(1,1); - RealScalar d = m.coeff(1,0) - m.coeff(0,1); - if(t == RealScalar(0)) - { - rot1.c() = RealScalar(0); - rot1.s() = d > RealScalar(0) ? RealScalar(1) : RealScalar(-1); - } - else - { - RealScalar u = d / t; - rot1.c() = RealScalar(1) / sqrt(RealScalar(1) + numext::abs2(u)); - rot1.s() = rot1.c() * u; - } - m.applyOnTheLeft(0,1,rot1); - j_right->makeJacobi(m,0,1); - *j_left = rot1 * j_right->transpose(); -} - -} // end namespace internal - -/** \ingroup SVD_Module - * - * - * \class JacobiSVD - * - * \brief Two-sided Jacobi SVD decomposition of a rectangular matrix - * - * \param MatrixType the type of the matrix of which we are computing the SVD decomposition - * \param QRPreconditioner this optional parameter allows to specify the type of QR decomposition that will be used internally - * for the R-SVD step for non-square matrices. See discussion of possible values below. - * - * SVD decomposition consists in decomposing any n-by-p matrix \a A as a product - * \f[ A = U S V^* \f] - * where \a U is a n-by-n unitary, \a V is a p-by-p unitary, and \a S is a n-by-p real positive matrix which is zero outside of its main diagonal; - * the diagonal entries of S are known as the \em singular \em values of \a A and the columns of \a U and \a V are known as the left - * and right \em singular \em vectors of \a A respectively. - * - * Singular values are always sorted in decreasing order. - * - * This JacobiSVD decomposition computes only the singular values by default. If you want \a U or \a V, you need to ask for them explicitly. - * - * You can ask for only \em thin \a U or \a V to be computed, meaning the following. In case of a rectangular n-by-p matrix, letting \a m be the - * smaller value among \a n and \a p, there are only \a m singular vectors; the remaining columns of \a U and \a V do not correspond to actual - * singular vectors. Asking for \em thin \a U or \a V means asking for only their \a m first columns to be formed. So \a U is then a n-by-m matrix, - * and \a V is then a p-by-m matrix. Notice that thin \a U and \a V are all you need for (least squares) solving. - * - * Here's an example demonstrating basic usage: - * \include JacobiSVD_basic.cpp - * Output: \verbinclude JacobiSVD_basic.out - * - * This JacobiSVD class is a two-sided Jacobi R-SVD decomposition, ensuring optimal reliability and accuracy. The downside is that it's slower than - * bidiagonalizing SVD algorithms for large square matrices; however its complexity is still \f$ O(n^2p) \f$ where \a n is the smaller dimension and - * \a p is the greater dimension, meaning that it is still of the same order of complexity as the faster bidiagonalizing R-SVD algorithms. - * In particular, like any R-SVD, it takes advantage of non-squareness in that its complexity is only linear in the greater dimension. - * - * If the input matrix has inf or nan coefficients, the result of the computation is undefined, but the computation is guaranteed to - * terminate in finite (and reasonable) time. - * - * The possible values for QRPreconditioner are: - * \li ColPivHouseholderQRPreconditioner is the default. In practice it's very safe. It uses column-pivoting QR. - * \li FullPivHouseholderQRPreconditioner, is the safest and slowest. It uses full-pivoting QR. - * Contrary to other QRs, it doesn't allow computing thin unitaries. - * \li HouseholderQRPreconditioner is the fastest, and less safe and accurate than the pivoting variants. It uses non-pivoting QR. - * This is very similar in safety and accuracy to the bidiagonalization process used by bidiagonalizing SVD algorithms (since bidiagonalization - * is inherently non-pivoting). However the resulting SVD is still more reliable than bidiagonalizing SVDs because the Jacobi-based iterarive - * process is more reliable than the optimized bidiagonal SVD iterations. - * \li NoQRPreconditioner allows not to use a QR preconditioner at all. This is useful if you know that you will only be computing - * JacobiSVD decompositions of square matrices. Non-square matrices require a QR preconditioner. Using this option will result in - * faster compilation and smaller executable code. It won't significantly speed up computation, since JacobiSVD is always checking - * if QR preconditioning is needed before applying it anyway. - * - * \sa MatrixBase::jacobiSvd() - */ -template<typename _MatrixType, int QRPreconditioner> -class JacobiSVD : public SVDBase<_MatrixType> -{ - public: - - typedef _MatrixType MatrixType; - typedef typename MatrixType::Scalar Scalar; - typedef typename NumTraits<typename MatrixType::Scalar>::Real RealScalar; - typedef typename MatrixType::Index Index; - enum { - RowsAtCompileTime = MatrixType::RowsAtCompileTime, - ColsAtCompileTime = MatrixType::ColsAtCompileTime, - DiagSizeAtCompileTime = EIGEN_SIZE_MIN_PREFER_DYNAMIC(RowsAtCompileTime,ColsAtCompileTime), - MaxRowsAtCompileTime = MatrixType::MaxRowsAtCompileTime, - MaxColsAtCompileTime = MatrixType::MaxColsAtCompileTime, - MaxDiagSizeAtCompileTime = EIGEN_SIZE_MIN_PREFER_FIXED(MaxRowsAtCompileTime,MaxColsAtCompileTime), - MatrixOptions = MatrixType::Options - }; - - typedef Matrix<Scalar, RowsAtCompileTime, RowsAtCompileTime, - MatrixOptions, MaxRowsAtCompileTime, MaxRowsAtCompileTime> - MatrixUType; - typedef Matrix<Scalar, ColsAtCompileTime, ColsAtCompileTime, - MatrixOptions, MaxColsAtCompileTime, MaxColsAtCompileTime> - MatrixVType; - typedef typename internal::plain_diag_type<MatrixType, RealScalar>::type SingularValuesType; - typedef typename internal::plain_row_type<MatrixType>::type RowType; - typedef typename internal::plain_col_type<MatrixType>::type ColType; - typedef Matrix<Scalar, DiagSizeAtCompileTime, DiagSizeAtCompileTime, - MatrixOptions, MaxDiagSizeAtCompileTime, MaxDiagSizeAtCompileTime> - WorkMatrixType; - - /** \brief Default Constructor. - * - * The default constructor is useful in cases in which the user intends to - * perform decompositions via JacobiSVD::compute(const MatrixType&). - */ - JacobiSVD() - : SVDBase<_MatrixType>::SVDBase() - {} - - - /** \brief Default Constructor with memory preallocation - * - * Like the default constructor but with preallocation of the internal data - * according to the specified problem size. - * \sa JacobiSVD() - */ - JacobiSVD(Index rows, Index cols, unsigned int computationOptions = 0) - : SVDBase<_MatrixType>::SVDBase() - { - allocate(rows, cols, computationOptions); - } - - /** \brief Constructor performing the decomposition of given matrix. - * - * \param matrix the matrix to decompose - * \param computationOptions optional parameter allowing to specify if you want full or thin U or V unitaries to be computed. - * By default, none is computed. This is a bit-field, the possible bits are #ComputeFullU, #ComputeThinU, - * #ComputeFullV, #ComputeThinV. - * - * Thin unitaries are only available if your matrix type has a Dynamic number of columns (for example MatrixXf). They also are not - * available with the (non-default) FullPivHouseholderQR preconditioner. - */ - JacobiSVD(const MatrixType& matrix, unsigned int computationOptions = 0) - : SVDBase<_MatrixType>::SVDBase() - { - compute(matrix, computationOptions); - } - - /** \brief Method performing the decomposition of given matrix using custom options. - * - * \param matrix the matrix to decompose - * \param computationOptions optional parameter allowing to specify if you want full or thin U or V unitaries to be computed. - * By default, none is computed. This is a bit-field, the possible bits are #ComputeFullU, #ComputeThinU, - * #ComputeFullV, #ComputeThinV. - * - * Thin unitaries are only available if your matrix type has a Dynamic number of columns (for example MatrixXf). They also are not - * available with the (non-default) FullPivHouseholderQR preconditioner. - */ - SVDBase<MatrixType>& compute(const MatrixType& matrix, unsigned int computationOptions); - - /** \brief Method performing the decomposition of given matrix using current options. - * - * \param matrix the matrix to decompose - * - * This method uses the current \a computationOptions, as already passed to the constructor or to compute(const MatrixType&, unsigned int). - */ - SVDBase<MatrixType>& compute(const MatrixType& matrix) - { - return compute(matrix, this->m_computationOptions); - } - - /** \returns a (least squares) solution of \f$ A x = b \f$ using the current SVD decomposition of A. - * - * \param b the right-hand-side of the equation to solve. - * - * \note Solving requires both U and V to be computed. Thin U and V are enough, there is no need for full U or V. - * - * \note SVD solving is implicitly least-squares. Thus, this method serves both purposes of exact solving and least-squares solving. - * In other words, the returned solution is guaranteed to minimize the Euclidean norm \f$ \Vert A x - b \Vert \f$. - */ - template<typename Rhs> - inline const internal::solve_retval<JacobiSVD, Rhs> - solve(const MatrixBase<Rhs>& b) const - { - eigen_assert(this->m_isInitialized && "JacobiSVD is not initialized."); - eigen_assert(SVDBase<MatrixType>::computeU() && SVDBase<MatrixType>::computeV() && "JacobiSVD::solve() requires both unitaries U and V to be computed (thin unitaries suffice)."); - return internal::solve_retval<JacobiSVD, Rhs>(*this, b.derived()); - } - - - - private: - void allocate(Index rows, Index cols, unsigned int computationOptions); - - protected: - WorkMatrixType m_workMatrix; - - template<typename __MatrixType, int _QRPreconditioner, bool _IsComplex> - friend struct internal::svd_precondition_2x2_block_to_be_real; - template<typename __MatrixType, int _QRPreconditioner, int _Case, bool _DoAnything> - friend struct internal::qr_preconditioner_impl; - - internal::qr_preconditioner_impl<MatrixType, QRPreconditioner, internal::PreconditionIfMoreColsThanRows> m_qr_precond_morecols; - internal::qr_preconditioner_impl<MatrixType, QRPreconditioner, internal::PreconditionIfMoreRowsThanCols> m_qr_precond_morerows; -}; - -template<typename MatrixType, int QRPreconditioner> -void JacobiSVD<MatrixType, QRPreconditioner>::allocate(Index rows, Index cols, unsigned int computationOptions) -{ - if (SVDBase<MatrixType>::allocate(rows, cols, computationOptions)) return; - - if (QRPreconditioner == FullPivHouseholderQRPreconditioner) - { - eigen_assert(!(this->m_computeThinU || this->m_computeThinV) && - "JacobiSVD: can't compute thin U or thin V with the FullPivHouseholderQR preconditioner. " - "Use the ColPivHouseholderQR preconditioner instead."); - } - - m_workMatrix.resize(this->m_diagSize, this->m_diagSize); - - if(this->m_cols>this->m_rows) m_qr_precond_morecols.allocate(*this); - if(this->m_rows>this->m_cols) m_qr_precond_morerows.allocate(*this); -} - -template<typename MatrixType, int QRPreconditioner> -SVDBase<MatrixType>& -JacobiSVD<MatrixType, QRPreconditioner>::compute(const MatrixType& matrix, unsigned int computationOptions) -{ - using std::abs; - allocate(matrix.rows(), matrix.cols(), computationOptions); - - // currently we stop when we reach precision 2*epsilon as the last bit of precision can require an unreasonable number of iterations, - // only worsening the precision of U and V as we accumulate more rotations - const RealScalar precision = RealScalar(2) * NumTraits<Scalar>::epsilon(); - - // limit for very small denormal numbers to be considered zero in order to avoid infinite loops (see bug 286) - const RealScalar considerAsZero = RealScalar(2) * std::numeric_limits<RealScalar>::denorm_min(); - - /*** step 1. The R-SVD step: we use a QR decomposition to reduce to the case of a square matrix */ - - if(!m_qr_precond_morecols.run(*this, matrix) && !m_qr_precond_morerows.run(*this, matrix)) - { - m_workMatrix = matrix.block(0,0,this->m_diagSize,this->m_diagSize); - if(this->m_computeFullU) this->m_matrixU.setIdentity(this->m_rows,this->m_rows); - if(this->m_computeThinU) this->m_matrixU.setIdentity(this->m_rows,this->m_diagSize); - if(this->m_computeFullV) this->m_matrixV.setIdentity(this->m_cols,this->m_cols); - if(this->m_computeThinV) this->m_matrixV.setIdentity(this->m_cols, this->m_diagSize); - } - - /*** step 2. The main Jacobi SVD iteration. ***/ - - bool finished = false; - while(!finished) - { - finished = true; - - // do a sweep: for all index pairs (p,q), perform SVD of the corresponding 2x2 sub-matrix - - for(Index p = 1; p < this->m_diagSize; ++p) - { - for(Index q = 0; q < p; ++q) - { - // if this 2x2 sub-matrix is not diagonal already... - // notice that this comparison will evaluate to false if any NaN is involved, ensuring that NaN's don't - // keep us iterating forever. Similarly, small denormal numbers are considered zero. - using std::max; - RealScalar threshold = (max)(considerAsZero, precision * (max)(abs(m_workMatrix.coeff(p,p)), - abs(m_workMatrix.coeff(q,q)))); - if((max)(abs(m_workMatrix.coeff(p,q)),abs(m_workMatrix.coeff(q,p))) > threshold) - { - finished = false; - - // perform SVD decomposition of 2x2 sub-matrix corresponding to indices p,q to make it diagonal - internal::svd_precondition_2x2_block_to_be_real<MatrixType, QRPreconditioner>::run(m_workMatrix, *this, p, q); - JacobiRotation<RealScalar> j_left, j_right; - internal::real_2x2_jacobi_svd(m_workMatrix, p, q, &j_left, &j_right); - - // accumulate resulting Jacobi rotations - m_workMatrix.applyOnTheLeft(p,q,j_left); - if(SVDBase<MatrixType>::computeU()) this->m_matrixU.applyOnTheRight(p,q,j_left.transpose()); - - m_workMatrix.applyOnTheRight(p,q,j_right); - if(SVDBase<MatrixType>::computeV()) this->m_matrixV.applyOnTheRight(p,q,j_right); - } - } - } - } - - /*** step 3. The work matrix is now diagonal, so ensure it's positive so its diagonal entries are the singular values ***/ - - for(Index i = 0; i < this->m_diagSize; ++i) - { - RealScalar a = abs(m_workMatrix.coeff(i,i)); - this->m_singularValues.coeffRef(i) = a; - if(SVDBase<MatrixType>::computeU() && (a!=RealScalar(0))) this->m_matrixU.col(i) *= this->m_workMatrix.coeff(i,i)/a; - } - - /*** step 4. Sort singular values in descending order and compute the number of nonzero singular values ***/ - - this->m_nonzeroSingularValues = this->m_diagSize; - for(Index i = 0; i < this->m_diagSize; i++) - { - Index pos; - RealScalar maxRemainingSingularValue = this->m_singularValues.tail(this->m_diagSize-i).maxCoeff(&pos); - if(maxRemainingSingularValue == RealScalar(0)) - { - this->m_nonzeroSingularValues = i; - break; - } - if(pos) - { - pos += i; - std::swap(this->m_singularValues.coeffRef(i), this->m_singularValues.coeffRef(pos)); - if(SVDBase<MatrixType>::computeU()) this->m_matrixU.col(pos).swap(this->m_matrixU.col(i)); - if(SVDBase<MatrixType>::computeV()) this->m_matrixV.col(pos).swap(this->m_matrixV.col(i)); - } - } - - this->m_isInitialized = true; - return *this; -} - -namespace internal { -template<typename _MatrixType, int QRPreconditioner, typename Rhs> -struct solve_retval<JacobiSVD<_MatrixType, QRPreconditioner>, Rhs> - : solve_retval_base<JacobiSVD<_MatrixType, QRPreconditioner>, Rhs> -{ - typedef JacobiSVD<_MatrixType, QRPreconditioner> JacobiSVDType; - EIGEN_MAKE_SOLVE_HELPERS(JacobiSVDType,Rhs) - - template<typename Dest> void evalTo(Dest& dst) const - { - eigen_assert(rhs().rows() == dec().rows()); - - // A = U S V^* - // So A^{-1} = V S^{-1} U^* - - Index diagSize = (std::min)(dec().rows(), dec().cols()); - typename JacobiSVDType::SingularValuesType invertedSingVals(diagSize); - - Index nonzeroSingVals = dec().nonzeroSingularValues(); - invertedSingVals.head(nonzeroSingVals) = dec().singularValues().head(nonzeroSingVals).array().inverse(); - invertedSingVals.tail(diagSize - nonzeroSingVals).setZero(); - - dst = dec().matrixV().leftCols(diagSize) - * invertedSingVals.asDiagonal() - * dec().matrixU().leftCols(diagSize).adjoint() - * rhs(); - } -}; -} // end namespace internal - -/** \svd_module - * - * \return the singular value decomposition of \c *this computed by two-sided - * Jacobi transformations. - * - * \sa class JacobiSVD - */ -template<typename Derived> -JacobiSVD<typename MatrixBase<Derived>::PlainObject> -MatrixBase<Derived>::jacobiSvd(unsigned int computationOptions) const -{ - return JacobiSVD<PlainObject>(*this, computationOptions); -} - -} // end namespace Eigen - -#endif // EIGEN_JACOBISVD_H diff --git a/unsupported/Eigen/src/SVD/SVDBase.h b/unsupported/Eigen/src/SVD/SVDBase.h deleted file mode 100644 index fd8af3b8c..000000000 --- a/unsupported/Eigen/src/SVD/SVDBase.h +++ /dev/null @@ -1,236 +0,0 @@ -// This file is part of Eigen, a lightweight C++ template library -// for linear algebra. -// -// Copyright (C) 2009-2010 Benoit Jacob <jacob.benoit.1@gmail.com> -// -// Copyright (C) 2013 Gauthier Brun <brun.gauthier@gmail.com> -// Copyright (C) 2013 Nicolas Carre <nicolas.carre@ensimag.fr> -// Copyright (C) 2013 Jean Ceccato <jean.ceccato@ensimag.fr> -// Copyright (C) 2013 Pierre Zoppitelli <pierre.zoppitelli@ensimag.fr> -// -// 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_SVD_H -#define EIGEN_SVD_H - -namespace Eigen { -/** \ingroup SVD_Module - * - * - * \class SVDBase - * - * \brief Mother class of SVD classes algorithms - * - * \param MatrixType the type of the matrix of which we are computing the SVD decomposition - * SVD decomposition consists in decomposing any n-by-p matrix \a A as a product - * \f[ A = U S V^* \f] - * where \a U is a n-by-n unitary, \a V is a p-by-p unitary, and \a S is a n-by-p real positive matrix which is zero outside of its main diagonal; - * the diagonal entries of S are known as the \em singular \em values of \a A and the columns of \a U and \a V are known as the left - * and right \em singular \em vectors of \a A respectively. - * - * Singular values are always sorted in decreasing order. - * - * - * You can ask for only \em thin \a U or \a V to be computed, meaning the following. In case of a rectangular n-by-p matrix, letting \a m be the - * smaller value among \a n and \a p, there are only \a m singular vectors; the remaining columns of \a U and \a V do not correspond to actual - * singular vectors. Asking for \em thin \a U or \a V means asking for only their \a m first columns to be formed. So \a U is then a n-by-m matrix, - * and \a V is then a p-by-m matrix. Notice that thin \a U and \a V are all you need for (least squares) solving. - * - * If the input matrix has inf or nan coefficients, the result of the computation is undefined, but the computation is guaranteed to - * terminate in finite (and reasonable) time. - * \sa MatrixBase::genericSvd() - */ -template<typename _MatrixType> -class SVDBase -{ - -public: - typedef _MatrixType MatrixType; - typedef typename MatrixType::Scalar Scalar; - typedef typename NumTraits<typename MatrixType::Scalar>::Real RealScalar; - typedef typename MatrixType::Index Index; - enum { - RowsAtCompileTime = MatrixType::RowsAtCompileTime, - ColsAtCompileTime = MatrixType::ColsAtCompileTime, - DiagSizeAtCompileTime = EIGEN_SIZE_MIN_PREFER_DYNAMIC(RowsAtCompileTime,ColsAtCompileTime), - MaxRowsAtCompileTime = MatrixType::MaxRowsAtCompileTime, - MaxColsAtCompileTime = MatrixType::MaxColsAtCompileTime, - MaxDiagSizeAtCompileTime = EIGEN_SIZE_MIN_PREFER_FIXED(MaxRowsAtCompileTime,MaxColsAtCompileTime), - MatrixOptions = MatrixType::Options - }; - - typedef Matrix<Scalar, RowsAtCompileTime, RowsAtCompileTime, - MatrixOptions, MaxRowsAtCompileTime, MaxRowsAtCompileTime> - MatrixUType; - typedef Matrix<Scalar, ColsAtCompileTime, ColsAtCompileTime, - MatrixOptions, MaxColsAtCompileTime, MaxColsAtCompileTime> - MatrixVType; - typedef typename internal::plain_diag_type<MatrixType, RealScalar>::type SingularValuesType; - typedef typename internal::plain_row_type<MatrixType>::type RowType; - typedef typename internal::plain_col_type<MatrixType>::type ColType; - typedef Matrix<Scalar, DiagSizeAtCompileTime, DiagSizeAtCompileTime, - MatrixOptions, MaxDiagSizeAtCompileTime, MaxDiagSizeAtCompileTime> - WorkMatrixType; - - - - - /** \brief Method performing the decomposition of given matrix using custom options. - * - * \param matrix the matrix to decompose - * \param computationOptions optional parameter allowing to specify if you want full or thin U or V unitaries to be computed. - * By default, none is computed. This is a bit-field, the possible bits are #ComputeFullU, #ComputeThinU, - * #ComputeFullV, #ComputeThinV. - * - * Thin unitaries are only available if your matrix type has a Dynamic number of columns (for example MatrixXf). They also are not - * available with the (non-default) FullPivHouseholderQR preconditioner. - */ - SVDBase& compute(const MatrixType& matrix, unsigned int computationOptions); - - /** \brief Method performing the decomposition of given matrix using current options. - * - * \param matrix the matrix to decompose - * - * This method uses the current \a computationOptions, as already passed to the constructor or to compute(const MatrixType&, unsigned int). - */ - //virtual SVDBase& compute(const MatrixType& matrix) = 0; - SVDBase& compute(const MatrixType& matrix); - - /** \returns the \a U matrix. - * - * For the SVDBase decomposition of a n-by-p matrix, letting \a m be the minimum of \a n and \a p, - * the U matrix is n-by-n if you asked for #ComputeFullU, and is n-by-m if you asked for #ComputeThinU. - * - * The \a m first columns of \a U are the left singular vectors of the matrix being decomposed. - * - * This method asserts that you asked for \a U to be computed. - */ - const MatrixUType& matrixU() const - { - eigen_assert(m_isInitialized && "SVD is not initialized."); - eigen_assert(computeU() && "This SVD decomposition didn't compute U. Did you ask for it?"); - return m_matrixU; - } - - /** \returns the \a V matrix. - * - * For the SVD decomposition of a n-by-p matrix, letting \a m be the minimum of \a n and \a p, - * the V matrix is p-by-p if you asked for #ComputeFullV, and is p-by-m if you asked for ComputeThinV. - * - * The \a m first columns of \a V are the right singular vectors of the matrix being decomposed. - * - * This method asserts that you asked for \a V to be computed. - */ - const MatrixVType& matrixV() const - { - eigen_assert(m_isInitialized && "SVD is not initialized."); - eigen_assert(computeV() && "This SVD decomposition didn't compute V. Did you ask for it?"); - return m_matrixV; - } - - /** \returns the vector of singular values. - * - * For the SVD decomposition of a n-by-p matrix, letting \a m be the minimum of \a n and \a p, the - * returned vector has size \a m. Singular values are always sorted in decreasing order. - */ - const SingularValuesType& singularValues() const - { - eigen_assert(m_isInitialized && "SVD is not initialized."); - return m_singularValues; - } - - - - /** \returns the number of singular values that are not exactly 0 */ - Index nonzeroSingularValues() const - { - eigen_assert(m_isInitialized && "SVD is not initialized."); - return m_nonzeroSingularValues; - } - - - /** \returns true if \a U (full or thin) is asked for in this SVD decomposition */ - inline bool computeU() const { return m_computeFullU || m_computeThinU; } - /** \returns true if \a V (full or thin) is asked for in this SVD decomposition */ - inline bool computeV() const { return m_computeFullV || m_computeThinV; } - - - inline Index rows() const { return m_rows; } - inline Index cols() const { return m_cols; } - - -protected: - // return true if already allocated - bool allocate(Index rows, Index cols, unsigned int computationOptions) ; - - MatrixUType m_matrixU; - MatrixVType m_matrixV; - SingularValuesType m_singularValues; - bool m_isInitialized, m_isAllocated; - bool m_computeFullU, m_computeThinU; - bool m_computeFullV, m_computeThinV; - unsigned int m_computationOptions; - Index m_nonzeroSingularValues, m_rows, m_cols, m_diagSize; - - - /** \brief Default Constructor. - * - * Default constructor of SVDBase - */ - SVDBase() - : m_isInitialized(false), - m_isAllocated(false), - m_computationOptions(0), - m_rows(-1), m_cols(-1) - {} - - -}; - - -template<typename MatrixType> -bool SVDBase<MatrixType>::allocate(Index rows, Index cols, unsigned int computationOptions) -{ - eigen_assert(rows >= 0 && cols >= 0); - - if (m_isAllocated && - rows == m_rows && - cols == m_cols && - computationOptions == m_computationOptions) - { - return true; - } - - m_rows = rows; - m_cols = cols; - m_isInitialized = false; - m_isAllocated = true; - m_computationOptions = computationOptions; - m_computeFullU = (computationOptions & ComputeFullU) != 0; - m_computeThinU = (computationOptions & ComputeThinU) != 0; - m_computeFullV = (computationOptions & ComputeFullV) != 0; - m_computeThinV = (computationOptions & ComputeThinV) != 0; - eigen_assert(!(m_computeFullU && m_computeThinU) && "SVDBase: you can't ask for both full and thin U"); - eigen_assert(!(m_computeFullV && m_computeThinV) && "SVDBase: you can't ask for both full and thin V"); - eigen_assert(EIGEN_IMPLIES(m_computeThinU || m_computeThinV, MatrixType::ColsAtCompileTime==Dynamic) && - "SVDBase: thin U and V are only available when your matrix has a dynamic number of columns."); - - m_diagSize = (std::min)(m_rows, m_cols); - m_singularValues.resize(m_diagSize); - if(RowsAtCompileTime==Dynamic) - m_matrixU.resize(m_rows, m_computeFullU ? m_rows - : m_computeThinU ? m_diagSize - : 0); - if(ColsAtCompileTime==Dynamic) - m_matrixV.resize(m_cols, m_computeFullV ? m_cols - : m_computeThinV ? m_diagSize - : 0); - - return false; -} - -}// end namespace - -#endif // EIGEN_SVD_H diff --git a/unsupported/Eigen/src/SparseExtra/DynamicSparseMatrix.h b/unsupported/Eigen/src/SparseExtra/DynamicSparseMatrix.h index dec16df28..e4dc1c1de 100644 --- a/unsupported/Eigen/src/SparseExtra/DynamicSparseMatrix.h +++ b/unsupported/Eigen/src/SparseExtra/DynamicSparseMatrix.h @@ -352,6 +352,36 @@ class DynamicSparseMatrix<Scalar,_Options,_Index>::ReverseInnerIterator : public const Index m_outer; }; +namespace internal { + +template<typename _Scalar, int _Options, typename _Index> +struct evaluator<DynamicSparseMatrix<_Scalar,_Options,_Index> > + : evaluator_base<DynamicSparseMatrix<_Scalar,_Options,_Index> > +{ + typedef _Scalar Scalar; + typedef _Index Index; + typedef DynamicSparseMatrix<_Scalar,_Options,_Index> SparseMatrixType; + typedef typename SparseMatrixType::InnerIterator InnerIterator; + typedef typename SparseMatrixType::ReverseInnerIterator ReverseInnerIterator; + + enum { + CoeffReadCost = NumTraits<_Scalar>::ReadCost, + Flags = SparseMatrixType::Flags + }; + + evaluator() : m_matrix(0) {} + evaluator(const SparseMatrixType &mat) : m_matrix(&mat) {} + + operator SparseMatrixType&() { return m_matrix->const_cast_derived(); } + operator const SparseMatrixType&() const { return *m_matrix; } + + Scalar coeff(Index row, Index col) const { return m_matrix->coeff(row,col); } + + const SparseMatrixType *m_matrix; +}; + +} + } // end namespace Eigen #endif // EIGEN_DYNAMIC_SPARSEMATRIX_H |