{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:43:07Z","timestamp":1787330587875,"version":"build-2736575974"},"reference-count":43,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100006227","name":"Lawrence Livermore National Laboratory","doi-asserted-by":"publisher","award":["B614452"],"award-info":[{"award-number":["B614452"]}],"id":[{"id":"10.13039\/100006227","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006227","name":"Lawrence Livermore National Laboratory","doi-asserted-by":"publisher","award":["B627942"],"award-info":[{"award-number":["B627942"]}],"id":[{"id":"10.13039\/100006227","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["NNSA DE-NA0002376"],"award-info":[{"award-number":["NNSA DE-NA0002376"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>Parareal and multigrid reduction in time (MGRiT) are two of the most popular parallel-in-time methods. The basic idea is to treat time integration in a parallel context by using a multigrid method in time. If $\\Phi$ is the (fine-grid) time-stepping scheme of interest, such as any Runge--Kutta scheme, then let $\\Psi$ denote a \u201ccoarse-grid\" time-stepping scheme chosen to approximate $k$ steps of $\\Phi$, where $k\\geq 1$. In particular, $\\Psi$ defines the coarse-grid correction, and evaluating $\\Psi$ should be (significantly) cheaper than evaluating $\\Phi^k$. Parareal is a two-level method with a fixed relaxation scheme, and MGRiT is a generalization to the multilevel setting, with the additional option of a modified, stronger relaxation scheme. A number of papers have studied the convergence of Parareal and MGRiT. However, general conditions on the convergence of Parareal or MGRiT that answer the following simple questions have yet to be developed: (i) For a given $\\Phi$ and $k$, what is the best $\\Psi$? (ii) Can Parareal\/MGRiT converge for my problem? This work derives necessary and sufficient conditions for the convergence of Parareal and MGRiT applied to linear problems, along with tight two-level convergence bounds, under minimal additional assumptions on $\\Phi$ and $\\Psi$. Results all rest on the introduction of a temporal approximation property (TAP) that indicates how $\\Phi^k$ must approximate the action of $\\Psi$ on different vectors. Loosely, for unitarily diagonalizable operators, the TAP indicates that the fine-grid and coarse-grid time integration schemes must integrate geometrically smooth spatial components similarly, and less so for geometrically high frequency. In the (nonunitarily) diagonalizable setting, the conditioning of each eigenvector, ${v}_i$, must also be reflected in how well $\\Psi{v}_i \\sim\\Phi^k{v}_i$. In general, worst-case convergence bounds are exactly given by $\\min \\varphi &lt; 1$ such that an inequality along the lines of $\\|(\\Psi-\\Phi^k){v}\\| \\leq\\varphi \\|(I - \\Psi){v}\\|$ holds for all ${v}$. Such inequalities are formalized as different realizations of the TAP in section 2 and form the basis for convergence of MGRiT and Parareal applied to linear problems.<\/jats:p>","DOI":"10.1137\/18m1226208","type":"journal-article","created":{"date-parts":[[2019,5,9]],"date-time":"2019-05-09T13:24:35Z","timestamp":1557408275000},"page":"564-608","source":"Crossref","is-referenced-by-count":33,"title":["Necessary Conditions and Tight Two-level Convergence Bounds for Parareal and Multigrid Reduction in Time"],"prefix":"10.1137","volume":"40","author":[{"given":"Ben S.","family":"Southworth","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,5,9]]},"reference":[{"key":"atypb1","first-page":"425","author":"Bal G.","year":"2005","journal-title":"Berlin"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"D. S. Bernstein,\n                      Scalar, Vector, and Matrix Mathematics: Theory, Facts, and Formulas\n                      , revised and expanded edition, Princeton University Press, Princeton, NJ, 2018.","DOI":"10.1515\/9781400888252"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"W. L. Briggs, V. E. Henson, and S. F. McCormick,\n                      A Multigrid Tutorial\n                      , 2nd ed., SIAM, Philadelphia, 2000,https:\/\/doi.org\/10.1137\/1.9780898719505.","DOI":"10.1137\/1.9780898719505"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1017\/S1446181108000102"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/16M1074096"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.2140\/camcos.2012.7.105"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/s00791-017-0283-9"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/130944230"},{"key":"atypb9","unstructured":"R. D. Falgout, M. Lecouvez, and C. S. Woodward,\n                      A Parallel-in-Time Algorithm for Variable Step Multistep Methods\n                      , manuscript, 2017."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/S0036142903429742"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1002\/nla.1977"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"H. Gahvari, V. A. Dobrev, R. D. Falgout, Tz. V. Kolev, J. B. Schroder, M. Schulz, and U. M. Yang,\n                      A performance model for allocating the parallelism in a multigrid-in-time solver\n                      , in Proceedings of the IEEE International Workshop on Performance Modeling, Benchmarking and Simulation of High Performance Computer Systems (PMBS), IEEE, Washington, DC, 2016, pp. 22-31.","DOI":"10.1109\/PMBS.2016.008"},{"key":"atypb13","first-page":"45","author":"Gander M. J.","year":"2008","journal-title":"Heidelberg"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/s00791-018-0297-y"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/05064607X"},{"key":"atypb16","first-page":"291","author":"Gander M. J.","year":"2007","journal-title":"Heidelberg"},{"key":"atypb17","unstructured":"A. Goddard and A. Wathen,\n                      A note on parallel preconditioning for all-at-once evolutionary PDEs\n                      , Electron. Trans. Numer. Anal., submitted; preprint,https:\/\/arxiv.org\/abs\/1810.00615, 2018."},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1002\/nla.2155"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/0916050"},{"key":"atypb21","unstructured":"A. Howse, H. De Sterck, S. MacLachlan, R. Falgout, and J. Schroder,\n                      Multigrid Reduction in Time with Adaptive Spatial Coarsening for the Linear Advection Equation\n                      , Tech. report, Lawrence Livermore National Laboratory (LLNL), Livermore, CA, 2017."},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"R. J. LeVeque,\n                      Finite Difference Methods for Ordinary and Partial Differential Equations: Steady-State and Time-Dependent Problems\n                      , SIAM, Philadelphia, 2007,https:\/\/doi.org\/10.1137\/1.9780898717839.","DOI":"10.1137\/1.9780898717839"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/S0764-4442(00)01793-6"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1002\/nla.486"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/17M1144350"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/16M1062016"},{"issue":"3","key":"atypb28","first-page":"50","author":"Mendelsohn N.","year":"1956","journal-title":"Trans. Roy. Soc. Canada Sect."},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479896313036"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2012.07.028"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(83)90091-5"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1002\/pamm.201410490"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1007\/s00791-018-0296-z"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479896310160"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(97)00231-0"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022329526925"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(99)00104-1"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(97)00308-X"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/dru031"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1137\/140970756"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1016\/0034-4877(80)90041-5"},{"key":"atypb42","unstructured":"W. Wyss,\n                      Two Non-Commutative Binomial Theorems\n                      , preprint,https:\/\/arxiv.org\/abs\/1707.03861, 2017."},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1137\/17M1162779"},{"key":"atypb44","first-page":"210","volume":"5","author":"Yueh W. C.","year":"2005","journal-title":"Appl. Math. E-Notes"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1007\/s002110050175"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1226208","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:13:44Z","timestamp":1787328824000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1226208"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/18M1226208"],"URL":"https:\/\/doi.org\/10.1137\/18m1226208","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}