A fast iterative algorithm for near-diagonal eigenvalue problems

12/29/2020
by   Maseim Kenmoe, et al.
0

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 has the complexity of one matrix-vector (when one eigenpair is requested) or one matrix-matrix multiplication (when all eigenpairs are requested) per iteration. 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 ∼50x with respect to LAPACK and ARPACK, ∼5x with respect to Davidson). When off-diagonal elements are comparable to eigengaps, IPT diverges like the quadratic map outside the Mandelbrot set; for such general matrices IPT can nevertheless be used to refine low-precision eigenvectors obtained by other methods. We give sufficient conditions for linear convergence and demonstrate performance on dense and sparse test matrices.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset