Towards a Computational Efficient, Implicitly Restarted Rational Krylov Method

Abstract

Rational Krylov sequences were introduced over 30 years ago by Ruhe (1984) and have been an active subject of research ever since. As a result, many advances have been made in different areas such as the introduction of extended Krylov sequences by Druskin et al. (1998), the development of a technique for implicitly restarting the rational Krylov sequence by De Samblanx et al. (1997) and, more recently, the computation of rational Krylov subspaces without explicit system solves by Mach et al. (2014). On the theoretical side, Güttel (2013) demonstrated how to optimally select the poles of the rational Krylov sequence and Beckermann et al. (2010) provided a convergence analysis based on methods from potential theory. That rational Krylov sequences have matured, is best indicated by the variety of numerical linear algebra problems they have been used for. This entails the solution of the linear eigenvalue problem, of nonlinear eigenvalue problems by Van Beeumen et al. (2015), of matrix functions by Güttel (2013), of matrix equations by Druskin et al. (2011) and model order reduction by Gugercin et al. (2008). In this talk we will highlight the strengths of the rational Krylov sequence, present the standard Arnoldi, shift-and-invert Arnoldi and extended Krylov sequences as special cases of a general rational Krylov representation and give our current findings on how all factorizations are connected. Moreover we present a compact factorization scheme of the associated recurrence matrices which could be used for efficiently running implicit restarts.