xref: /aosp_15_r20/external/eigen/Eigen/src/QR/CompleteOrthogonalDecomposition.h (revision bf2c37156dfe67e5dfebd6d394bad8b2ab5804d4)
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