Skip to main content

Module schur

Module schur 

Source
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).
SchurOptions 🔒
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-triangular t.
check_quasi_triangular 🔒
(E2)’s shape: exact zeros below the subdiagonal, no two consecutive nonzero subdiagonal entries, and every 2 × 2 block standardized.
hessenberg 🔒
Algorithm HR in place on h, accumulating into z (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 μ, 1 otherwise.
real_schur 🔒
Algorithms HR + FQ: h becomes the standardized real Schur form T, z ← z Q with h_in = Q T Qᵀ.
rebuild 🔒
The blocks of t with the ranks of old carried over by start row.
reflect_cols 🔒
Apply a small reflector to columns k..k+len over the rows r0..r1.
reflect_rows 🔒
Apply a small reflector to rows k..k+len over the columns c0..c1.
reorder 🔒
Algorithm RO: reorder t (and z) so that the blocks of least rank lead, until at least need rows are settled. rank[b] is the rank of block b of blocks. Returns the final blocks with their ranks and whether every swap was accepted.
rot_cols 🔒
Rotate columns i, j of a column-major array with rows rows over the rows r0..r1: (x, y) ← (c x + s y, c y − s x) (LAPACK drot).
rot_rows 🔒
Rotate rows i, j over the columns c0..c1 (as rot_cols).
schur_eigvec 🔒
Algorithm EV: the eigenvector of the quasi-triangular t for the block (q, s) (for s = 2, the eigenvalue with positive imaginary part), as p complex entries (zero below the block).
sign1 🔒
sign(1, x) of Fortran: −1 for negative x, +1 otherwise.
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 × n system (n ≤ 4), pivots below smin replaced by smin.
standardize 🔒
Standardize the 2 × 2 block at k of t (Algorithm SV) and apply its rotation to the rest of t and to z.
swap_blocks 🔒
Algorithm SW: swap the adjacent blocks at j of sizes n1, n2. Returns false (nothing modified) when SW3 refuses.
sym_eig 🔒
Algorithm SJ: eigenvalues d (unsorted) and orthogonal Z with A ≈ Z diag(d) Zᵀ, for symmetric a (its upper and lower triangles are averaged).