Chase and Trim: Earlier Deflation in Bidiagonal QR for the SVD

Abstract

Chase and Trim (CAT) extends the bidiagonal QR algorithm for computing singular values and singular vectors by introducing additional deflation opportunities between QR sweeps. For selected interior superdiagonal couplings, CAT applies a local 2×2 singular value decomposition using left and right rotations. When both resulting cross-boundary fill-ins satisfy the conventional deflation tolerance, they are discarded, allowing the active block to split earlier. We derive algebraic conditions for rejecting infeasible candidates without constructing the rotations. Two inexpensive rejection tests screen candidates before invoking LAPACK DLASV2 for final verification and application. We also show that the spectral norm of the perturbation discarded by an accepted CAT split does not exceed the local tolerance permitted for conventional deflation. The algorithm was tested against standard bidiagonal QR using the same instrumented LAPACK DBDSQR implementation, with singular-vector accumulation enabled. Experiments covered 12 matrix families, five matrix orders from 64 to 1024, and five samples per family and order. Computational effort was measured using QR sweep positions and weighted arithmetic work, including candidate screening and singular-vector updates. Across the tested spectral families, CAT reduced weighted arithmetic work by approximately 3%–38%. The pooled reduction remained relatively stable as matrix order increased, from approximately 10% at n = 64 to 11% at n = 1024. The largest reductions occurred for geometrically spaced singular values. The two rejection tests eliminated approximately 99.95% of candidates before production verification, with no missed feasible opportunities observed. Singular-value accuracy, left and right singular-vector orthogonality, and reconstruction residuals remained comparable to conventional bidiagonal QR. The study reports algorithmic work reductions rather than wall-clock performance.