A fast iterative algorithm for near-diagonal eigenvalue problems

We introduce a novel iterative 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 computes one or all eigenpairs with a complexity per iteration of one matrix-vector or one matrix-matrix multiplication respectively. Thanks to the high parallelism of these basic linear algebra operations, we obtain excellent performance on multi-core processors and GPUs, with large speed-ups over standard methods (up to $\sim50$x with respect to LAPACK and ARPACK). 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 IPT performs similarly to the Davidson algorithm.