A fast iterative algorithm for near-diagonal eigenvalue problems

We introduce a novel eigenvalue algorithm for near-diagonal matrices termed iterative perturbative theory (IPT). Built upon a "perturbative" partitioning of the matrix into diagonal and off-diagonal parts, IPT can be used to compute one or all eigenpairs with the same basic iterative algorithm. Thanks to the high parallelism of matrix-matrix products, full-spectrum IPT shows excellent performance on multi-core processors and GPUs, with large speed-ups over standard direct methods (up to $\sim50$x with respect to LAPACK and MAGMA). For matrices which are not close to being diagonal but have well-separated eigenvalues, IPT can be be used to refine low-precision eigenpairs obtained by other methods. We give sufficient conditions for linear convergence and demonstrate performance on dense and sparse test matrices. In a real-world application from quantum chemistry, we find that single-eigenpair IPT performs similarly to the Davidson algorithm.