SVD — Chase And Trim (CAT)

CAT retains conventional bidiagonal QR deflation and introduces a local two-sided transformation only where an additional split is feasible.

• For an m×n matrix with m ≥ n, Householder reduction produces an upper-bidiagonal n×n block; when m < n, the algorithm can act on Aᵀ
• A local 2×2 SVD annihilates a selected superdiagonal entry but can create two cross-boundary fill-ins, with magnitudes |sᴿeₖ₋₁| and |sᴸeₖ₊₁|
• Both fill-ins must satisfy the directional local deflation tolerance τ before an active split is accepted
• Two inexpensive sufficient rejection conditions screen candidates before LAPACK DLASV2 computes the final left and right rotations
• Accepted rotations update both left and right singular vectors; one paired update costs 12n arithmetic operations in the chapter's model
• The discarded two-entry perturbation has spectral norm equal to the larger fill magnitude, at most τ
• In the tested families, CAT reduces QR sweep positions and weighted arithmetic work; benefits depend strongly on the singular-value spectrum

The comparisons concern phase-2 bidiagonal QR work, not overall SVD runtime. Both algorithms use the same Householder preprocessing and the same instrumented LAPACK DBDSQR implementation.

The selected 2×2 upper-bidiagonal block is diagonalized by a right rotation and a left rotation, rather than the single similarity rotation used for symmetric eigenvalues. Applied to the full bidiagonal matrix, these rotations eliminate the selected coupling but can create one fill-in on each side. CAT accepts the split only when both fill magnitudes pass the local tolerance test; otherwise ordinary bidiagonal QR continues.

The experiments used 12 matrix families, sizes n = 64, 128, 256 and 512, and three deterministic samples per family-size combination. Both methods accumulate left and right singular vectors during the bidiagonal QR phase.

Pooled across samples and matrix sizes, weighted arithmetic-work reduction ranged from about 4.4% for IID rectangular noise to about 41% for geometrically spaced singular values. The geometric family showed the largest reductions in QR sweep positions as well.

The two rejection screens eliminated approximately 99.91% of inspected candidates before production verification. No valid CAT opportunities were missed by the screens in the reported experiments; only five of 9,546 surviving candidates were rejected by the production verification. Combined screening and accepted-rotation work was about 0.23% of total weighted work.

Singular-value errors against LAPACK DGESVD, left and right singular-vector orthogonality, and SVD reconstruction residuals remained comparable to conventional QR. These results concern modeled arithmetic work, not measured execution time.

The chapter is available as a PDF. Page links below are best-effort: most browsers support them but some viewers may ignore the page hint.

The smaller local SVD rotation tends to be favored by a small selected superdiagonal coupling, larger separation between the neighboring diagonal magnitudes, and small outer couplings. The chapter derives approximate conditions for linear versus geometric singular-value spacing; geometric spacing can produce larger favorable diagonal separation and more interior splits. That is consistent with the larger work reductions observed for the geometric-spectrum family.

Quick feedback helps us improve the site.