blob: bbb6f5cf7ca42a1eb2d21ac610c7cfec53a0e916 [file] [edit]
// This file is part of Eigen, a lightweight C++ template library
// for linear algebra.
//
// 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/.
// SPDX-License-Identifier: 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); \
}
static long int nb_temporaries;
#define EIGEN_SPARSE_CREATE_TEMPORARY_PLUGIN \
{ nb_temporaries++; }
#define VERIFY_TEMPORARY_COUNT(XPR, N) \
{ \
nb_temporaries = 0; \
XPR; \
if (nb_temporaries != N) std::cerr << "nb_temporaries == " << nb_temporaries << "\n"; \
VERIFY((#XPR) && nb_temporaries == N); \
}
#include "sparse.h"
#include "sparse_test_helpers.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();
const Index cols = ref.cols();
using Scalar = typename SparseMatrixType::Scalar;
using StorageIndex = typename SparseMatrixType::StorageIndex;
using OtherSparseMatrixType = SparseMatrix<Scalar, OtherStorage, StorageIndex>;
using DenseMatrix = Matrix<Scalar, Dynamic, Dynamic>;
using VectorI = Matrix<StorageIndex, Dynamic, 1>;
// bool IsRowMajor1 = SparseMatrixType::IsRowMajor;
// bool IsRowMajor2 = OtherSparseMatrixType::IsRowMajor;
double density = (std::max)(8. / static_cast<double>(rows * cols), 0.01);
SparseMatrixType mat(rows, cols), up(rows, cols), lo(rows, cols);
OtherSparseMatrixType res;
DenseMatrix mat_d = DenseMatrix::Zero(rows, cols), up_sym_d, lo_sym_d, res_d;
initSparse<Scalar>(density, mat_d, mat, 0);
up = mat.template triangularView<Upper>();
lo = mat.template triangularView<Lower>();
up_sym_d = mat_d.template selfadjointView<Upper>();
lo_sym_d = mat_d.template selfadjointView<Lower>();
VERIFY_IS_APPROX(mat, mat_d);
VERIFY_IS_APPROX(up, DenseMatrix(mat_d.template triangularView<Upper>()));
VERIFY_IS_APPROX(lo, DenseMatrix(mat_d.template triangularView<Lower>()));
PermutationMatrix<Dynamic> p, p_null;
VectorI pi;
randomPermutationVector(pi, cols);
p.indices() = pi;
VERIFY(is_sorted(::eval(mat * p)));
VERIFY(is_sorted(res = mat * p));
VERIFY_TRANSPOSITION_COUNT(::eval(mat * p), 0);
VERIFY_TEMPORARY_COUNT(::eval(mat * p), 1)
res_d = mat_d * p;
VERIFY(res.isApprox(res_d) && "mat*p");
VERIFY(is_sorted(::eval(p * mat)));
VERIFY(is_sorted(res = p * mat));
VERIFY_TRANSPOSITION_COUNT(::eval(p * mat), 0);
VERIFY_TEMPORARY_COUNT(::eval(p * mat), 1);
res_d = p * mat_d;
VERIFY(res.isApprox(res_d) && "p*mat");
VERIFY(is_sorted((mat * p).eval()));
VERIFY(is_sorted(res = mat * p.inverse()));
VERIFY_TRANSPOSITION_COUNT(::eval(mat * p.inverse()), 0);
VERIFY_TEMPORARY_COUNT(::eval(mat * p.inverse()), 1);
res_d = mat * p.inverse();
VERIFY(res.isApprox(res_d) && "mat*inv(p)");
VERIFY(is_sorted((p * mat + p * mat).eval()));
VERIFY(is_sorted(res = p.inverse() * mat));
VERIFY_TRANSPOSITION_COUNT(::eval(p.inverse() * mat), 0);
VERIFY_TEMPORARY_COUNT(::eval(p.inverse() * mat), 1);
res_d = p.inverse() * mat_d;
VERIFY(res.isApprox(res_d) && "inv(p)*mat");
//
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)");
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");
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");
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");
VERIFY(is_sorted(res = lo.template selfadjointView<Lower>().twistedBy(p_null)));
res_d = lo_sym_d;
VERIFY(res.isApprox(res_d) && "lower selfadjoint full");
VERIFY(is_sorted(res = mat.template selfadjointView<Upper>()));
res_d = up_sym_d;
VERIFY(res.isApprox(res_d) && "full selfadjoint upper to full");
VERIFY(is_sorted(res = mat.template selfadjointView<Lower>()));
res_d = lo_sym_d;
VERIFY(res.isApprox(res_d) && "full selfadjoint lower to full");
VERIFY(is_sorted(res = up.template selfadjointView<Upper>()));
res_d = up_sym_d;
VERIFY(res.isApprox(res_d) && "upper selfadjoint to full");
VERIFY(is_sorted(res = lo.template selfadjointView<Lower>()));
res_d = lo_sym_d;
VERIFY(res.isApprox(res_d) && "lower selfadjoint full");
res.template selfadjointView<Upper>() = mat.template selfadjointView<Upper>();
res_d = up_sym_d.template triangularView<Upper>();
VERIFY(res.isApprox(res_d) && "full selfadjoint upper to upper");
res.template selfadjointView<Lower>() = mat.template selfadjointView<Upper>();
res_d = up_sym_d.template triangularView<Lower>();
VERIFY(res.isApprox(res_d) && "full selfadjoint upper to lower");
res.template selfadjointView<Upper>() = mat.template selfadjointView<Lower>();
res_d = lo_sym_d.template triangularView<Upper>();
VERIFY(res.isApprox(res_d) && "full selfadjoint lower to upper");
res.template selfadjointView<Lower>() = mat.template selfadjointView<Lower>();
res_d = lo_sym_d.template triangularView<Lower>();
VERIFY(res.isApprox(res_d) && "full selfadjoint lower to lower");
res.template selfadjointView<Upper>() = mat.template selfadjointView<Upper>().twistedBy(p);
res_d = ((p * up_sym_d) * p.inverse()).eval().template triangularView<Upper>();
VERIFY(res.isApprox(res_d) && "full selfadjoint upper twisted to upper");
res.template selfadjointView<Upper>() = mat.template selfadjointView<Lower>().twistedBy(p);
res_d = ((p * lo_sym_d) * p.inverse()).eval().template triangularView<Upper>();
VERIFY(res.isApprox(res_d) && "full selfadjoint lower twisted to upper");
res.template selfadjointView<Lower>() = mat.template selfadjointView<Lower>().twistedBy(p);
res_d = ((p * lo_sym_d) * p.inverse()).eval().template triangularView<Lower>();
VERIFY(res.isApprox(res_d) && "full selfadjoint lower twisted to lower");
res.template selfadjointView<Lower>() = mat.template selfadjointView<Upper>().twistedBy(p);
res_d = ((p * up_sym_d) * p.inverse()).eval().template triangularView<Lower>();
VERIFY(res.isApprox(res_d) && "full selfadjoint upper twisted to lower");
res.template selfadjointView<Upper>() = up.template selfadjointView<Upper>().twistedBy(p);
res_d = ((p * up_sym_d) * p.inverse()).eval().template triangularView<Upper>();
VERIFY(res.isApprox(res_d) && "upper selfadjoint twisted to upper");
res.template selfadjointView<Upper>() = lo.template selfadjointView<Lower>().twistedBy(p);
res_d = ((p * lo_sym_d) * p.inverse()).eval().template triangularView<Upper>();
VERIFY(res.isApprox(res_d) && "lower selfadjoint twisted to upper");
res.template selfadjointView<Lower>() = lo.template selfadjointView<Lower>().twistedBy(p);
res_d = ((p * lo_sym_d) * p.inverse()).eval().template triangularView<Lower>();
VERIFY(res.isApprox(res_d) && "lower selfadjoint twisted to lower");
res.template selfadjointView<Lower>() = up.template selfadjointView<Upper>().twistedBy(p);
res_d = ((p * up_sym_d) * p.inverse()).eval().template triangularView<Lower>();
VERIFY(res.isApprox(res_d) && "upper selfadjoint twisted to lower");
// A symmetric matrix with both triangles stored, viewed as Upper | Lower: only one triangle may be copied, so
// each off-diagonal entry appears once.
const SparseMatrixType sym = mat + SparseMatrixType(mat.adjoint());
const DenseMatrix sym_d = mat_d + mat_d.adjoint();
const DenseMatrix sym_twisted_d = ((p * sym_d) * p.inverse()).eval();
Index sym_triangle_nonzeros = 0;
for (Index k = 0; k < sym.outerSize(); ++k)
for (typename SparseMatrixType::InnerIterator it(sym, k); it; ++it)
if (it.row() <= it.col()) ++sym_triangle_nonzeros;
res.template selfadjointView<Upper>() = sym.template selfadjointView<Upper | Lower>().twistedBy(p_null);
res_d = sym_d.template triangularView<Upper>();
VERIFY(res.isApprox(res_d) && "both selfadjoint to upper");
VERIFY_IS_EQUAL(res.nonZeros(), sym_triangle_nonzeros);
res.template selfadjointView<Lower>() = sym.template selfadjointView<Upper | Lower>().twistedBy(p_null);
res_d = sym_d.template triangularView<Lower>();
VERIFY(res.isApprox(res_d) && "both selfadjoint to lower");
VERIFY_IS_EQUAL(res.nonZeros(), sym_triangle_nonzeros);
res.template selfadjointView<Upper>() = sym.template selfadjointView<Upper | Lower>().twistedBy(p);
res_d = sym_twisted_d.template triangularView<Upper>();
VERIFY(res.isApprox(res_d) && "both selfadjoint twisted to upper");
VERIFY_IS_EQUAL(res.nonZeros(), sym_triangle_nonzeros);
res.template selfadjointView<Lower>() = sym.template selfadjointView<Upper | Lower>().twistedBy(p);
res_d = sym_twisted_d.template triangularView<Lower>();
VERIFY(res.isApprox(res_d) && "both selfadjoint twisted to lower");
VERIFY_IS_EQUAL(res.nonZeros(), sym_triangle_nonzeros);
VERIFY(is_sorted(res = sym.template selfadjointView<Upper | Lower>().twistedBy(p)));
VERIFY(res.isApprox(sym_twisted_d) && "both selfadjoint twisted to full");
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");
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");
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");
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");
}
// A narrow StorageIndex bounds the stored indices, not the dimensions: n exceeds its range, while every stored index
// fits. The storage-order copy and both selfadjoint copies visit all n outer vectors.
template <int SrcOrder, int DstOrder>
void sparse_permutations_narrow_index() {
using StorageIndex = short;
using DstMatrix = SparseMatrix<double, DstOrder, StorageIndex>;
const Index n = Index(NumTraits<StorageIndex>::highest()) + 1000;
const std::vector<Triplet<double, StorageIndex>> entries = {{1, 1, 1.0}, {3, 1, 2.0}};
SparseMatrix<double, SrcOrder, StorageIndex> lower(n, n);
lower.setFromTriplets(entries.begin(), entries.end());
const DstMatrix copy = lower;
VERIFY_IS_EQUAL(copy.nonZeros(), 2);
VERIFY_IS_EQUAL(copy.coeff(1, 1), 1.0);
VERIFY_IS_EQUAL(copy.coeff(3, 1), 2.0);
const DstMatrix full = lower.template selfadjointView<Lower>();
VERIFY_IS_EQUAL(full.nonZeros(), 3);
VERIFY_IS_EQUAL(full.coeff(1, 1), 1.0);
VERIFY_IS_EQUAL(full.coeff(3, 1), 2.0);
VERIFY_IS_EQUAL(full.coeff(1, 3), 2.0);
VERIFY(is_sorted(full));
DstMatrix upper(n, n);
upper.template selfadjointView<Upper>() = lower.template selfadjointView<Lower>();
VERIFY_IS_EQUAL(upper.nonZeros(), 2);
VERIFY_IS_EQUAL(upper.coeff(1, 1), 1.0);
VERIFY_IS_EQUAL(upper.coeff(1, 3), 2.0);
// An entry in an outer vector beyond highest(): only its inner index has to fit, in the source and the destination.
constexpr int SrcMode = SrcOrder == ColMajor ? Upper : Lower;
constexpr int DstMode = DstOrder == ColMajor ? Upper : Lower;
const Index last = n - 1;
SparseMatrix<double, SrcOrder, StorageIndex> far(n, n);
insert_by_outer(far, last, 1) = 2.0;
far.makeCompressed();
DstMatrix dst(n, n);
dst.template selfadjointView<DstMode>() = far.template selfadjointView<SrcMode>();
VERIFY_IS_EQUAL(dst.nonZeros(), 1);
VERIFY_IS_EQUAL(coeff_by_outer(dst, last, 1), 2.0);
// Viewed as Upper | Lower, the full copy keeps the entry in its outer vector, so with matching storage orders its
// inner index still fits.
if (int(SrcOrder) == int(DstOrder)) {
const DstMatrix farFull = far.template selfadjointView<Upper | Lower>();
VERIFY_IS_EQUAL(farFull.nonZeros(), 1);
VERIFY_IS_EQUAL(coeff_by_outer(farFull, last, 1), 2.0);
}
}
template <typename Scalar>
void sparse_permutations_all(int size) {
CALL_SUBTEST((sparse_permutations<ColMajor>(SparseMatrix<Scalar, ColMajor>(size, size))));
CALL_SUBTEST((sparse_permutations<ColMajor>(SparseMatrix<Scalar, RowMajor>(size, size))));
CALL_SUBTEST((sparse_permutations<RowMajor>(SparseMatrix<Scalar, ColMajor>(size, size))));
CALL_SUBTEST((sparse_permutations<RowMajor>(SparseMatrix<Scalar, RowMajor>(size, size))));
}
// Products of permutations with a sparse matrix and with products of one, for both storage orders of the matrix and of
// the destination, against a dense reference.
template <int SrcOrder, int DstOrder>
void sparse_permutation_products() {
using SrcMatrix = SparseMatrix<double, SrcOrder>;
using DstMatrix = SparseMatrix<double, DstOrder>;
using DenseMat = Matrix<double, Dynamic, Dynamic>;
using Perm = PermutationMatrix<Dynamic, Dynamic, int>;
const Index n = internal::random<Index>(1, 20);
DenseMat D = (DenseMat::Random(n, n).array().abs() < 0.3).select(DenseMat::Random(n, n), 0.0);
SrcMatrix A = D.sparseView();
Perm p(n), q(n);
p.setIdentity();
q.setIdentity();
for (Index i = 0; i < n; ++i) {
std::swap(p.indices()(i), p.indices()(internal::random<Index>(0, n - 1)));
std::swap(q.indices()(i), q.indices()(internal::random<Index>(0, n - 1)));
}
const DenseMat P = p.toDenseMatrix().cast<double>(), Q = q.toDenseMatrix().cast<double>();
DstMatrix R;
auto check = [&](const DenseMat& expected) {
VERIFY(is_sorted(R));
VERIFY_IS_APPROX(DenseMat(R), expected);
};
R = p * A;
check(P * D);
R = A * q;
check(D * Q);
R = p.inverse() * A;
check(P.transpose() * D);
R = A * q.transpose();
check(D * Q.transpose());
R = p * A * q;
check(P * D * Q);
R = (p * A) * q;
check(P * D * Q);
R = p * (A * q);
check(P * D * Q);
R = p * A * p.transpose();
check(P * D * P.transpose());
R = p.inverse() * A * q.inverse();
check(P.transpose() * D * Q.transpose());
R = p.transpose() * (A * p);
check(P.transpose() * D * P);
R = (p * A) * p.inverse();
check(P * D * P.transpose());
R = (p * A * q) * p.inverse();
check(P * D * Q * P.transpose());
R = p * (2.0 * A) * q;
check(P * (2.0 * D) * Q);
R = (A * q).eval() * p;
check(D * Q * P);
R = A.twistedBy(p);
check(P * D * P.transpose());
}
EIGEN_DECLARE_TEST(sparse_permutations) {
for (int i = 0; i < g_repeat; i++) {
int s = Eigen::internal::random<int>(1, 50);
CALL_SUBTEST_1((sparse_permutations_all<double>(s)));
CALL_SUBTEST_2((sparse_permutations_all<std::complex<double>>(s)));
}
for (int i = 0; i < g_repeat; i++) {
CALL_SUBTEST_1((sparse_permutation_products<ColMajor, ColMajor>()));
CALL_SUBTEST_1((sparse_permutation_products<ColMajor, RowMajor>()));
CALL_SUBTEST_1((sparse_permutation_products<RowMajor, ColMajor>()));
CALL_SUBTEST_1((sparse_permutation_products<RowMajor, RowMajor>()));
}
CALL_SUBTEST_1((sparse_permutations_narrow_index<ColMajor, ColMajor>()));
CALL_SUBTEST_1((sparse_permutations_narrow_index<ColMajor, RowMajor>()));
CALL_SUBTEST_1((sparse_permutations_narrow_index<RowMajor, ColMajor>()));
CALL_SUBTEST_1((sparse_permutations_narrow_index<RowMajor, RowMajor>()));
VERIFY((std::is_same<
internal::permutation_matrix_product<SparseMatrix<double>, OnTheRight, false, SparseShape>::ReturnType,
internal::nested_eval<Product<SparseMatrix<double>, PermutationMatrix<Dynamic, Dynamic>, AliasFreeProduct>,
1>::type>::value));
VERIFY((std::is_same<
internal::permutation_matrix_product<SparseMatrix<double>, OnTheLeft, false, SparseShape>::ReturnType,
internal::nested_eval<Product<PermutationMatrix<Dynamic, Dynamic>, SparseMatrix<double>, AliasFreeProduct>,
1>::type>::value));
}