MGRIT swMATH ID: 30280 Software Authors: Dobrev, V. A.; Kolev, Tz.; Petersson, N. A.; Schroder, J. B. Description: Two-level convergence theory for multigrid reduction in time (MGRIT). In this paper we develop a two-grid convergence theory for the parallel-in-time scheme known as multigrid reduction in time (MGRIT), as it is implemented in the open-source package [XBraid: Parallel Multigrid in Time, http://llnl.gov/casc/xbraid]. MGRIT is a scalable and multilevel approach to parallel-in-time simulations that nonintrusively uses existing time-stepping schemes, and in a specific two-level setting it is equivalent to the widely known parareal algorithm. The goal of this paper is twofold. First, we present a two-level MGRIT convergence analysis for linear problems where the spatial discretization matrix can be diagonalized, and then apply this analysis to our two basic model problems, the heat equation and the advection equation. One important assumption is that the coarse and fine time-grid propagators can be diagaonalized by the same set of eigenvectors, which is often the case when the same spatial discretization operator is used on the coarse and fine time grids. In many cases, the MGRIT algorithm is guaranteed to converge, and we demonstrate numerically that the theoretically predicted convergence rates are sharp in practice for our model problems. Second, we explore how the convergence of MGRIT compares to the stability of the chosen time-stepping scheme. In particular, we demonstrate that a stable time-stepping scheme does not necessarily imply convergence of MGRIT, although MGRIT with FCF-relaxation always converges for the diffusion dominated problems considered here. Homepage: https://epubs.siam.org/doi/10.1137/16M1074096 Keywords: multigrid; multigrid-in-time; parallel-in-time; convergence theory; high performance computing Related Software: XBraid; pyParareal; PARALAAOMPI; PARAEXP; ParaDiag; RODAS; CHeart; PFASST; ParaOpt; GitHub; MUMPS; iFEM; TR-BDF2; AlexNet; torchdiffeq; ImageNet; TensorFlow; IFISS; Parallel Computing Toolbox; Parareal Cited in: 22 Publications Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year Two-level convergence theory for multigrid reduction in time (MGRIT). Zbl 1416.65329Dobrev, V. A.; Kolev, Tz.; Petersson, N. A.; Schroder, J. B. 2017 all top 5 Cited by 38 Authors 7 Schroder, Jacob B. 5 Wu, Shulin 4 Falgout, Robert D. 4 Hessenthaler, Andreas 4 Nordsletten, David A. 4 Röhrle, Oliver 3 Southworth, Ben S. 3 Zhou, Tao 2 Gander, Martin Jakob 2 Gauger, Nicolas R. 2 Günther, Stefanie 2 Manteuffel, Thomas A. 2 Notay, Yvan 2 Pan, Kejia 2 Shu, Shi 2 Yue, Xiaoqiang 1 Balmus, Maximilian 1 Bu, Weiping 1 Cyr, Eric C. 1 de Vecchi, Adelaide 1 Dobrev, Veselin A. 1 Jiang, Yaolin 1 Kolev, Tzanio V. 1 Kwok, Felix 1 Lin, Xuelei 1 Miao, Zhen 1 Münzenmaier, Steffen 1 Ng, Michael Kwok-Po 1 Petersson, N. Anders 1 Ruge, John W. 1 Ruthotto, Lars 1 Salomon, Julien 1 Tang, Juan 1 Wang, Chen-Ye 1 Weng, Zhifeng 1 Xu, Xiaowen 1 Zhou, Jie 1 Zhou, Zhi all top 5 Cited in 13 Serials 7 SIAM Journal on Scientific Computing 2 Computers & Mathematics with Applications 2 Computer Methods in Applied Mechanics and Engineering 2 SIAM Journal on Matrix Analysis and Applications 1 Journal of Computational Physics 1 Mathematics of Computation 1 SIAM Journal on Numerical Analysis 1 Applied Numerical Mathematics 1 Numerical Algorithms 1 Numerical Linear Algebra with Applications 1 ETNA. Electronic Transactions on Numerical Analysis 1 Optimization Methods & Software 1 SIAM Journal on Mathematics of Data Science all top 5 Cited in 11 Fields 20 Numerical analysis (65-XX) 4 Partial differential equations (35-XX) 4 Calculus of variations and optimal control; optimization (49-XX) 3 Mechanics of deformable solids (74-XX) 2 Linear and multilinear algebra; matrix theory (15-XX) 2 Computer science (68-XX) 2 Fluid mechanics (76-XX) 1 Real functions (26-XX) 1 Integral equations (45-XX) 1 Biology and other natural sciences (92-XX) 1 Systems theory; control (93-XX) Citations by Year