Skip to main content

Module jacobi

Module jacobi 

Source
Expand description

§Chapter 12.0.6 — One-sided Jacobi SVD of a small dense matrix

§Purpose

Both truncated SVDs end with the SVD of a small matrix: the l × l triangle of step S5 of crate::rsvd() and the projected B of step B4 of crate::svds() (and eigsh/eigs of L3.4 will reuse the sorting and completion conventions). DenseKernel has no SVD and the crate is generic in T: Real (decision S1), so this is the classical one-sided (Hestenes) Jacobi method: it needs only + − · /, sqrt and the order, and it is backward stable column by column (Demmel & Veselić), which is what the residual guarantees of 12.4 and 12.5 rest on.

§Notation

B ∈ T^{p×q}, p ≥ q; w_i the columns of the working copy W; Y ∈ T^{q×q} the accumulated rotations, so W = B Y throughout; at the end w_i = σ_i x_i with ‖x_i‖ = 1, hence B Y = X Σ, B = X Σ Yᵀ. tol and max_sweeps are the fields of JacobiOptions.

§Algorithm J

J1. [Scale.] μ ← max |b_ij|. If μ = 0: Σ = 0, Y = I, X the first q columns of I_p; done. Otherwise W ← B/2^⌊log₂ μ⌋ (exact), so the squares below neither overflow nor underflow. J2. [Sweep.] First set to zero every column whose ‖w_i‖² underflows to 0 (its norm is below 2⁻⁵³⁷ while max |w_ij| ≥ 1: far below ε_T‖B‖, so a negligible backward perturbation; without it such a column, with a = 0 but γ ≠ 0, would be rotated forever). Then for every pair i < j in row-cyclic order: a ← ‖w_i‖², b ← ‖w_j‖², γ ← w_iᵀw_j. If |γ| > tol·√(a b): ζ ← (b − a)/(2γ), t ← sign(ζ)/(|ζ| + √(1 + ζ²)) (written as sign(ζ)/(|ζ|(1 + √(1 + ζ⁻²))) when |ζ| ≥ 1, so that ζ² never overflows), c ← 1/√(1 + t²), s ← c t; (w_i, w_j) ← (c w_i − s w_j, s w_i + c w_j), the same on the columns of Y. This makes the new pair exactly orthogonal in exact arithmetic (cs(a − b) + (c² − s²)γ = 0). J3. [Stop.] Stop after a sweep without rotation. After max_sweeps sweeps, report non-convergence (never seen: the method converges quadratically once the off-diagonal mass is small). J4. [Values.] Divide y_i and w_i by ‖y_i‖ (this keeps W = B Y and removes the drift of the column norms of Y: c² + s² rounds with a bias, and a column touched by r rotations drifts by up to r·u — measured 1.3·10⁻¹⁴ for q = 21 before this step, 8·10⁻¹⁶ after, in task L3.3; without it the restarts of 12.5, P ← P Y, compound the drift). Then σ_i ← ‖w_i‖ (unscaled); sort nonincreasingly (stable: ties keep their column order), permuting W and Y alike. J5. [Left vectors.] x_i ← w_i/‖w_i‖ for σ_i > 0. For σ_i = 0 (an exactly zero column) complete X to orthonormal columns: try e_0, e_1, … in turn, orthogonalize against the columns already in X (two Gram–Schmidt passes) and take the first whose remaining norm exceeds ½.

§Invariants

(J1) σ nonincreasing, nonnegative, finite for finite B. (J2) Y orthogonal and X orthonormal to O(tol) — by the stopping test, |x_iᵀx_j| ≤ tol relative, whatever the sizes of σ_i, σ_j (this is why the one-sided method gives small singular values with orthogonal vectors). (J3) ‖B Y − X Σ‖ ≤ c·q·u·‖B‖ (backward stability of the rotations). All three are checked by the tests below (and debug-asserted for J1).

§References

Hestenes, “Inversion of matrices by biorthogonalization”, J. SIAM 6 (1958); Demmel & Veselić, “Jacobi’s method is more accurate than QR”, SIMAX 13 (1992); Golub & Van Loan, Matrix Computations, 4th ed., §8.6.3; Drmač & Veselić, “New fast and accurate Jacobi SVD algorithm”, SIMAX 29 (2008) (the √p·ε tolerance of LAPACK dgesvj). Cited from memory.

Structs§

JacobiOptions 🔒
The thresholds of Algorithm J.
SmallSvd 🔒
The result B = X diag(s) Yᵀ of Algorithm J.

Functions§

jacobi_svd 🔒
Algorithm J on b (p × q, p ≥ q, finite).
pow2_floor 🔒
2^⌊log₂ μ⌋ for a positive normal μ, 1 otherwise.
rotate 🔒
Rotate columns i < j of the rows-row array: (a, b) ← (c a − s b, s a + c b).