GraphMath

QR eigenvalue algorithm — Chase And Trim (CAT)

Earlier matrix splits inside symmetric bulge-chasing QR iteration

Under construction. This chapter is still being developed and may change as the analysis and experiments are refined.

Can a matrix be split before conventional QR deflation says the coupling is negligible?

Chase And Trim (CAT) augments the standard bulge-chasing QR eigenvalue algorithm for symmetric matrices. When a first-band coupling is not yet small enough for conventional deflation, CAT tests whether one Jacobi similarity rotation can annihilate it while creating only negligible cross-cut fill. If so, those fill entries are discarded and the active block splits earlier into independent subproblems.

Open chapter PDF Key ideas Chapter index Back to Linear Algebra

Key ideas

CAT keeps the ordinary shifted QR sweep and conventional deflation rules, but adds a local test for one-rotation active splits.

  • A Jacobi rotation can annihilate a selected first-band coupling b exactly
  • The rotation creates at most two cross-cut fill magnitudes, |sa| and |sg|
  • An active split is accepted when both fill magnitudes are no larger than the same local tolerance τ used for conventional deflation
  • The exact split condition |s|M ≤ τ, with M = max(|a|, |g|), leads to the cheaper sufficient test |b|M ≤ |Δ|τ
  • Non-intersecting candidate cuts can be grouped into three rows and tested and applied in parallel within each row
  • Earlier splits reduce subsequent QR work on the larger child block and let independent child blocks continue concurrently
  • The experiments compare sweep positions, weighted arithmetic work, weighted arithmetic span and eigenvalue error against the same QR implementation without CAT

The main objective is reduction of the arithmetic dependency path, not merely reduction of the total operation count.

How can CAT create a valid split with one rotation?

At a proposed cut, CAT applies a Jacobi rotation to the two adjacent coordinates and chooses the shorter-angle branch 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 within the accepted tolerance τ, removing them gives a numerically valid split. Thus CAT can divide the active block even when b itself has not yet passed the conventional deflation test.

What did the experiments show?

CAT reduced the number of QR sweep positions in all 32 tested matrix-family and matrix-size combinations. The relative reduction ranged from 1.93% to 20.99%.

Weighted arithmetic span, the main metric for the parallel model, was also reduced in all 32 combinations. The reduction ranged from about 1.47% to 27.58%.

Weighted arithmetic work decreased in 23 of 32 combinations. In the other nine, the extra candidate-testing work met or exceeded the arithmetic eliminated by earlier splitting.

Across the tested cases, the largest combined CAT overhead was 4.31% of weighted work and 1.00% of weighted span. Candidate and baseline eigenvalue errors relative to LAPACK remained of the same order.

These are algorithmic work-and-span results, not wall-clock performance claims; the present experiments compute eigenvalues only.

Related chapters

  • Tridiagonalization & Jacobi algorithm studies a complementary Jacobi-oriented route for symmetric eigenvalue computation and provides the comparison discussed in CAT's future directions
  • Jacobi algorithm develops the Jacobi similarity rotation used by CAT to annihilate a candidate coupling
  • Givens rotations develops the plane rotations used in QR factorization and provides background for the adjacent rotations used in bulge chasing
  • Householder reflection develops the orthogonal transformations used to reduce dense symmetric matrices to tridiagonal form before QR iteration
  • Eigenvectors and eigenvalues provides the eigenvalue and eigenvector background for the eigensolver problem

Chapter contents

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
Introduction 1–4
Jacobi rotation and fill-in 4–8
Why two fill-ins do not mean more accepted error 9–11
From the exact condition to an acceptance test 11–13
Why were so few exact opportunities missed? 13–15
Evaluating the acceptance inequality without forming products 15–16
How can we process active splits in parallel? 16–20
Eigenvectors: work and span 20–22
Matrix families used for testing 22–24
Methods 25–27
Arithmetic span during active-split evaluation and execution 27–33
Reported quantities 33–36
General dense symmetric 36–41
Dense correlation 41–45
Dense clustered spectrum 45–49
Dense graded spectrum 49–53
General symmetric tridiagonal 53–57
Weak-link symmetric tridiagonal 57–61
Wilkinson tridiagonal 61–65
Unequal variance-covariance 65–69
Conclusions 69–74
References 74–77
Open PDF

Was this chapter helpful?

Quick feedback helps us improve the site.

Yes No