An Efficient Block Rational Krylov Solver for Sylvester Equations with Adaptive Pole Selection

We present an algorithm for the solution of Sylvester equations with right-hand side of low rank. The method is based on projection onto a block rational Krylov subspace, with two key contributions with respect to the state of the art. First, we show how to maintain the last pole equal to infinity throughout the iteration, by means of pole reordering, which allows for a cheap evaluation of the true residual at every step. Second, we extend the convergence analysis in [B. Beckermann, SIAM J. Numer. Anal., 49 (2011), pp. 2430--2450] to the block case. This extension allows us to link the convergence with the problem of minimizing the norm of a small rational matrix over the spectra or field -of -values of the involved matrices. This is in contrast with the nonblock case, where the minimum problem is scalar, instead of matrix valued. Replacing the norm of the objective function with a more easily evaluated function yields several adaptive pole selection strategies, providing a theoretical analysis for known heuristics, as well as effective novel techniques.