Transpositions.h (13567B)
1 // This file is part of Eigen, a lightweight C++ template library 2 // for linear algebra. 3 // 4 // Copyright (C) 2010-2011 Gael Guennebaud <gael.guennebaud@inria.fr> 5 // 6 // This Source Code Form is subject to the terms of the Mozilla 7 // Public License v. 2.0. If a copy of the MPL was not distributed 8 // with this file, You can obtain one at http://mozilla.org/MPL/2.0/. 9 10 #ifndef EIGEN_TRANSPOSITIONS_H 11 #define EIGEN_TRANSPOSITIONS_H 12 13 namespace Eigen { 14 15 template<typename Derived> 16 class TranspositionsBase 17 { 18 typedef internal::traits<Derived> Traits; 19 20 public: 21 22 typedef typename Traits::IndicesType IndicesType; 23 typedef typename IndicesType::Scalar StorageIndex; 24 typedef Eigen::Index Index; ///< \deprecated since Eigen 3.3 25 26 EIGEN_DEVICE_FUNC 27 Derived& derived() { return *static_cast<Derived*>(this); } 28 EIGEN_DEVICE_FUNC 29 const Derived& derived() const { return *static_cast<const Derived*>(this); } 30 31 /** Copies the \a other transpositions into \c *this */ 32 template<typename OtherDerived> 33 Derived& operator=(const TranspositionsBase<OtherDerived>& other) 34 { 35 indices() = other.indices(); 36 return derived(); 37 } 38 39 /** \returns the number of transpositions */ 40 EIGEN_DEVICE_FUNC 41 Index size() const { return indices().size(); } 42 /** \returns the number of rows of the equivalent permutation matrix */ 43 EIGEN_DEVICE_FUNC 44 Index rows() const { return indices().size(); } 45 /** \returns the number of columns of the equivalent permutation matrix */ 46 EIGEN_DEVICE_FUNC 47 Index cols() const { return indices().size(); } 48 49 /** Direct access to the underlying index vector */ 50 EIGEN_DEVICE_FUNC 51 inline const StorageIndex& coeff(Index i) const { return indices().coeff(i); } 52 /** Direct access to the underlying index vector */ 53 inline StorageIndex& coeffRef(Index i) { return indices().coeffRef(i); } 54 /** Direct access to the underlying index vector */ 55 inline const StorageIndex& operator()(Index i) const { return indices()(i); } 56 /** Direct access to the underlying index vector */ 57 inline StorageIndex& operator()(Index i) { return indices()(i); } 58 /** Direct access to the underlying index vector */ 59 inline const StorageIndex& operator[](Index i) const { return indices()(i); } 60 /** Direct access to the underlying index vector */ 61 inline StorageIndex& operator[](Index i) { return indices()(i); } 62 63 /** const version of indices(). */ 64 EIGEN_DEVICE_FUNC 65 const IndicesType& indices() const { return derived().indices(); } 66 /** \returns a reference to the stored array representing the transpositions. */ 67 EIGEN_DEVICE_FUNC 68 IndicesType& indices() { return derived().indices(); } 69 70 /** Resizes to given size. */ 71 inline void resize(Index newSize) 72 { 73 indices().resize(newSize); 74 } 75 76 /** Sets \c *this to represents an identity transformation */ 77 void setIdentity() 78 { 79 for(StorageIndex i = 0; i < indices().size(); ++i) 80 coeffRef(i) = i; 81 } 82 83 // FIXME: do we want such methods ? 84 // might be useful when the target matrix expression is complex, e.g.: 85 // object.matrix().block(..,..,..,..) = trans * object.matrix().block(..,..,..,..); 86 /* 87 template<typename MatrixType> 88 void applyForwardToRows(MatrixType& mat) const 89 { 90 for(Index k=0 ; k<size() ; ++k) 91 if(m_indices(k)!=k) 92 mat.row(k).swap(mat.row(m_indices(k))); 93 } 94 95 template<typename MatrixType> 96 void applyBackwardToRows(MatrixType& mat) const 97 { 98 for(Index k=size()-1 ; k>=0 ; --k) 99 if(m_indices(k)!=k) 100 mat.row(k).swap(mat.row(m_indices(k))); 101 } 102 */ 103 104 /** \returns the inverse transformation */ 105 inline Transpose<TranspositionsBase> inverse() const 106 { return Transpose<TranspositionsBase>(derived()); } 107 108 /** \returns the tranpose transformation */ 109 inline Transpose<TranspositionsBase> transpose() const 110 { return Transpose<TranspositionsBase>(derived()); } 111 112 protected: 113 }; 114 115 namespace internal { 116 template<int SizeAtCompileTime, int MaxSizeAtCompileTime, typename _StorageIndex> 117 struct traits<Transpositions<SizeAtCompileTime,MaxSizeAtCompileTime,_StorageIndex> > 118 : traits<PermutationMatrix<SizeAtCompileTime,MaxSizeAtCompileTime,_StorageIndex> > 119 { 120 typedef Matrix<_StorageIndex, SizeAtCompileTime, 1, 0, MaxSizeAtCompileTime, 1> IndicesType; 121 typedef TranspositionsStorage StorageKind; 122 }; 123 } 124 125 /** \class Transpositions 126 * \ingroup Core_Module 127 * 128 * \brief Represents a sequence of transpositions (row/column interchange) 129 * 130 * \tparam SizeAtCompileTime the number of transpositions, or Dynamic 131 * \tparam MaxSizeAtCompileTime the maximum number of transpositions, or Dynamic. This optional parameter defaults to SizeAtCompileTime. Most of the time, you should not have to specify it. 132 * 133 * This class represents a permutation transformation as a sequence of \em n transpositions 134 * \f$[T_{n-1} \ldots T_{i} \ldots T_{0}]\f$. It is internally stored as a vector of integers \c indices. 135 * Each transposition \f$ T_{i} \f$ applied on the left of a matrix (\f$ T_{i} M\f$) interchanges 136 * the rows \c i and \c indices[i] of the matrix \c M. 137 * A transposition applied on the right (e.g., \f$ M T_{i}\f$) yields a column interchange. 138 * 139 * Compared to the class PermutationMatrix, such a sequence of transpositions is what is 140 * computed during a decomposition with pivoting, and it is faster when applying the permutation in-place. 141 * 142 * To apply a sequence of transpositions to a matrix, simply use the operator * as in the following example: 143 * \code 144 * Transpositions tr; 145 * MatrixXf mat; 146 * mat = tr * mat; 147 * \endcode 148 * In this example, we detect that the matrix appears on both side, and so the transpositions 149 * are applied in-place without any temporary or extra copy. 150 * 151 * \sa class PermutationMatrix 152 */ 153 154 template<int SizeAtCompileTime, int MaxSizeAtCompileTime, typename _StorageIndex> 155 class Transpositions : public TranspositionsBase<Transpositions<SizeAtCompileTime,MaxSizeAtCompileTime,_StorageIndex> > 156 { 157 typedef internal::traits<Transpositions> Traits; 158 public: 159 160 typedef TranspositionsBase<Transpositions> Base; 161 typedef typename Traits::IndicesType IndicesType; 162 typedef typename IndicesType::Scalar StorageIndex; 163 164 inline Transpositions() {} 165 166 /** Copy constructor. */ 167 template<typename OtherDerived> 168 inline Transpositions(const TranspositionsBase<OtherDerived>& other) 169 : m_indices(other.indices()) {} 170 171 /** Generic constructor from expression of the transposition indices. */ 172 template<typename Other> 173 explicit inline Transpositions(const MatrixBase<Other>& indices) : m_indices(indices) 174 {} 175 176 /** Copies the \a other transpositions into \c *this */ 177 template<typename OtherDerived> 178 Transpositions& operator=(const TranspositionsBase<OtherDerived>& other) 179 { 180 return Base::operator=(other); 181 } 182 183 /** Constructs an uninitialized permutation matrix of given size. 184 */ 185 inline Transpositions(Index size) : m_indices(size) 186 {} 187 188 /** const version of indices(). */ 189 EIGEN_DEVICE_FUNC 190 const IndicesType& indices() const { return m_indices; } 191 /** \returns a reference to the stored array representing the transpositions. */ 192 EIGEN_DEVICE_FUNC 193 IndicesType& indices() { return m_indices; } 194 195 protected: 196 197 IndicesType m_indices; 198 }; 199 200 201 namespace internal { 202 template<int SizeAtCompileTime, int MaxSizeAtCompileTime, typename _StorageIndex, int _PacketAccess> 203 struct traits<Map<Transpositions<SizeAtCompileTime,MaxSizeAtCompileTime,_StorageIndex>,_PacketAccess> > 204 : traits<PermutationMatrix<SizeAtCompileTime,MaxSizeAtCompileTime,_StorageIndex> > 205 { 206 typedef Map<const Matrix<_StorageIndex,SizeAtCompileTime,1,0,MaxSizeAtCompileTime,1>, _PacketAccess> IndicesType; 207 typedef _StorageIndex StorageIndex; 208 typedef TranspositionsStorage StorageKind; 209 }; 210 } 211 212 template<int SizeAtCompileTime, int MaxSizeAtCompileTime, typename _StorageIndex, int PacketAccess> 213 class Map<Transpositions<SizeAtCompileTime,MaxSizeAtCompileTime,_StorageIndex>,PacketAccess> 214 : public TranspositionsBase<Map<Transpositions<SizeAtCompileTime,MaxSizeAtCompileTime,_StorageIndex>,PacketAccess> > 215 { 216 typedef internal::traits<Map> Traits; 217 public: 218 219 typedef TranspositionsBase<Map> Base; 220 typedef typename Traits::IndicesType IndicesType; 221 typedef typename IndicesType::Scalar StorageIndex; 222 223 explicit inline Map(const StorageIndex* indicesPtr) 224 : m_indices(indicesPtr) 225 {} 226 227 inline Map(const StorageIndex* indicesPtr, Index size) 228 : m_indices(indicesPtr,size) 229 {} 230 231 /** Copies the \a other transpositions into \c *this */ 232 template<typename OtherDerived> 233 Map& operator=(const TranspositionsBase<OtherDerived>& other) 234 { 235 return Base::operator=(other); 236 } 237 238 #ifndef EIGEN_PARSED_BY_DOXYGEN 239 /** This is a special case of the templated operator=. Its purpose is to 240 * prevent a default operator= from hiding the templated operator=. 241 */ 242 Map& operator=(const Map& other) 243 { 244 m_indices = other.m_indices; 245 return *this; 246 } 247 #endif 248 249 /** const version of indices(). */ 250 EIGEN_DEVICE_FUNC 251 const IndicesType& indices() const { return m_indices; } 252 253 /** \returns a reference to the stored array representing the transpositions. */ 254 EIGEN_DEVICE_FUNC 255 IndicesType& indices() { return m_indices; } 256 257 protected: 258 259 IndicesType m_indices; 260 }; 261 262 namespace internal { 263 template<typename _IndicesType> 264 struct traits<TranspositionsWrapper<_IndicesType> > 265 : traits<PermutationWrapper<_IndicesType> > 266 { 267 typedef TranspositionsStorage StorageKind; 268 }; 269 } 270 271 template<typename _IndicesType> 272 class TranspositionsWrapper 273 : public TranspositionsBase<TranspositionsWrapper<_IndicesType> > 274 { 275 typedef internal::traits<TranspositionsWrapper> Traits; 276 public: 277 278 typedef TranspositionsBase<TranspositionsWrapper> Base; 279 typedef typename Traits::IndicesType IndicesType; 280 typedef typename IndicesType::Scalar StorageIndex; 281 282 explicit inline TranspositionsWrapper(IndicesType& indices) 283 : m_indices(indices) 284 {} 285 286 /** Copies the \a other transpositions into \c *this */ 287 template<typename OtherDerived> 288 TranspositionsWrapper& operator=(const TranspositionsBase<OtherDerived>& other) 289 { 290 return Base::operator=(other); 291 } 292 293 /** const version of indices(). */ 294 EIGEN_DEVICE_FUNC 295 const IndicesType& indices() const { return m_indices; } 296 297 /** \returns a reference to the stored array representing the transpositions. */ 298 EIGEN_DEVICE_FUNC 299 IndicesType& indices() { return m_indices; } 300 301 protected: 302 303 typename IndicesType::Nested m_indices; 304 }; 305 306 307 308 /** \returns the \a matrix with the \a transpositions applied to the columns. 309 */ 310 template<typename MatrixDerived, typename TranspositionsDerived> 311 EIGEN_DEVICE_FUNC 312 const Product<MatrixDerived, TranspositionsDerived, AliasFreeProduct> 313 operator*(const MatrixBase<MatrixDerived> &matrix, 314 const TranspositionsBase<TranspositionsDerived>& transpositions) 315 { 316 return Product<MatrixDerived, TranspositionsDerived, AliasFreeProduct> 317 (matrix.derived(), transpositions.derived()); 318 } 319 320 /** \returns the \a matrix with the \a transpositions applied to the rows. 321 */ 322 template<typename TranspositionsDerived, typename MatrixDerived> 323 EIGEN_DEVICE_FUNC 324 const Product<TranspositionsDerived, MatrixDerived, AliasFreeProduct> 325 operator*(const TranspositionsBase<TranspositionsDerived> &transpositions, 326 const MatrixBase<MatrixDerived>& matrix) 327 { 328 return Product<TranspositionsDerived, MatrixDerived, AliasFreeProduct> 329 (transpositions.derived(), matrix.derived()); 330 } 331 332 // Template partial specialization for transposed/inverse transpositions 333 334 namespace internal { 335 336 template<typename Derived> 337 struct traits<Transpose<TranspositionsBase<Derived> > > 338 : traits<Derived> 339 {}; 340 341 } // end namespace internal 342 343 template<typename TranspositionsDerived> 344 class Transpose<TranspositionsBase<TranspositionsDerived> > 345 { 346 typedef TranspositionsDerived TranspositionType; 347 typedef typename TranspositionType::IndicesType IndicesType; 348 public: 349 350 explicit Transpose(const TranspositionType& t) : m_transpositions(t) {} 351 352 EIGEN_DEVICE_FUNC EIGEN_CONSTEXPR 353 Index size() const EIGEN_NOEXCEPT { return m_transpositions.size(); } 354 EIGEN_DEVICE_FUNC EIGEN_CONSTEXPR 355 Index rows() const EIGEN_NOEXCEPT { return m_transpositions.size(); } 356 EIGEN_DEVICE_FUNC EIGEN_CONSTEXPR 357 Index cols() const EIGEN_NOEXCEPT { return m_transpositions.size(); } 358 359 /** \returns the \a matrix with the inverse transpositions applied to the columns. 360 */ 361 template<typename OtherDerived> friend 362 const Product<OtherDerived, Transpose, AliasFreeProduct> 363 operator*(const MatrixBase<OtherDerived>& matrix, const Transpose& trt) 364 { 365 return Product<OtherDerived, Transpose, AliasFreeProduct>(matrix.derived(), trt); 366 } 367 368 /** \returns the \a matrix with the inverse transpositions applied to the rows. 369 */ 370 template<typename OtherDerived> 371 const Product<Transpose, OtherDerived, AliasFreeProduct> 372 operator*(const MatrixBase<OtherDerived>& matrix) const 373 { 374 return Product<Transpose, OtherDerived, AliasFreeProduct>(*this, matrix.derived()); 375 } 376 377 EIGEN_DEVICE_FUNC 378 const TranspositionType& nestedExpression() const { return m_transpositions; } 379 380 protected: 381 const TranspositionType& m_transpositions; 382 }; 383 384 } // end namespace Eigen 385 386 #endif // EIGEN_TRANSPOSITIONS_H