Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
SparseApproxComparisons.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2008-2014 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// SPDX-License-Identifier: MPL-2.0
10
11#ifndef EIGEN_SPARSE_APPROX_COMPARISONS_H
12#define EIGEN_SPARSE_APPROX_COMPARISONS_H
13
14// IWYU pragma: private
15#include "./InternalHeaderCheck.h"
16
17namespace Eigen {
18
19namespace internal {
20
21template <typename Scalar, bool UseScaledComparison>
22struct sparse_approx_comparison {
23 using RealScalar = typename NumTraits<Scalar>::Real;
24 using Accumulator = RealScalar;
25 // Custom scalars are summed as they are; a conversion to std::complex is not required of them.
26 using Wide = Scalar;
27
28 template <typename DifferenceNorm2, typename Scaled>
29 static bool compare(const RealScalar& x2, const RealScalar& y2, Index, const RealScalar& prec,
30 const DifferenceNorm2& difference2, const Scaled&) {
31 return difference2() <= prec * prec * numext::mini(x2, y2);
32 }
33
34 template <typename X, typename Y>
35 static bool isApprox(const X& x, const Y& y, const RealScalar& prec) {
36 return compare(
37 x.squaredNorm(), y.squaredNorm(), 0, prec, [&] { return (x - y).squaredNorm(); }, [] { return false; });
38 }
39};
40
41// |x - y| <= prec min(|x|, |y|) as in the dense approx_comparison_impl: from the squared norms of the stored values
42// while they are in range, and otherwise from norms of values scaled by powers of two, so tiny and huge matrices are
43// compared rather than their flushed or overflowed squares.
44template <typename Scalar>
45struct sparse_approx_comparison<Scalar, true> {
46 using RealScalar = typename NumTraits<Scalar>::Real;
47 using Accumulator = typename stable_norm_accumulator<RealScalar>::type;
48 // Coefficients widened to the accumulator, as approx_comparison_wide_t widens an expression's.
49 using Wide = std::conditional_t<NumTraits<Scalar>::IsComplex, std::complex<Accumulator>, Accumulator>;
50 using Dense = approx_comparison_impl<Scalar, true>;
51
52 // x2 and y2 are the squared norms of operands with at most size stored values between them; difference2() gives
53 // that of their difference, and scaled() decides the comparison when the squares cannot.
54 template <typename DifferenceNorm2, typename Scaled>
55 static bool compare(const Accumulator& x2, const Accumulator& y2, Index size, const RealScalar& prec,
56 const DifferenceNorm2& difference2, const Scaled& scaled) {
57 const Accumulator minimum = numext::mini(x2, y2);
58 const Accumulator precision2 = Accumulator(prec) * Accumulator(prec);
59 const Accumulator bound = precision2 * minimum;
60 // Only the smaller norm enters the bound; overflow of the larger norm is harmless.
61 if (Dense::safe_squared_norm(bound, size) &&
62 minimum >= Dense::template squared_norm_lower_bound<RealScalar>(size) &&
63 precision2 >= Dense::template squared_norm_lower_bound<RealScalar>(1))
64 return Accumulator(difference2()) <= bound;
65 return scaled();
66 }
67
68 template <typename X, typename Y>
69 static bool isApprox(const X& x, const Y& y, const RealScalar& prec) {
70 // Widening must not admit operands that cannot be subtracted, such as half and float.
71 EIGEN_CHECK_BINARY_COMPATIBILITY(scalar_difference_op<typename X::Scalar EIGEN_COMMA typename Y::Scalar>,
72 typename X::Scalar, typename Y::Scalar)
73 const auto& wideX = x.template cast<approx_comparison_wide_t<X>>();
74 const auto& wideY = y.template cast<approx_comparison_wide_t<Y>>();
75 // x - y stores at most the entries of both operands.
76 return compare(
77 wideX.squaredNorm(), wideY.squaredNorm(), stored_size(x) + stored_size(y), prec,
78 [&] { return (wideX - wideY).squaredNorm(); }, [&] { return isApprox_scaled(x, y, prec); });
79 }
80
81 private:
82 // An upper bound on the number of stored values; only types with compressed access count them.
83 template <typename X, std::enable_if_t<has_compressed_access<X>::value, int> = 0>
84 static Index stored_size(const X& x) {
85 return x.nonZeros();
86 }
87 template <typename X, std::enable_if_t<!has_compressed_access<X>::value, int> = 0>
88 static Index stored_size(const X& x) {
89 return x.rows() * x.cols();
90 }
91
92 // The norm of a compressed matrix is that of its stored values, which the dense scaled norm takes as a vector.
93 template <typename Plain>
94 static comparison_magnitude<Accumulator> norm(const Plain& m) {
95 return scaled_comparison_norm(m.coeffs().matrix());
96 }
97
98 template <typename X, typename Y>
99 static EIGEN_DONT_INLINE bool isApprox_scaled(const X& xExpr, const Y& yExpr, const RealScalar& prec) {
100 constexpr int Order = X::IsRowMajor ? RowMajor : ColMajor;
101 using StorageIndex = typename X::StorageIndex;
102 using WideX = approx_comparison_wide_t<X>;
103 using WideY = approx_comparison_wide_t<Y>;
104 using WideDifference = std::conditional_t<NumTraits<WideX>::IsComplex, WideX, WideY>;
105 const SparseMatrix<WideX, Order, StorageIndex> x = xExpr.template cast<WideX>();
106 const SparseMatrix<WideY, Order, StorageIndex> y = yExpr.template cast<WideY>();
107 const auto nx = norm(x);
108 const auto ny = norm(y);
109 if (!nx.isFinite() || !ny.isFinite()) return false;
110 auto tolerance = nx <= ny ? nx : ny;
111 tolerance.multiply(numext::abs(Accumulator(prec)));
112
113 // As in scaled_comparison_distance_impl: lift a maximum below 1 by a power of two first, so FTZ does not flush a
114 // subnormal difference of normal values, and halve if the difference of finite values overflows.
115 const Accumulator maxCoeff =
116 numext::mini(Accumulator(1), numext::maxi(scaled_comparison_max_coeff(x.coeffs().matrix().realView()),
117 scaled_comparison_max_coeff(y.coeffs().matrix().realView())));
118 const safe_scaling_factors<Accumulator> factors = supports_power_of_two_scaling<Accumulator>::value
119 ? safe_scaling<Accumulator>::compute_floor_factors(maxCoeff)
120 : safe_scaling_factors<Accumulator>();
121 SparseMatrix<WideDifference, Order, StorageIndex> difference = x * factors.invScale - y * factors.invScale;
122 auto distance = norm(difference);
123 if (!distance.isFinite()) {
124 const Accumulator halfInvScale = factors.invScale * Accumulator(0.5);
125 difference = x * halfInvScale - y * halfInvScale;
126 distance = norm(difference);
127 distance.multiply(Accumulator(2));
128 }
129 distance.multiply(factors.scale);
130 return distance <= tolerance;
131 }
132};
133
134} // namespace internal
135
136template <typename Derived>
137template <typename OtherDerived>
138bool SparseMatrixBase<Derived>::isApprox(const SparseMatrixBase<OtherDerived>& other, const RealScalar& prec) const {
139 const typename internal::nested_eval<Derived, 2, PlainObject>::type actualA(derived());
140 std::conditional_t<bool(IsRowMajor) == bool(OtherDerived::IsRowMajor),
141 const typename internal::nested_eval<OtherDerived, 2, PlainObject>::type, const PlainObject>
142 actualB(other.derived());
143
144 return internal::sparse_approx_comparison<Scalar>::isApprox(actualA, actualB, prec);
145}
146
147} // end namespace Eigen
148
149#endif // EIGEN_SPARSE_APPROX_COMPARISONS_H
Base class of any sparse matrices or sparse expressions.
Definition SparseMatrixBase.h:31
@ ColMajor
Definition Constants.h:319
@ RowMajor
Definition Constants.h:321