Expand description
§Chapter 12.6.1 — Small dense eigensolvers: symmetric Jacobi, Hessenberg–Francis real Schur, reordering, eigenvectors
§Purpose
The restarted drivers of Chapter 12.6 project the operator onto a basis
of ncv vectors and need, at every restart, the eigen-decomposition of
the projected ncv × ncv matrix H — in the symmetric case its
eigenvalues and orthogonal eigenvectors, in the general case a real
Schur form H = Z T Zᵀ (Z orthogonal, T quasi-upper-triangular)
whose leading block holds the wanted Ritz values. DenseKernel has no
eigensolver and the crate is generic in T: Real (decision S1), so the
five routines are written here with only + − · /, sqrt, abs and
the order; each is backward stable (orthogonal transformations only),
which is what the residual guarantees of 12.6 rest on.
§Notation
A, H, T ∈ T^{p×p} column-major, a_ij = data[i + j·p]; Z the
accumulated orthogonal transformation (H_in = Z T Zᵀ with the Z
passed in multiplied on the right); ε = ε_T; a block of T is a
1 × 1 diagonal entry or a 2 × 2 diagonal block [a b; c a] with bc < 0 (the standardized form: eigenvalues a ± i√(|b||c|)), and T is
zero below the diagonal outside the blocks. ‖·‖ is the largest
absolute entry where a scale is needed (μ).
§Algorithm SJ (cyclic Jacobi for a symmetric matrix)
SJ1. [Scale.] μ ← max |a_ij|; if μ = 0 return d = 0, Z = I.
W ← A/2^⌊log₂ μ⌋ (exact).
SJ2. [Sweep.] For every p < q in row-cyclic order: if |w_pq| > tol·√|w_pp|·√|w_qq| and |w_pq| > tol² (the second test is an
absolute floor ε²μ: below it the entry is negligible against
ε‖A‖ even when both diagonals vanish): θ ← (w_qq − w_pp)/(2w_pq),
t ← sign(θ)/(|θ| + √(1 + θ²)) (with θ⁻¹ inside the root when |θ| ≥ 1), c ← 1/√(1 + t²), s ← t c; W ← JᵀWJ and Z ← ZJ with J
the rotation in the plane (p, q) (col_p ← c col_p − s col_q, col_q ← s col_p + c col_q, the same on the rows), then w_pp ← w_pp − t w_pq, w_qq ← w_qq + t w_pq, w_pq = w_qp ← 0 exactly (GVL
§8.5.2, the formulas that keep the diagonal accurate).
SJ3. [Stop.] After a sweep without rotation, d_i ← w_ii · 2^⌊log₂ μ⌋;
the columns of Z are renormalized (the drift of c² + s², as J4 of
Chapter 12.0.6). After max_sweeps, non-convergence (never seen).
The entries left are ≤ tol·√|d_p d_q| (relative) or ≤ ε²μ, so every
eigenvalue is within O(p·tol·‖A‖) of one of A (Weyl), and the
eigenvectors are orthogonal to O(tol).
§Algorithm HR (Hessenberg reduction)
For k = 0, …, p − 3: the reflector P_k = I − τvvᵀ of Algorithm H
(Chapter 12.0.4) on h_{k+1:p, k}; H ← P_k H P_k, Z ← Z P_k; the
entries h_{k+2:p, k} are set to zero exactly (GVL Alg. 7.4.2).
§Algorithm FQ (Francis double-shift QR to real Schur form)
The window is [l, i], initially [0, p − 1]; its counts the sweeps
spent on the current bottom block.
FQ1. [Deflate.] Find the largest l ≤ i with l = 0 or |h_{l,l−1}| ≤ ε(|h_{l−1,l−1}| + |h_{ll}|) (if that sum is 0, against the largest
absolute entry μ of H); set h_{l,l−1} ← 0.
FQ2. [One converged.] If l = i: i ← i − 1, its ← 0; go to FQ1 (stop
when the window is empty).
FQ3. [Two converged.] If l = i − 1: standardize the 2 × 2 block by
Algorithm SV, apply its rotation to rows i − 1, i (columns i + 1..),
to columns i − 1, i (rows ..i − 1) and to Z; i ← i − 2, its ← 0; go to FQ1.
FQ4. [Shifts.] its ← its + 1; if the total exceeds 30·max(10, p),
non-convergence. The shifts are the eigenvalues of the trailing 2 × 2
of the window (trace s, determinant t); at its = 10 and its = 20 the exceptional shifts of LAPACK dlahqr break a cycle: the
trailing block is replaced by [0.75w + h_rr, −0.4375w; w, 0.75w + h_rr] with w = |h_{l+1,l}| + |h_{l+2,l+1}|, r = l (at 10) or w = |h_{i,i−1}| + |h_{i−1,i−2}|, r = i (at 20).
FQ5. [Sweep.] (x, y, z) ← the first column of (H − λ₁I)(H − λ₂I) at
l: x = h_ll² + h_{l,l+1}h_{l+1,l} − s h_ll + t, y = h_{l+1,l}(h_ll + h_{l+1,l+1} − s), z = h_{l+1,l}h_{l+2,l+1}. For k = l, …, i − 2: the
reflector of (x, y, z) (length 2 at k = i − 1, done after the
loop) applied to rows k..k+3 (columns max(l, k − 1)..p), to
columns k..k+3 (rows 0..min(k + 4, i + 1)) and to Z; for k > l
the bulge entries h_{k+1,k−1}, h_{k+2,k−1} are set to zero; (x, y, z) ← (h_{k+1,k}, h_{k+2,k}, h_{k+3,k}) (GVL Alg. 7.5.1, the
wantt/wantz form of dlahqr). Go to FQ1.
§Algorithm SV (standardization of a 2 × 2 block, LAPACK dlanv2)
Given [a b; c d], a rotation R = [cs −sn; sn cs] with [a b; c d] = R [a′ b′; c′ d′] Rᵀ where either c′ = 0 (real eigenvalues a′, d′) or a′ = d′, b′c′ < 0 (eigenvalues a′ ± i√(|b′||c′|)). The branches are those
of dlanv2 (the real case by the stable root z = p + sign(p)√(p² + bc), p = (a − d)/2; otherwise the rotation that equalizes the
diagonal, then a second one if the result has real eigenvalues),
without its rescaling loop (the callers’ matrices are scaled to O(1)
entries by the drivers’ normalization of V).
§Algorithm SW (swap two adjacent blocks; Bai & Demmel 1993)
Blocks T_11 ∈ T^{n₁×n₁}, T_22 ∈ T^{n₂×n₂} adjacent at j, D = [T_11 T_12; 0 T_22].
SW1. [Sylvester.] Solve T_11 X − X T_22 = T_12 (n₁n₂ ≤ 4 unknowns,
Gaussian elimination with complete pivoting on the Kronecker form;
a pivot below ε·μ_D is replaced by ε·μ_D — eigenvalues that
close make the swap ill-conditioned, caught in SW3).
SW2. [Basis.] Householder QR of [−X; I_{n₂}] = Q [R; 0] (its columns
span the invariant subspace of T_22), so QᵀDQ = [T̃_22 *; E T̃_11]
with E = 0 in exact arithmetic.
SW3. [Test.] On a copy: if max |E| > 10·ε·μ_D, refuse (return false,
nothing modified) — the weak stability test of LAPACK dlaexc.
SW4. [Apply.] T ← QᵀTQ on rows j..j+n (columns j..p), columns
j..j+n (rows 0..j+n), Z ← ZQ; E ← 0 exactly; standardize each
new 2 × 2 block by SV (it may split into two 1 × 1 blocks when
the eigenvalues were nearly real and double).
For n₁ = n₂ = 1 the rotation of (t_12, t_22 − t_11) is used instead
(it leaves t_12 unchanged and is exact for diagonal T).
§Algorithm RO (reordering by rank)
Each block carries an integer rank (lower = wanted earlier) that travels
with it through the swaps. For pos = 0, 1, … while the leading need
rows are not settled: pick the block of least rank at or after pos
(the first on ties), bubble it up to pos by SW, pos ← pos + size. A
refused swap stops the reordering (false is returned; the order
reached is consistent and the caller treats it as is).
§Algorithm EV (eigenvector of a quasi-triangular matrix, LAPACK dtrevc)
For the block at q (size s) with eigenvalue λ (for s = 2, the one
with positive imaginary part ω = √(|b||c|)):
EV1. x_q = 1 (s = 1); for s = 2: (x_q, x_{q+1}) = (1, iω/b) if |b| ≥ |c|, else (iω/c, 1) — a null vector of [a − λ, b; c, a − λ].
EV2. For the blocks above q, bottom to top: solve (T_bb − λI) x_b = −Σ_{j>b} T_bj x_j (complex 1 × 1 or 2 × 2, partial pivoting;
a pivot below smin = max(ε μ, tiny) is replaced by smin). If an
entry exceeds 2⁵⁰⁰, the whole x is scaled down by a power of two.
The rows below the block are zero. T x = λ x up to O(ε‖T‖)‖x‖.
§Invariants
(E1) SJ: ‖A Z − Z diag(d)‖ ≤ c p u ‖A‖, ‖ZᵀZ − I‖ ≤ c p u.
(E2) HR + FQ + SW: H_in Z_out = Z_out T to c p u ‖H‖, Z orthogonal
to c p u, T quasi-triangular with standardized 2 × 2 blocks
(exact zeros below; check_quasi_triangular).
(E3) EV: ‖T x − λ x‖ ≤ c p u ‖T‖ ‖x‖.
All three are checked by the unit tests below (and (E2)’s shape is
debug-asserted after FQ and SW).
§References
Golub & Van Loan, Matrix Computations, 4th ed. (2013), §7.4–7.5
(Hessenberg, Francis), §8.5 (Jacobi); Anderson et al., LAPACK Users’
Guide, 3rd ed. (1999), routines dlahqr, dlanv2, dlaexc,
dtrexc, dtrevc; Bai & Demmel, “On swapping diagonal blocks in real
Schur form”, Linear Algebra Appl. 186 (1993); Demmel & Veselić, SIMAX 13
(1992). Cited from memory.
Structs§
- Cx 🔒
- A complex value for Algorithm EV (no public arithmetic: internal).
- Schur
Options 🔒 - The thresholds of Algorithms SJ and FQ.
Constants§
- BIG 🔒
2⁵⁰⁰: the size above which EV2 rescales (a property of the exponent range, not a tuning knob).
Functions§
- block_
value 🔒 - The eigenvalue
(re, im)of a block,im ≥ 0. - blocks 🔒
- The diagonal blocks
(start, size)of a quasi-triangulart. - check_
quasi_ 🔒triangular - (E2)’s shape: exact zeros below the subdiagonal, no two consecutive
nonzero subdiagonal entries, and every
2 × 2block standardized. - hessenberg 🔒
- Algorithm HR in place on
h, accumulating intoz(z ← z P). - hypot 🔒
√(x² + y²)without overflow.- identity 🔒
- The identity of order
p. - lanv2 🔒
- Algorithm SV on
(a, b, c, d): returns the standardized block and(cs, sn)with[a b; c d] = R [a′ b′; c′ d′] Rᵀ,R = [cs −sn; sn cs]. - max_abs 🔒
- The largest absolute entry.
- pow2_
floor 🔒 2^⌊log₂ μ⌋for a positive normalμ,1otherwise.- real_
schur 🔒 - Algorithms HR + FQ:
hbecomes the standardized real Schur formT,z ← z Qwithh_in = Q T Qᵀ. - rebuild 🔒
- The blocks of
twith the ranks ofoldcarried over by start row. - reflect_
cols 🔒 - Apply a small reflector to columns
k..k+lenover the rowsr0..r1. - reflect_
rows 🔒 - Apply a small reflector to rows
k..k+lenover the columnsc0..c1. - reorder 🔒
- Algorithm RO: reorder
t(andz) so that the blocks of least rank lead, until at leastneedrows are settled.rank[b]is the rank of blockbofblocks. Returns the final blocks with their ranks and whether every swap was accepted. - rot_
cols 🔒 - Rotate columns
i,jof a column-major array withrowsrows over the rowsr0..r1:(x, y) ← (c x + s y, c y − s x)(LAPACKdrot). - rot_
rows 🔒 - Rotate rows
i,jover the columnsc0..c1(asrot_cols). - schur_
eigvec 🔒 - Algorithm EV: the eigenvector of the quasi-triangular
tfor the block(q, s)(fors = 2, the eigenvalue with positive imaginary part), aspcomplex entries (zero below the block). - sign1 🔒
sign(1, x)of Fortran:−1for negativex,+1otherwise.- small_
reflector 🔒 - The reflector of a 2- or 3-vector:
(τ, v_tail, β)with(I − τvvᵀ)x = β e_0. - solve_
small 🔒 - Gaussian elimination with complete pivoting on an
n × nsystem (n ≤ 4), pivots belowsminreplaced bysmin. - standardize 🔒
- Standardize the
2 × 2block atkoft(Algorithm SV) and apply its rotation to the rest oftand toz. - swap_
blocks 🔒 - Algorithm SW: swap the adjacent blocks at
jof sizesn1,n2. Returnsfalse(nothing modified) when SW3 refuses. - sym_eig 🔒
- Algorithm SJ: eigenvalues
d(unsorted) and orthogonalZwithA ≈ Z diag(d) Zᵀ, for symmetrica(its upper and lower triangles are averaged).