2018/10/16 by Ben S. Southworth, Southworth, Ben S. · 1 citation
Engineering · Mathematics · #65F10 65M55 65M12 #Advanced Numerical Methods in Computational Mathematics #Electromagnetic Simulation and Numerical Methods #FOS: Mathematics #Numerical Analysis (math.NA) #Numerical methods for differential equations
paper · pdf · doi:10.48550/arxiv.1810.07292
openalex publication_date 2018/10/16 · openalex created_date 2022/08/02 · openalex updated_date 2026/07/28
Parareal and multigrid reduction in time (MGRiT) are two of the most popular\nparallel-in-time methods. The idea is to treat time integration in a parallel\ncontext by using a multigrid method in time. If \Φ is a (fine-grid)\ntime-stepping scheme, let \Ψ denote a "coarse-grid" time-stepping scheme\nchosen to approximate k steps of \Φ, k\≥ 1. In particular, \Ψ\ndefines the coarse-grid correction, and evaluating \Ψ should be\n(significantly) cheaper than evaluating \Φk.\n A number of papers have studied the convergence of Parareal and MGRiT.\nHowever, there have yet to be general conditions developed on the convergence\nof Parareal or MGRiT that answer simple questions such as, (i) for a given\n\Φ and k, what is the best \Ψ, or (ii) can Parareal/MGRiT converge\nfor my problem? This work derives necessary and sufficient conditions for the\nconvergence of Parareal and MGRiT applied to linear problems, along with tight\ntwo-level convergence bounds. Results rest on the introduction of a "temporal\napproximation property" (TAP) that indicates how \Φk must approximate the\naction of \Ψ on different vectors. Loosely, for unitarily diagonalizable\noperators, the TAP indicates that fine-grid and coarse-grid time integration\nschemes must integrate geometrically smooth spatial components similarly, and\nless so for geometrically high frequency. In the (non-unitarily) diagonalizable\nsetting, the conditioning of each eigenvector, \vi, must also be\nreflected in how well \Ψ\vi \∼\Φk\vi. In general,\nworst-case convergence bounds are exactly given by \min \φ < 1 such that\nan inequality along the lines of \‖(\Ψ-\Φk)\v\‖ \≤\φ \‖(I\n- \Ψ)\v\‖ holds for all \v. Such inequalities are\nformalized as different realizations of the TAP, and form the basis for\nconvergence of MGRiT and Parareal.\n