diff options
author | Gael Guennebaud <g.gael@free.fr> | 2015-10-14 10:16:48 +0200 |
---|---|---|
committer | Gael Guennebaud <g.gael@free.fr> | 2015-10-14 10:16:48 +0200 |
commit | c0adf6e38d9f9d3a8f8e5c1ff4c2c3939cf0e070 (patch) | |
tree | 39bb4e437d502fc46f534e49b38505a15b003ea0 | |
parent | 527fc4bc86380eee9e9d77fd1890556da8070fc3 (diff) |
Fix perm*sparse return type and nesting, and add several sanity checks for perm*sparse
-rw-r--r-- | Eigen/src/SparseCore/SparseMatrix.h | 3 | ||||
-rw-r--r-- | Eigen/src/SparseCore/SparsePermutation.h | 63 | ||||
-rw-r--r-- | test/sparse_permutations.cpp | 87 |
3 files changed, 109 insertions, 44 deletions
diff --git a/Eigen/src/SparseCore/SparseMatrix.h b/Eigen/src/SparseCore/SparseMatrix.h index 5e2b14554..f4d0a28dc 100644 --- a/Eigen/src/SparseCore/SparseMatrix.h +++ b/Eigen/src/SparseCore/SparseMatrix.h @@ -1045,6 +1045,9 @@ EIGEN_DONT_INLINE SparseMatrix<Scalar,_Options,_Index>& SparseMatrix<Scalar,_Opt const bool needToTranspose = (Flags & RowMajorBit) != (internal::evaluator<OtherDerived>::Flags & RowMajorBit); if (needToTranspose) { + #ifdef EIGEN_SPARSE_TRANSPOSED_COPY_PLUGIN + EIGEN_SPARSE_TRANSPOSED_COPY_PLUGIN + #endif // two passes algorithm: // 1 - compute the number of coeffs per dest inner vector // 2 - do the actual copy/eval diff --git a/Eigen/src/SparseCore/SparsePermutation.h b/Eigen/src/SparseCore/SparsePermutation.h index 3c58e3b4f..ef38357ae 100644 --- a/Eigen/src/SparseCore/SparsePermutation.h +++ b/Eigen/src/SparseCore/SparsePermutation.h @@ -16,15 +16,17 @@ namespace Eigen { namespace internal { -template<typename MatrixType, int Side, bool Transposed> -struct permutation_matrix_product<MatrixType, Side, Transposed, SparseShape> +template<typename ExpressionType, int Side, bool Transposed> +struct permutation_matrix_product<ExpressionType, Side, Transposed, SparseShape> { - typedef typename remove_all<typename MatrixType::Nested>::type MatrixTypeNestedCleaned; - typedef typename MatrixTypeNestedCleaned::Scalar Scalar; - typedef typename MatrixTypeNestedCleaned::StorageIndex StorageIndex; + typedef typename nested_eval<ExpressionType, 1>::type MatrixType; + typedef typename remove_all<MatrixType>::type MatrixTypeCleaned; + + typedef typename MatrixTypeCleaned::Scalar Scalar; + typedef typename MatrixTypeCleaned::StorageIndex StorageIndex; enum { - SrcStorageOrder = MatrixTypeNestedCleaned::Flags&RowMajorBit ? RowMajor : ColMajor, + SrcStorageOrder = MatrixTypeCleaned::Flags&RowMajorBit ? RowMajor : ColMajor, MoveOuter = SrcStorageOrder==RowMajor ? Side==OnTheLeft : Side==OnTheRight }; @@ -33,8 +35,9 @@ struct permutation_matrix_product<MatrixType, Side, Transposed, SparseShape> SparseMatrix<Scalar,int(SrcStorageOrder)==RowMajor?ColMajor:RowMajor,StorageIndex> >::type ReturnType; template<typename Dest,typename PermutationType> - static inline void run(Dest& dst, const PermutationType& perm, const MatrixType& mat) + static inline void run(Dest& dst, const PermutationType& perm, const ExpressionType& xpr) { + MatrixType mat(xpr); if(MoveOuter) { SparseMatrix<Scalar,SrcStorageOrder,StorageIndex> tmp(mat.rows(), mat.cols()); @@ -50,7 +53,7 @@ struct permutation_matrix_product<MatrixType, Side, Transposed, SparseShape> Index jp = perm.indices().coeff(j); Index jsrc = ((Side==OnTheRight) ^ Transposed) ? jp : j; Index jdst = ((Side==OnTheLeft) ^ Transposed) ? jp : j; - for(typename MatrixTypeNestedCleaned::InnerIterator it(mat,jsrc); it; ++it) + for(typename MatrixTypeCleaned::InnerIterator it(mat,jsrc); it; ++it) tmp.insertByOuterInner(jdst,it.index()) = it.value(); } dst = tmp; @@ -67,11 +70,11 @@ struct permutation_matrix_product<MatrixType, Side, Transposed, SparseShape> perm_cpy = perm.transpose(); for(Index j=0; j<mat.outerSize(); ++j) - for(typename MatrixTypeNestedCleaned::InnerIterator it(mat,j); it; ++it) + for(typename MatrixTypeCleaned::InnerIterator it(mat,j); it; ++it) sizes[perm_cpy.indices().coeff(it.index())]++; tmp.reserve(sizes); for(Index j=0; j<mat.outerSize(); ++j) - for(typename MatrixTypeNestedCleaned::InnerIterator it(mat,j); it; ++it) + for(typename MatrixTypeCleaned::InnerIterator it(mat,j); it; ++it) tmp.insertByOuterInner(perm_cpy.indices().coeff(it.index()),j) = it.value(); dst = tmp; } @@ -90,40 +93,48 @@ template <int ProductTag> struct product_promote_storage_type<PermutationStorage // whereas it should be correctly handled by traits<Product<> >::PlainObject template<typename Lhs, typename Rhs, int ProductTag> -struct product_evaluator<Product<Lhs, Rhs, AliasFreeProduct>, ProductTag, PermutationShape, SparseShape, typename traits<Lhs>::Scalar, typename traits<Rhs>::Scalar> - : public evaluator<typename permutation_matrix_product<Rhs,OnTheRight,false,SparseShape>::ReturnType> +struct product_evaluator<Product<Lhs, Rhs, AliasFreeProduct>, ProductTag, PermutationShape, SparseShape> + : public evaluator<typename permutation_matrix_product<Rhs,OnTheLeft,false,SparseShape>::ReturnType> { typedef Product<Lhs, Rhs, AliasFreeProduct> XprType; - typedef typename permutation_matrix_product<Rhs,OnTheRight,false,SparseShape>::ReturnType PlainObject; + typedef typename permutation_matrix_product<Rhs,OnTheLeft,false,SparseShape>::ReturnType PlainObject; typedef evaluator<PlainObject> Base; + enum { + Flags = Base::Flags | EvalBeforeNestingBit + }; + explicit product_evaluator(const XprType& xpr) : m_result(xpr.rows(), xpr.cols()) { ::new (static_cast<Base*>(this)) Base(m_result); generic_product_impl<Lhs, Rhs, PermutationShape, SparseShape, ProductTag>::evalTo(m_result, xpr.lhs(), xpr.rhs()); } - -protected: + +protected: PlainObject m_result; }; template<typename Lhs, typename Rhs, int ProductTag> -struct product_evaluator<Product<Lhs, Rhs, AliasFreeProduct>, ProductTag, SparseShape, PermutationShape, typename traits<Lhs>::Scalar, typename traits<Rhs>::Scalar> +struct product_evaluator<Product<Lhs, Rhs, AliasFreeProduct>, ProductTag, SparseShape, PermutationShape > : public evaluator<typename permutation_matrix_product<Lhs,OnTheRight,false,SparseShape>::ReturnType> { typedef Product<Lhs, Rhs, AliasFreeProduct> XprType; typedef typename permutation_matrix_product<Lhs,OnTheRight,false,SparseShape>::ReturnType PlainObject; typedef evaluator<PlainObject> Base; + enum { + Flags = Base::Flags | EvalBeforeNestingBit + }; + explicit product_evaluator(const XprType& xpr) : m_result(xpr.rows(), xpr.cols()) { ::new (static_cast<Base*>(this)) Base(m_result); generic_product_impl<Lhs, Rhs, SparseShape, PermutationShape, ProductTag>::evalTo(m_result, xpr.lhs(), xpr.rhs()); } - -protected: + +protected: PlainObject m_result; }; @@ -132,34 +143,34 @@ protected: /** \returns the matrix with the permutation applied to the columns */ template<typename SparseDerived, typename PermDerived> -inline const Product<SparseDerived, PermDerived> +inline const Product<SparseDerived, PermDerived, AliasFreeProduct> operator*(const SparseMatrixBase<SparseDerived>& matrix, const PermutationBase<PermDerived>& perm) -{ return Product<SparseDerived, PermDerived>(matrix.derived(), perm.derived()); } +{ return Product<SparseDerived, PermDerived, AliasFreeProduct>(matrix.derived(), perm.derived()); } /** \returns the matrix with the permutation applied to the rows */ template<typename SparseDerived, typename PermDerived> -inline const Product<PermDerived, SparseDerived> +inline const Product<PermDerived, SparseDerived, AliasFreeProduct> operator*( const PermutationBase<PermDerived>& perm, const SparseMatrixBase<SparseDerived>& matrix) -{ return Product<PermDerived, SparseDerived>(perm.derived(), matrix.derived()); } +{ return Product<PermDerived, SparseDerived, AliasFreeProduct>(perm.derived(), matrix.derived()); } /** \returns the matrix with the inverse permutation applied to the columns. */ template<typename SparseDerived, typename PermutationType> -inline const Product<SparseDerived, Inverse<PermutationType > > +inline const Product<SparseDerived, Inverse<PermutationType>, AliasFreeProduct> operator*(const SparseMatrixBase<SparseDerived>& matrix, const InverseImpl<PermutationType, PermutationStorage>& tperm) { - return Product<SparseDerived, Inverse<PermutationType> >(matrix.derived(), tperm.derived()); + return Product<SparseDerived, Inverse<PermutationType>, AliasFreeProduct>(matrix.derived(), tperm.derived()); } /** \returns the matrix with the inverse permutation applied to the rows. */ template<typename SparseDerived, typename PermutationType> -inline const Product<Inverse<PermutationType>, SparseDerived> +inline const Product<Inverse<PermutationType>, SparseDerived, AliasFreeProduct> operator*(const InverseImpl<PermutationType,PermutationStorage>& tperm, const SparseMatrixBase<SparseDerived>& matrix) { - return Product<Inverse<PermutationType>, SparseDerived>(tperm.derived(), matrix.derived()); + return Product<Inverse<PermutationType>, SparseDerived, AliasFreeProduct>(tperm.derived(), matrix.derived()); } } // end namespace Eigen diff --git a/test/sparse_permutations.cpp b/test/sparse_permutations.cpp index dec586776..c2e1d84a3 100644 --- a/test/sparse_permutations.cpp +++ b/test/sparse_permutations.cpp @@ -1,14 +1,46 @@ // This file is part of Eigen, a lightweight C++ template library // for linear algebra. // -// Copyright (C) 2011 Gael Guennebaud <gael.guennebaud@inria.fr> +// Copyright (C) 2011-2015 Gael Guennebaud <gael.guennebaud@inria.fr> // // This Source Code Form is subject to the terms of the Mozilla // Public License v. 2.0. If a copy of the MPL was not distributed // with this file, You can obtain one at http://mozilla.org/MPL/2.0/. + +static long int nb_transposed_copies; +#define EIGEN_SPARSE_TRANSPOSED_COPY_PLUGIN {nb_transposed_copies++;} +#define VERIFY_TRANSPOSITION_COUNT(XPR,N) {\ + nb_transposed_copies = 0; \ + XPR; \ + if(nb_transposed_copies!=N) std::cerr << "nb_transposed_copies == " << nb_transposed_copies << "\n"; \ + VERIFY( (#XPR) && nb_transposed_copies==N ); \ + } + #include "sparse.h" +template<typename T> +bool is_sorted(const T& mat) { + for(Index k = 0; k<mat.outerSize(); ++k) + { + Index prev = -1; + for(typename T::InnerIterator it(mat,k); it; ++it) + { + if(prev>=it.index()) + return false; + prev = it.index(); + } + } + return true; +} + +template<typename T> +typename internal::nested_eval<T,1>::type eval(const T &xpr) +{ + VERIFY( int(internal::nested_eval<T,1>::type::Flags&RowMajorBit) == int(internal::evaluator<T>::Flags&RowMajorBit) ); + return xpr; +} + template<int OtherStorage, typename SparseMatrixType> void sparse_permutations(const SparseMatrixType& ref) { const Index rows = ref.rows(); @@ -18,6 +50,8 @@ template<int OtherStorage, typename SparseMatrixType> void sparse_permutations(c typedef SparseMatrix<Scalar, OtherStorage, StorageIndex> OtherSparseMatrixType; typedef Matrix<Scalar,Dynamic,Dynamic> DenseMatrix; typedef Matrix<StorageIndex,Dynamic,1> VectorI; +// bool IsRowMajor1 = SparseMatrixType::IsRowMajor; +// bool IsRowMajor2 = OtherSparseMatrixType::IsRowMajor; double density = (std::max)(8./(rows*cols), 0.01); @@ -42,58 +76,69 @@ template<int OtherStorage, typename SparseMatrixType> void sparse_permutations(c randomPermutationVector(pi, cols); p.indices() = pi; - res = mat*p; + VERIFY( is_sorted( eval(mat*p) )); + VERIFY( is_sorted( res = mat*p )); + VERIFY_TRANSPOSITION_COUNT( eval(mat*p), 0); + //VERIFY_TRANSPOSITION_COUNT( res = mat*p, IsRowMajor ? 1 : 0 ); res_d = mat_d*p; VERIFY(res.isApprox(res_d) && "mat*p"); - res = p*mat; + VERIFY( is_sorted( eval(p*mat) )); + VERIFY( is_sorted( res = p*mat )); + VERIFY_TRANSPOSITION_COUNT( eval(p*mat), 0); res_d = p*mat_d; VERIFY(res.isApprox(res_d) && "p*mat"); - res = mat*p.inverse(); + VERIFY( is_sorted( (mat*p).eval() )); + VERIFY( is_sorted( res = mat*p.inverse() )); + VERIFY_TRANSPOSITION_COUNT( eval(mat*p.inverse()), 0); res_d = mat*p.inverse(); VERIFY(res.isApprox(res_d) && "mat*inv(p)"); - res = p.inverse()*mat; + VERIFY( is_sorted( (p*mat+p*mat).eval() )); + VERIFY( is_sorted( res = p.inverse()*mat )); + VERIFY_TRANSPOSITION_COUNT( eval(p.inverse()*mat), 0); res_d = p.inverse()*mat_d; VERIFY(res.isApprox(res_d) && "inv(p)*mat"); - res = mat.twistedBy(p); + VERIFY( is_sorted( (p * mat * p.inverse()).eval() )); + VERIFY( is_sorted( res = mat.twistedBy(p) )); + VERIFY_TRANSPOSITION_COUNT( eval(p * mat * p.inverse()), 0); res_d = (p * mat_d) * p.inverse(); VERIFY(res.isApprox(res_d) && "p*mat*inv(p)"); - res = mat.template selfadjointView<Upper>().twistedBy(p_null); + VERIFY( is_sorted( res = mat.template selfadjointView<Upper>().twistedBy(p_null) )); res_d = up_sym_d; VERIFY(res.isApprox(res_d) && "full selfadjoint upper to full"); - res = mat.template selfadjointView<Lower>().twistedBy(p_null); + VERIFY( is_sorted( res = mat.template selfadjointView<Lower>().twistedBy(p_null) )); res_d = lo_sym_d; VERIFY(res.isApprox(res_d) && "full selfadjoint lower to full"); - res = up.template selfadjointView<Upper>().twistedBy(p_null); + VERIFY( is_sorted( res = up.template selfadjointView<Upper>().twistedBy(p_null) )); res_d = up_sym_d; VERIFY(res.isApprox(res_d) && "upper selfadjoint to full"); - res = lo.template selfadjointView<Lower>().twistedBy(p_null); + VERIFY( is_sorted( res = lo.template selfadjointView<Lower>().twistedBy(p_null) )); res_d = lo_sym_d; VERIFY(res.isApprox(res_d) && "lower selfadjoint full"); - res = mat.template selfadjointView<Upper>(); + VERIFY( is_sorted( res = mat.template selfadjointView<Upper>() )); res_d = up_sym_d; VERIFY(res.isApprox(res_d) && "full selfadjoint upper to full"); - res = mat.template selfadjointView<Lower>(); + VERIFY( is_sorted( res = mat.template selfadjointView<Lower>() )); res_d = lo_sym_d; VERIFY(res.isApprox(res_d) && "full selfadjoint lower to full"); - res = up.template selfadjointView<Upper>(); + VERIFY( is_sorted( res = up.template selfadjointView<Upper>() )); res_d = up_sym_d; VERIFY(res.isApprox(res_d) && "upper selfadjoint to full"); - res = lo.template selfadjointView<Lower>(); + VERIFY( is_sorted( res = lo.template selfadjointView<Lower>() )); res_d = lo_sym_d; VERIFY(res.isApprox(res_d) && "lower selfadjoint full"); @@ -150,19 +195,19 @@ template<int OtherStorage, typename SparseMatrixType> void sparse_permutations(c VERIFY(res.isApprox(res_d) && "upper selfadjoint twisted to lower"); - res = mat.template selfadjointView<Upper>().twistedBy(p); + VERIFY( is_sorted( res = mat.template selfadjointView<Upper>().twistedBy(p) )); res_d = (p * up_sym_d) * p.inverse(); VERIFY(res.isApprox(res_d) && "full selfadjoint upper twisted to full"); - res = mat.template selfadjointView<Lower>().twistedBy(p); + VERIFY( is_sorted( res = mat.template selfadjointView<Lower>().twistedBy(p) )); res_d = (p * lo_sym_d) * p.inverse(); VERIFY(res.isApprox(res_d) && "full selfadjoint lower twisted to full"); - res = up.template selfadjointView<Upper>().twistedBy(p); + VERIFY( is_sorted( res = up.template selfadjointView<Upper>().twistedBy(p) )); res_d = (p * up_sym_d) * p.inverse(); VERIFY(res.isApprox(res_d) && "upper selfadjoint twisted to full"); - res = lo.template selfadjointView<Lower>().twistedBy(p); + VERIFY( is_sorted( res = lo.template selfadjointView<Lower>().twistedBy(p) )); res_d = (p * lo_sym_d) * p.inverse(); VERIFY(res.isApprox(res_d) && "lower selfadjoint twisted to full"); } @@ -182,4 +227,10 @@ void test_sparse_permutations() CALL_SUBTEST_1(( sparse_permutations_all<double>(s) )); CALL_SUBTEST_2(( sparse_permutations_all<std::complex<double> >(s) )); } + + VERIFY((internal::is_same<typename internal::permutation_matrix_product<SparseMatrix<double>,OnTheRight,false,SparseShape>::ReturnType, + typename internal::nested_eval<Product<SparseMatrix<double>,PermutationMatrix<Dynamic,Dynamic>,AliasFreeProduct>,1>::type>::value)); + + VERIFY((internal::is_same<typename internal::permutation_matrix_product<SparseMatrix<double>,OnTheLeft,false,SparseShape>::ReturnType, + typename internal::nested_eval<Product<PermutationMatrix<Dynamic,Dynamic>,SparseMatrix<double>,AliasFreeProduct>,1>::type>::value)); } |