{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,20]],"date-time":"2024-08-20T13:52:35Z","timestamp":1724161955130},"reference-count":38,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2020,4,23]],"date-time":"2020-04-23T00:00:00Z","timestamp":1587600000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Numerical Linear Algebra App"],"published-print":{"date-parts":[[2021,5]]},"abstract":"Summary<\/jats:title>Although convergence of the Parareal and multigrid\u2010reduction\u2010in\u2010time (MGRIT) parallel\u2010in\u2010time algorithms is well studied, results on their optimality is limited. Appealing to recently derived tight bounds of two\u2010level Parareal and MGRIT convergence, this article proves (or disproves) h<\/jats:italic>x<\/jats:italic><\/jats:sub>\u2010 and h<\/jats:italic>t<\/jats:italic><\/jats:sub>\u2010independent convergence of two\u2010level Parareal and MGRIT, for linear problems of the form , where is symmetric positive definite and Runge\u2010Kutta time integration is used. The theory presented in this article also encompasses analysis of some modified Parareal algorithms, such as the \u03b8<\/jats:italic>\u2010Parareal method, and shows that not all Runge\u2010Kutta schemes are equal from the perspective of parallel\u2010in\u2010time. Some schemes, particularly L\u2010stable methods, offer significantly better convergence than others as they are guaranteed to converge rapidly at both limits of small and large h<\/jats:italic>t<\/jats:italic><\/jats:sub>\u03be<\/jats:italic>, where \u03be<\/jats:italic> denotes an eigenvalue of and h<\/jats:italic>t<\/jats:italic><\/jats:sub> time\u2010step size. On the other hand, some schemes do not obtain h<\/jats:italic>\u2010optimal convergence, and two\u2010level convergence is restricted to certain regimes. In certain cases, an factor change in time step h<\/jats:italic>t<\/jats:italic><\/jats:sub> or coarsening factor k<\/jats:italic> can be the difference between convergence factors \u03c1<\/jats:italic>\u22480.02 and divergence! The analysis is extended to skew\u2010symmetric operators as well, which cannot obtain h<\/jats:italic>\u2010independent convergence and, in fact, will generally not converge for a sufficiently large number of time steps. Numerical results confirm the analysis in practice and emphasize the importance of a priori analysis in choosing an effective coarse\u2010grid scheme and coarsening factor. A Mathematica notebook to perform a priori two\u2010grid analysis is available at https:\/\/github.com\/XBraid\/xbraid\u2010convergence\u2010est<\/jats:ext-link>.<\/jats:p>","DOI":"10.1002\/nla.2301","type":"journal-article","created":{"date-parts":[[2020,4,23]],"date-time":"2020-04-23T08:56:43Z","timestamp":1587632203000},"update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["On \u201cOptimal\u201d h<\/i>\u2010independent convergence of Parareal and multigrid\u2010reduction\u2010in\u2010time using Runge\u2010Kutta time integration"],"prefix":"10.1002","volume":"28","author":[{"given":"Stephanie","family":"Friedhoff","sequence":"first","affiliation":[{"name":"Department of Mathematics Bergische Universit\u00e4t Wuppertal Wuppertal Germany"}]},{"given":"Ben S.","family":"Southworth","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics University of Colorado at Boulder Boulder Colorado USA"}]}],"member":"311","published-online":{"date-parts":[[2020,4,23]]},"reference":[{"key":"e_1_2_9_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01446807"},{"key":"e_1_2_9_3_1","first-page":"435","article-title":"Beitrag zur n\u00e4herungsweisen Integration totaler Differentialgleichungen","volume":"46","author":"Kutta W","year":"1901","journal-title":"Zeitschr f\u00fcr Math u Phys"},{"key":"e_1_2_9_4_1","volume-title":"Solving ordinary differential equations. I. vol. 8 of springer series in computational mathematics","author":"Hairer E","year":"1993"},{"key":"e_1_2_9_5_1","volume-title":"Solving ordinary differential equations. II. vol. 14 of springer series in computational mathematics","author":"Hairer E","year":"2010"},{"key":"e_1_2_9_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/9781119121534"},{"key":"e_1_2_9_7_1","volume-title":"Numerical mathematics and scientific computation","author":"Burrage K","year":"1995"},{"key":"e_1_2_9_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23321-5_3"},{"key":"e_1_2_9_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0764-4442(00)01793-6"},{"key":"e_1_2_9_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/130944230"},{"key":"e_1_2_9_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-26825-1_43"},{"key":"e_1_2_9_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/05064607X"},{"key":"e_1_2_9_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75199-1_4"},{"key":"e_1_2_9_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.1977"},{"key":"e_1_2_9_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1074096"},{"key":"e_1_2_9_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1226208"},{"key":"e_1_2_9_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-26825-1_44"},{"key":"e_1_2_9_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2010.05.012"},{"key":"e_1_2_9_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.2155"},{"key":"e_1_2_9_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00791-018-0297-y"},{"key":"e_1_2_9_21_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1977-0431719-X"},{"key":"e_1_2_9_22_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-99-01035-2"},{"key":"e_1_2_9_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827501388509"},{"key":"e_1_2_9_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-006-0049-7"},{"key":"e_1_2_9_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-26825-1_46"},{"key":"e_1_2_9_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/080717481"},{"key":"e_1_2_9_27_1","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/dru031"},{"key":"e_1_2_9_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.1985.1270142"},{"key":"e_1_2_9_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/140970756"},{"key":"e_1_2_9_30_1","unstructured":"ArielG NguyenH TsaiR.\u03b8\u2010parareal schemes;2018. arXiv e\u2010prints. ArXiv:1704.06882."},{"key":"e_1_2_9_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2016.05.036"},{"key":"e_1_2_9_32_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1974-0331793-2"},{"key":"e_1_2_9_33_1","unstructured":"KennedyCA CarpenterMA. Diagonally implicit runge\u2010kutta methods for ordinary differential equations. A Review. NASA; March2016."},{"key":"e_1_2_9_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1238812"},{"key":"e_1_2_9_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-9274(95)00115-8"},{"key":"e_1_2_9_36_1","unstructured":"XBraid: parallel multigrid in time version.http:\/\/llnl.gov\/casc\/xbraid."},{"key":"e_1_2_9_37_1","unstructured":"MFEM: modular finite element methods library. Version 3.4. http:\/\/mfem.org."},{"key":"e_1_2_9_38_1","doi-asserted-by":"crossref","unstructured":"SouthworthBS MitchellW HessenthalerA. Tight two\u2010level convergence of linear parareal and MGRiT: extensions and implications in practice. (in review);2020;.","DOI":"10.1007\/978-3-030-75933-9_1"},{"key":"e_1_2_9_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2016.10.046"}],"container-title":["Numerical Linear Algebra with Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnla.2301","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/nla.2301","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/nla.2301","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/nla.2301","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,1]],"date-time":"2023-09-01T03:29:00Z","timestamp":1693538940000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/nla.2301"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,23]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["10.1002\/nla.2301"],"URL":"https:\/\/doi.org\/10.1002\/nla.2301","archive":["Portico"],"relation":{},"ISSN":["1070-5325","1099-1506"],"issn-type":[{"value":"1070-5325","type":"print"},{"value":"1099-1506","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,23]]},"assertion":[{"value":"2019-06-17","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-26","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-04-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}