Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
StableNorm.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2009 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_STABLENORM_H
12#define EIGEN_STABLENORM_H
13
14// IWYU pragma: private
15#include "./InternalHeaderCheck.h"
16
17namespace Eigen {
18
19namespace internal {
20
21template <typename Accumulator, bool = std::is_floating_point<Accumulator>::value>
22struct stable_norm_unscaled_predicate {
23 static inline bool run(const Accumulator&, const Accumulator&) { return false; }
24};
25
26template <typename Accumulator>
27struct stable_norm_unscaled_predicate<Accumulator, true> {
28 static inline bool run(const Accumulator& maxCoeff, const Accumulator& invScale) {
29 using std::sqrt;
30 // A block has at most 8192 real components. These bounds keep the error
31 // from flushed component squares below one epsilon.
32 static const Accumulator kSqrtMin =
33 sqrt((numext::numeric_limits<Accumulator>::min)() * (Accumulator(16384) / NumTraits<Accumulator>::epsilon()));
34 static const Accumulator kSqrtMax = sqrt(NumTraits<Accumulator>::highest() / Accumulator(16384));
35 // A normal invScale avoids fast-math flushing invScale^2.
36 static const Accumulator kSqrtNormalMin = sqrt((numext::numeric_limits<Accumulator>::min)());
37 return maxCoeff >= kSqrtMin && maxCoeff <= kSqrtMax && invScale >= kSqrtNormalMin;
38 }
39};
40
41template <typename ExpressionType, typename Accumulator>
42inline Accumulator stable_norm_squared_norm(const ExpressionType& block, const Accumulator& invScale,
43 const Accumulator& maxCoeff) {
44 if (stable_norm_unscaled_predicate<Accumulator>::run(maxCoeff, invScale)) {
45 return block.realView().template cast<Accumulator>().squaredNorm() * numext::abs2(invScale);
46 }
47 return (block.realView().template cast<Accumulator>() * invScale).squaredNorm();
48}
49
50template <typename ExpressionType, typename Accumulator>
51inline void stable_norm_kernel(const ExpressionType& block, Accumulator& ssq, Accumulator& scale,
52 Accumulator& invScale) {
53 // Component-wise maxima give the required scale without complex hypot calls.
54 Accumulator maxCoeff = block.realView().template cast<Accumulator>().cwiseAbs().template maxCoeff<PropagateNaN>();
55
56 if (maxCoeff > scale) {
57 if (maxCoeff > NumTraits<Accumulator>::highest()) // we got an INF
58 {
59 invScale = Accumulator(1);
60 scale = maxCoeff;
61 } else {
62 const auto factors = safe_scaling<Accumulator>::compute_ceiling_factors_with_normal_reciprocal(maxCoeff);
63 if (scale > Accumulator(0)) ssq = ssq * numext::abs2(scale * factors.invScale);
64 scale = factors.scale;
65 invScale = factors.invScale;
66 }
67 } else if (maxCoeff != maxCoeff) // we got a NaN
68 {
69 scale = maxCoeff;
70 }
71
72 // TODO: skip sub-vector when maxCoeff << current scale.
73 if (scale > Accumulator(0)) // if scale==0, then block is 0
74 ssq += stable_norm_squared_norm(block, invScale, maxCoeff);
75}
76
77template <typename VectorType, typename Accumulator>
78void stable_norm_impl_inner_step(const VectorType& vec, Accumulator& ssq, Accumulator& scale, Accumulator& invScale) {
79 const Index blockSize = 4096;
80
81 Index n = vec.size();
82 Index blockEnd = numext::round_down(n, blockSize);
83 for (Index i = 0; i < blockEnd; i += blockSize) {
84 internal::stable_norm_kernel(vec.template segment<blockSize>(i), ssq, scale, invScale);
85 }
86 if (n > blockEnd) {
87 internal::stable_norm_kernel(vec.tail(n - blockEnd), ssq, scale, invScale);
88 }
89}
90
91template <typename VectorType, typename Accumulator,
92 bool = bool(traits<VectorType>::Flags & DirectAccessBit) &&
93 (int(inner_stride_at_compile_time<VectorType>::value) != 1)>
94struct stable_norm_vector_dispatch {
95 static inline void run(const VectorType& vec, Accumulator& ssq, Accumulator& scale, Accumulator& invScale) {
96 stable_norm_impl_inner_step(vec, ssq, scale, invScale);
97 }
98};
99
100template <typename VectorType, typename Accumulator>
101struct stable_norm_vector_dispatch<VectorType, Accumulator, true> {
102 static inline void run(const VectorType& vec, Accumulator& ssq, Accumulator& scale, Accumulator& invScale) {
103 if (vec.innerStride() == 1) {
104 using Scalar = typename traits<VectorType>::Scalar;
105 using PlainVector = Matrix<Scalar, VectorType::SizeAtCompileTime, 1, 0, VectorType::MaxSizeAtCompileTime, 1>;
106 using ContiguousMap = Map<const PlainVector, evaluator<VectorType>::Alignment>;
107 const ContiguousMap contiguous(vec.data(), vec.size());
108 stable_norm_impl_inner_step(contiguous, ssq, scale, invScale);
109 return;
110 }
111 stable_norm_impl_inner_step(vec, ssq, scale, invScale);
112 }
113};
114
115template <typename VectorType, typename Accumulator>
116inline void stable_norm_impl_inner_dispatch(const VectorType& vec, Accumulator& ssq, Accumulator& scale,
117 Accumulator& invScale) {
118 stable_norm_vector_dispatch<VectorType, Accumulator>::run(vec, ssq, scale, invScale);
119}
120
121template <typename MatrixType, typename Accumulator>
122inline void stable_norm_impl_outer_steps(const MatrixType& mat, Accumulator& ssq, Accumulator& scale,
123 Accumulator& invScale) {
124 for (Index j = 0; j < mat.outerSize(); ++j) {
125 stable_norm_impl_inner_dispatch(mat.innerVector(j), ssq, scale, invScale);
126 }
127}
128
129template <typename MatrixType, typename Accumulator, bool = bool(traits<MatrixType>::Flags & DirectAccessBit)>
130struct stable_norm_matrix_dispatch {
131 static inline void run(const MatrixType& mat, Accumulator& ssq, Accumulator& scale, Accumulator& invScale) {
132 stable_norm_impl_outer_steps(mat, ssq, scale, invScale);
133 }
134};
135
136template <typename MatrixType, typename Accumulator>
137struct stable_norm_matrix_dispatch<MatrixType, Accumulator, true> {
138 static inline void run(const MatrixType& mat, Accumulator& ssq, Accumulator& scale, Accumulator& invScale) {
139 if (mat.innerStride() == 1 && (mat.outerSize() == 1 || mat.outerStride() == mat.innerSize())) {
140 using Scalar = typename traits<MatrixType>::Scalar;
141 using PlainVector = Matrix<Scalar, MatrixType::SizeAtCompileTime, 1, 0, MatrixType::MaxSizeAtCompileTime, 1>;
142 using ContiguousMap = Map<const PlainVector, evaluator<MatrixType>::Alignment>;
143 const ContiguousMap contiguous(mat.data(), mat.size());
144 stable_norm_impl_inner_step(contiguous, ssq, scale, invScale);
145 return;
146 }
147 stable_norm_impl_outer_steps(mat, ssq, scale, invScale);
148 }
149};
150
151// Avoid instantiating block reductions for statically empty inputs, including in C++14.
152template <typename Derived, std::enable_if_t<Derived::MaxSizeAtCompileTime == 0, int> = 0>
153typename Derived::RealScalar stable_norm_impl(const Derived&) {
154 return typename Derived::RealScalar(0);
155}
156
157template <typename VectorType,
158 std::enable_if_t<VectorType::IsVectorAtCompileTime && VectorType::MaxSizeAtCompileTime != 0, int> = 0>
159typename VectorType::RealScalar stable_norm_impl(const VectorType& vec) {
160 Index n = vec.size();
161 if (EIGEN_PREDICT_FALSE(n == 1)) return numext::abs(vec.coeff(0));
162
163 using RealScalar = typename VectorType::RealScalar;
164 using Accumulator = typename stable_norm_accumulator<RealScalar>::type;
165 Accumulator scale(0);
166 Accumulator invScale(1);
167 Accumulator ssq(0); // sum of squares
168
169 stable_norm_vector_dispatch<VectorType, Accumulator>::run(vec, ssq, scale, invScale);
170
171 return RealScalar(scale * numext::sqrt(ssq));
172}
173
174template <typename MatrixType,
175 std::enable_if_t<!MatrixType::IsVectorAtCompileTime && MatrixType::MaxSizeAtCompileTime != 0, int> = 0>
176typename MatrixType::RealScalar stable_norm_impl(const MatrixType& mat) {
177 using RealScalar = typename MatrixType::RealScalar;
178 using Accumulator = typename stable_norm_accumulator<RealScalar>::type;
179 Accumulator scale(0);
180 Accumulator invScale(1);
181 Accumulator ssq(0); // sum of squares
182
183 stable_norm_matrix_dispatch<MatrixType, Accumulator>::run(mat, ssq, scale, invScale);
184 return RealScalar(scale * numext::sqrt(ssq));
185}
186
187inline int stable_norm_floor_div2(int value) { return value / 2 - ((value < 0 && value % 2 != 0) ? 1 : 0); }
188
189inline int stable_norm_ceil_div2(int value) { return value / 2 + ((value > 0 && value % 2 != 0) ? 1 : 0); }
191template <typename Accumulator>
192inline void blue_norm_accumulate_component(const Accumulator& ax, const Accumulator& tsml, const Accumulator& tbig,
193 const Accumulator& ssml, const Accumulator& sbig, bool& notBig,
194 Accumulator& asml, Accumulator& amed, Accumulator& abig) {
195 if (ax > tbig) {
196 abig += numext::abs2(ax * sbig);
197 notBig = false;
198 } else if (ax < tsml) {
199 if (notBig) asml += numext::abs2(ax * ssml);
200 } else {
201 amed += numext::abs2(ax);
202 }
203}
204
205template <typename Scalar, typename Accumulator, bool = NumTraits<Scalar>::IsComplex>
206struct blue_norm_accumulate_scalar {
207 static inline void run(const Scalar& value, const Accumulator& tsml, const Accumulator& tbig, const Accumulator& ssml,
208 const Accumulator& sbig, bool& notBig, Accumulator& asml, Accumulator& amed,
209 Accumulator& abig) {
210 const Accumulator ax = numext::abs(Accumulator(value));
211 blue_norm_accumulate_component(ax, tsml, tbig, ssml, sbig, notBig, asml, amed, abig);
212 }
213};
214
215template <typename Scalar, typename Accumulator>
216struct blue_norm_accumulate_scalar<Scalar, Accumulator, true> {
217 static inline void run(const Scalar& value, const Accumulator& tsml, const Accumulator& tbig, const Accumulator& ssml,
218 const Accumulator& sbig, bool& notBig, Accumulator& asml, Accumulator& amed,
219 Accumulator& abig) {
220 const Accumulator real = numext::abs(Accumulator(numext::real(value)));
221 const Accumulator imag = numext::abs(Accumulator(numext::imag(value)));
222 blue_norm_accumulate_component(real, tsml, tbig, ssml, sbig, notBig, asml, amed, abig);
223 blue_norm_accumulate_component(imag, tsml, tbig, ssml, sbig, notBig, asml, amed, abig);
224 }
225};
226
227template <typename Derived>
228inline typename NumTraits<typename traits<Derived>::Scalar>::Real blueNorm_impl(const EigenBase<Derived>& _vec) {
229 using RealScalar = typename Derived::RealScalar;
230 using Accumulator = typename stable_norm_accumulator<RealScalar>::type;
231 using Scalar = typename traits<Derived>::Scalar;
232 using std::pow;
233
234 const Derived& vec(_vec.derived());
235 if (vec.size() == 0) return RealScalar(0);
236
237 // Blue, ACM TOMS 4(1), 1978, https://doi.org/10.1145/355769.355771.
238 // The small-value multiplier includes Anderson's denormal correction from
239 // Algorithm 978, ACM TOMS 44(1), 2017, https://doi.org/10.1145/3061665.
240 // These thresholds and the three-accumulator merge follow Reference BLAS
241 // xNRM2 (LAPACK 3.12.1), expressed independently for Eigen scalar types.
242 static const int ibeta = std::numeric_limits<Accumulator>::radix;
243 static const int it = NumTraits<Accumulator>::digits();
244 static const int iemin = NumTraits<Accumulator>::min_exponent();
245 static const int iemax = NumTraits<Accumulator>::max_exponent();
246 static const Accumulator tsml = Accumulator(pow(Accumulator(ibeta), Accumulator(stable_norm_ceil_div2(iemin - 1))));
247 static const Accumulator tbig =
248 Accumulator(pow(Accumulator(ibeta), Accumulator(stable_norm_floor_div2(iemax - it + 1))));
249 static const Accumulator ssml =
250 Accumulator(pow(Accumulator(ibeta), Accumulator(-stable_norm_floor_div2(iemin - it))));
251 static const Accumulator sbig =
252 Accumulator(pow(Accumulator(ibeta), Accumulator(-stable_norm_ceil_div2(iemax + it - 1))));
253
254 bool notBig = true;
255 Accumulator asml(0);
256 Accumulator amed(0);
257 Accumulator abig(0);
258
259 for (Index j = 0; j < vec.outerSize(); ++j) {
260 for (typename Derived::InnerIterator iter(vec, j); iter; ++iter) {
261 blue_norm_accumulate_scalar<Scalar, Accumulator>::run(iter.value(), tsml, tbig, ssml, sbig, notBig, asml, amed,
262 abig);
263 }
264 }
265
266 Accumulator scale(1);
267 Accumulator sumsq(0);
268 if (abig > Accumulator(0)) {
269 if (amed > Accumulator(0) || amed > NumTraits<Accumulator>::highest() || amed != amed) abig += (amed * sbig) * sbig;
270 scale = Accumulator(1) / sbig;
271 sumsq = abig;
272 } else if (asml > Accumulator(0)) {
273 if (amed > Accumulator(0) || amed > NumTraits<Accumulator>::highest() || amed != amed) {
274 amed = numext::sqrt(amed);
275 asml = numext::sqrt(asml) / ssml;
276 // Spell this as in xNRM2 rather than with min/max: when amed is NaN,
277 // it must become ymax so that the final result remains NaN.
278 const bool smallIsLarger = asml > amed;
279 const Accumulator ymin = smallIsLarger ? amed : asml;
280 const Accumulator ymax = smallIsLarger ? asml : amed;
281 sumsq = numext::abs2(ymax) * (Accumulator(1) + numext::abs2(ymin / ymax));
282 } else {
283 scale = Accumulator(1) / ssml;
284 sumsq = asml;
285 }
286 } else {
287 sumsq = amed;
288 }
289 return RealScalar(scale * numext::sqrt(sumsq));
290}
291
292} // end namespace internal
293
305template <typename Derived>
307 using Nested = typename internal::nested_eval<Derived, 2>::type;
308 Nested nested(derived());
309 return internal::stable_norm_impl(nested);
310}
311
322template <typename Derived>
324 return internal::blueNorm_impl(*this);
325}
326
332template <typename Derived>
334 using Accumulator = typename internal::stable_norm_accumulator<RealScalar>::type;
335 // Component reduction avoids rounded complex magnitudes and permits promoted accumulation.
336 return RealScalar(internal::redux_with_identity(derived().realView().template cast<Accumulator>().cwiseAbs(),
337 internal::scalar_hypot_op<Accumulator>(), 0));
338}
339
340} // end namespace Eigen
341
342#endif // EIGEN_STABLENORM_H
RealViewReturnType realView()
Definition RealView.h:361
CoeffReturnType value() const
Definition DenseBase.h:454
constexpr CastXpr< NewType >::Type cast() const
Definition DenseBase.h:66
RealScalar blueNorm() const
Definition StableNorm.h:323
RealScalar hypotNorm() const
Definition StableNorm.h:333
RealScalar stableNorm() const
Definition StableNorm.h:306
const CwiseUnaryOp< internal::scalar_abs_op< Scalar >, const Derived > cwiseAbs() const
constexpr unsigned int DirectAccessBit
Definition Constants.h:160
Holds information about the various numeric (i.e. scalar) types allowed by Eigen.
Definition NumTraits.h:267