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⁵⁰⁰and2⁻⁵⁰⁰: the range in which the squares of Algorithm N can neither overflow nor underflow (a property of thef64exponent 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) toy(length1 + v_tail.len()). - axpy_
sub 🔒 y ← y − α x.- check_
finite 🔒 - The first non-finite entry of
x, as the error ofwhat. - check_
len 🔒 - The length check of a vector argument.
- dot 🔒
xᵀy, summed in index order.- givens 🔒
- Algorithm G:
(G, r)withG (a, b) = (r, 0),r ≥ 0. - householder 🔒
- Algorithm H on
x(lengthp ≥ 1), in place: on returnx_0 = α,x_1.. = v_1..(withv_0 = 1implicit); returnsτ. - householder_
qr 🔒 - Algorithm Q:
(Q, R)of them × lblocka(m ≥ l),r_kk ≥ 0. - norm2 🔒
- Algorithm N:
‖x‖. - orthogonalize 🔒
- Algorithm D:
x ← (I − QQᵀ)xagainst the columns ofq(q.rows = x.len()), accumulating the coefficients intoh(lengthq.cols). Returns(‖x‖, passes). - orthogonalize_
against 🔒 - Algorithm D on the first
ncolscolumns of the column-major arraydata(rowsrows 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 intoh(length≥ ncols) when given — the Arnoldi column of Chapter 12.6. The arithmetic onxis the same either way. - pow2_
floor 🔒 2^⌊log₂ μ⌋for a positive normalμ(its bits with the mantissa cleared);1otherwise.