Under construction. This chapter is still being developed and may change as the analysis and experiments are refined.
Chase And Trim (CAT) adds a deflation mechanism to symmetric tridiagonal QR by testing whether a selected first-subdiagonal coupling can be removed by one local Jacobi similarity rotation. The rotation annihilates that coupling and creates at most two cross-cut fill-in pairs. CAT accepts the split only when both fill magnitudes are within the same local tolerance used for conventional deflation.
CAT keeps the standard symmetric tridiagonal QR pathway and adds a local deflation test that can split an active block before conventional deflation.
The aim is to create independent subproblems earlier, reducing later QR iteration while keeping the accepted local perturbation under the same tolerance used by conventional deflation.
At a proposed cut, CAT applies the shorter Jacobi rotation that annihilates the central coupling b. The neighboring first-band entries become ca and cg, while the only new cross-cut fill entries have magnitudes |sa| and |sg|. If both are no larger than τ, CAT discards those fill entries and splits the active block. The original coupling therefore need not satisfy the conventional condition |b| ≤ τ before the split can occur.
The eigenvector-accumulating algorithm was tested on eight matrix families at n = 63, 255, 511 and 1023, with ε = 1e−14. Five deterministic matrices were used for each family-size combination except the Wilkinson family, for which one matrix was used at each size.
Across the tested family-size averages, QR sweep-position reduction ranged from about 0.8% to 22.5%, and weighted arithmetic-work reduction ranged from about 0.2% to 22.4%. The largest reductions occurred for the weak-link symmetric tridiagonal cases; the dense graded-spectrum family also showed a large average sweep-position reduction of about 10.3%.
The largest combined cost of CAT testing and accepted rotations was about 1.2% of candidate weighted work. In every tested family-size average, the reduction in QR sweep work exceeded this CAT overhead.
Scaled eigenvalue error versus LAPACK, eigenvector orthogonality error and relative eigenpair residual remained of the same order as for the standard QR implementation. The chapter makes no arithmetic-span claim and does not test CAT together with aggressive early deflation.
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.
| Topic | Pages |
|---|---|
| Abstract | 1 |
| Introduction | 2–4 |
| Jacobi rotation and fill-in | 4–8 |
| Why two fill-ins do not increase the accepted perturbation | 8–11 |
| From the exact condition to an acceptance test | 11–13 |
| Why were so few exact opportunities missed? | 13–14 |
| Eigenvectors | 15–16 |
| Matrix families used for testing | 17–19 |
| Common computational pathway | 20–22 |
| How can we evaluate active splits in parallel? | 22–25 |
| Arithmetic work of active split evaluation and execution | 25–28 |
| Reported quantities | 29–32 |
| Pseudocode | 32–34 |
| General dense symmetric | 35–38 |
| Dense correlation | 39–43 |
| Dense clustered spectrum | 44–47 |
| Dense graded spectrum | 48–52 |
| General symmetric tridiagonal | 53–56 |
| Weak-link symmetric tridiagonal | 57–61 |
| Wilkinson tridiagonal | 62–65 |
| Unequal variance-covariance | 66–70 |
| Conclusions | 71–74 |
| References | 74–76 |
For an active block of size m, most charged QR sweep work is proportional to m − 1. Summed over the iteration, the dominant QR work is therefore proportional to the total number of sweep positions. CAT reduces that count by splitting blocks earlier, while candidate testing and accepted CAT rotations consume part of the saving. Weighted-work reduction consequently tends to follow sweep-position reduction without being exactly equal to it.