Treffer: 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 ...