Implicitly Restarted DEIM_Arnoldi: An inner product free Krylov method for eigenproblems

Abstract

This thesis proposes an inner product free Krylov method called Implicitly Restarted DEIM_Arnoldi (IRD) to solve large scale eigenvalue problems. This algorithm is based on the Implicitly Restarted Arnoldi (IRA) scheme, which is very efficient for solving eigenproblems. IRA uses the Arnoldi factorization, which requires inner products. In contrast, IRD employs the Discrete Empirical Interpolation (DEIM) technique and the DEIM_Arnoldi algorithm to avoid inner products, thereby resulting in faster running times for large eigenproblems. Furthermore, IRD may be able to greatly reduce the latency caused by inner products in parallel computation. This work conducts many numerical experiments to compare the performance of IRD and IRA in serial computation, and discusses the possible ways to avoid the need for communication in parallel computation.