1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
//! Francis double-shift implicit QR iteration on a real upper-Hessenberg matrix,
//! accumulating the orthogonal similarity.
//!
//! Operates entirely in real arithmetic: complex eigenvalues surface as isolated
//! 2×2 diagonal blocks (standardized later), so no complex type is needed here.
//!
//! # Theorem (Francis step = one implicit double-shift QR step)
//! Let `H` be unreduced upper Hessenberg and `μ₁, μ₂` a shift pair that is either
//! two reals or a complex-conjugate pair. One Francis step computes an orthogonal
//! `Z` with `Zᵀ H Z` again upper Hessenberg, and `Zᵀ H Z` equals the matrix
//! produced by one explicit double-shift QR step — i.e. `Q` from the QR
//! factorization `(H − μ₁I)(H − μ₂I) = Q R`, applied as `Qᵀ H Q` — without ever
//! forming the product or leaving real arithmetic.
//!
//! *Proof (implicit-Q).* `M = (H − μ₁I)(H − μ₂I)` is real: a conjugate pair gives
//! `M = H² − (μ₁+μ₂)H + μ₁μ₂I` with real coefficients `s = μ₁+μ₂`, `t = μ₁μ₂`.
//! The step builds the Householder `P₀` mapping `M e₁` (its first column,
//! computed directly from `s, t` and the top-left of `H` — the `x, y, zz` below)
//! to a multiple of `e₁`, then forms `P₀ᵀ H P₀`, which bulges `H` just below the
//! subdiagonal, and chases the bulge with Householders `P₁ … P_{n-2}` that
//! restore Hessenberg form. Set `Z = P₀ P₁ … P_{n-2}`; then `Zᵀ H Z` is upper
//! Hessenberg and `Z e₁ = P₀ e₁ ∝ M e₁`. The implicit-Q theorem states that for
//! unreduced `H`, an orthogonal `Z` with `Zᵀ H Z` unreduced Hessenberg is
//! determined, up to column signs, by `Z e₁`. The explicit step's `Q` satisfies
//! `Q e₁ ∝ M e₁` as well (first column of `Q R = M`), so `Z` and `Q` agree up to
//! signs and yield the same Hessenberg form. Hence the bulge chase realizes the
//! double-shift QR step in real arithmetic. ∎
//!
//! # Corollary (convergence and deflation)
//! With Wilkinson-type shifts (eigenvalues of the trailing 2×2 block) the bottom
//! subdiagonal entry converges quadratically to zero; the iteration zeroes it
//! (LAPACK `dlahqr`'s small-subdiagonal test with the Ahues–Tisseur
//! refinement), splitting off a 1×1 (real eigenvalue) or 2×2 (conjugate pair)
//! block, and recurses on the leading submatrix. `dlahqr`'s exceptional
//! shifts every ten stalled iterations break the rare non-convergent cycles.
//!
//! # Theorem (eigenvalues-only within-block apply window — LAPACK `dlahqr`)
//! For the spectrum it suffices to apply each bulge-chasing reflector `Pₖ` only on
//! the window columns `[k, hi]` (left) and rows `[lo, k+len]` (right), provided the
//! annihilated bulge column `k−1` is set to its known image `(α, 0, 0)ᵀ`. The
//! eigenvalues read off the converged quasi-triangular `H` are unchanged.
//!
//! *Proof.* `H` stays similar to the original under every two-sided reflector, so
//! the spectrum is preserved regardless of which entries are stored. The
//! eigenvalues are read from the **diagonal blocks** only. An entry skipped by the
//! window is one of: (i) the bulge subdiagonal in column `k−1`, whose post-reflector
//! value is exactly `(α, 0, 0)` — written explicitly, so no information is lost; or
//! (ii) an entry with row `< lo` or column `> hi`, which is strictly above the
//! active diagonal block (`row < lo ≤ col` or `row ≤ hi < col`) and hence never
//! lies on a diagonal block, is never a shift source (shifts come from the trailing
//! 2×2 of `[lo, hi]`), and never enters the bulge band. Because `hi` is
//! non-increasing and `lo` is non-decreasing for fixed `hi` (deflation sets
//! `h[lo][lo−1]` to exact zero, a hard floor), such an entry is never read by a
//! future active block either. The window thus omits only never-read entries, so
//! the diagonal blocks — hence the eigenvalues — match the full sweep. ∎
//!
//! *Numerical note (evidence tier: differential + empirical).* The window reorders
//! the floating-point updates relative to a full sweep, so on a **defective**
//! eigenvalue (perturbation `O(√(ε‖A‖))`) the computed value can differ from a full
//! sweep — and from a backward-stable reference — by `O(√(ε‖A‖))`. This is within
//! backward stability, not an error; the eigenvalue battery asserts the derived
//! `8·√(ε‖A‖)` tolerance accordingly. The `ACCUMULATE_Q` (Schur) path applies
//! each reflector where `dlahqr`'s `WANTT` form does — columns `k ..` to the
//! right edge and rows `0 ..= min(k + 3, hi)` — because `T` and the Schur
//! vectors are outputs.
use crateRealScalar;
use ;
use ;
use ;
use Shift;
/// The subnormal part of the deflation threshold, `safmin`: a subdiagonal
/// driven into the subnormals, where no relative test can be met short of an
/// exact zero, still deflates. At most `n − 1` such deflations perturb by at
/// most `√n·safmin` jointly, which the matrix-tier gate (`schur/mod.rs`,
/// [`thresholds::deflation_count_log2`](crate::application::linalg::thresholds::deflation_count_log2))
/// keeps below `ε·‖A‖_F`.
pub
/// The smallest `|h_{k,k−1}|` over the block `[lo, hi]` relative to its
/// [`neighbourhood_scale`]: how far the block is from its nearest
/// deflation, in units of `ulp` once divided by it, reported when the
/// iteration gives up.
/// Drive the Francis iteration to convergence: `h` becomes real
/// quasi-upper-triangular (real Schur form `T`) and `z` accumulates the
/// orthogonal similarity so that `H₀ = z T zᵀ`.
///
/// # Errors
/// [`LetoError::ConvergenceError`] if a block fails to converge within
/// [`iteration_cap`]: `max_iters` is the cap, `residual` the block's
/// smallest `|h_{k,k−1}|` relative to its [`neighbourhood_scale`] (the
/// quantity the last deflation test compares), `tol` the `ulp` it had to
/// reach. The backward-error bounds of the test suite are taken at the cap.
pub