blob: cd64d836380b544a3951f9b266b4e4d29424f013 [file] [edit]
// SPDX-FileCopyrightText: The Eigen Authors
// SPDX-License-Identifier: MPL-2.0
#define TEST_ENABLE_TEMPORARY_TRACKING
#define TEST_IGNORE_STACK_ALLOCATED_TEMPORARY
#include "main.h"
#include <Eigen/SparseCore>
#include "NonCommutativeScalar.h"
template <typename Matrix, typename Expression>
void check_indexed_update(const Matrix& input, const Matrix& expected, const Expression& expression, int allocations) {
Matrix dst = Matrix::Constant(expected.rows(), expected.cols(), typename Matrix::Scalar(3));
const Matrix initial = dst;
VERIFY_EVALUATION_COUNT((dst.noalias() += expression), allocations);
VERIFY_IS_APPROX(dst, (initial + expected).eval());
VERIFY_EVALUATION_COUNT((dst.noalias() -= expression), allocations);
VERIFY_IS_APPROX(dst, initial);
Matrix padded = Matrix::Zero(expected.rows() + 2, expected.cols() + 2);
auto block = padded.block(1, 1, expected.rows(), expected.cols());
VERIFY_EVALUATION_COUNT((block.noalias() += expression), allocations);
VERIFY_IS_APPROX(block, expected);
VERIFY_EVALUATION_COUNT((block.noalias() -= expression), allocations);
VERIFY(padded.isZero(0));
dst.noalias() = expression;
VERIFY_IS_APPROX(dst, expected);
EIGEN_UNUSED_VARIABLE(input);
}
template <typename Scalar, int Order>
void permutation_updates() {
using Matrix = Eigen::Matrix<Scalar, Dynamic, Dynamic, Order>;
for (Index n : {Index(0), Index(1), Index(7), Index(24)}) {
PermutationMatrix<Dynamic> p(n);
p.setIdentity();
for (Index i = 0; i < n; ++i) p.applyTranspositionOnTheRight(i, internal::random<Index>(i, n - 1));
const Matrix a = Matrix::Random(n, n + 3), b = Matrix::Random(n + 3, n);
Matrix left(n, n + 3), inverseLeft(n, n + 3), right(n + 3, n), inverseRight(n + 3, n);
for (Index i = 0; i < n; ++i)
for (Index j = 0; j < n + 3; ++j) {
left(p.indices()(i), j) = a(i, j);
inverseLeft(i, j) = a(p.indices()(i), j);
right(j, i) = b(j, p.indices()(i));
inverseRight(j, p.indices()(i)) = b(j, i);
}
const auto check = [&](const Matrix& input, const Matrix& expected, const auto& makeProduct) {
check_indexed_update(input, expected, makeProduct(input), 0);
Matrix alias = input;
alias += makeProduct(alias);
VERIFY_IS_APPROX(alias, (input + expected).eval());
alias = input;
alias -= makeProduct(alias);
VERIFY_IS_APPROX(alias, (input - expected).eval());
};
check(a, left, [&](const auto& x) { return p * x; });
check(a, inverseLeft, [&](const auto& x) { return p.inverse() * x; });
check(b, right, [&](const auto& x) { return x * p; });
check(b, inverseRight, [&](const auto& x) { return x * p.inverse(); });
check_indexed_update(a, left, p * a.block(0, 0, n, n + 3), 0);
check_indexed_update(a, Matrix(inverseRight.transpose()), p * b.transpose(), 0);
check_indexed_update(b, Matrix(inverseLeft.transpose()), a.transpose() * p, 0);
check_indexed_update(a, Matrix(left + left), p * (a + a), 0);
const Map<const Matrix, Unaligned, Stride<Dynamic, Dynamic>> mapped(
a.data(), a.rows(), a.cols(), Stride<Dynamic, Dynamic>(a.outerStride(), a.innerStride()));
check_indexed_update(a, left, p * mapped, 0);
SparseMatrix<Scalar, Order> sparse = a.sparseView();
Matrix dst = Matrix::Zero(n, n + 3);
dst += p * sparse;
VERIFY_IS_APPROX(dst, left);
}
}
template <typename Scalar, int Order, typename Tr>
void transposition_updates(const Tr& tr) {
using Matrix = Eigen::Matrix<Scalar, Dynamic, Dynamic, Order>;
const Index n = tr.size();
constexpr bool FitsStack = Tr::IndicesType::MaxSizeAtCompileTime != Dynamic &&
(EIGEN_STACK_ALLOCATION_LIMIT == 0 || std::size_t(Tr::IndicesType::MaxSizeAtCompileTime) <=
EIGEN_STACK_ALLOCATION_LIMIT / sizeof(Index));
const int allocations = n != 0 && !FitsStack ? 1 : 0;
const Matrix a = Matrix::Random(n, n + 3), b = Matrix::Random(n + 3, n);
const auto reference = [&](Matrix result, bool left, bool inverse) {
for (Index step = 0; step < n; ++step) {
const Index k = inverse ? n - 1 - step : step;
for (Index j = 0; j < n + 3; ++j) {
if (left)
numext::swap(result(k, j), result(tr.coeff(k), j));
else
numext::swap(result(j, k), result(j, tr.coeff(k)));
}
}
return result;
};
const auto check = [&](const Matrix& input, const Matrix& expected, const auto& makeProduct) {
check_indexed_update(input, expected, makeProduct(input), allocations);
Matrix alias = input;
alias += makeProduct(alias);
VERIFY_IS_APPROX(alias, (input + expected).eval());
alias = input;
alias -= makeProduct(alias);
VERIFY_IS_APPROX(alias, (input - expected).eval());
alias = input;
VERIFY_EVALUATION_COUNT((alias = makeProduct(alias)), 0);
VERIFY_IS_APPROX(alias, expected);
Matrix overlap = Matrix::Random(input.rows() + 1, input.cols() + 1);
const Matrix saved = overlap.block(0, 0, input.rows(), input.cols());
const Matrix product = makeProduct(saved);
Matrix expectedOverlap = overlap;
expectedOverlap.block(1, 1, input.rows(), input.cols()) += product;
overlap.block(1, 1, input.rows(), input.cols()) += makeProduct(overlap.block(0, 0, input.rows(), input.cols()));
VERIFY_IS_APPROX(overlap, expectedOverlap);
};
const auto inverse = tr.inverse();
check(a, reference(a, true, false), [&](const auto& x) { return tr * x; });
check(a, reference(a, true, true), [&](const auto& x) { return inverse * x; });
check(b, reference(b, false, false), [&](const auto& x) { return x * tr; });
check(b, reference(b, false, true), [&](const auto& x) { return x * inverse; });
}
template <typename Scalar, int Order>
void transposition_update_cases() {
for (Index n : {Index(0), Index(1), Index(7), Index(24)}) {
Transpositions<Dynamic> dynamic(n);
Transpositions<Dynamic, 32, Index> bounded(n);
for (Index i = 0; i < n; ++i) {
dynamic.coeffRef(i) = internal::convert_index<int>(internal::random<Index>(0, n - 1));
bounded.coeffRef(i) = dynamic.coeff(i);
}
transposition_updates<Scalar, Order>(dynamic);
transposition_updates<Scalar, Order>(bounded);
const Map<Transpositions<Dynamic, 32, Index>> mapped(bounded.indices().data(), n);
transposition_updates<Scalar, Order>(mapped);
}
Transpositions<7, 7, short> fixed;
for (Index i = 0; i < fixed.size(); ++i) fixed.coeffRef(i) = internal::random<short>(0, 6);
transposition_updates<Scalar, Order>(fixed);
Transpositions<Dynamic, Dynamic, signed char> narrow(129);
narrow.indices().setZero();
transposition_updates<Scalar, Order>(narrow);
Transpositions<Dynamic, 129, signed char> narrowBounded(129);
narrowBounded.indices().setZero();
transposition_updates<Scalar, Order>(narrowBounded);
}
template <typename Scalar, int Order>
void structured_permutation_updates() {
using Matrix = Eigen::Matrix<Scalar, Dynamic, Dynamic, Order>;
for (Index n : {Index(0), Index(1), Index(7), Index(24)}) {
PermutationMatrix<Dynamic> p(n);
for (Index i = 0; i < n; ++i) p.indices()(i) = internal::convert_index<int>((i + 1) % n);
Matrix a = Matrix::Random(n, n);
const auto check = [&](const auto& view, const Matrix* expectedDense = nullptr) {
const Matrix dense = expectedDense ? *expectedDense : Matrix(view);
Matrix left(n, n), right(n, n), inverseLeft(n, n), inverseRight(n, n);
for (Index i = 0; i < n; ++i)
for (Index j = 0; j < n; ++j) {
const Index k = p.indices()(i);
left(k, j) = dense(i, j);
inverseLeft(i, j) = dense(k, j);
right(j, i) = dense(j, k);
inverseRight(j, k) = dense(j, i);
}
const int allocations = n ? 1 : 0;
check_indexed_update(dense, left, p * view, allocations);
check_indexed_update(dense, inverseLeft, p.inverse() * view, allocations);
check_indexed_update(dense, right, view * p, allocations);
check_indexed_update(dense, inverseRight, view * p.inverse(), allocations);
};
check(a.template triangularView<UnitLower>());
check(a.template triangularView<StrictlyUpper>());
check(a.template selfadjointView<Lower>());
check(a.template selfadjointView<Upper>());
const Scalar alpha = Scalar(2) + internal::random<Scalar>();
// Product factor extraction scales the whole reconstructed view, including its mirrored half.
const Matrix scaled = alpha * Matrix(a.template selfadjointView<Lower>());
check((alpha * a).template selfadjointView<Lower>(), &scaled);
}
}
template <typename Scalar, int Order>
void transposition_row_wrappers() {
RowVector3i fixed;
fixed << 2, 2, 2;
const TranspositionsWrapper<RowVector3i> fixedWrapper(fixed);
transposition_updates<Scalar, Order>(fixedWrapper);
const TranspositionsWrapper<const RowVector3i> constWrapper(fixed);
transposition_updates<Scalar, Order>(constWrapper);
for (Index n : {Index(0), Index(1), Index(7)}) {
RowVectorXi dynamic(n);
for (Index i = 0; i < n; ++i) dynamic(i) = int(n - 1 - i);
const TranspositionsWrapper<RowVectorXi> dynamicWrapper(dynamic);
transposition_updates<Scalar, Order>(dynamicWrapper);
Map<RowVectorXi> mapped(dynamic.data(), n);
const TranspositionsWrapper<Map<RowVectorXi>> mappedWrapper(mapped);
transposition_updates<Scalar, Order>(mappedWrapper);
Eigen::Matrix<int, 1, Dynamic, RowMajor, 1, 7> bounded = dynamic;
const TranspositionsWrapper<decltype(bounded)> boundedWrapper(bounded);
transposition_updates<Scalar, Order>(boundedWrapper);
}
}
template <int Order>
void transposition_widened_capacity() {
// The input fits the stack limit; widening its maximum capacity to Index may not.
constexpr int Capacity = EIGEN_STACK_ALLOCATION_LIMIT == 0 ? 20000 : int(EIGEN_STACK_ALLOCATION_LIMIT / sizeof(int));
const Index n = (std::min)(Index(3), Index(Capacity));
// Wrappers avoid the owning transpositions' square-matrix traits, whose capacity squared can overflow int.
Eigen::Matrix<int, Dynamic, 1, 0, Capacity, 1> indices(n);
for (Index i = 0; i < n; ++i) indices(i) = int(n - 1 - i);
const TranspositionsWrapper<decltype(indices)> tr(indices);
transposition_updates<double, Order>(tr);
Eigen::Matrix<int, 1, Dynamic, RowMajor, 1, Capacity> row(n);
for (Index i = 0; i < n; ++i) row(i) = tr.coeff(i);
const TranspositionsWrapper<decltype(row)> wrapper(row);
transposition_updates<double, Order>(wrapper);
Eigen::Matrix<int, Capacity, 1> fixedIndices;
fixedIndices.setZero();
const TranspositionsWrapper<decltype(fixedIndices)> fixed(fixedIndices);
using Matrix = Eigen::Matrix<double, Dynamic, Dynamic, Order>;
const Matrix input = Matrix::Random(Capacity, 2);
Matrix expected = input, dst = Matrix::Zero(Capacity, 2);
for (Index i = 0; i < Capacity; ++i)
for (Index j = 0; j < 2; ++j) numext::swap(expected(i, j), expected(0, j));
constexpr bool FitsStack =
EIGEN_STACK_ALLOCATION_LIMIT == 0 || std::size_t(Capacity) <= EIGEN_STACK_ALLOCATION_LIMIT / sizeof(Index);
const int allocations = Capacity != 0 && !FitsStack ? 1 : 0;
VERIFY_EVALUATION_COUNT((dst.noalias() += fixed * input), allocations);
VERIFY_IS_EQUAL(dst, expected);
VERIFY_EVALUATION_COUNT((dst.noalias() -= fixed * input), allocations);
VERIFY(dst.isZero(0));
}
struct CountingUpdateIndex {
Index* reads;
int operator()(Index i) const {
++*reads;
return int((i + 1) % 7);
}
};
#if defined(EIGEN_TEST_PART_7) || defined(EIGEN_TEST_PART_ALL)
template <typename Tr>
void transposition_destination_aliases(const Tr& tr) {
using Matrix = Matrix4d;
const Matrix original = Matrix::Random();
for (bool subtract : {false, true}) {
const double sign = subtract ? -1.0 : 1.0;
Matrix matrix = original, expected = original;
const RowVector4d rowProduct = original.row(0) * tr;
expected.row(0) += sign * rowProduct;
if (subtract)
matrix.row(0) -= matrix.row(0) * tr;
else
matrix.row(0) += matrix.row(0) * tr;
VERIFY_IS_EQUAL(matrix, expected);
matrix = original;
expected = original;
const Vector4d columnProduct = tr * original.col(0);
expected.col(0) += sign * columnProduct;
if (subtract)
matrix.col(0) -= tr * matrix.col(0);
else
matrix.col(0) += tr * matrix.col(0);
VERIFY_IS_EQUAL(matrix, expected);
matrix = original;
const Matrix transposedProduct = tr * original.transpose();
const Matrix expectedTranspose = original.transpose() + sign * transposedProduct;
if (subtract)
matrix.transpose() -= tr * matrix.transpose();
else
matrix.transpose() += tr * matrix.transpose();
VERIFY_IS_EQUAL(Matrix(matrix.transpose()), expectedTranspose);
matrix = original;
expected = original;
const Vector4d diagonalProduct = tr * original.diagonal();
expected.diagonal() += sign * diagonalProduct;
if (subtract)
matrix.diagonal() -= tr * matrix.diagonal();
else
matrix.diagonal() += tr * matrix.diagonal();
VERIFY_IS_EQUAL(matrix, expected);
matrix = original;
Ref<Matrix> reference(matrix);
const Matrix product = tr * original;
if (subtract)
reference -= tr * reference;
else
reference += tr * reference;
VERIFY_IS_EQUAL(matrix, Matrix(original + sign * product));
}
}
void indexed_update_alias_policy() {
using Left = Product<Transpositions<4>, Matrix4d, AliasFreeProduct>;
using Right =
internal::remove_all_t<decltype(std::declval<Matrix4d>() * std::declval<Transpositions<4>>().inverse())>;
using Permutation = Product<PermutationMatrix<4>, Matrix4d, AliasFreeProduct>;
using Dense = Product<Matrix4d, Matrix4d>;
using Assign = internal::assign_op<double, double>;
using Add = internal::add_assign_op<double, double>;
using Sub = internal::sub_assign_op<double, double>;
STATIC_CHECK((internal::assignment_assume_aliasing<Left, Add>::value));
STATIC_CHECK((internal::assignment_assume_aliasing<Right, Sub>::value));
// The policy does not depend on the functor's source scalar matching the product's.
using Cd = std::complex<double>;
STATIC_CHECK((internal::assignment_assume_aliasing<Left, internal::add_assign_op<Cd, Cd>>::value));
STATIC_CHECK((internal::assignment_assume_aliasing<Right, internal::sub_assign_op<Cd, Cd>>::value));
STATIC_CHECK((!internal::assignment_assume_aliasing<Left, Assign>::value));
STATIC_CHECK((!internal::assignment_assume_aliasing<Permutation, Add>::value));
STATIC_CHECK((internal::assignment_assume_aliasing<Dense, Assign>::value));
Transpositions<4> tr;
tr.indices() << 2, 3, 3, 3;
transposition_destination_aliases(tr);
transposition_destination_aliases(tr.inverse());
}
#endif
void indexed_update_scalar_and_index_cases() {
using Q = noncommutative_scalar::Quaternion;
using Matrix = Eigen::Matrix<Q, Dynamic, Dynamic>;
Matrix source(7, 3), expected(7, 3), dst = Matrix::Zero(7, 3);
PermutationMatrix<7> p;
for (Index i = 0; i < 7; ++i) {
p.indices()(i) = int((i + 1) % 7);
for (Index j = 0; j < 3; ++j) source(i, j) = Q(double(i), double(j), 1, -1);
}
for (Index i = 0; i < 7; ++i) expected.row(p.indices()(i)) = source.row(i);
dst.noalias() += p * source;
VERIFY(dst == expected);
dst.noalias() -= p * source;
VERIFY(dst == Matrix::Zero(7, 3));
Transpositions<7> tr;
for (Index i = 0; i < 7; ++i) tr.coeffRef(i) = int(6 - i);
expected = source;
for (Index i = 0; i < 7; ++i) expected.row(i).swap(expected.row(tr.coeff(i)));
dst.noalias() += tr * source;
VERIFY(dst == expected);
dst.noalias() -= tr * source;
VERIFY(dst == Matrix::Zero(7, 3));
Index reads = 0;
const auto indices = VectorXi::NullaryExpr(7, CountingUpdateIndex{&reads});
using RowMatrix = Eigen::Matrix<double, Dynamic, Dynamic, RowMajor>;
const RowMatrix values = RowMatrix::Random(3, 7);
RowMatrix actual = RowMatrix::Zero(3, 7), reference(3, 7);
for (Index i = 0; i < 7; ++i) reference.col((i + 1) % 7) = values.col(i);
actual.noalias() += values * indices.asPermutation().inverse();
VERIFY_IS_EQUAL(reads, 7);
VERIFY_IS_EQUAL(actual, reference);
}
EIGEN_DECLARE_TEST(indexed_product_updates) {
for (int i = 0; i < g_repeat; ++i) {
CALL_SUBTEST_1((permutation_updates<double, ColMajor>()));
CALL_SUBTEST_1((permutation_updates<double, RowMajor>()));
CALL_SUBTEST_2((permutation_updates<std::complex<double>, ColMajor>()));
CALL_SUBTEST_2((permutation_updates<std::complex<double>, RowMajor>()));
CALL_SUBTEST_3((transposition_update_cases<double, ColMajor>()));
CALL_SUBTEST_3((transposition_update_cases<double, RowMajor>()));
CALL_SUBTEST_4((transposition_update_cases<std::complex<double>, ColMajor>()));
CALL_SUBTEST_4((transposition_update_cases<std::complex<double>, RowMajor>()));
CALL_SUBTEST_5((structured_permutation_updates<double, ColMajor>()));
CALL_SUBTEST_5((structured_permutation_updates<double, RowMajor>()));
CALL_SUBTEST_6((structured_permutation_updates<std::complex<double>, ColMajor>()));
CALL_SUBTEST_6((structured_permutation_updates<std::complex<double>, RowMajor>()));
CALL_SUBTEST_7(indexed_update_scalar_and_index_cases());
CALL_SUBTEST_7(indexed_update_alias_policy());
CALL_SUBTEST_8((permutation_updates<float, ColMajor>()));
CALL_SUBTEST_8((permutation_updates<std::complex<float>, RowMajor>()));
CALL_SUBTEST_8((transposition_update_cases<float, RowMajor>()));
CALL_SUBTEST_8((structured_permutation_updates<std::complex<float>, ColMajor>()));
CALL_SUBTEST_9((transposition_row_wrappers<double, ColMajor>()));
CALL_SUBTEST_9((transposition_row_wrappers<double, RowMajor>()));
CALL_SUBTEST_9((transposition_row_wrappers<std::complex<double>, ColMajor>()));
CALL_SUBTEST_9((transposition_row_wrappers<std::complex<double>, RowMajor>()));
CALL_SUBTEST_10((transposition_widened_capacity<ColMajor>()));
CALL_SUBTEST_10((transposition_widened_capacity<RowMajor>()));
}
}