Eigendecomposition memory: dense N×N, or 46 bytes per N

The dense requirement

A symmetric matrix of dimension N stored densely holds N×N double-precision numbers at eight bytes each. The requirement grows with the square of N, so doubling the problem quadruples the memory. At N = 524,288 it is 2,048 GiB, which no single machine holds; the bands-native path peaked at 53 MB on that problem.

This is not a limit of any particular library. eigvalsh, dsyev and every dense routine take the matrix as their input, so the matrix has to be built before the first instruction of the solver runs. Nobody can recompile their way out of it without changing what the function accepts.

Bands-native values-only path, second-difference matrix. Peak resident memory against the dense N×N buffer the same problem would require.
N	VVE peak RSS	Dense N×N	Ratio	max \|Δλ\|
8,192	28.7 MB	0.5 GiB	18×	1.78e-15
32,768	31.5 MB	8.0 GiB	260×	1.78e-15
131,072	≈ 53.0 MB	128 GiB	≈ 2,500×	1.78e-15
524,288	≈ 53.0 MB	2,048 GiB	≈ 39,600×	1.78e-15

VVE peak RSS against the dense N×N requirement, log-log. One line is flat; the other is a slope of 2.

Memory figure data
8,192	28.7 MB	0.5 GiB
32,768	31.5 MB	8.0 GiB
131,072	53.0 MB	128 GiB
524,288	53.0 MB	2,048 GiB

The band carries the spectrum

A tridiagonal matrix has numbers only on its main diagonal and the two beside it. That is 3N − 2 numbers, and they determine the eigenvalues completely. A solver that accepts the two diagonals directly never needs the other N² − 3N + 2 entries, which are all zero, and its working memory can grow with N instead of N².

The same structure is why the work shrinks. The dense path spends its time reducing the full matrix to this band before it can start; a path that is handed the band skips that stage.

The dense path reduces the whole N×N matrix with Householder reflections, so doubling N costs 8×. The band that carries the spectrum costs 4× per doubling. Same matrix, same eigenvalues.

What was measured

Peak resident memory, N = 524,288

53MB

against the dense N×N buffer the same problem would require

Growth per dimension

46bytes / dimension

measured over a Python and NumPy baseline

Eigenvalue error

1.78e-15

identical at every size from N = 8,192 to 524,288

The one condition

/* pass D and E — no dense N×N is ever allocated */
vve_eigen_values_tridiag(D, E, N, W);

The drop-in gives a program that already builds the dense matrix the speed of the structure-aware path. Only a program that stops building the matrix gets the memory. In most codebases that is a change of a few lines at the point where the matrix is assembled, and it is the change that lets a problem move from a server's memory budget to a board's.

How much memory does an eigendecomposition need?