12#ifndef EIGEN_HOUSEHOLDER_H
13#define EIGEN_HOUSEHOLDER_H
16#include "./InternalHeaderCheck.h"
22struct decrement_size : std::integral_constant<int, N - 1> {};
24struct decrement_size<0> : std::integral_constant<int, 0> {};
26struct decrement_size<Dynamic> : std::integral_constant<int, Dynamic> {};
28template <
typename RealScalar>
29struct householder_norm_accumulator : stable_norm_accumulator<RealScalar> {};
32struct householder_norm_accumulator<float> {
38template <typename Scalar, typename Accumulator, bool IsComplex = NumTraits<Scalar>::IsComplex>
39struct householder_rescale;
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);
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;
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))
58 .template cast<Scalar>();
62template <
typename Scalar,
typename Accumulator>
63struct householder_rescale<Scalar, Accumulator, true> {
64 using RealScalar =
typename NumTraits<Scalar>::Real;
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));
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);
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>());
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;
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;
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);
123template <
typename Derived>
152template <
typename Derived>
153template <
typename EssentialPart>
155 RealScalar& beta)
const {
156 EIGEN_STATIC_ASSERT_VECTOR_ONLY(EssentialPart)
159 const RealScalar tailSqNorm = size() == 1 ? RealScalar(0) :
tail.unwind().squaredNorm();
161 const RealScalar tol = (std::numeric_limits<RealScalar>::min)();
162 RealScalar unscaledNormThreshold = tol;
165 bool unscaledSqNormOverflows =
false;
168 bool tailHasInfinity =
false;
169 EIGEN_IF_CONSTEXPR (!NumTraits<RealScalar>::IsInteger) {
170 const RealScalar precision = RealScalar(NumTraits<RealScalar>::epsilon());
175 const RealScalar componentCount = RealScalar(size() - 1) * RealScalar(NumTraits<Scalar>::IsComplex ? 2 : 1);
176 unscaledNormThreshold = (tol / precision) * componentCount;
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();
196 const bool scaledCandidate = (tailSqNorm <= unscaledNormThreshold || unscaledSqNormOverflows) &&
197 !(numext::isnan)(tailSqNorm) && !tailHasInfinity;
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()))) {
208 beta = numext::real(c0);
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();
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))) {
221 beta = numext::real(c0);
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);
231 if (scale < Accumulator(tol) && numext::is_exactly_zero(realScale + realScale)) {
233 beta = numext::real(c0);
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));
242 scaledBeta = internal::householder_beta<RealScalar>(scaledBeta, numext::real(c0));
243 beta = RealScalar(scale * Accumulator(scaledBeta));
245 tau = internal::householder_rescale<Scalar, Accumulator>::zero_tail_tau(scaledReal, scaledImag, scaledBeta);
249 Accumulator scaledTailSqNorm;
250 EIGEN_IF_CONSTEXPR (std::is_same<RealScalar, float>::value) {
252 scaledTailSqNorm = tailComponents.template
cast<Accumulator>().squaredNorm() / (scale * scale);
254 scaledTailSqNorm = (tailComponents.template
cast<Accumulator>().array() / scale).matrix().squaredNorm();
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);
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);
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,
282 mat.rows() - 1, mat.cols());
283 tmp.noalias() = essential.adjoint() * bottom.unwind();
284 tmp = tau * (tmp + mat.
row(0));
286 bottom.unwind().noalias() -= essential * tmp;
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,
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;
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,
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(),
322 tmp.noalias() = right.unwind() * essential;
324 tmp = (tmp + mat.col(0)) * tau;
325 mat.col(0) = mat.col(0) - tmp;
326 right.unwind().noalias() -= tmp * essential.adjoint();
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;
338 static EIGEN_DEVICE_FUNC
void run(MatrixBase<Derived>& mat,
const EssentialPart& essential,
const Scalar& tau,
340 constexpr Index PacketSize = unpacket_traits<Packet>::size;
341 eigen_assert(mat.cols() == K + 1);
344 for (
int j = 0; j < K; ++j) {
345 v[j] = essential.coeff(j);
346 vc[j] = numext::conj(v[j]);
348 const Scalar tauValue = tau;
349 const Index rows = mat.rows();
351 for (
int j = 0; j <= K; ++j) col[j] = &mat.derived().coeffRef(0, j);
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]);
359 const Index vectorEnd = numext::round_down(rows, PacketSize);
360 for (Index i = 0; i < vectorEnd; i += PacketSize) {
362 for (
int j = 0; j <= K; ++j) x[j] = ploadu<Packet>(col[j] + i);
364 for (
int j = 0; j < K; ++j) t = pmadd(x[j + 1], pv[j], t);
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]));
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];
374 for (
int j = 0; j < K; ++j) col[j + 1][i] -= t * vc[j];
396template <
typename Derived>
397template <
typename EssentialPart>
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);
423template <
typename Derived>
424template <
typename EssentialPart>
429 }
else if (!numext::is_exactly_zero(tau)) {
430 internal::householder_apply_right_impl<Derived, EssentialPart>::run(*
this, essential, tau, workspace);
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