Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
Householder.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2010 Benoit Jacob <jacob.benoit.1@gmail.com>
5// Copyright (C) 2009 Gael Guennebaud <gael.guennebaud@inria.fr>
6//
7// This Source Code Form is subject to the terms of the Mozilla
8// Public License v. 2.0. If a copy of the MPL was not distributed
9// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
10// SPDX-License-Identifier: MPL-2.0
11
12#ifndef EIGEN_HOUSEHOLDER_H
13#define EIGEN_HOUSEHOLDER_H
14
15// IWYU pragma: private
16#include "./InternalHeaderCheck.h"
17
18namespace Eigen {
19
20namespace internal {
21template <int N>
22struct decrement_size : std::integral_constant<int, N - 1> {};
23template <>
24struct decrement_size<0> : std::integral_constant<int, 0> {};
25template <>
26struct decrement_size<Dynamic> : std::integral_constant<int, Dynamic> {};
27
28template <typename RealScalar>
29struct householder_norm_accumulator : stable_norm_accumulator<RealScalar> {};
30
31template <>
32struct householder_norm_accumulator<float> {
33 // Stable norm reductions can avoid underflow by scaling in float. Householder construction must also preserve each
34 // subnormal component while forming scale-free tau and essential-vector ratios, so widen only these intermediates.
35 using type = double;
36};
37
38template <typename Scalar, typename Accumulator, bool IsComplex = NumTraits<Scalar>::IsComplex>
39struct householder_rescale;
40
41template <typename Scalar, typename Accumulator>
42struct householder_rescale<Scalar, Accumulator, false> {
43 EIGEN_DEVICE_FUNC static Scalar run(const Scalar& value, const Accumulator& scale) {
44 return Scalar(Accumulator(value) / scale);
45 }
46
47 // This overload only keeps the shared C++14 call site well-formed; real inputs return before reaching it.
48 EIGEN_DEVICE_FUNC static Scalar zero_tail_tau(const Accumulator& scaledReal, const Accumulator&,
49 const Scalar& scaledBeta) {
50 return Scalar(1) - Scalar(scaledReal) / scaledBeta;
51 }
52
53 template <typename EssentialPart, typename TailView>
54 EIGEN_DEVICE_FUNC static void run(EssentialPart& essential, const TailView& tail, const Accumulator& scale,
55 const Scalar& denominator) {
56 essential = ((tail.template cast<Accumulator>().array() / scale) / Accumulator(denominator))
57 .matrix()
58 .template cast<Scalar>();
59 }
60};
61
62template <typename Scalar, typename Accumulator>
63struct householder_rescale<Scalar, Accumulator, true> {
64 using RealScalar = typename NumTraits<Scalar>::Real;
65
66 EIGEN_DEVICE_FUNC static Scalar run(const Scalar& value, const Accumulator& scale) {
67 return Scalar(RealScalar(Accumulator(numext::real(value)) / scale),
68 RealScalar(Accumulator(numext::imag(value)) / scale));
69 }
70
71 EIGEN_DEVICE_FUNC static Scalar zero_tail_tau(const Accumulator& scaledReal, const Accumulator& scaledImag,
72 const RealScalar& scaledBeta) {
73 return Scalar(RealScalar(1) - RealScalar(scaledReal) / scaledBeta, RealScalar(scaledImag) / scaledBeta);
74 }
75
76 template <typename EssentialPart, typename TailView>
77 EIGEN_DEVICE_FUNC static void run(EssentialPart& essential, const TailView& tail, const Accumulator& scale,
78 const Scalar& denominator) {
79 run(essential, tail, scale, denominator, complex_array_access<Scalar>());
80 }
81
82 private:
83 template <typename EssentialPart, typename TailView>
84 EIGEN_DEVICE_FUNC static void run(EssentialPart& essential, const TailView& tail, const Accumulator& scale,
85 const Scalar& denominator, std::true_type) {
86 essential.realView().array() =
87 (tail.realView().array().template cast<Accumulator>() / scale).template cast<RealScalar>();
88 essential.array() /= denominator;
89 }
90
91 template <typename EssentialPart, typename TailView>
92 EIGEN_DEVICE_FUNC static void run(EssentialPart& essential, const TailView& tail, const Accumulator& scale,
93 const Scalar& denominator, std::false_type) {
94 for (Index i = 0; i < tail.size(); ++i) essential.coeffRef(i) = run(tail.coeff(i), scale) / denominator;
95 }
96};
97
98// -copysign(norm, head) for norm >= 0. Other scalars select the sign by comparison: an autodiff scalar's copysign
99// differentiates through head, with an impulse at head == 0.
100template <typename RealScalar>
101EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE RealScalar householder_beta(const RealScalar& norm, const RealScalar& head) {
102 EIGEN_IF_CONSTEXPR (supports_power_of_two_scaling<RealScalar>::value) return -numext::copysign(norm, head);
103 return head < RealScalar(0) ? norm : RealScalar(-norm);
104}
105} // namespace internal
106
123template <typename Derived>
124EIGEN_DEVICE_FUNC void MatrixBase<Derived>::makeHouseholderInPlace(Scalar& tau, RealScalar& beta) {
126 size() - 1);
127 makeHouseholder(essentialPart, tau, beta);
128}
129
152template <typename Derived>
153template <typename EssentialPart>
154EIGEN_DEVICE_FUNC void MatrixBase<Derived>::makeHouseholder(EssentialPart& essential, Scalar& tau,
155 RealScalar& beta) const {
156 EIGEN_STATIC_ASSERT_VECTOR_ONLY(EssentialPart)
158
159 const RealScalar tailSqNorm = size() == 1 ? RealScalar(0) : tail.unwind().squaredNorm();
160 Scalar c0 = coeff(0);
161 const RealScalar tol = (std::numeric_limits<RealScalar>::min)();
162 RealScalar unscaledNormThreshold = tol;
163 // Whether the direct construction's abs2(c0) + tailSqNorm would exceed the range. Integer scalars keep the direct
164 // path they have always taken; the scaled path divides by a component maximum, which does not apply to them.
165 bool unscaledSqNormOverflows = false;
166 // Whether a tail component is infinite. Only an overflowed tailSqNorm can mean that, so the ordinary path never
167 // scans.
168 bool tailHasInfinity = false;
169 EIGEN_IF_CONSTEXPR (!NumTraits<RealScalar>::IsInteger) {
170 const RealScalar precision = RealScalar(NumTraits<RealScalar>::epsilon());
171 // With flush-to-zero arithmetic, every tail component square below tol can be lost. Account for every component
172 // so the discarded contribution is at most epsilon relative to a squared norm above this threshold. The narrow
173 // normal range of half makes this scaled path common for moderately small inputs; preserving the bound there is
174 // intentional.
175 const RealScalar componentCount = RealScalar(size() - 1) * RealScalar(NumTraits<Scalar>::IsComplex ? 2 : 1);
176 unscaledNormThreshold = (tol / precision) * componentCount;
177
178 // Both terms overflow well before the reflector stops being representable, so classify the input before the
179 // squares are formed: abs2(c0) is at most twice the square of the larger component of c0, and the tail's own
180 // reduction has already overflowed if tailSqNorm exceeds the bound. Testing the sum with isinf() instead would
181 // not survive -ffinite-math-only, which folds that test away, whereas a comparison against a finite bound is
182 // still evaluated.
183 const RealScalar sqNormBound = NumTraits<RealScalar>::highest() / RealScalar(2);
184 const RealScalar componentBound = numext::sqrt<RealScalar>(sqNormBound / RealScalar(2));
185 const RealScalar c0Max = numext::maxi(numext::abs(numext::real(c0)), numext::abs(numext::imag(c0)));
186 unscaledSqNormOverflows = !(c0Max <= componentBound) || !(tailSqNorm <= sqNormBound);
187 if (unscaledSqNormOverflows) tailHasInfinity = !tail.unwind().realView().allFinite();
188 }
189
190 // The scaled path forms the reflector from ratios of the largest component and never squares an unscaled
191 // coefficient, so it is also the path for inputs the direct construction cannot square. A NaN tail, which the
192 // overflow test above counts as overflow, takes the direct construction instead: it propagates the NaN into beta,
193 // tau, and the essential part, as xLARFG does, whereas the component maxima below can skip it. So does a tail with
194 // an infinite component, whose scale would be infinite and every ratio NaN: the direct construction gives
195 // xLARFG's beta = -copysign(inf, real(c0)), tau = NaN, and NaN only where the tail is infinite.
196 const bool scaledCandidate = (tailSqNorm <= unscaledNormThreshold || unscaledSqNormOverflows) &&
197 !(numext::isnan)(tailSqNorm) && !tailHasInfinity;
198 // A head with a NaN or infinite component cannot be scaled by the component maximum: c0 / scale would be NaN. The
199 // direct construction then gives xLARFG's result, which is NaN throughout for a NaN head, and
200 // beta = -sign(Re(c0)) * inf, tau = NaN, and a zero essential part for an infinite one. The exception is a real head
201 // over an exactly zero tail, for which xLARFG returns tau = 0 and beta = alpha whatever alpha is.
202 // Short-circuited on scaledCandidate, so the ordinary direct path does no extra work.
203 const bool headIsFinite =
204 scaledCandidate && (numext::isfinite)(numext::real(c0)) && (numext::isfinite)(numext::imag(c0));
205 if (scaledCandidate && !headIsFinite && numext::is_exactly_zero(numext::imag(c0)) &&
206 (size() == 1 || numext::is_exactly_zero(tail.unwind().realView().cwiseAbs().maxCoeff()))) {
207 tau = RealScalar(0);
208 beta = numext::real(c0);
209 essential.setZero();
210 return;
211 }
212 if (scaledCandidate && headIsFinite) {
213 using Accumulator = typename internal::householder_norm_accumulator<RealScalar>::type;
214 const auto tailView = tail.unwind();
215 const auto tailComponents = tailView.realView();
216 // Component maxima cannot underflow when a representable tail is nonzero.
217 const Accumulator tailMax =
218 tailView.size() == 0 ? Accumulator(0) : Accumulator(tailComponents.cwiseAbs().maxCoeff());
219 if (numext::is_exactly_zero(tailMax) && numext::is_exactly_zero(numext::imag(c0))) {
220 tau = RealScalar(0);
221 beta = numext::real(c0);
222 essential.setZero();
223 return;
224 }
225 const Accumulator c0RealAbs = numext::abs(Accumulator(numext::real(c0)));
226 const Accumulator c0ImagAbs = numext::abs(Accumulator(numext::imag(c0)));
227 const Accumulator c0Max = numext::maxi(c0RealAbs, c0ImagAbs);
228 const Accumulator scale = numext::maxi(c0Max, tailMax);
229 const RealScalar realScale = RealScalar(scale);
230 // A target that flushes this scale cannot form meaningful ratios from the entirely subnormal vector.
231 if (scale < Accumulator(tol) && numext::is_exactly_zero(realScale + realScale)) {
232 tau = RealScalar(0);
233 beta = numext::real(c0);
234 essential.setZero();
235 return;
236 }
237 if (numext::is_exactly_zero(tailMax)) {
238 const Accumulator scaledReal = Accumulator(numext::real(c0)) / scale;
239 const Accumulator scaledImag = Accumulator(numext::imag(c0)) / scale;
240 RealScalar scaledBeta = RealScalar(numext::hypot(scaledReal, scaledImag));
241 // xLARFG's beta = -SIGN(norm, alpha) takes the sign bit of alpha, so a head of -0 gives beta = +norm.
242 scaledBeta = internal::householder_beta<RealScalar>(scaledBeta, numext::real(c0));
243 beta = RealScalar(scale * Accumulator(scaledBeta));
244 essential.setZero();
245 tau = internal::householder_rescale<Scalar, Accumulator>::zero_tail_tau(scaledReal, scaledImag, scaledBeta);
246 return;
247 }
248 // Form the reflector from scale-free ratios to preserve subnormal inputs and avoid overflowing c0 - beta.
249 Accumulator scaledTailSqNorm;
250 EIGEN_IF_CONSTEXPR (std::is_same<RealScalar, float>::value) {
251 // Double has enough exponent range to square every finite float scale without underflow or overflow.
252 scaledTailSqNorm = tailComponents.template cast<Accumulator>().squaredNorm() / (scale * scale);
253 } else {
254 scaledTailSqNorm = (tailComponents.template cast<Accumulator>().array() / scale).matrix().squaredNorm();
255 }
256 const Scalar scaledC0 = internal::householder_rescale<Scalar, Accumulator>::run(c0, scale);
257 RealScalar scaledBeta =
258 RealScalar(numext::hypot(Accumulator(numext::abs(scaledC0)), numext::sqrt(scaledTailSqNorm)));
259 scaledBeta = internal::householder_beta<RealScalar>(scaledBeta, numext::real(c0));
260 beta = RealScalar(scale * Accumulator(scaledBeta));
261 internal::householder_rescale<Scalar, Accumulator>::run(essential, tailView, scale, scaledC0 - scaledBeta);
262 tau = numext::conj(Scalar(RealScalar(1)) - scaledC0 / scaledBeta);
263 return;
264 }
265 beta = numext::sqrt<RealScalar>(numext::abs2(c0) + tailSqNorm);
266 beta = internal::householder_beta<RealScalar>(beta, numext::real(c0));
267 essential = tail.unwind() / (c0 - beta);
268 tau = numext::conj((beta - c0) / beta);
269}
270
271namespace internal {
272
273template <typename Derived, typename EssentialPart,
274 bool Fused = !Derived::IsRowMajor && EssentialPart::ColsAtCompileTime == 1 &&
275 (EssentialPart::RowsAtCompileTime == 1 || EssentialPart::RowsAtCompileTime == 2)>
276struct householder_apply_left_impl {
277 using Scalar = typename Derived::Scalar;
278 static EIGEN_DEVICE_FUNC void run(MatrixBase<Derived>& mat, const EssentialPart& essential, const Scalar& tau,
279 Scalar* workspace) {
282 mat.rows() - 1, mat.cols());
283 tmp.noalias() = essential.adjoint() * bottom.unwind();
284 tmp = tau * (tmp + mat.row(0));
285 mat.row(0) -= tmp;
286 bottom.unwind().noalias() -= essential * tmp;
287 }
288};
289
290// Two- and three-element reflectors on column-major storage: finishing each column before advancing replaces
291// four strided row passes, which thrash the cache at large outer strides (issue #3160).
292template <typename Derived, typename EssentialPart>
293struct householder_apply_left_impl<Derived, EssentialPart, true> {
294 using Scalar = typename Derived::Scalar;
295 static EIGEN_DEVICE_FUNC void run(MatrixBase<Derived>& mat, const EssentialPart& essential, const Scalar& tau,
296 Scalar*) {
297 // Evaluated once so that the column loop reads plain coefficients; tau may reference a coefficient of mat.
298 const Matrix<Scalar, EssentialPart::RowsAtCompileTime, 1> v = essential;
299 const Scalar tauValue = tau;
300 Block<Derived, EssentialPart::RowsAtCompileTime, Derived::ColsAtCompileTime> bottom(mat.derived(), 1, 0,
301 mat.rows() - 1, mat.cols());
302 for (Index j = 0; j < mat.cols(); ++j) {
303 const Scalar tmp = tauValue * (v.dot(bottom.col(j)) + mat.coeff(0, j));
304 mat.coeffRef(0, j) -= tmp;
305 bottom.col(j) -= v * tmp;
306 }
307 }
308};
309
310template <typename Derived, typename EssentialPart,
311 bool Fused = !Derived::IsRowMajor && bool(traits<Derived>::Flags & DirectAccessBit) &&
312 inner_stride_at_compile_time<Derived>::value == 1 &&
313 packet_traits<typename Derived::Scalar>::Vectorizable && EssentialPart::ColsAtCompileTime == 1 &&
314 (EssentialPart::RowsAtCompileTime == 1 || EssentialPart::RowsAtCompileTime == 2)>
315struct householder_apply_right_impl {
316 using Scalar = typename Derived::Scalar;
317 static EIGEN_DEVICE_FUNC void run(MatrixBase<Derived>& mat, const EssentialPart& essential, const Scalar& tau,
318 Scalar* workspace) {
319 Map<typename plain_col_type<typename Derived::PlainObject>::type> tmp(workspace, mat.rows());
320 Block<Derived, Derived::RowsAtCompileTime, EssentialPart::SizeAtCompileTime> right(mat.derived(), 0, 1, mat.rows(),
321 mat.cols() - 1);
322 tmp.noalias() = right.unwind() * essential;
323 // M H = M - (M v) tau v^*: tau multiplies from the right, as in the one-column branch.
324 tmp = (tmp + mat.col(0)) * tau;
325 mat.col(0) = mat.col(0) - tmp;
326 right.unwind().noalias() -= tmp * essential.adjoint();
327 }
328};
329
330// Two- and three-element reflectors on contiguous columns: one pass down the rows updates all the columns, where the
331// general path makes four passes through a temporary. These are the O(n^3) updates of the Francis QR step.
332template <typename Derived, typename EssentialPart>
333struct householder_apply_right_impl<Derived, EssentialPart, true> {
334 using Scalar = typename Derived::Scalar;
335 using Packet = typename packet_traits<Scalar>::type;
336 static constexpr int K = EssentialPart::RowsAtCompileTime;
337
338 static EIGEN_DEVICE_FUNC void run(MatrixBase<Derived>& mat, const EssentialPart& essential, const Scalar& tau,
339 Scalar*) {
340 constexpr Index PacketSize = unpacket_traits<Packet>::size;
341 eigen_assert(mat.cols() == K + 1);
342 // Copied first: tau and the essential part may alias coefficients of mat.
343 Scalar v[K], vc[K];
344 for (int j = 0; j < K; ++j) {
345 v[j] = essential.coeff(j);
346 vc[j] = numext::conj(v[j]);
347 }
348 const Scalar tauValue = tau;
349 const Index rows = mat.rows();
350 Scalar* col[K + 1];
351 for (int j = 0; j <= K; ++j) col[j] = &mat.derived().coeffRef(0, j);
352
353 const Packet ptau = pset1<Packet>(tauValue);
354 Packet pv[K], pvc[K];
355 for (int j = 0; j < K; ++j) {
356 pv[j] = pset1<Packet>(v[j]);
357 pvc[j] = pset1<Packet>(vc[j]);
358 }
359 const Index vectorEnd = numext::round_down(rows, PacketSize);
360 for (Index i = 0; i < vectorEnd; i += PacketSize) {
361 Packet x[K + 1];
362 for (int j = 0; j <= K; ++j) x[j] = ploadu<Packet>(col[j] + i);
363 Packet t = x[0];
364 for (int j = 0; j < K; ++j) t = pmadd(x[j + 1], pv[j], t);
365 t = pmul(t, ptau);
366 pstoreu(col[0] + i, psub(x[0], t));
367 for (int j = 0; j < K; ++j) pstoreu(col[j + 1] + i, pnmadd(t, pvc[j], x[j + 1]));
368 }
369 for (Index i = vectorEnd; i < rows; ++i) {
370 Scalar t = col[0][i];
371 for (int j = 0; j < K; ++j) t += col[j + 1][i] * v[j];
372 t *= tauValue;
373 col[0][i] -= t;
374 for (int j = 0; j < K; ++j) col[j + 1][i] -= t * vc[j];
375 }
376 }
377};
378
379} // namespace internal
380
396template <typename Derived>
397template <typename EssentialPart>
398EIGEN_DEVICE_FUNC void MatrixBase<Derived>::applyHouseholderOnTheLeft(const EssentialPart& essential, const Scalar& tau,
399 Scalar* workspace) {
400 if (rows() == 1) {
401 // H = 1 - tau multiplies from the left, which a noncommutative scalar distinguishes.
402 *this = (Scalar(1) - tau) * *this;
403 } else if (!numext::is_exactly_zero(tau)) {
404 internal::householder_apply_left_impl<Derived, EssentialPart>::run(*this, essential, tau, workspace);
405 }
406}
407
423template <typename Derived>
424template <typename EssentialPart>
425EIGEN_DEVICE_FUNC void MatrixBase<Derived>::applyHouseholderOnTheRight(const EssentialPart& essential,
426 const Scalar& tau, Scalar* workspace) {
427 if (cols() == 1) {
428 *this *= Scalar(1) - tau;
429 } else if (!numext::is_exactly_zero(tau)) {
430 internal::householder_apply_right_impl<Derived, EssentialPart>::run(*this, essential, tau, workspace);
431 }
432}
433
434} // end namespace Eigen
435
436#endif // EIGEN_HOUSEHOLDER_H
Expression of a fixed-size or dynamic-size block.
Definition Block.h:111
constexpr FixedSegmentReturnType<... >::Type tail(NType n)
Definition DenseBase.h:1222
constexpr RowXpr row(Index i)
Definition DenseBase.h:1095
typename internal::traits< Derived >::Scalar Scalar
Definition DenseBase.h:63
constexpr CastXpr< NewType >::Type cast() const
Definition DenseBase.h:66
A matrix or vector expression mapping an existing array of data.
Definition Map.h:97
Base class for all dense matrices, vectors, and expressions.
Definition MatrixBase.h:53
void makeHouseholder(EssentialPart &essential, Scalar &tau, RealScalar &beta) const
Definition Householder.h:154
void applyHouseholderOnTheLeft(const EssentialPart &essential, const Scalar &tau, Scalar *workspace)
Definition Householder.h:398
void applyHouseholderOnTheRight(const EssentialPart &essential, const Scalar &tau, Scalar *workspace)
Definition Householder.h:425
void makeHouseholderInPlace(Scalar &tau, RealScalar &beta)
Definition Householder.h:124
Expression of a fixed-size or dynamic-size sub-vector.
Definition VectorBlock.h:59
constexpr unsigned int DirectAccessBit
Definition Constants.h:160