Chase And Trim (CAT): Active One-Rotation Deflation for the Symmetric QR Eigenvalue Algorithm

Chase And Trim (CAT) extends symmetric tridiagonal QR by creating additional deflation opportunities between QR sweeps. When a selected first-band coupling has not yet passed conventional deflation, CAT tests whether one local Jacobi rotation can annihilate it while creating only negligible cross-cut fill. The split is accepted only when both resulting fill magnitudes are no larger than the same local tolerance used for conventional deflation, so the discarded perturbation satisfies the same local spectral-norm bound. chase-and-trim chase-and-trim We derive the exact one-rotation split condition and a cheaper sufficient acceptance inequality, reduce the candidate test through factor comparisons before products are formed, and organize non-intersecting candidate cuts for parallel testing and execution. The present implementation also accumulates eigenvectors during both ordinary QR rotations and accepted CAT rotations. chase-and-trim chase-and-trim The eigenvector-accumulating branch was tested on eight matrix families at \(n=63,255,511,1023\), with five deterministic matrices per family-size combination except for the Wilkinson family. Across the tested family-size averages, the reduction in QR sweep positions ranged from approximately 0.8% to 22%, while the reduction in weighted arithmetic work ranged from approximately 0.2% to 22%. The largest combined CAT testing-and-rotation cost was about 1.2% of candidate weighted work. chase-and-trim chase-and-trim Numerical accuracy remained comparable with the standard QR implementation. Eigenvalue errors relative to LAPACK, eigenvector orthogonality errors, and relative eigenpair residuals remained of the same order for the baseline and CAT methods. The present study reports weighted arithmetic work rather than wall-clock performance or arithmetic span.