Skip to main content

Module small

Module small 

Source
Expand description

§Chapter 12.0.4 — Small dense routines: norms, Givens rotations, Householder reflectors, DGKS Gram–Schmidt

§Purpose

The kernels of xingo-sparse (DenseKernel) are the BLAS-3 operations of a supernodal factorization; the updating algorithms of Chapters 12.2 and 12.3 need the BLAS-1 and LAPACK-auxiliary ones instead — a plane rotation, an elementary reflector, a Gram–Schmidt step. They are written here once, generic in T: Real (decision S1 of D-0127), with only + − · /, sqrt, abs and the order.

§Notation

x, y ∈ T^m; ‖x‖ the 2-norm; a rotation G = (c, s) with c² + s² = 1 acts on a pair as (x, y) ↦ (c x + s y, −s x + c y); a reflector H = I − τ v vᵀ with v_0 = 1; Q ∈ T^{m×k} with orthonormal columns (k may be 0).

§Algorithm N (2-norm)

N1. μ ← max |x_i|. If μ = 0, return 0. N2. If 2⁻⁵⁰⁰ ≤ μ ≤ 2⁵⁰⁰ (as f64), return √(Σ x_i²), summed in index order. N3. Otherwise let σ = 2^⌊log₂ μ⌋ (read off the bits of μ as f64): return σ·√(Σ (x_i/σ)²). Scaling by a power of two is exact in f64 and in double-double, so N2 and N3 round identically; N3 only avoids overflow and underflow of the squares.

§Algorithm G (Givens rotation; Golub & Van Loan §5.1.8)

Given (a, b), find G = (c, s) and r ≥ 0 with c a + s b = r and −s a + c b = 0: G1. If b = 0: (c, s, r) = (1, 0, a) if a ≥ 0, else (−1, 0, −a). G2. Else μ ← |a| + |b|, r ← μ·√((a/μ)² + (b/μ)²), c ← a/r, s ← b/r (the scaling is the “safe hypot” of the contract).

§Algorithm H (Householder reflector; GVL §5.1.3)

Given x ∈ T^p, p ≥ 1, find τ, v (v_0 = 1) and α with H x = α e_0: H1. σ ← ‖x‖ (Algorithm N). If σ = 0: τ = 0, α = 0, v = e_0. H2. α ← −σ if x_0 ≥ 0, else σ (no cancellation in x_0 − α). H3. v_i ← x_i / (x_0 − α) for i ≥ 1, τ ← (α − x_0)/α. The callers flip signs afterwards to make the diagonal of R positive.

§Algorithm D (classical Gram–Schmidt with DGKS reorthogonalization)

Given Q and x, compute x ← (I − QQᵀ) x and the coefficients h with x_in = Q h + x_out: D1. ν₀ ← ‖x‖; h ← 0. D2. [Pass.] s_j ← q_jᵀ x for every j (all dot products first: CGS), then x ← x − Σ_j s_j q_j, h ← h + s; ν ← ‖x‖. D3. [DGKS.] If ν < η ν₀, the pass cancelled: repeat D2 once (with ν₀ ← ν unused afterwards). Never a third pass (Daniel, Gragg, Kaufman & Stewart 1976: “twice is enough” when the input is not numerically dependent; a dependent input is caught by the caller’s rank test). D4. Return ν = ‖x‖ and the number of passes.

§Algorithm Q (thin Householder QR with explicit Q, any rank)

Given A ∈ T^{m×l}, m ≥ l: the reflectors of F2 in Chapter 12.3 (Algorithm H column by column), Q ← H_0 ⋯ H_{l−1} [I_l; 0] applied backwards, and the signs flipped so that r_kk ≥ 0. Unlike crate::Qr::factor there is no rank test: a rank-deficient A still gives an orthonormal Q (the range finder of Chapter 12.4 must accept a sketch AΩ of a low-rank A).

§Invariants

(S1) Algorithm G returns r ≥ 0 and |c|, |s| ≤ 1; for finite input the output is finite (debug-asserted). (S2) After Algorithm D, ‖Qᵀx‖ ≤ c · m · u · ‖x_in‖ when the second pass was taken or not needed and x is not numerically in the range of Q — the property (Q1) of Chapter 12.3 rests on; tested in Chapter 12.3 (and in the mutation check that disables D3).

§References

Golub & Van Loan, Matrix Computations, 4th ed. (2013), §5.1; Daniel, Gragg, Kaufman & Stewart, Math. Comp. 30 (1976); Björck, Numerical Methods for Least Squares Problems (1996), §2.4 (cited from memory).

Structs§

Rot 🔒
A plane rotation (c, s): (x, y) ↦ (c x + s y, −s x + c y).

Constants§

BIG 🔒
2⁵⁰⁰ and 2⁻⁵⁰⁰: the range in which the squares of Algorithm N can neither overflow nor underflow (a property of the f64 exponent range — the double-double has the same — not a tuning knob).
SMALL 🔒

Functions§

apply_householder 🔒
Apply H = I − τ v vᵀ (v_0 = 1, v_1.. = v_tail) to y (length 1 + v_tail.len()).
axpy_sub 🔒
y ← y − α x.
check_finite 🔒
The first non-finite entry of x, as the error of what.
check_len 🔒
The length check of a vector argument.
dot 🔒
xᵀy, summed in index order.
givens 🔒
Algorithm G: (G, r) with G (a, b) = (r, 0), r ≥ 0.
householder 🔒
Algorithm H on x (length p ≥ 1), in place: on return x_0 = α, x_1.. = v_1.. (with v_0 = 1 implicit); returns τ.
householder_qr 🔒
Algorithm Q: (Q, R) of the m × l block a (m ≥ l), r_kk ≥ 0.
norm2 🔒
Algorithm N: ‖x‖.
orthogonalize 🔒
Algorithm D: x ← (I − QQᵀ)x against the columns of q (q.rows = x.len()), accumulating the coefficients into h (length q.cols). Returns (‖x‖, passes).
orthogonalize_against 🔒
Algorithm D on the first ncols columns of the column-major array data (rows rows each) — the growing Krylov bases of Chapter 12.5 live in preallocated blocks. The coefficients are discarded. Returns (‖x‖, passes).
orthogonalize_prefix 🔒
Algorithm D as orthogonalize_against, accumulating the coefficients of both passes into h (length ≥ ncols) when given — the Arnoldi column of Chapter 12.6. The arithmetic on x is the same either way.
pow2_floor 🔒
2^⌊log₂ μ⌋ for a positive normal μ (its bits with the mantissa cleared); 1 otherwise.