A DIRECT TIME PARALLEL SOLVER BY DIAGONALIZATION FOR THE WAVE EQUATION

With the advent of very large scale parallel computers, it has become more and more important to also use the time direction for parallelization when solving evolution problems. While there are many successful algorithms for diffusive problems, it has turned out to be substantially more difficult to solve hyperbolic problems in a time parallel fashion. We present here a mathematical analysis of a new method based on the diagonalization of the time stepping matrix proposed by Maday and Rønquist in 2007. Like for many time parallelization methods, this seems at first not to be a very promising approach, since this matrix is essentially triangular, and for a fixed time step even a Jordan block, and thus not diagonalizable. If one chooses however different time steps, diagonalization is possible, and one has to trade off between the accuracy due to necessarily having different time steps, and numerical errors in the diagonalization process of these almost non-diagonalizable matrices. We study this trade-off mathematically for the wave equation with a Crank-Nicolson discretization, and propose an optimization strategy for the choice of the parameters. We illustrate our results with numerical experiments for model wave equations in various dimensions, and also an industrial test case for the elasticity equations. 1. Introduction. Using the time direction in evolution problems for paralleliza-tion is an active field of research, for an overview, see [?]. Most of the methods developed for this purpose are iterative, see for example the parareal algorithm [?], whose convergence was analyzed in [?] for linear problems, where also convergence difficulties in the hyperbolic case were identified; for an analysis in the non-linear case, see [?]. A variation of the parareal algorithm using spectral deferred correction [?] led then to the PFASST algorithm [?], which is a multilevel method. Space-time multigrid methods were also developed, see [?] and references therein, and a new such method using only standard components can be found in [?] with excellent strong and weak scaling properties for parabolic problems. There is also the non-invasive MGRIT algorithm [?, ?], and it was shown in [?] that MGRIT is equivalent to an overlapping parareal algorithm, which led to a detailed non-linear convergence analysis for MGRIT [?]. Early versions of these space-time multigrid methods were based on waveform relaxation [?, ?], and there are also very successful Schwarz waveform relaxation methods for the time parallel solution of evolution partial differential equations [?, ?, ?, ?, ?], and the more recent Dirichlet-Neumann and Neumann-Neumann waveform relaxation methods [?, ?, ?]. These are among the very few space-time iterative methods that are effective for hyperbolic problems, see [?, ?, ?], since they use the finite speed of propagation for good space-time decompositions, and also the related tent-pitching approach [?] which removes the need for iteration completely by following in the decomposition the characteristics. A different approach for hyperbolic problems are the Krylov parareal methods [?, ?, ?, ?], which however have an important overhead due to orthogonalization. As an alternative, one can use direct space-time parallel solvers, like RIDC [?]