Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
TridiagonalInverseIteration.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2026 Rasmus Munk Larsen <rmlarsen@gmail.com>
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_TRIDIAGONAL_INVERSE_ITERATION_H
12#define EIGEN_TRIDIAGONAL_INVERSE_ITERATION_H
13
14#include "./SelfAdjointEigenSolver.h"
15// For tridiagonal_sturm_count_below(), used to assign eigenvalues to disconnected blocks.
16#include "./TridiagonalBisection.h"
17
18// IWYU pragma: private
19#include "./InternalHeaderCheck.h"
20
21namespace Eigen {
22namespace internal {
23
35struct inverse_iteration_rng {
36 numext::uint64_t state;
37
38 explicit inverse_iteration_rng(numext::uint64_t seed) : state(seed) {}
39
40 template <typename RealScalar>
41 RealScalar next() {
42 // SplitMix64: a strong avalanche so that consecutive per-column seeds yield well-separated
43 // (uncorrelated) start vectors -- consecutive LCG seeds would produce near-parallel starts that
44 // collapse under the cluster reorthogonalization.
45 state += 0x9E3779B97F4A7C15ULL;
46 const numext::uint64_t z = splitmix64_mix(state);
47 // Top 32 bits give a uniform integer in [0, 2^32); map to [0, 1) and then to [-1, 1).
48 // RealScalar must be float or wider: a narrower scalar overflows RealScalar(hi) to infinity
49 // (inf * 0 = NaN start vectors), which is why TridiagonalEigenSolver computes scalars narrower
50 // than float in float (see its ComputeScalar) and none of this code ever runs on them.
51 const numext::uint32_t hi = numext::uint32_t(z >> 32);
52 const RealScalar u = RealScalar(hi) * (RealScalar(1) / RealScalar(4294967296.0));
53 return RealScalar(2) * u - RealScalar(1);
54 }
55};
56
84template <typename RealScalar>
85void tridiagonal_lagtf(RealScalar* d, RealScalar* du, RealScalar* dl, RealScalar* du2, Index* piv, RealScalar lambda,
86 Index n) {
87 d[0] -= lambda;
88 piv[n - 1] = 0;
89 if (n == 1) return;
90
91 RealScalar scale1 = numext::abs(d[0]) + numext::abs(du[0]);
92 for (Index k = 0; k < n - 1; ++k) {
93 d[k + 1] -= lambda;
94 RealScalar scale2 = numext::abs(dl[k]) + numext::abs(d[k + 1]);
95 if (k < n - 2) scale2 += numext::abs(du[k + 1]);
96 // Scaled magnitudes of the two candidate pivots; pick the larger (partial pivoting).
97 const RealScalar piv1 = numext::is_exactly_zero(d[k]) ? RealScalar(0) : numext::abs(d[k]) / scale1;
98 if (numext::is_exactly_zero(dl[k])) {
99 piv[k] = 0;
100 scale1 = scale2;
101 if (k < n - 2) du2[k] = RealScalar(0);
102 } else {
103 const RealScalar piv2 = numext::abs(dl[k]) / scale2;
104 if (piv2 <= piv1) {
105 // No interchange: eliminate using the diagonal pivot d[k] (non-zero, since piv2 > 0).
106 piv[k] = 0;
107 scale1 = scale2;
108 dl[k] = dl[k] / d[k];
109 d[k + 1] -= dl[k] * du[k];
110 if (k < n - 2) du2[k] = RealScalar(0);
111 } else {
112 // Interchange rows k and k+1; the sub-diagonal entry becomes the pivot.
113 piv[k] = 1;
114 const RealScalar mult = d[k] / dl[k];
115 d[k] = dl[k];
116 const RealScalar temp = d[k + 1];
117 d[k + 1] = du[k] - mult * temp;
118 if (k < n - 2) {
119 du2[k] = du[k + 1];
120 du[k + 1] = -mult * du2[k];
121 }
122 du[k] = temp;
123 dl[k] = mult;
124 }
125 }
126 }
127}
128
150template <typename RealScalar>
151void tridiagonal_lagts(const RealScalar* d, const RealScalar* rcp, const RealScalar* du, const RealScalar* dl,
152 const RealScalar* du2, const Index* piv, RealScalar* b, Index n) {
153 const RealScalar eps = NumTraits<RealScalar>::epsilon();
154 const RealScalar sfmin = (std::numeric_limits<RealScalar>::min)();
155 const RealScalar bignum = RealScalar(1) / sfmin;
156
157 // Perturbation floor: eps times the largest magnitude entry of U.
158 using ArrayBuf = Map<const Array<RealScalar, Dynamic, 1>>;
159 RealScalar tol = ArrayBuf(d, n).abs().maxCoeff();
160 if (n > 1) tol = numext::maxi(tol, ArrayBuf(du, n - 1).abs().maxCoeff());
161 if (n > 2) tol = numext::maxi(tol, ArrayBuf(du2, n - 2).abs().maxCoeff());
162 tol *= eps;
163 if (numext::is_exactly_zero(tol)) tol = eps;
164
165 // Forward substitution: apply P then L^{-1}. Written branchlessly in the (data-dependent, roughly
166 // 50/50) pivot-interchange flag so a misprediction cannot stall the serial recurrence; both arms
167 // are evaluated and selected, reproducing the two branches bit for bit.
168 for (Index k = 1; k < n; ++k) {
169 const RealScalar dlk = dl[k - 1];
170 const RealScalar bkm1 = b[k - 1];
171 const RealScalar bk = b[k];
172 const bool interchange = piv[k - 1] != 0;
173 b[k - 1] = interchange ? bk : bkm1;
174 b[k] = interchange ? (bkm1 - dlk * bk) : (bk - dlk * bkm1);
175 }
176
177 // Back substitution: solve U x = b. Away from the singularity the pivot is safe and the quotient is
178 // a reciprocal multiply (rcp[k] = 1/d[k], exact and precomputed once for all the solves); only a
179 // dangerously small pivot -- the rare near-singular element of the deliberately singular system --
180 // falls back to the LAPACK xLAGTS perturbation/rescale with a true division. The guard is written so
181 // the fast path is taken exactly when the original would divide by the unperturbed pivot, and is
182 // virtually always predicted taken.
183 for (Index k = n - 1; k >= 0; --k) {
184 RealScalar temp = b[k];
185 if (k <= n - 2) temp -= du[k] * b[k + 1];
186 if (k <= n - 3) temp -= du2[k] * b[k + 2];
187 const RealScalar ak = d[k];
188 const RealScalar absak = numext::abs(ak);
189 if (EIGEN_PREDICT_TRUE(absak >= RealScalar(1) || (absak >= sfmin && numext::abs(temp) <= absak * bignum))) {
190 b[k] = temp * rcp[k];
191 } else {
192 // Tiny pivot: perturb (or rescale) exactly as LAPACK xLAGTS so the quotient cannot overflow.
193 RealScalar a = ak;
194 RealScalar t = temp;
195 RealScalar pert = (a >= RealScalar(0)) ? tol : -tol;
196 while (true) {
197 const RealScalar aa = numext::abs(a);
198 if (aa < RealScalar(1)) {
199 if (aa < sfmin) {
200 if (numext::is_exactly_zero(aa) || numext::abs(t) * sfmin > aa) {
201 a += pert;
202 pert *= RealScalar(2);
203 continue;
204 } else {
205 t *= bignum;
206 a *= bignum;
207 }
208 } else if (numext::abs(t) > aa * bignum) {
209 a += pert;
210 pert *= RealScalar(2);
211 continue;
212 }
213 }
214 break;
215 }
216 b[k] = t / a;
217 }
218 }
219}
220
247template <typename RealScalar, typename EivecType>
248Index tridiagonal_inverse_iteration_block(const RealScalar* sdiag, const RealScalar* ssub, const RealScalar* xj_scaled,
249 const Index* clstart, Index n, RealScalar onenrm, RealScalar dtpcrt,
250 int maxits, int extra, EivecType& eivecs, Index j_lo, Index j_hi) {
251 using RealVectorType = Matrix<RealScalar, Dynamic, 1>;
252 const RealScalar eps = NumTraits<RealScalar>::epsilon();
253
254 // Work arrays for the LU factors of T - xj*I (reused across the block's columns) and the iterate.
255 // lu_rcp holds the exact reciprocal of the U diagonal, computed once per factorization and reused by
256 // the inverse-iteration back-solves. Being locals, each thread gets its own copy.
257 RealVectorType lu_d(n), lu_dl(n), lu_du(n), lu_du2(n), lu_rcp(n), b(n);
258 Matrix<Index, Dynamic, 1> piv(n);
259
260 Index nonconv = 0; // columns that exhausted maxits without satisfying the growth test
261 for (Index j = j_lo; j < j_hi; ++j) {
262 const RealScalar xj = xj_scaled[j];
263 const Index gpind = clstart[j]; // first column of j's cluster (>= j_lo by block alignment)
264
265 // Factor T - xj*I = P L U once; the inverse-iteration loop reuses it.
266 lu_d = Map<const RealVectorType>(sdiag, n);
267 lu_du.head(n - 1) = Map<const RealVectorType>(ssub, n - 1);
268 lu_dl.head(n - 1) = Map<const RealVectorType>(ssub, n - 1);
269 tridiagonal_lagtf<RealScalar>(lu_d.data(), lu_du.data(), lu_dl.data(), lu_du2.data(), piv.data(), xj, n);
270 // Exact reciprocals of the U diagonal (pdiv, not the approximate preciprocal of cwiseInverse());
271 // a vanishing pivot yields inf, which the back-solve fast path never consumes.
272 lu_rcp.array() = RealScalar(1) / lu_d.array();
273
274 // Deterministic pseudo-random start vector (seeded per column for thread independence).
275 inverse_iteration_rng rng(numext::uint64_t(j) + 1);
276 for (Index i = 0; i < n; ++i) b[i] = rng.template next<RealScalar>();
277
278 int nrmchk = 0;
279 bool converged = false;
280 for (int its = 0; its < maxits; ++its) {
281 // Scale the right-hand side so the near-singular solve neither overflows nor underflows.
282 const RealScalar bmax = b.cwiseAbs().maxCoeff();
283 if (numext::is_exactly_zero(bmax)) break; // degenerate iterate; cannot grow -> not converged
284 const RealScalar target = RealScalar(n) * onenrm * numext::maxi(eps, numext::abs(lu_d[n - 1]));
285 const RealScalar scl = target / bmax;
286 if (EIGEN_PREDICT_TRUE(scl >= (std::numeric_limits<RealScalar>::min)())) {
287 b *= scl;
288 } else {
289 // scl underflowed (huge iterate from a shift within ~pivmin of an exact eigenvalue). A
290 // subnormal or flushed-to-zero scale would zero the iterate on flush-to-zero hardware
291 // (ARMv7 NEON), so scale in two in-range steps instead.
292 b /= bmax;
293 b *= target;
294 }
295 tridiagonal_lagts<RealScalar>(lu_d.data(), lu_rcp.data(), lu_du.data(), lu_dl.data(), lu_du2.data(), piv.data(),
296 b.data(), n);
297
298 // Modified Gram-Schmidt against the already-accepted eigenvectors of this cluster.
299 for (Index i = gpind; i < j; ++i) b -= b.dot(eivecs.col(i)) * eivecs.col(i);
300
301 const RealScalar nrm = b.cwiseAbs().maxCoeff();
302 if (nrm < dtpcrt) continue; // not yet grown into the eigenvector; iterate
303 if (++nrmchk < extra + 1) continue; // a couple of safety iterations past the threshold
304 converged = true;
305 break;
306 }
307 // LAPACK xSTEIN reports vectors that never satisfied the growth test; mirror that. The column is
308 // still written (best effort), but the caller surfaces the count as ComputationInfo::NoConvergence.
309 if (!converged) ++nonconv;
310
311 // Normalize to unit 2-norm with a deterministic sign (largest-magnitude entry positive). The
312 // iterate can carry huge entries (~1/eps times the start) on a nearly singular solve, so scale
313 // before taking the norm -- otherwise squaredNorm() would overflow and zero out the vector.
314 Index jmax = 0;
315 const RealScalar binf = b.cwiseAbs().maxCoeff(&jmax);
316 safe_scaling<RealScalar>::scale_to(b, b, binf);
317 const RealScalar nrm2 = b.norm();
318 RealScalar scl = numext::is_exactly_zero(nrm2) ? RealScalar(1) : RealScalar(1) / nrm2;
319 if (b[jmax] < RealScalar(0)) scl = -scl;
320 eivecs.col(j) = b * scl;
321 }
322 return nonconv;
323}
324
346template <typename DiagType, typename SubdiagType, typename EivalType, typename EivecType>
347Index tridiagonal_inverse_iteration_connected(const DiagType& diag, const SubdiagType& subdiag, const EivalType& eivals,
348 EivecType& eivecs) {
349 using RealScalar = typename DiagType::Scalar;
350 EIGEN_STATIC_ASSERT(NumTraits<RealScalar>::IsInteger == 0 && NumTraits<RealScalar>::IsComplex == 0,
351 THIS_FUNCTION_IS_NOT_FOR_INTEGER_OR_COMPLEX_TYPES)
352
353 const Index n = diag.size();
354 const Index m = eivals.size();
355 if (n == 0 || m == 0) return 0;
356 if (n == 1) {
357 eivecs.setOnes();
358 return 0;
359 }
360
361 const RealScalar eps = NumTraits<RealScalar>::epsilon();
362
363 // Normalize T (and the shifts) to O(1) so the deliberately near-singular factor/solve cannot
364 // overflow or underflow; eigenvectors are invariant under this uniform scaling.
365 // The rescan recovers an all-subnormal input that a flushing SIMD unit reads as zero.
366 const RealScalar maxCoeff = max_preserving_subnormals(
367 safe_scaling<RealScalar>::recover_flushed_max_coeff(diag, diag.cwiseAbs().maxCoeff()),
368 safe_scaling<RealScalar>::recover_flushed_max_coeff(subdiag, subdiag.cwiseAbs().maxCoeff()));
369 Matrix<RealScalar, Dynamic, 1> sdiag(n), ssub(n - 1);
370 const auto factors = safe_scaling<RealScalar>::scale_to(sdiag, diag, maxCoeff);
371 safe_scaling<RealScalar>::scale_to(ssub, subdiag, maxCoeff, factors);
372 Matrix<RealScalar, Dynamic, 1> xj_scaled(m);
373 safe_scaling<RealScalar>::scale_to(xj_scaled, eivals, maxCoeff, factors);
374 if (maxCoeff > RealScalar(0) && maxCoeff < (std::numeric_limits<RealScalar>::min)()) {
375 // The first scale is clamped to normal range. Finish normalization in a second finite step
376 // so the absolute pivot floor and growth threshold still see an O(1) matrix.
377 const RealScalar scaledMax = numext::maxi(sdiag.cwiseAbs().maxCoeff(), ssub.cwiseAbs().maxCoeff());
378 const auto remaining = safe_scaling<RealScalar>::scale_in_place(sdiag, scaledMax);
379 safe_scaling<RealScalar>::scale_in_place(ssub, scaledMax, remaining);
380 safe_scaling<RealScalar>::scale_in_place(xj_scaled, scaledMax, remaining);
381 }
382
383 // Infinity norm of the scaled T: max_i (|e_{i-1}| + |d_i| + |e_i|), missing boundary off-diagonals zero.
384 RealScalar onenrm = numext::abs(sdiag[0]) + numext::abs(ssub[0]);
385 onenrm = numext::maxi(onenrm, numext::abs(sdiag[n - 1]) + numext::abs(ssub[n - 2]));
386 if (n > 2)
387 onenrm = numext::maxi(onenrm, (ssub.head(n - 2).array().abs() + sdiag.segment(1, n - 2).array().abs() +
388 ssub.segment(1, n - 2).array().abs())
389 .maxCoeff());
390 if (numext::is_exactly_zero(onenrm)) onenrm = RealScalar(1); // T == 0: any orthonormal basis works
391
392 // Cluster threshold and convergence threshold (LAPACK xSTEIN constants).
393 const RealScalar ortol = RealScalar(1e-3) * onenrm;
394 const RealScalar dtpcrt = numext::sqrt(RealScalar(0.1) / RealScalar(n));
395 const int maxits = 5;
396 const int extra = 2;
397
398 // Pre-pass (sequential, O(m)): the perturbed, scaled shift xj_scaled[j] and the cluster start
399 // clstart[j] (index of the first eigenvalue of j's cluster). Reproduced exactly as the serial sweep
400 // would, so the parallel column blocks below match the serial result bit for bit. A shift sitting on
401 // top of its predecessor is nudged up by pertol so the two factorizations stay distinct; a gap larger
402 // than ortol starts a new cluster (within which the eigenvectors are reorthogonalized). The
403 // perturbation is at most ~pertol << ortol, so it never moves a column across a cluster boundary.
404 Matrix<Index, Dynamic, 1> clstart(m);
405 {
406 Index gpind = 0;
407 RealScalar xjm = RealScalar(0); // previous (possibly perturbed) shift
408 for (Index j = 0; j < m; ++j) {
409 RealScalar xj = xj_scaled[j];
410 if (j > 0) {
411 // The xSTEIN nudge 10*eps*|xj| separates coincident shifts so their factorizations differ.
412 // Capped at a fraction of the cluster threshold: at low precision (bfloat16: 10*eps ~ 0.08)
413 // the un-capped nudge can push a shift across a cluster boundary into a neighbouring
414 // eigenspace. Shifts the cap leaves coincident still yield an orthonormal basis, via the
415 // per-cluster Gram-Schmidt on independent random starts.
416 const RealScalar pertol = numext::mini(RealScalar(10) * numext::abs(eps * xj), RealScalar(0.25) * ortol);
417 if (xj - xjm < pertol) xj = xjm + pertol;
418 }
419 if (j == 0 || numext::abs(xj - xjm) > ortol) gpind = j;
420 xj_scaled[j] = xj;
421 clstart[j] = gpind;
422 xjm = xj;
423 }
424 }
425
426 const RealScalar* sdiag_p = sdiag.data();
427 const RealScalar* ssub_p = ssub.data();
428 const RealScalar* xj_p = xj_scaled.data();
429 const Index* cl_p = clstart.data();
430
431 // Distinct clusters are independent, so the columns split across threads with a single fork/join:
432 // thread t owns a contiguous slice of columns snapped to cluster boundaries (so no cluster straddles
433 // two threads) and writes only those columns of eivecs. No communication until the join, and the
434 // result is bit-identical to the serial path for any thread count. Each thread tallies its own
435 // non-converged columns; the reduction sums them into the value returned to the caller.
436 Index nonconv = 0;
437#if defined(EIGEN_HAS_OPENMP)
438 int nthreads = 1;
439 // Don't nest inside an existing parallel region, and only fork when there is enough work to amortize
440 // the thread overhead. Each column costs ~one O(n) factorization plus a few O(n) back-solves.
441 if (omp_get_num_threads() == 1) {
442 // Work ~ m columns * n rows (a factorization plus a few O(n) back-solves each). kMinTaskSize is the
443 // minimum such work to give each thread before adding one: m*n / kMinTaskSize threads, capped at
444 // the pool size. The value is measured -- at m*n = 2*kMinTaskSize (the two-thread point) inverse
445 // iteration is already ~2x faster than serial, with the gain growing to the core count for larger n.
446 const double work = double(m) * double(n);
447 const double kMinTaskSize = 2048.0;
448 const Index work_threads = Index(work / kMinTaskSize);
449 nthreads = int(numext::maxi(Index(1), numext::mini(work_threads, Index(Eigen::nbThreads()))));
450 }
451 if (nthreads > 1) {
452#pragma omp parallel num_threads(nthreads) reduction(+ : nonconv)
453 {
454 const Index nt = omp_get_num_threads();
455 const Index tid = omp_get_thread_num();
456 // Balanced split snapped up to the next cluster boundary (clstart[j]==j marks a cluster start).
457 // Adjacent threads snap the same raw index to the same boundary, so the blocks tile [0, m)
458 // exactly; a thread whose whole share falls inside one cluster simply gets an empty block.
459 Index lo = tid * m / nt;
460 Index hi = (tid + 1) * m / nt;
461 while (lo < m && cl_p[lo] != lo) ++lo;
462 while (hi < m && cl_p[hi] != hi) ++hi;
463 nonconv += tridiagonal_inverse_iteration_block<RealScalar>(sdiag_p, ssub_p, xj_p, cl_p, n, onenrm, dtpcrt, maxits,
464 extra, eivecs, lo, hi);
465 }
466 } else
467#endif
468 {
469 nonconv = tridiagonal_inverse_iteration_block<RealScalar>(sdiag_p, ssub_p, xj_p, cl_p, n, onenrm, dtpcrt, maxits,
470 extra, eivecs, 0, m);
471 }
472 return nonconv;
473}
474
518template <typename DiagType, typename SubdiagType, typename EivalType, typename EivecType>
519Index tridiagonal_inverse_iteration(const DiagType& diag, const SubdiagType& subdiag, const EivalType& eivals,
520 EivecType& eivecs,
521 typename DiagType::Scalar shift_tol = typename DiagType::Scalar(0)) {
522 using RealScalar = typename DiagType::Scalar;
523 using VectorType = Matrix<RealScalar, Dynamic, 1>;
524 const Index n = diag.size();
525 const Index m = eivals.size();
526 if (n == 0 || m == 0) return 0;
527
528 // A matrix whose largest entry is below the recovery threshold min / eps can hold significant subnormal
529 // couplings, which FTZ/DAZ hardware reads as zero in the comparisons below (ARMv7 NEON also in the packet maxima).
530 // Scale it into the normal range first, exactly, through integer significands: the eigenvectors are invariant
531 // under the scaling, and every representable entry becomes normal. The test reads the exponent from the
532 // representation, since the maximum itself may be subnormal and a floating-point comparison on it is what FTZ/DAZ
533 // breaks; a zero or non-finite maximum has no exponent in range and is left alone.
534 {
535 RealScalar maxCoeff = safe_scaling<RealScalar>::recover_flushed_max_coeff(diag, diag.cwiseAbs().maxCoeff());
536 if (n >= 2) {
537 maxCoeff = max_preserving_subnormals(
538 maxCoeff, safe_scaling<RealScalar>::recover_flushed_max_coeff(subdiag, subdiag.cwiseAbs().maxCoeff()));
539 }
540 // 2^(e - 1) <= maxCoeff < 2^e, so maxCoeff < 2^recovery iff e <= recovery; e == 0 for a zero maximum and one
541 // above the largest finite exponent for infinities and NaN.
542 const int e = frexp_exponent_preserving_subnormals(maxCoeff);
543 if (e != 0 && e <= safe_scaling<RealScalar>::subnormal_recovery_exponent()) {
544 VectorType sdiag(n), ssub(n - 1), seivals(m), stol(1);
545 const auto factors = safe_scaling<RealScalar>::scale_to(sdiag, diag, maxCoeff);
546 safe_scaling<RealScalar>::scale_to(ssub, subdiag, maxCoeff, factors);
547 safe_scaling<RealScalar>::scale_to(seivals, eivals, maxCoeff, factors);
548 safe_scaling<RealScalar>::scale_to(stol, VectorType::Constant(1, shift_tol), maxCoeff, factors);
549 return tridiagonal_inverse_iteration(sdiag, ssub, seivals, eivecs, stol(0));
550 }
551 }
552
553 // Split at negligible couplings (cf. xSTEBZ): |e_k| <= eps * sqrt(|d_k|) * sqrt(|d_k+1|). The
554 // geometric-mean form is scale-invariant on its own (both sides scale linearly) and needs no
555 // additive floor: a floor expressed at any single scale falsely splits strongly connected blocks
556 // living far below that scale. Taking square roots before multiplying keeps every intermediate in
557 // range, so the comparison stays exact down to subnormal entries; a zero coupling always splits.
558 const RealScalar eps = NumTraits<RealScalar>::epsilon();
559 Matrix<Index, Dynamic, 1> bstart(n + 1); // block b spans rows [bstart(b), bstart(b+1))
560 Index nblocks = 1;
561 bstart(0) = 0;
562 if (n > 1) {
563 const Array<bool, Dynamic, 1> split = (subdiag.array().abs() <= eps * (diag.head(n - 1).array().abs().sqrt() *
564 diag.tail(n - 1).array().abs().sqrt()));
565 for (Index k = 0; k + 1 < n; ++k)
566 if (split(k)) bstart(nblocks++) = k + 1;
567 }
568 bstart(nblocks) = n;
569
570 if (nblocks == 1) return tridiagonal_inverse_iteration_connected(diag, subdiag, eivals, eivecs);
571
572 // Per-block normalized data (block-local scale) for the assignment Sturm counts, and the
573 // per-block localization tolerance btol: the count's rounding-displacement bound at the block's
574 // own scale. The subset-edge windows below are widened by btol so that a requested value equal to
575 // a block eigenvalue (up to that block's rounding) is found, without a window at any other
576 // block's scale swallowing well-separated foreign eigenvalues -- a tolerance expressed at the
577 // global scale would hand a small block's eigenvalue to whichever block comes first.
578 const RealScalar safemin = numext::maxi(RealScalar(1) / NumTraits<RealScalar>::highest(),
579 (RealScalar(1) + eps) * (std::numeric_limits<RealScalar>::min)());
580 // bgap is the connected kernel's reorthogonalization threshold for the block, in original units.
581 VectorType alpha_all(n), beta_sq_all(n), bscale(nblocks), bpivmin(nblocks), btol(nblocks), bgap(nblocks);
582 RealScalar gscale = RealScalar(0);
583 for (Index b = 0; b < nblocks; ++b) {
584 const Index b0 = bstart(b), nb = bstart(b + 1) - b0;
585 RealScalar s = diag.segment(b0, nb).cwiseAbs().maxCoeff();
586 if (nb > 1) s = numext::maxi(s, subdiag.segment(b0, nb - 1).cwiseAbs().maxCoeff());
587 if (numext::is_exactly_zero(s)) s = RealScalar(1);
588 gscale = numext::maxi(gscale, s);
589 auto alpha = alpha_all.segment(b0, nb);
590 const auto factors = safe_scaling<RealScalar>::scale_to(alpha, diag.segment(b0, nb), s);
591 bscale(b) = factors.scale;
592 RealScalar max_bsq = RealScalar(0);
593 // Infinity norm of the normalized block, as tridiagonal_inverse_iteration_connected() computes it.
594 RealScalar onenrm = numext::abs(alpha(0));
595 if (nb > 1) {
596 auto beta = beta_sq_all.segment(b0, nb - 1);
597 safe_scaling<RealScalar>::scale_to(beta, subdiag.segment(b0, nb - 1), s, factors);
598 beta = beta.cwiseAbs();
599 for (Index i = 0; i < nb; ++i) {
600 const RealScalar radius = (i > 0 ? beta(i - 1) : RealScalar(0)) + (i + 1 < nb ? beta(i) : RealScalar(0));
601 onenrm = numext::maxi(onenrm, numext::abs(alpha(i)) + radius);
602 }
603 beta = beta.array().square();
604 max_bsq = beta.maxCoeff();
605 }
606 bpivmin(b) = safemin * numext::maxi(max_bsq, RealScalar(1));
607 bgap(b) = RealScalar(1e-3) * onenrm * bscale(b);
608 // In original units, block row sums are bounded by 3*s, independently of the chosen scaling factor.
609 btol(b) = RealScalar(2.1) * (RealScalar(3) * RealScalar(nb) * eps + RealScalar(4) * safemin) * s;
610 }
611
612 // Assign each requested eigenvalue to a block by capacity. Groups are runs of exactly-equal
613 // requested values; a block's capacity for a group is its Sturm count over the group's value
614 // interval, bounded by the midpoints to the neighbouring distinct values and, at the subset's
615 // edges, widened by a tolerance. The edge tolerance is tiered: the per-block btol first, so that
616 // exactly supplied eigenvalues can only be claimed by the block that owns them, and -- when the
617 // edge group still cannot cover its copies -- the matrix-scale gtol, which admits requested
618 // values whose error is at the scale of the whole matrix (e.g. the staged bisection's output for
619 // a block much smaller than the matrix norm). The intervals partition the requested span and
620 // adjacent intervals share their boundary evaluation, so each block eigenvalue is counted exactly
621 // once even at count knife-edges. A copy its own interval cannot supply is carried into the next
622 // interval; copies left at the end pair up with the blocks holding leftover span capacity (a
623 // miscount that let a block absorb a foreign copy freed exactly one such slot elsewhere).
624 const RealScalar gtol = RealScalar(2.1) * (RealScalar(3) * RealScalar(n) * eps + RealScalar(4) * safemin) * gscale;
625 Matrix<Index, Dynamic, 1> blockof(m), assigned(nblocks), caps(nblocks), below_prev(nblocks), below_cur(nblocks),
626 below_edge(nblocks), carry(m), carry_next(m);
627 assigned.setZero();
628 Matrix<Index, Dynamic, 1> local_index(m);
629 Array<bool, Dynamic, 1> claimed = Array<bool, Dynamic, 1>::Constant(n, false);
630 // The shift x + t (t a tolerance of either sign) in block b's normalized units, clamped to +-16. The normalized
631 // entries are below 4, so the block's spectrum lies in (-12, 12) there and the Sturm count anywhere beyond +-16 is 0
632 // or nb: clamping changes no count, and keeps x + t and (x + t) / bscale from overflowing (for x within t of the
633 // overflow threshold, or far outside a small block). Each operation stays in range on both sides of every select,
634 // which compilers may evaluate eagerly.
635 const RealScalar highest = NumTraits<RealScalar>::highest();
636 const RealScalar half_ulp_highest =
637 numext::ldexp(RealScalar(1), NumTraits<RealScalar>::max_exponent() - NumTraits<RealScalar>::digits() - 1);
638 auto normalized_shift = [&](Index b, RealScalar x, RealScalar t) -> RealScalar {
639 const RealScalar limit(16);
640 // x + t overflows iff x and t share a sign and |x| + |t| >= highest + half_ulp_highest. With a >= c their
641 // magnitudes, highest - a is exact for a >= highest / 2 and exceeds c otherwise, so this test is exact.
642 const RealScalar a = numext::maxi(numext::abs(x), numext::abs(t));
643 const RealScalar c = numext::mini(numext::abs(x), numext::abs(t));
644 const bool beyond = (x > RealScalar(0)) == (t > RealScalar(0)) && c - (highest - a) >= half_ulp_highest;
645 const RealScalar y = x + (beyond ? RealScalar(0) : t);
646 // limit * bscale where finite; beyond that, |y| / bscale < limit for every finite y.
647 const RealScalar ymax = numext::mini(bscale(b), highest / limit) * limit;
648 const RealScalar yn = numext::mini(numext::maxi(y, -ymax), ymax) / bscale(b);
649 return beyond ? (t > RealScalar(0) ? limit : -limit) : yn;
650 };
651 // Sturm count over block b of its eigenvalues strictly below the unnormalized shift x + t.
652 auto count_below = [&](Index b, RealScalar x, RealScalar t) -> Index {
653 const Index b0 = bstart(b), nb = bstart(b + 1) - b0;
654 return tridiagonal_sturm_count_below<RealScalar>(alpha_all.data() + b0, beta_sq_all.data() + b0, nb, bpivmin(b),
655 normalized_shift(b, x, t));
656 };
657 for (Index b = 0; b < nblocks; ++b) below_prev(b) = count_below(b, eivals[0], -btol(b));
658 below_edge = below_prev;
659 Index ncarry = 0;
660 Index g_begin = 0;
661 while (g_begin < m) {
662 Index g_end = g_begin + 1;
663 while (g_end < m && !(eivals[g_begin] < eivals[g_end])) ++g_end;
664 // Upper boundary: midpoint to the next distinct value, or the per-block widened edge at the end.
665 const bool first = (g_begin == 0);
666 const bool last = (g_end >= m);
667 const RealScalar mid_bound =
668 last ? RealScalar(0) : RealScalar(0.5) * eivals[g_end - 1] + RealScalar(0.5) * eivals[g_end];
669 bool widened = false;
670 while (true) {
671 Index total = 0;
672 for (Index b = 0; b < nblocks; ++b) {
673 // t = -0 keeps a mid_bound of -0 intact: x + -0 == x for every x.
674 below_cur(b) =
675 last ? count_below(b, eivals[m - 1], widened ? gtol : btol(b)) : count_below(b, mid_bound, -RealScalar(0));
676 caps(b) = numext::maxi(Index(0), below_cur(b) - below_prev(b));
677 total += caps(b);
678 }
679 // Retry an edge group once with the matrix-scale tolerance if the block-scale windows left it
680 // short; interior deficits are handled by the carry chain instead.
681 if (widened || !(first || last) || total >= g_end - g_begin + (last ? ncarry : 0)) break;
682 widened = true;
683 if (first) {
684 for (Index b = 0; b < nblocks; ++b) below_prev(b) = count_below(b, eivals[0], -gtol);
685 below_edge = below_prev;
686 }
687 }
688 // The group's own copies first, then the carried ones; whatever finds no capacity carries on.
689 Index ncarry_next = 0;
690 for (Index pass = 0; pass < 2; ++pass) {
691 const Index count = (pass == 0) ? g_end - g_begin : ncarry;
692 for (Index c = 0; c < count; ++c) {
693 const Index j = (pass == 0) ? g_begin + c : carry(c);
694 Index chosen = -1;
695 for (Index b = 0; b < nblocks && chosen < 0; ++b)
696 if (caps(b) > 0) chosen = b;
697 if (chosen < 0) {
698 carry_next(ncarry_next++) = j;
699 continue;
700 }
701 const Index index = below_cur(chosen) - caps(chosen);
702 local_index(j) = index;
703 claimed(bstart(chosen) + index) = true;
704 --caps(chosen);
705 ++assigned(chosen);
706 blockof(j) = chosen;
707 }
708 }
709 carry.swap(carry_next);
710 ncarry = ncarry_next;
711 below_prev = below_cur;
712 g_begin = g_end;
713 }
714 // Leftover copies: first blocks with leftover span capacity, then any block with spare rows.
715 for (Index c = 0; c < ncarry; ++c) {
716 const Index j = carry(c);
717 Index chosen = -1;
718 for (Index b = 0; b < nblocks && chosen < 0; ++b)
719 if (below_cur(b) - below_edge(b) - assigned(b) > 0) chosen = b;
720 if (chosen < 0)
721 for (Index b = 0; b < nblocks && chosen < 0; ++b)
722 if (bstart(b + 1) - bstart(b) - assigned(b) > 0) chosen = b;
723 if (chosen < 0) chosen = 0;
724 {
725 const Index b0 = bstart(chosen), nb = bstart(chosen + 1) - b0;
726 Index index = numext::mini(below_edge(chosen), nb - 1);
727 while (index < nb && claimed(b0 + index)) ++index;
728 if (index == nb) {
729 index = 0;
730 while (index < nb && claimed(b0 + index)) ++index;
731 }
732 if (index == nb) {
733 eivecs.setZero();
734 return m;
735 }
736 local_index(j) = index;
737 claimed(b0 + index) = true;
738 }
739 ++assigned(chosen);
740 blockof(j) = chosen;
741 }
742
743 // Run each block independently and scatter its columns; rows outside the block stay exactly zero.
744 eivecs.setZero();
745 Index nonconv = 0;
746 VectorType wloc, refined, endpoints;
747 Matrix<numext::int64_t, Dynamic, 1> counts;
748 Matrix<Index, Dynamic, 1> indices;
749 Matrix<RealScalar, Dynamic, Dynamic> vloc;
750 Matrix<Index, Dynamic, 1> colmap(m);
751 for (Index b = 0; b < nblocks; ++b) {
752 const Index b0 = bstart(b), nb = bstart(b + 1) - b0;
753 Index mb = 0;
754 for (Index j = 0; j < m; ++j)
755 if (blockof(j) == b) colmap(mb++) = j;
756 if (mb == 0) continue;
757 wloc.resize(mb);
758 for (Index k = 0; k < mb; ++k) wloc(k) = eivals[colmap(k)];
759 vloc.resize(nb, mb);
760 const VectorType bdiag = diag.segment(b0, nb);
761 const VectorType bsub = subdiag.segment(b0, nb > 1 ? nb - 1 : 0);
762 if (nb > 1) {
763 // Retain the capacity assignment, including multiplicities across blocks. As in LAPACK
764 // xSTEBZ, use block-local bisection accuracy rather than a global reorthogonalization floor.
765 indices.resize(mb);
766 for (Index k = 0; k < mb; ++k) indices(k) = local_index(colmap(k));
767 std::sort(indices.data(), indices.data() + mb);
768 // After the kernel's three inverse-iteration steps from a random start (tan(theta0) ~ sqrt(nb)),
769 // neighbours at its reorthogonalization threshold bgap keep |v_i' v_j| <~ sqrt(nb) (shift_tol / bgap)^3.
770 // The Sturm check below passes such shifts, so re-bisect at the block's scale when that can exceed
771 // 32 eps: in float from ||T|| ~ 40 ||T_b|| at nb = 1000, in double only beyond that check's own reach.
772 // Tested as shift_tol > bgap (32 eps / sqrt(nb))^(1/3), which neither divides nor overflows (the factor is
773 // below 1), whereas (shift_tol / bgap)^3 overflows once ||T|| / ||T_b|| passes about 6e16 in float and 3e115
774 // in double, and is 0/0 for supplied shifts on a block whose gap underflows.
775 bool needs_refinement = shift_tol > bgap(b) * numext::cbrt(RealScalar(32) * eps / numext::sqrt(RealScalar(nb)));
776 if (!needs_refinement) {
777 endpoints.resize(2 * mb);
778 counts.resize(2 * mb);
779 for (Index k = 0; k < mb; ++k) {
780 endpoints(k) = normalized_shift(b, wloc(k), -btol(b));
781 endpoints(mb + k) = normalized_shift(b, wloc(k), btol(b));
782 }
783 tridiagonal_sturm_counts(alpha_all.data() + b0, beta_sq_all.data() + b0, nb, bpivmin(b), endpoints.data(),
784 counts.data(), 2 * mb);
785 // A supplied shift is locally resolved if its rounding-sized interval contains the
786 // assigned eigenvalue index. This also detects repeated coarse shifts claiming one root.
787 for (Index k = 0; k < mb && !needs_refinement; ++k) {
788 needs_refinement = counts(k) > indices(k) || counts(mb + k) <= indices(k);
789 }
790 }
791 if (needs_refinement) {
792 for (Index first = 0; first < mb;) {
793 Index last = first + 1;
794 while (last < mb && indices(last) == indices(last - 1) + 1) ++last;
795 tridiagonal_bisection(bdiag, bsub, EigenvalueRange::indices(indices(first), indices(last - 1) + 1),
796 RealScalar(0), refined);
797 wloc.segment(first, last - first) = refined;
798 first = last;
799 }
800 }
801 }
802 nonconv += tridiagonal_inverse_iteration_connected(bdiag, bsub, wloc, vloc);
803 for (Index k = 0; k < mb; ++k) eivecs.col(colmap(k)).segment(b0, nb) = vloc.col(k);
804 }
805 return nonconv;
806}
807
842template <typename DiagType, typename SubdiagType, typename EivalType, typename EivecType>
843void tridiagonal_rayleigh_ritz_refine(const DiagType& diag, const SubdiagType& subdiag, const EivalType& eivals,
844 EivecType& eivecs) {
845 using RealScalar = typename DiagType::Scalar;
846 using DenseType = Matrix<RealScalar, Dynamic, Dynamic>;
847 const Index n = diag.size();
848 const Index m = eivals.size();
849 if (n < 2 || m < 2) return;
850
851 // Inf-norm of T and the cluster threshold, matching tridiagonal_inverse_iteration()'s grouping.
852 RealScalar onenrm = numext::abs(diag[0]) + numext::abs(subdiag[0]);
853 onenrm = numext::maxi(onenrm, numext::abs(diag[n - 1]) + numext::abs(subdiag[n - 2]));
854 for (Index i = 1; i < n - 1; ++i)
855 onenrm = numext::maxi(onenrm, numext::abs(subdiag[i - 1]) + numext::abs(diag[i]) + numext::abs(subdiag[i]));
856 const RealScalar ortol = RealScalar(1e-3) * onenrm;
857 if (!(ortol > RealScalar(0))) return; // T == 0: nothing to refine
858 const RealScalar inv_onenrm = RealScalar(1) / onenrm;
859 const RealScalar refine_threshold = RealScalar(16) * NumTraits<RealScalar>::epsilon();
860
861 SelfAdjointEigenSolver<DenseType> block_solver;
862 // Per-cluster scratch, hoisted out of the loop and reused across clusters: each assignment below
863 // resizes only when a cluster is larger than any seen so far, so the common many-small-clusters case
864 // allocates once rather than per cluster. Bsym is the distinct target for the symmetrization, which
865 // also lets B + B.transpose() avoid an aliasing temporary.
866 DenseType Vc, TVc, B, Bsym;
867 Index s = 0;
868 while (s < m) {
869 Index t = s;
870 while (t + 1 < m && (eivals[t + 1] - eivals[t]) < ortol) ++t;
871 const Index c = t - s + 1;
872 if (c > 1) {
873 // Project T onto the cluster basis. T V_c via the tridiagonal structure:
874 // (T V_c)(i,:) = e_{i-1} V_c(i-1,:) + d_i V_c(i,:) + e_i V_c(i+1,:).
875 Vc = eivecs.middleCols(s, c); // copy so the write-back below cannot alias
876 TVc = diag.asDiagonal() * Vc;
877 TVc.topRows(n - 1) += subdiag.asDiagonal() * Vc.bottomRows(n - 1);
878 TVc.bottomRows(n - 1) += subdiag.asDiagonal() * Vc.topRows(n - 1);
879 // Worst per-vector residual in the cluster (scaled by 1/||T|| so it cannot overflow). Skip the
880 // refinement when the cluster is already at machine precision -- refining it would only add the
881 // subspace error to vectors that are individually more accurate.
882 const RealScalar cluster_resid =
883 ((TVc - Vc * eivals.segment(s, c).asDiagonal()) * inv_onenrm).colwise().norm().maxCoeff();
884 if (cluster_resid > refine_threshold) {
885 B.noalias() = Vc.transpose() * TVc;
886 Bsym = B + B.transpose(); // enforce exact symmetry (distinct target avoids an aliasing temp)
887 Bsym *= RealScalar(0.5);
888 block_solver.compute(Bsym, ComputeEigenvectors);
889 eivecs.middleCols(s, c).noalias() = Vc * block_solver.eigenvectors();
890 }
891 }
892 s = t + 1;
893 }
894}
895
896} // namespace internal
897} // namespace Eigen
898
899#endif // EIGEN_TRIDIAGONAL_INVERSE_ITERATION_H
@ ComputeEigenvectors
Definition Constants.h:406
static EigenvalueRange indices(Index il, Index iu)
Definition TridiagonalBisection.h:53