Main MRPT website > C++ reference
MRPT logo

SolveTriangular.h

Go to the documentation of this file.
00001 // This file is part of Eigen, a lightweight C++ template library
00002 // for linear algebra.
00003 //
00004 // Copyright (C) 2008-2009 Gael Guennebaud <gael.guennebaud@inria.fr>
00005 //
00006 // Eigen is free software; you can redistribute it and/or
00007 // modify it under the terms of the GNU Lesser General Public
00008 // License as published by the Free Software Foundation; either
00009 // version 3 of the License, or (at your option) any later version.
00010 //
00011 // Alternatively, you can redistribute it and/or
00012 // modify it under the terms of the GNU General Public License as
00013 // published by the Free Software Foundation; either version 2 of
00014 // the License, or (at your option) any later version.
00015 //
00016 // Eigen is distributed in the hope that it will be useful, but WITHOUT ANY
00017 // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
00018 // FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License or the
00019 // GNU General Public License for more details.
00020 //
00021 // You should have received a copy of the GNU Lesser General Public
00022 // License and a copy of the GNU General Public License along with
00023 // Eigen. If not, see <http://www.gnu.org/licenses/>.
00024 
00025 #ifndef EIGEN_SOLVETRIANGULAR_H
00026 #define EIGEN_SOLVETRIANGULAR_H
00027 
00028 namespace internal {
00029 
00030 // Forward declarations:
00031 // The following two routines are implemented in the products/TriangularSolver*.h files
00032 template<typename LhsScalar, typename RhsScalar, typename Index, int Side, int Mode, bool Conjugate, int StorageOrder>
00033 struct triangular_solve_vector;
00034 
00035 template <typename Scalar, typename Index, int Side, int Mode, bool Conjugate, int TriStorageOrder, int OtherStorageOrder>
00036 struct triangular_solve_matrix;
00037 
00038 // small helper struct extracting some traits on the underlying solver operation
00039 template<typename Lhs, typename Rhs, int Side>
00040 class trsolve_traits
00041 {
00042   private:
00043     enum {
00044       RhsIsVectorAtCompileTime = (Side==OnTheLeft ? Rhs::ColsAtCompileTime : Rhs::RowsAtCompileTime)==1
00045     };
00046   public:
00047     enum {
00048       Unrolling   = (RhsIsVectorAtCompileTime && Rhs::SizeAtCompileTime != Dynamic && Rhs::SizeAtCompileTime <= 8)
00049                   ? CompleteUnrolling : NoUnrolling,
00050       RhsVectors  = RhsIsVectorAtCompileTime ? 1 : Dynamic
00051     };
00052 };
00053 
00054 template<typename Lhs, typename Rhs,
00055   int Side, // can be OnTheLeft/OnTheRight
00056   int Mode, // can be Upper/Lower | UnitDiag
00057   int Unrolling = trsolve_traits<Lhs,Rhs,Side>::Unrolling,
00058   int RhsVectors = trsolve_traits<Lhs,Rhs,Side>::RhsVectors
00059   >
00060 struct triangular_solver_selector;
00061 
00062 template<typename Lhs, typename Rhs, int Side, int Mode>
00063 struct triangular_solver_selector<Lhs,Rhs,Side,Mode,NoUnrolling,1>
00064 {
00065   typedef typename Lhs::Scalar LhsScalar;
00066   typedef typename Rhs::Scalar RhsScalar;
00067   typedef blas_traits<Lhs> LhsProductTraits;
00068   typedef typename LhsProductTraits::ExtractType ActualLhsType;
00069   typedef Map<Matrix<RhsScalar,Dynamic,1>, Aligned> MappedRhs;
00070   static void run(const Lhs& lhs, Rhs& rhs)
00071   {
00072     ActualLhsType actualLhs = LhsProductTraits::extract(lhs);
00073 
00074     // FIXME find a way to allow an inner stride if packet_traits<Scalar>::size==1
00075 
00076     bool useRhsDirectly = Rhs::InnerStrideAtCompileTime==1 || rhs.innerStride()==1;
00077     RhsScalar* actualRhs;
00078     if(useRhsDirectly)
00079     {
00080       actualRhs = &rhs.coeffRef(0);
00081     }
00082     else
00083     {
00084       actualRhs = ei_aligned_stack_new(RhsScalar,rhs.size());
00085       MappedRhs(actualRhs,rhs.size()) = rhs;
00086     }
00087 
00088     triangular_solve_vector<LhsScalar, RhsScalar, typename Lhs::Index, Side, Mode, LhsProductTraits::NeedToConjugate,
00089                             (int(Lhs::Flags) & RowMajorBit) ? RowMajor : ColMajor>
00090       ::run(actualLhs.cols(), actualLhs.data(), actualLhs.outerStride(), actualRhs);
00091 
00092     if(!useRhsDirectly)
00093     {
00094       rhs = MappedRhs(actualRhs, rhs.size());
00095       ei_aligned_stack_delete(RhsScalar, actualRhs, rhs.size());
00096     }
00097   }
00098 };
00099 
00100 // the rhs is a matrix
00101 template<typename Lhs, typename Rhs, int Side, int Mode>
00102 struct triangular_solver_selector<Lhs,Rhs,Side,Mode,NoUnrolling,Dynamic>
00103 {
00104   typedef typename Rhs::Scalar Scalar;
00105   typedef typename Rhs::Index Index;
00106   typedef blas_traits<Lhs> LhsProductTraits;
00107   typedef typename LhsProductTraits::DirectLinearAccessType ActualLhsType;
00108   static void run(const Lhs& lhs, Rhs& rhs)
00109   {
00110     const ActualLhsType actualLhs = LhsProductTraits::extract(lhs);
00111     triangular_solve_matrix<Scalar,Index,Side,Mode,LhsProductTraits::NeedToConjugate,(int(Lhs::Flags) & RowMajorBit) ? RowMajor : ColMajor,
00112                                (Rhs::Flags&RowMajorBit) ? RowMajor : ColMajor>
00113       ::run(lhs.rows(), Side==OnTheLeft? rhs.cols() : rhs.rows(), &actualLhs.coeffRef(0,0), actualLhs.outerStride(), &rhs.coeffRef(0,0), rhs.outerStride());
00114   }
00115 };
00116 
00117 /***************************************************************************
00118 * meta-unrolling implementation
00119 ***************************************************************************/
00120 
00121 template<typename Lhs, typename Rhs, int Mode, int Index, int Size,
00122          bool Stop = Index==Size>
00123 struct triangular_solver_unroller;
00124 
00125 template<typename Lhs, typename Rhs, int Mode, int Index, int Size>
00126 struct triangular_solver_unroller<Lhs,Rhs,Mode,Index,Size,false> {
00127   enum {
00128     IsLower = ((Mode&Lower)==Lower),
00129     I = IsLower ? Index : Size - Index - 1,
00130     S = IsLower ? 0     : I+1
00131   };
00132   static void run(const Lhs& lhs, Rhs& rhs)
00133   {
00134     if (Index>0)
00135       rhs.coeffRef(I) -= lhs.row(I).template segment<Index>(S).transpose()
00136                          .cwiseProduct(rhs.template segment<Index>(S)).sum();
00137 
00138     if(!(Mode & UnitDiag))
00139       rhs.coeffRef(I) /= lhs.coeff(I,I);
00140 
00141     triangular_solver_unroller<Lhs,Rhs,Mode,Index+1,Size>::run(lhs,rhs);
00142   }
00143 };
00144 
00145 template<typename Lhs, typename Rhs, int Mode, int Index, int Size>
00146 struct triangular_solver_unroller<Lhs,Rhs,Mode,Index,Size,true> {
00147   static void run(const Lhs&, Rhs&) {}
00148 };
00149 
00150 template<typename Lhs, typename Rhs, int Mode>
00151 struct triangular_solver_selector<Lhs,Rhs,OnTheLeft,Mode,CompleteUnrolling,1> {
00152   static void run(const Lhs& lhs, Rhs& rhs)
00153   { triangular_solver_unroller<Lhs,Rhs,Mode,0,Rhs::SizeAtCompileTime>::run(lhs,rhs); }
00154 };
00155 
00156 template<typename Lhs, typename Rhs, int Mode>
00157 struct triangular_solver_selector<Lhs,Rhs,OnTheRight,Mode,CompleteUnrolling,1> {
00158   static void run(const Lhs& lhs, Rhs& rhs)
00159   {
00160     Transpose<Lhs> trLhs(lhs);
00161     Transpose<Rhs> trRhs(rhs);
00162     
00163     triangular_solver_unroller<Transpose<Lhs>,Transpose<Rhs>,
00164                               ((Mode&Upper)==Upper ? Lower : Upper) | (Mode&UnitDiag),
00165                               0,Rhs::SizeAtCompileTime>::run(trLhs,trRhs);
00166   }
00167 };
00168 
00169 } // end namespace internal
00170 
00171 /***************************************************************************
00172 * TriangularView methods
00173 ***************************************************************************/
00174 
00175 /** "in-place" version of TriangularView::solve() where the result is written in \a other
00176   *
00177   *
00178   *
00179   * \warning The parameter is only marked 'const' to make the C++ compiler accept a temporary expression here.
00180   * This function will const_cast it, so constness isn't honored here.
00181   *
00182   * See TriangularView:solve() for the details.
00183   */
00184 template<typename MatrixType, unsigned int Mode>
00185 template<int Side, typename OtherDerived>
00186 void TriangularView<MatrixType,Mode>::solveInPlace(const MatrixBase<OtherDerived>& _other) const
00187 {
00188   OtherDerived& other = _other.const_cast_derived();
00189   eigen_assert(cols() == rows());
00190   eigen_assert( (Side==OnTheLeft && cols() == other.rows()) || (Side==OnTheRight && cols() == other.cols()) );
00191   eigen_assert(!(Mode & ZeroDiag));
00192   eigen_assert(Mode & (Upper|Lower));
00193 
00194   enum { copy = internal::traits<OtherDerived>::Flags & RowMajorBit  && OtherDerived::IsVectorAtCompileTime };
00195   typedef typename internal::conditional<copy,
00196     typename internal::plain_matrix_type_column_major<OtherDerived>::type, OtherDerived&>::type OtherCopy;
00197   OtherCopy otherCopy(other);
00198 
00199   internal::triangular_solver_selector<MatrixType, typename internal::remove_reference<OtherCopy>::type,
00200     Side, Mode>::run(nestedExpression(), otherCopy);
00201 
00202   if (copy)
00203     other = otherCopy;
00204 }
00205 
00206 /** \returns the product of the inverse of \c *this with \a other, \a *this being triangular.
00207   *
00208   *
00209   *
00210   * This function computes the inverse-matrix matrix product inverse(\c *this) * \a other.
00211   * The matrix \c *this must be triangular and invertible (i.e., all the coefficients of the
00212   * diagonal must be non zero). It works as a forward (resp. backward) substitution if \c *this
00213   * is an upper (resp. lower) triangular matrix.
00214   *
00215   * It is required that \c *this be marked as either an upper or a lower triangular matrix, which
00216   * can be done by marked(), and that is automatically the case with expressions such as those returned
00217   * by extract().
00218   *
00219   * Example: \include MatrixBase_marked.cpp
00220   * Output: \verbinclude MatrixBase_marked.out
00221   *
00222   * This function is essentially a wrapper to the faster solveTriangularInPlace() function creating
00223   * a temporary copy of \a other, calling solveTriangularInPlace() on the copy and returning it.
00224   * Therefore, if \a other is not needed anymore, it is quite faster to call solveTriangularInPlace()
00225   * instead of solveTriangular().
00226   *
00227   * For users coming from BLAS, this function (and more specifically solveTriangularInPlace()) offer
00228   * all the operations supported by the \c *TRSV and \c *TRSM BLAS routines.
00229   *
00230   * \b Tips: to perform a \em "right-inverse-multiply" you can simply transpose the operation, e.g.:
00231   * \code
00232   * M * T^1  <=>  T.transpose().solveInPlace(M.transpose());
00233   * \endcode
00234   *
00235   * \sa TriangularView::solveInPlace()
00236   */
00237 template<typename Derived, unsigned int Mode>
00238 template<int Side, typename RhsDerived>
00239 typename internal::plain_matrix_type_column_major<RhsDerived>::type
00240 TriangularView<Derived,Mode>::solve(const MatrixBase<RhsDerived>& rhs) const
00241 {
00242   typename internal::plain_matrix_type_column_major<RhsDerived>::type res(rhs);
00243   solveInPlace<Side>(res);
00244   return res;
00245 }
00246 
00247 #endif // EIGEN_SOLVETRIANGULAR_H



Page generated by Doxygen 1.7.3 for MRPT 0.9.4 SVN: at Sat Mar 26 06:16:28 UTC 2011