Parallel-in-Time Solver for the All-at-Once Runge–Kutta Discretization

In this article, we derive fast and robust parallel-in-time preconditioned iterative methods for the all-at-once linear systems arising upon discretization of time-dependent PDEs. The discretization we employ is based on a Runge–Kutta method in time, for which the development of parallel solvers is an emerging research area in the literature of numerical methods for time-dependent PDEs. By making use of classical theory of block matrices, one is able to derive a preconditioner for the systems considered. The block structure of the preconditioner allows for parallelism in the time variable, as long as one is able to provide a robust solver for the system of the stages of the method. We thus propose a preconditioner for the latter system based on a singular value decomposition (SVD) of the (real) Runge–Kutta matrix \(A_{\textrm{RK}} = U \Sigma V^\top\). Supposing \(A_{\textrm{RK}}\) is invertible and the discretization of the differential operator in space is symmetric positive definite, we prove that the spectrum of the system for the stages preconditioned by our SVD-based preconditioner is contained within the right-half of the unit circle, under suitable assumptions on the matrix \(U^\top V\) (the assumptions are well posed due to the polar decomposition of \(A_{\textrm{RK}}\) ). We show the numerical efficiency of our approach by solving the system of the stages arising from the discretization of the heat equation and the Stokes equations, with sequential time-stepping. Finally, we provide numerical results of the all-at-once approach for both problems, showing the speedup achieved on a parallel architecture.