The routines, side by side
| Routine | Second stage | Typical use | Starts from |
|---|---|---|---|
| dsyev | implicit QL/QR iteration | the default; simple and robust; what NumPy, SciPy and most bindings reach for | dense N×N |
| dsyevd | divide and conquer | all eigenpairs of a dense matrix; usually the fastest dense path, with more workspace | dense N×N |
| dsyevr | MRRR, via dstemr | a subset of eigenpairs, or all of them with a cheaper second stage | dense N×N |
| dstemr | MRRR on the tridiagonal matrix | the expert route when the two diagonals are already in hand | the band (D and E) |
| dstev | QL/QR on the tridiagonal matrix | the simple route from the two diagonals | the band (D and E) |
MRRR stands for multiple relatively robust representations. It is the algorithm that lets the second stage run in time proportional to N² rather than N³, and dstemr is where LAPACK implements it. A specialist who knows the matrix is tridiagonal calls dstemr directly with the two diagonals and never pays for the reduction. Almost nobody else does, because almost nobody's code knows what shape its matrix has.
Where the time goes
Many of the matrices that matter in physics, engineering and signal processing are banded: the information sits on a narrow band and the rest is zero. Handed to dsyev, such a matrix is reduced as if it were dense, because the routine cannot know. That reduction is the whole cost. VVE SmartRoute, the routing inside VVE EigenCore, detects the band on every call and works along it instead, so the effort grows with N² rather than N³.
The result is two different comparisons, and the benchmarks page keeps them apart on purpose. Against the default path that deployed code actually calls, the margin is large. Against dstemr, the expert routine that already knows the matrix is tridiagonal, the margin is smaller and honest.
Against the default path, N = 16,384
98–103×
vs single-threaded reference netlib LAPACK dsyev (the default dense path) — one core against one core, same machine
Against the expert route, N = 45,056
5.16×
vs LAPACK's own expert O(N²) routine, single-threaded dstemr (MRRR) — one core against one core, accuracy gated on both sides
The second comparison is not a clean sweep, and the record says so. On clustered spectra such as the Wilkinson and Schrödinger families, VVE is ahead of dstemr at every size measured. On well-separated or random spectra, dstemr leads at small N and VVE passes it between N = 8,192 and N = 16,384, with the margin growing from there.
What VVE intercepts
Switched on at start-up, VVE EigenCore answers these LAPACK calls in place of the host library, with zero code changes. The program never has to know its matrix is banded or which special routine to reach for.
| Routine | What it computes | Intercepted |
|---|---|---|
| dsyev | symmetric eigenvalues and eigenvectors, the default path | yes |
| dsyevd | the same, by divide and conquer | yes |
| dsyevr | the same, by MRRR, with eigenvalue subsets | yes |
| dstev | eigenvalues of a tridiagonal matrix given its two diagonals | yes |
| dgesdd | singular value decomposition, divide and conquer | yes |
| dgesvd | singular value decomposition, QR iteration | yes |
| dstemr | tridiagonal MRRR, the expert route | no |
A program that already holds the band of its matrix can hand it to VVE directly. That is the path the memory law applies to.
With VVE, you do not have to choose
The table above is a decision most programs never make well: the code calls dsyev because that is the default, and the matrix's structure goes unused. VVE takes that decision off the table.
- Keep calling what you call. Whether the code reaches
dsyev,dsyevdordsyevr, VVE SmartRoute looks at the matrix on every call and takes the fast path whenever there is a band to follow. Nobody has to know in advance which routine would have been right. That is the case the benchmarks measure. - The same answer on every machine, whichever routine it was. The result does not change between the workstation the code was written on and the board it ships to, so a choice made once does not have to be re-argued later.
- Already holding the band? Skip the matrix. Hand VVE the band directly and the full matrix never has to exist, which is how a problem that would not fit on a server runs on a board. The arithmetic is on the memory page.
- Dense with no structure? VVE returns the right answer there too. It just does not claim to be the fast one; a tuned vendor library is.