1*bf2c3715SXin Li // This file is part of Eigen, a lightweight C++ template library 2*bf2c3715SXin Li // for linear algebra. 3*bf2c3715SXin Li // 4*bf2c3715SXin Li // Copyright (C) 2016 Rasmus Munk Larsen <[email protected]> 5*bf2c3715SXin Li // 6*bf2c3715SXin Li // This Source Code Form is subject to the terms of the Mozilla 7*bf2c3715SXin Li // Public License v. 2.0. If a copy of the MPL was not distributed 8*bf2c3715SXin Li // with this file, You can obtain one at http://mozilla.org/MPL/2.0/. 9*bf2c3715SXin Li 10*bf2c3715SXin Li #ifndef EIGEN_COMPLETEORTHOGONALDECOMPOSITION_H 11*bf2c3715SXin Li #define EIGEN_COMPLETEORTHOGONALDECOMPOSITION_H 12*bf2c3715SXin Li 13*bf2c3715SXin Li namespace Eigen { 14*bf2c3715SXin Li 15*bf2c3715SXin Li namespace internal { 16*bf2c3715SXin Li template <typename _MatrixType> 17*bf2c3715SXin Li struct traits<CompleteOrthogonalDecomposition<_MatrixType> > 18*bf2c3715SXin Li : traits<_MatrixType> { 19*bf2c3715SXin Li typedef MatrixXpr XprKind; 20*bf2c3715SXin Li typedef SolverStorage StorageKind; 21*bf2c3715SXin Li typedef int StorageIndex; 22*bf2c3715SXin Li enum { Flags = 0 }; 23*bf2c3715SXin Li }; 24*bf2c3715SXin Li 25*bf2c3715SXin Li } // end namespace internal 26*bf2c3715SXin Li 27*bf2c3715SXin Li /** \ingroup QR_Module 28*bf2c3715SXin Li * 29*bf2c3715SXin Li * \class CompleteOrthogonalDecomposition 30*bf2c3715SXin Li * 31*bf2c3715SXin Li * \brief Complete orthogonal decomposition (COD) of a matrix. 32*bf2c3715SXin Li * 33*bf2c3715SXin Li * \param MatrixType the type of the matrix of which we are computing the COD. 34*bf2c3715SXin Li * 35*bf2c3715SXin Li * This class performs a rank-revealing complete orthogonal decomposition of a 36*bf2c3715SXin Li * matrix \b A into matrices \b P, \b Q, \b T, and \b Z such that 37*bf2c3715SXin Li * \f[ 38*bf2c3715SXin Li * \mathbf{A} \, \mathbf{P} = \mathbf{Q} \, 39*bf2c3715SXin Li * \begin{bmatrix} \mathbf{T} & \mathbf{0} \\ 40*bf2c3715SXin Li * \mathbf{0} & \mathbf{0} \end{bmatrix} \, \mathbf{Z} 41*bf2c3715SXin Li * \f] 42*bf2c3715SXin Li * by using Householder transformations. Here, \b P is a permutation matrix, 43*bf2c3715SXin Li * \b Q and \b Z are unitary matrices and \b T an upper triangular matrix of 44*bf2c3715SXin Li * size rank-by-rank. \b A may be rank deficient. 45*bf2c3715SXin Li * 46*bf2c3715SXin Li * This class supports the \link InplaceDecomposition inplace decomposition \endlink mechanism. 47*bf2c3715SXin Li * 48*bf2c3715SXin Li * \sa MatrixBase::completeOrthogonalDecomposition() 49*bf2c3715SXin Li */ 50*bf2c3715SXin Li template <typename _MatrixType> class CompleteOrthogonalDecomposition 51*bf2c3715SXin Li : public SolverBase<CompleteOrthogonalDecomposition<_MatrixType> > 52*bf2c3715SXin Li { 53*bf2c3715SXin Li public: 54*bf2c3715SXin Li typedef _MatrixType MatrixType; 55*bf2c3715SXin Li typedef SolverBase<CompleteOrthogonalDecomposition> Base; 56*bf2c3715SXin Li 57*bf2c3715SXin Li template<typename Derived> 58*bf2c3715SXin Li friend struct internal::solve_assertion; 59*bf2c3715SXin Li 60*bf2c3715SXin Li EIGEN_GENERIC_PUBLIC_INTERFACE(CompleteOrthogonalDecomposition) 61*bf2c3715SXin Li enum { 62*bf2c3715SXin Li MaxRowsAtCompileTime = MatrixType::MaxRowsAtCompileTime, 63*bf2c3715SXin Li MaxColsAtCompileTime = MatrixType::MaxColsAtCompileTime 64*bf2c3715SXin Li }; 65*bf2c3715SXin Li typedef typename internal::plain_diag_type<MatrixType>::type HCoeffsType; 66*bf2c3715SXin Li typedef PermutationMatrix<ColsAtCompileTime, MaxColsAtCompileTime> 67*bf2c3715SXin Li PermutationType; 68*bf2c3715SXin Li typedef typename internal::plain_row_type<MatrixType, Index>::type 69*bf2c3715SXin Li IntRowVectorType; 70*bf2c3715SXin Li typedef typename internal::plain_row_type<MatrixType>::type RowVectorType; 71*bf2c3715SXin Li typedef typename internal::plain_row_type<MatrixType, RealScalar>::type 72*bf2c3715SXin Li RealRowVectorType; 73*bf2c3715SXin Li typedef HouseholderSequence< 74*bf2c3715SXin Li MatrixType, typename internal::remove_all< 75*bf2c3715SXin Li typename HCoeffsType::ConjugateReturnType>::type> 76*bf2c3715SXin Li HouseholderSequenceType; 77*bf2c3715SXin Li typedef typename MatrixType::PlainObject PlainObject; 78*bf2c3715SXin Li 79*bf2c3715SXin Li private: 80*bf2c3715SXin Li typedef typename PermutationType::Index PermIndexType; 81*bf2c3715SXin Li 82*bf2c3715SXin Li public: 83*bf2c3715SXin Li /** 84*bf2c3715SXin Li * \brief Default Constructor. 85*bf2c3715SXin Li * 86*bf2c3715SXin Li * The default constructor is useful in cases in which the user intends to 87*bf2c3715SXin Li * perform decompositions via 88*bf2c3715SXin Li * \c CompleteOrthogonalDecomposition::compute(const* MatrixType&). 89*bf2c3715SXin Li */ 90*bf2c3715SXin Li CompleteOrthogonalDecomposition() : m_cpqr(), m_zCoeffs(), m_temp() {} 91*bf2c3715SXin Li 92*bf2c3715SXin Li /** \brief Default Constructor with memory preallocation 93*bf2c3715SXin Li * 94*bf2c3715SXin Li * Like the default constructor but with preallocation of the internal data 95*bf2c3715SXin Li * according to the specified problem \a size. 96*bf2c3715SXin Li * \sa CompleteOrthogonalDecomposition() 97*bf2c3715SXin Li */ 98*bf2c3715SXin Li CompleteOrthogonalDecomposition(Index rows, Index cols) 99*bf2c3715SXin Li : m_cpqr(rows, cols), m_zCoeffs((std::min)(rows, cols)), m_temp(cols) {} 100*bf2c3715SXin Li 101*bf2c3715SXin Li /** \brief Constructs a complete orthogonal decomposition from a given 102*bf2c3715SXin Li * matrix. 103*bf2c3715SXin Li * 104*bf2c3715SXin Li * This constructor computes the complete orthogonal decomposition of the 105*bf2c3715SXin Li * matrix \a matrix by calling the method compute(). The default 106*bf2c3715SXin Li * threshold for rank determination will be used. It is a short cut for: 107*bf2c3715SXin Li * 108*bf2c3715SXin Li * \code 109*bf2c3715SXin Li * CompleteOrthogonalDecomposition<MatrixType> cod(matrix.rows(), 110*bf2c3715SXin Li * matrix.cols()); 111*bf2c3715SXin Li * cod.setThreshold(Default); 112*bf2c3715SXin Li * cod.compute(matrix); 113*bf2c3715SXin Li * \endcode 114*bf2c3715SXin Li * 115*bf2c3715SXin Li * \sa compute() 116*bf2c3715SXin Li */ 117*bf2c3715SXin Li template <typename InputType> 118*bf2c3715SXin Li explicit CompleteOrthogonalDecomposition(const EigenBase<InputType>& matrix) 119*bf2c3715SXin Li : m_cpqr(matrix.rows(), matrix.cols()), 120*bf2c3715SXin Li m_zCoeffs((std::min)(matrix.rows(), matrix.cols())), 121*bf2c3715SXin Li m_temp(matrix.cols()) 122*bf2c3715SXin Li { 123*bf2c3715SXin Li compute(matrix.derived()); 124*bf2c3715SXin Li } 125*bf2c3715SXin Li 126*bf2c3715SXin Li /** \brief Constructs a complete orthogonal decomposition from a given matrix 127*bf2c3715SXin Li * 128*bf2c3715SXin Li * This overloaded constructor is provided for \link InplaceDecomposition inplace decomposition \endlink when \c MatrixType is a Eigen::Ref. 129*bf2c3715SXin Li * 130*bf2c3715SXin Li * \sa CompleteOrthogonalDecomposition(const EigenBase&) 131*bf2c3715SXin Li */ 132*bf2c3715SXin Li template<typename InputType> 133*bf2c3715SXin Li explicit CompleteOrthogonalDecomposition(EigenBase<InputType>& matrix) 134*bf2c3715SXin Li : m_cpqr(matrix.derived()), 135*bf2c3715SXin Li m_zCoeffs((std::min)(matrix.rows(), matrix.cols())), 136*bf2c3715SXin Li m_temp(matrix.cols()) 137*bf2c3715SXin Li { 138*bf2c3715SXin Li computeInPlace(); 139*bf2c3715SXin Li } 140*bf2c3715SXin Li 141*bf2c3715SXin Li #ifdef EIGEN_PARSED_BY_DOXYGEN 142*bf2c3715SXin Li /** This method computes the minimum-norm solution X to a least squares 143*bf2c3715SXin Li * problem \f[\mathrm{minimize} \|A X - B\|, \f] where \b A is the matrix of 144*bf2c3715SXin Li * which \c *this is the complete orthogonal decomposition. 145*bf2c3715SXin Li * 146*bf2c3715SXin Li * \param b the right-hand sides of the problem to solve. 147*bf2c3715SXin Li * 148*bf2c3715SXin Li * \returns a solution. 149*bf2c3715SXin Li * 150*bf2c3715SXin Li */ 151*bf2c3715SXin Li template <typename Rhs> 152*bf2c3715SXin Li inline const Solve<CompleteOrthogonalDecomposition, Rhs> solve( 153*bf2c3715SXin Li const MatrixBase<Rhs>& b) const; 154*bf2c3715SXin Li #endif 155*bf2c3715SXin Li 156*bf2c3715SXin Li HouseholderSequenceType householderQ(void) const; 157*bf2c3715SXin Li HouseholderSequenceType matrixQ(void) const { return m_cpqr.householderQ(); } 158*bf2c3715SXin Li 159*bf2c3715SXin Li /** \returns the matrix \b Z. 160*bf2c3715SXin Li */ 161*bf2c3715SXin Li MatrixType matrixZ() const { 162*bf2c3715SXin Li MatrixType Z = MatrixType::Identity(m_cpqr.cols(), m_cpqr.cols()); 163*bf2c3715SXin Li applyZOnTheLeftInPlace<false>(Z); 164*bf2c3715SXin Li return Z; 165*bf2c3715SXin Li } 166*bf2c3715SXin Li 167*bf2c3715SXin Li /** \returns a reference to the matrix where the complete orthogonal 168*bf2c3715SXin Li * decomposition is stored 169*bf2c3715SXin Li */ 170*bf2c3715SXin Li const MatrixType& matrixQTZ() const { return m_cpqr.matrixQR(); } 171*bf2c3715SXin Li 172*bf2c3715SXin Li /** \returns a reference to the matrix where the complete orthogonal 173*bf2c3715SXin Li * decomposition is stored. 174*bf2c3715SXin Li * \warning The strict lower part and \code cols() - rank() \endcode right 175*bf2c3715SXin Li * columns of this matrix contains internal values. 176*bf2c3715SXin Li * Only the upper triangular part should be referenced. To get it, use 177*bf2c3715SXin Li * \code matrixT().template triangularView<Upper>() \endcode 178*bf2c3715SXin Li * For rank-deficient matrices, use 179*bf2c3715SXin Li * \code 180*bf2c3715SXin Li * matrixR().topLeftCorner(rank(), rank()).template triangularView<Upper>() 181*bf2c3715SXin Li * \endcode 182*bf2c3715SXin Li */ 183*bf2c3715SXin Li const MatrixType& matrixT() const { return m_cpqr.matrixQR(); } 184*bf2c3715SXin Li 185*bf2c3715SXin Li template <typename InputType> 186*bf2c3715SXin Li CompleteOrthogonalDecomposition& compute(const EigenBase<InputType>& matrix) { 187*bf2c3715SXin Li // Compute the column pivoted QR factorization A P = Q R. 188*bf2c3715SXin Li m_cpqr.compute(matrix); 189*bf2c3715SXin Li computeInPlace(); 190*bf2c3715SXin Li return *this; 191*bf2c3715SXin Li } 192*bf2c3715SXin Li 193*bf2c3715SXin Li /** \returns a const reference to the column permutation matrix */ 194*bf2c3715SXin Li const PermutationType& colsPermutation() const { 195*bf2c3715SXin Li return m_cpqr.colsPermutation(); 196*bf2c3715SXin Li } 197*bf2c3715SXin Li 198*bf2c3715SXin Li /** \returns the absolute value of the determinant of the matrix of which 199*bf2c3715SXin Li * *this is the complete orthogonal decomposition. It has only linear 200*bf2c3715SXin Li * complexity (that is, O(n) where n is the dimension of the square matrix) 201*bf2c3715SXin Li * as the complete orthogonal decomposition has already been computed. 202*bf2c3715SXin Li * 203*bf2c3715SXin Li * \note This is only for square matrices. 204*bf2c3715SXin Li * 205*bf2c3715SXin Li * \warning a determinant can be very big or small, so for matrices 206*bf2c3715SXin Li * of large enough dimension, there is a risk of overflow/underflow. 207*bf2c3715SXin Li * One way to work around that is to use logAbsDeterminant() instead. 208*bf2c3715SXin Li * 209*bf2c3715SXin Li * \sa logAbsDeterminant(), MatrixBase::determinant() 210*bf2c3715SXin Li */ 211*bf2c3715SXin Li typename MatrixType::RealScalar absDeterminant() const; 212*bf2c3715SXin Li 213*bf2c3715SXin Li /** \returns the natural log of the absolute value of the determinant of the 214*bf2c3715SXin Li * matrix of which *this is the complete orthogonal decomposition. It has 215*bf2c3715SXin Li * only linear complexity (that is, O(n) where n is the dimension of the 216*bf2c3715SXin Li * square matrix) as the complete orthogonal decomposition has already been 217*bf2c3715SXin Li * computed. 218*bf2c3715SXin Li * 219*bf2c3715SXin Li * \note This is only for square matrices. 220*bf2c3715SXin Li * 221*bf2c3715SXin Li * \note This method is useful to work around the risk of overflow/underflow 222*bf2c3715SXin Li * that's inherent to determinant computation. 223*bf2c3715SXin Li * 224*bf2c3715SXin Li * \sa absDeterminant(), MatrixBase::determinant() 225*bf2c3715SXin Li */ 226*bf2c3715SXin Li typename MatrixType::RealScalar logAbsDeterminant() const; 227*bf2c3715SXin Li 228*bf2c3715SXin Li /** \returns the rank of the matrix of which *this is the complete orthogonal 229*bf2c3715SXin Li * decomposition. 230*bf2c3715SXin Li * 231*bf2c3715SXin Li * \note This method has to determine which pivots should be considered 232*bf2c3715SXin Li * nonzero. For that, it uses the threshold value that you can control by 233*bf2c3715SXin Li * calling setThreshold(const RealScalar&). 234*bf2c3715SXin Li */ 235*bf2c3715SXin Li inline Index rank() const { return m_cpqr.rank(); } 236*bf2c3715SXin Li 237*bf2c3715SXin Li /** \returns the dimension of the kernel of the matrix of which *this is the 238*bf2c3715SXin Li * complete orthogonal decomposition. 239*bf2c3715SXin Li * 240*bf2c3715SXin Li * \note This method has to determine which pivots should be considered 241*bf2c3715SXin Li * nonzero. For that, it uses the threshold value that you can control by 242*bf2c3715SXin Li * calling setThreshold(const RealScalar&). 243*bf2c3715SXin Li */ 244*bf2c3715SXin Li inline Index dimensionOfKernel() const { return m_cpqr.dimensionOfKernel(); } 245*bf2c3715SXin Li 246*bf2c3715SXin Li /** \returns true if the matrix of which *this is the decomposition represents 247*bf2c3715SXin Li * an injective linear map, i.e. has trivial kernel; false otherwise. 248*bf2c3715SXin Li * 249*bf2c3715SXin Li * \note This method has to determine which pivots should be considered 250*bf2c3715SXin Li * nonzero. For that, it uses the threshold value that you can control by 251*bf2c3715SXin Li * calling setThreshold(const RealScalar&). 252*bf2c3715SXin Li */ 253*bf2c3715SXin Li inline bool isInjective() const { return m_cpqr.isInjective(); } 254*bf2c3715SXin Li 255*bf2c3715SXin Li /** \returns true if the matrix of which *this is the decomposition represents 256*bf2c3715SXin Li * a surjective linear map; false otherwise. 257*bf2c3715SXin Li * 258*bf2c3715SXin Li * \note This method has to determine which pivots should be considered 259*bf2c3715SXin Li * nonzero. For that, it uses the threshold value that you can control by 260*bf2c3715SXin Li * calling setThreshold(const RealScalar&). 261*bf2c3715SXin Li */ 262*bf2c3715SXin Li inline bool isSurjective() const { return m_cpqr.isSurjective(); } 263*bf2c3715SXin Li 264*bf2c3715SXin Li /** \returns true if the matrix of which *this is the complete orthogonal 265*bf2c3715SXin Li * decomposition is invertible. 266*bf2c3715SXin Li * 267*bf2c3715SXin Li * \note This method has to determine which pivots should be considered 268*bf2c3715SXin Li * nonzero. For that, it uses the threshold value that you can control by 269*bf2c3715SXin Li * calling setThreshold(const RealScalar&). 270*bf2c3715SXin Li */ 271*bf2c3715SXin Li inline bool isInvertible() const { return m_cpqr.isInvertible(); } 272*bf2c3715SXin Li 273*bf2c3715SXin Li /** \returns the pseudo-inverse of the matrix of which *this is the complete 274*bf2c3715SXin Li * orthogonal decomposition. 275*bf2c3715SXin Li * \warning: Do not compute \c this->pseudoInverse()*rhs to solve a linear systems. 276*bf2c3715SXin Li * It is more efficient and numerically stable to call \c this->solve(rhs). 277*bf2c3715SXin Li */ 278*bf2c3715SXin Li inline const Inverse<CompleteOrthogonalDecomposition> pseudoInverse() const 279*bf2c3715SXin Li { 280*bf2c3715SXin Li eigen_assert(m_cpqr.m_isInitialized && "CompleteOrthogonalDecomposition is not initialized."); 281*bf2c3715SXin Li return Inverse<CompleteOrthogonalDecomposition>(*this); 282*bf2c3715SXin Li } 283*bf2c3715SXin Li 284*bf2c3715SXin Li inline Index rows() const { return m_cpqr.rows(); } 285*bf2c3715SXin Li inline Index cols() const { return m_cpqr.cols(); } 286*bf2c3715SXin Li 287*bf2c3715SXin Li /** \returns a const reference to the vector of Householder coefficients used 288*bf2c3715SXin Li * to represent the factor \c Q. 289*bf2c3715SXin Li * 290*bf2c3715SXin Li * For advanced uses only. 291*bf2c3715SXin Li */ 292*bf2c3715SXin Li inline const HCoeffsType& hCoeffs() const { return m_cpqr.hCoeffs(); } 293*bf2c3715SXin Li 294*bf2c3715SXin Li /** \returns a const reference to the vector of Householder coefficients 295*bf2c3715SXin Li * used to represent the factor \c Z. 296*bf2c3715SXin Li * 297*bf2c3715SXin Li * For advanced uses only. 298*bf2c3715SXin Li */ 299*bf2c3715SXin Li const HCoeffsType& zCoeffs() const { return m_zCoeffs; } 300*bf2c3715SXin Li 301*bf2c3715SXin Li /** Allows to prescribe a threshold to be used by certain methods, such as 302*bf2c3715SXin Li * rank(), who need to determine when pivots are to be considered nonzero. 303*bf2c3715SXin Li * Most be called before calling compute(). 304*bf2c3715SXin Li * 305*bf2c3715SXin Li * When it needs to get the threshold value, Eigen calls threshold(). By 306*bf2c3715SXin Li * default, this uses a formula to automatically determine a reasonable 307*bf2c3715SXin Li * threshold. Once you have called the present method 308*bf2c3715SXin Li * setThreshold(const RealScalar&), your value is used instead. 309*bf2c3715SXin Li * 310*bf2c3715SXin Li * \param threshold The new value to use as the threshold. 311*bf2c3715SXin Li * 312*bf2c3715SXin Li * A pivot will be considered nonzero if its absolute value is strictly 313*bf2c3715SXin Li * greater than 314*bf2c3715SXin Li * \f$ \vert pivot \vert \leqslant threshold \times \vert maxpivot \vert \f$ 315*bf2c3715SXin Li * where maxpivot is the biggest pivot. 316*bf2c3715SXin Li * 317*bf2c3715SXin Li * If you want to come back to the default behavior, call 318*bf2c3715SXin Li * setThreshold(Default_t) 319*bf2c3715SXin Li */ 320*bf2c3715SXin Li CompleteOrthogonalDecomposition& setThreshold(const RealScalar& threshold) { 321*bf2c3715SXin Li m_cpqr.setThreshold(threshold); 322*bf2c3715SXin Li return *this; 323*bf2c3715SXin Li } 324*bf2c3715SXin Li 325*bf2c3715SXin Li /** Allows to come back to the default behavior, letting Eigen use its default 326*bf2c3715SXin Li * formula for determining the threshold. 327*bf2c3715SXin Li * 328*bf2c3715SXin Li * You should pass the special object Eigen::Default as parameter here. 329*bf2c3715SXin Li * \code qr.setThreshold(Eigen::Default); \endcode 330*bf2c3715SXin Li * 331*bf2c3715SXin Li * See the documentation of setThreshold(const RealScalar&). 332*bf2c3715SXin Li */ 333*bf2c3715SXin Li CompleteOrthogonalDecomposition& setThreshold(Default_t) { 334*bf2c3715SXin Li m_cpqr.setThreshold(Default); 335*bf2c3715SXin Li return *this; 336*bf2c3715SXin Li } 337*bf2c3715SXin Li 338*bf2c3715SXin Li /** Returns the threshold that will be used by certain methods such as rank(). 339*bf2c3715SXin Li * 340*bf2c3715SXin Li * See the documentation of setThreshold(const RealScalar&). 341*bf2c3715SXin Li */ 342*bf2c3715SXin Li RealScalar threshold() const { return m_cpqr.threshold(); } 343*bf2c3715SXin Li 344*bf2c3715SXin Li /** \returns the number of nonzero pivots in the complete orthogonal 345*bf2c3715SXin Li * decomposition. Here nonzero is meant in the exact sense, not in a 346*bf2c3715SXin Li * fuzzy sense. So that notion isn't really intrinsically interesting, 347*bf2c3715SXin Li * but it is still useful when implementing algorithms. 348*bf2c3715SXin Li * 349*bf2c3715SXin Li * \sa rank() 350*bf2c3715SXin Li */ 351*bf2c3715SXin Li inline Index nonzeroPivots() const { return m_cpqr.nonzeroPivots(); } 352*bf2c3715SXin Li 353*bf2c3715SXin Li /** \returns the absolute value of the biggest pivot, i.e. the biggest 354*bf2c3715SXin Li * diagonal coefficient of R. 355*bf2c3715SXin Li */ 356*bf2c3715SXin Li inline RealScalar maxPivot() const { return m_cpqr.maxPivot(); } 357*bf2c3715SXin Li 358*bf2c3715SXin Li /** \brief Reports whether the complete orthogonal decomposition was 359*bf2c3715SXin Li * successful. 360*bf2c3715SXin Li * 361*bf2c3715SXin Li * \note This function always returns \c Success. It is provided for 362*bf2c3715SXin Li * compatibility 363*bf2c3715SXin Li * with other factorization routines. 364*bf2c3715SXin Li * \returns \c Success 365*bf2c3715SXin Li */ 366*bf2c3715SXin Li ComputationInfo info() const { 367*bf2c3715SXin Li eigen_assert(m_cpqr.m_isInitialized && "Decomposition is not initialized."); 368*bf2c3715SXin Li return Success; 369*bf2c3715SXin Li } 370*bf2c3715SXin Li 371*bf2c3715SXin Li #ifndef EIGEN_PARSED_BY_DOXYGEN 372*bf2c3715SXin Li template <typename RhsType, typename DstType> 373*bf2c3715SXin Li void _solve_impl(const RhsType& rhs, DstType& dst) const; 374*bf2c3715SXin Li 375*bf2c3715SXin Li template<bool Conjugate, typename RhsType, typename DstType> 376*bf2c3715SXin Li void _solve_impl_transposed(const RhsType &rhs, DstType &dst) const; 377*bf2c3715SXin Li #endif 378*bf2c3715SXin Li 379*bf2c3715SXin Li protected: 380*bf2c3715SXin Li static void check_template_parameters() { 381*bf2c3715SXin Li EIGEN_STATIC_ASSERT_NON_INTEGER(Scalar); 382*bf2c3715SXin Li } 383*bf2c3715SXin Li 384*bf2c3715SXin Li template<bool Transpose_, typename Rhs> 385*bf2c3715SXin Li void _check_solve_assertion(const Rhs& b) const { 386*bf2c3715SXin Li EIGEN_ONLY_USED_FOR_DEBUG(b); 387*bf2c3715SXin Li eigen_assert(m_cpqr.m_isInitialized && "CompleteOrthogonalDecomposition is not initialized."); 388*bf2c3715SXin Li eigen_assert((Transpose_?derived().cols():derived().rows())==b.rows() && "CompleteOrthogonalDecomposition::solve(): invalid number of rows of the right hand side matrix b"); 389*bf2c3715SXin Li } 390*bf2c3715SXin Li 391*bf2c3715SXin Li void computeInPlace(); 392*bf2c3715SXin Li 393*bf2c3715SXin Li /** Overwrites \b rhs with \f$ \mathbf{Z} * \mathbf{rhs} \f$ or 394*bf2c3715SXin Li * \f$ \mathbf{\overline Z} * \mathbf{rhs} \f$ if \c Conjugate 395*bf2c3715SXin Li * is set to \c true. 396*bf2c3715SXin Li */ 397*bf2c3715SXin Li template <bool Conjugate, typename Rhs> 398*bf2c3715SXin Li void applyZOnTheLeftInPlace(Rhs& rhs) const; 399*bf2c3715SXin Li 400*bf2c3715SXin Li /** Overwrites \b rhs with \f$ \mathbf{Z}^* * \mathbf{rhs} \f$. 401*bf2c3715SXin Li */ 402*bf2c3715SXin Li template <typename Rhs> 403*bf2c3715SXin Li void applyZAdjointOnTheLeftInPlace(Rhs& rhs) const; 404*bf2c3715SXin Li 405*bf2c3715SXin Li ColPivHouseholderQR<MatrixType> m_cpqr; 406*bf2c3715SXin Li HCoeffsType m_zCoeffs; 407*bf2c3715SXin Li RowVectorType m_temp; 408*bf2c3715SXin Li }; 409*bf2c3715SXin Li 410*bf2c3715SXin Li template <typename MatrixType> 411*bf2c3715SXin Li typename MatrixType::RealScalar 412*bf2c3715SXin Li CompleteOrthogonalDecomposition<MatrixType>::absDeterminant() const { 413*bf2c3715SXin Li return m_cpqr.absDeterminant(); 414*bf2c3715SXin Li } 415*bf2c3715SXin Li 416*bf2c3715SXin Li template <typename MatrixType> 417*bf2c3715SXin Li typename MatrixType::RealScalar 418*bf2c3715SXin Li CompleteOrthogonalDecomposition<MatrixType>::logAbsDeterminant() const { 419*bf2c3715SXin Li return m_cpqr.logAbsDeterminant(); 420*bf2c3715SXin Li } 421*bf2c3715SXin Li 422*bf2c3715SXin Li /** Performs the complete orthogonal decomposition of the given matrix \a 423*bf2c3715SXin Li * matrix. The result of the factorization is stored into \c *this, and a 424*bf2c3715SXin Li * reference to \c *this is returned. 425*bf2c3715SXin Li * 426*bf2c3715SXin Li * \sa class CompleteOrthogonalDecomposition, 427*bf2c3715SXin Li * CompleteOrthogonalDecomposition(const MatrixType&) 428*bf2c3715SXin Li */ 429*bf2c3715SXin Li template <typename MatrixType> 430*bf2c3715SXin Li void CompleteOrthogonalDecomposition<MatrixType>::computeInPlace() 431*bf2c3715SXin Li { 432*bf2c3715SXin Li check_template_parameters(); 433*bf2c3715SXin Li 434*bf2c3715SXin Li // the column permutation is stored as int indices, so just to be sure: 435*bf2c3715SXin Li eigen_assert(m_cpqr.cols() <= NumTraits<int>::highest()); 436*bf2c3715SXin Li 437*bf2c3715SXin Li const Index rank = m_cpqr.rank(); 438*bf2c3715SXin Li const Index cols = m_cpqr.cols(); 439*bf2c3715SXin Li const Index rows = m_cpqr.rows(); 440*bf2c3715SXin Li m_zCoeffs.resize((std::min)(rows, cols)); 441*bf2c3715SXin Li m_temp.resize(cols); 442*bf2c3715SXin Li 443*bf2c3715SXin Li if (rank < cols) { 444*bf2c3715SXin Li // We have reduced the (permuted) matrix to the form 445*bf2c3715SXin Li // [R11 R12] 446*bf2c3715SXin Li // [ 0 R22] 447*bf2c3715SXin Li // where R11 is r-by-r (r = rank) upper triangular, R12 is 448*bf2c3715SXin Li // r-by-(n-r), and R22 is empty or the norm of R22 is negligible. 449*bf2c3715SXin Li // We now compute the complete orthogonal decomposition by applying 450*bf2c3715SXin Li // Householder transformations from the right to the upper trapezoidal 451*bf2c3715SXin Li // matrix X = [R11 R12] to zero out R12 and obtain the factorization 452*bf2c3715SXin Li // [R11 R12] = [T11 0] * Z, where T11 is r-by-r upper triangular and 453*bf2c3715SXin Li // Z = Z(0) * Z(1) ... Z(r-1) is an n-by-n orthogonal matrix. 454*bf2c3715SXin Li // We store the data representing Z in R12 and m_zCoeffs. 455*bf2c3715SXin Li for (Index k = rank - 1; k >= 0; --k) { 456*bf2c3715SXin Li if (k != rank - 1) { 457*bf2c3715SXin Li // Given the API for Householder reflectors, it is more convenient if 458*bf2c3715SXin Li // we swap the leading parts of columns k and r-1 (zero-based) to form 459*bf2c3715SXin Li // the matrix X_k = [X(0:k, k), X(0:k, r:n)] 460*bf2c3715SXin Li m_cpqr.m_qr.col(k).head(k + 1).swap( 461*bf2c3715SXin Li m_cpqr.m_qr.col(rank - 1).head(k + 1)); 462*bf2c3715SXin Li } 463*bf2c3715SXin Li // Construct Householder reflector Z(k) to zero out the last row of X_k, 464*bf2c3715SXin Li // i.e. choose Z(k) such that 465*bf2c3715SXin Li // [X(k, k), X(k, r:n)] * Z(k) = [beta, 0, .., 0]. 466*bf2c3715SXin Li RealScalar beta; 467*bf2c3715SXin Li m_cpqr.m_qr.row(k) 468*bf2c3715SXin Li .tail(cols - rank + 1) 469*bf2c3715SXin Li .makeHouseholderInPlace(m_zCoeffs(k), beta); 470*bf2c3715SXin Li m_cpqr.m_qr(k, rank - 1) = beta; 471*bf2c3715SXin Li if (k > 0) { 472*bf2c3715SXin Li // Apply Z(k) to the first k rows of X_k 473*bf2c3715SXin Li m_cpqr.m_qr.topRightCorner(k, cols - rank + 1) 474*bf2c3715SXin Li .applyHouseholderOnTheRight( 475*bf2c3715SXin Li m_cpqr.m_qr.row(k).tail(cols - rank).adjoint(), m_zCoeffs(k), 476*bf2c3715SXin Li &m_temp(0)); 477*bf2c3715SXin Li } 478*bf2c3715SXin Li if (k != rank - 1) { 479*bf2c3715SXin Li // Swap X(0:k,k) back to its proper location. 480*bf2c3715SXin Li m_cpqr.m_qr.col(k).head(k + 1).swap( 481*bf2c3715SXin Li m_cpqr.m_qr.col(rank - 1).head(k + 1)); 482*bf2c3715SXin Li } 483*bf2c3715SXin Li } 484*bf2c3715SXin Li } 485*bf2c3715SXin Li } 486*bf2c3715SXin Li 487*bf2c3715SXin Li template <typename MatrixType> 488*bf2c3715SXin Li template <bool Conjugate, typename Rhs> 489*bf2c3715SXin Li void CompleteOrthogonalDecomposition<MatrixType>::applyZOnTheLeftInPlace( 490*bf2c3715SXin Li Rhs& rhs) const { 491*bf2c3715SXin Li const Index cols = this->cols(); 492*bf2c3715SXin Li const Index nrhs = rhs.cols(); 493*bf2c3715SXin Li const Index rank = this->rank(); 494*bf2c3715SXin Li Matrix<typename Rhs::Scalar, Dynamic, 1> temp((std::max)(cols, nrhs)); 495*bf2c3715SXin Li for (Index k = rank-1; k >= 0; --k) { 496*bf2c3715SXin Li if (k != rank - 1) { 497*bf2c3715SXin Li rhs.row(k).swap(rhs.row(rank - 1)); 498*bf2c3715SXin Li } 499*bf2c3715SXin Li rhs.middleRows(rank - 1, cols - rank + 1) 500*bf2c3715SXin Li .applyHouseholderOnTheLeft( 501*bf2c3715SXin Li matrixQTZ().row(k).tail(cols - rank).transpose().template conjugateIf<!Conjugate>(), zCoeffs().template conjugateIf<Conjugate>()(k), 502*bf2c3715SXin Li &temp(0)); 503*bf2c3715SXin Li if (k != rank - 1) { 504*bf2c3715SXin Li rhs.row(k).swap(rhs.row(rank - 1)); 505*bf2c3715SXin Li } 506*bf2c3715SXin Li } 507*bf2c3715SXin Li } 508*bf2c3715SXin Li 509*bf2c3715SXin Li template <typename MatrixType> 510*bf2c3715SXin Li template <typename Rhs> 511*bf2c3715SXin Li void CompleteOrthogonalDecomposition<MatrixType>::applyZAdjointOnTheLeftInPlace( 512*bf2c3715SXin Li Rhs& rhs) const { 513*bf2c3715SXin Li const Index cols = this->cols(); 514*bf2c3715SXin Li const Index nrhs = rhs.cols(); 515*bf2c3715SXin Li const Index rank = this->rank(); 516*bf2c3715SXin Li Matrix<typename Rhs::Scalar, Dynamic, 1> temp((std::max)(cols, nrhs)); 517*bf2c3715SXin Li for (Index k = 0; k < rank; ++k) { 518*bf2c3715SXin Li if (k != rank - 1) { 519*bf2c3715SXin Li rhs.row(k).swap(rhs.row(rank - 1)); 520*bf2c3715SXin Li } 521*bf2c3715SXin Li rhs.middleRows(rank - 1, cols - rank + 1) 522*bf2c3715SXin Li .applyHouseholderOnTheLeft( 523*bf2c3715SXin Li matrixQTZ().row(k).tail(cols - rank).adjoint(), zCoeffs()(k), 524*bf2c3715SXin Li &temp(0)); 525*bf2c3715SXin Li if (k != rank - 1) { 526*bf2c3715SXin Li rhs.row(k).swap(rhs.row(rank - 1)); 527*bf2c3715SXin Li } 528*bf2c3715SXin Li } 529*bf2c3715SXin Li } 530*bf2c3715SXin Li 531*bf2c3715SXin Li #ifndef EIGEN_PARSED_BY_DOXYGEN 532*bf2c3715SXin Li template <typename _MatrixType> 533*bf2c3715SXin Li template <typename RhsType, typename DstType> 534*bf2c3715SXin Li void CompleteOrthogonalDecomposition<_MatrixType>::_solve_impl( 535*bf2c3715SXin Li const RhsType& rhs, DstType& dst) const { 536*bf2c3715SXin Li const Index rank = this->rank(); 537*bf2c3715SXin Li if (rank == 0) { 538*bf2c3715SXin Li dst.setZero(); 539*bf2c3715SXin Li return; 540*bf2c3715SXin Li } 541*bf2c3715SXin Li 542*bf2c3715SXin Li // Compute c = Q^* * rhs 543*bf2c3715SXin Li typename RhsType::PlainObject c(rhs); 544*bf2c3715SXin Li c.applyOnTheLeft(matrixQ().setLength(rank).adjoint()); 545*bf2c3715SXin Li 546*bf2c3715SXin Li // Solve T z = c(1:rank, :) 547*bf2c3715SXin Li dst.topRows(rank) = matrixT() 548*bf2c3715SXin Li .topLeftCorner(rank, rank) 549*bf2c3715SXin Li .template triangularView<Upper>() 550*bf2c3715SXin Li .solve(c.topRows(rank)); 551*bf2c3715SXin Li 552*bf2c3715SXin Li const Index cols = this->cols(); 553*bf2c3715SXin Li if (rank < cols) { 554*bf2c3715SXin Li // Compute y = Z^* * [ z ] 555*bf2c3715SXin Li // [ 0 ] 556*bf2c3715SXin Li dst.bottomRows(cols - rank).setZero(); 557*bf2c3715SXin Li applyZAdjointOnTheLeftInPlace(dst); 558*bf2c3715SXin Li } 559*bf2c3715SXin Li 560*bf2c3715SXin Li // Undo permutation to get x = P^{-1} * y. 561*bf2c3715SXin Li dst = colsPermutation() * dst; 562*bf2c3715SXin Li } 563*bf2c3715SXin Li 564*bf2c3715SXin Li template<typename _MatrixType> 565*bf2c3715SXin Li template<bool Conjugate, typename RhsType, typename DstType> 566*bf2c3715SXin Li void CompleteOrthogonalDecomposition<_MatrixType>::_solve_impl_transposed(const RhsType &rhs, DstType &dst) const 567*bf2c3715SXin Li { 568*bf2c3715SXin Li const Index rank = this->rank(); 569*bf2c3715SXin Li 570*bf2c3715SXin Li if (rank == 0) { 571*bf2c3715SXin Li dst.setZero(); 572*bf2c3715SXin Li return; 573*bf2c3715SXin Li } 574*bf2c3715SXin Li 575*bf2c3715SXin Li typename RhsType::PlainObject c(colsPermutation().transpose()*rhs); 576*bf2c3715SXin Li 577*bf2c3715SXin Li if (rank < cols()) { 578*bf2c3715SXin Li applyZOnTheLeftInPlace<!Conjugate>(c); 579*bf2c3715SXin Li } 580*bf2c3715SXin Li 581*bf2c3715SXin Li matrixT().topLeftCorner(rank, rank) 582*bf2c3715SXin Li .template triangularView<Upper>() 583*bf2c3715SXin Li .transpose().template conjugateIf<Conjugate>() 584*bf2c3715SXin Li .solveInPlace(c.topRows(rank)); 585*bf2c3715SXin Li 586*bf2c3715SXin Li dst.topRows(rank) = c.topRows(rank); 587*bf2c3715SXin Li dst.bottomRows(rows()-rank).setZero(); 588*bf2c3715SXin Li 589*bf2c3715SXin Li dst.applyOnTheLeft(householderQ().setLength(rank).template conjugateIf<!Conjugate>() ); 590*bf2c3715SXin Li } 591*bf2c3715SXin Li #endif 592*bf2c3715SXin Li 593*bf2c3715SXin Li namespace internal { 594*bf2c3715SXin Li 595*bf2c3715SXin Li template<typename MatrixType> 596*bf2c3715SXin Li struct traits<Inverse<CompleteOrthogonalDecomposition<MatrixType> > > 597*bf2c3715SXin Li : traits<typename Transpose<typename MatrixType::PlainObject>::PlainObject> 598*bf2c3715SXin Li { 599*bf2c3715SXin Li enum { Flags = 0 }; 600*bf2c3715SXin Li }; 601*bf2c3715SXin Li 602*bf2c3715SXin Li template<typename DstXprType, typename MatrixType> 603*bf2c3715SXin Li struct Assignment<DstXprType, Inverse<CompleteOrthogonalDecomposition<MatrixType> >, internal::assign_op<typename DstXprType::Scalar,typename CompleteOrthogonalDecomposition<MatrixType>::Scalar>, Dense2Dense> 604*bf2c3715SXin Li { 605*bf2c3715SXin Li typedef CompleteOrthogonalDecomposition<MatrixType> CodType; 606*bf2c3715SXin Li typedef Inverse<CodType> SrcXprType; 607*bf2c3715SXin Li static void run(DstXprType &dst, const SrcXprType &src, const internal::assign_op<typename DstXprType::Scalar,typename CodType::Scalar> &) 608*bf2c3715SXin Li { 609*bf2c3715SXin Li typedef Matrix<typename CodType::Scalar, CodType::RowsAtCompileTime, CodType::RowsAtCompileTime, 0, CodType::MaxRowsAtCompileTime, CodType::MaxRowsAtCompileTime> IdentityMatrixType; 610*bf2c3715SXin Li dst = src.nestedExpression().solve(IdentityMatrixType::Identity(src.cols(), src.cols())); 611*bf2c3715SXin Li } 612*bf2c3715SXin Li }; 613*bf2c3715SXin Li 614*bf2c3715SXin Li } // end namespace internal 615*bf2c3715SXin Li 616*bf2c3715SXin Li /** \returns the matrix Q as a sequence of householder transformations */ 617*bf2c3715SXin Li template <typename MatrixType> 618*bf2c3715SXin Li typename CompleteOrthogonalDecomposition<MatrixType>::HouseholderSequenceType 619*bf2c3715SXin Li CompleteOrthogonalDecomposition<MatrixType>::householderQ() const { 620*bf2c3715SXin Li return m_cpqr.householderQ(); 621*bf2c3715SXin Li } 622*bf2c3715SXin Li 623*bf2c3715SXin Li /** \return the complete orthogonal decomposition of \c *this. 624*bf2c3715SXin Li * 625*bf2c3715SXin Li * \sa class CompleteOrthogonalDecomposition 626*bf2c3715SXin Li */ 627*bf2c3715SXin Li template <typename Derived> 628*bf2c3715SXin Li const CompleteOrthogonalDecomposition<typename MatrixBase<Derived>::PlainObject> 629*bf2c3715SXin Li MatrixBase<Derived>::completeOrthogonalDecomposition() const { 630*bf2c3715SXin Li return CompleteOrthogonalDecomposition<PlainObject>(eval()); 631*bf2c3715SXin Li } 632*bf2c3715SXin Li 633*bf2c3715SXin Li } // end namespace Eigen 634*bf2c3715SXin Li 635*bf2c3715SXin Li #endif // EIGEN_COMPLETEORTHOGONALDECOMPOSITION_H 636