Finding *all* the eigenvalues of a sparse matrix?

[Ralph_Smith]

Petschow’s paper concerns the tridiagonal problem, not the full dense case. The reduction to tridiagonal (or Hessenberg) form was traditionally dominated by level 2 BLAS and thus memory/communication bound, so was the bottleneck that inspired my claim. TIL that the ELPA and SLATE teams have built blocking schemes which radically improve this for the Hermitian case, so you are correct there. I haven’t found similar results for the nonsymmetric (Hessenberg) case, but the SLATE team seems to be working on it.