Abstract
Excessive spatial parallelization can introduce a performance bottleneck due to the communication overhead. While time-parallel method multigrid-reduction-in-time (MGRIT) provides an alternative to enhance concurrency, it generally requires large numbers of iterations to converge or even fails when applied to advection-dominated problems. To enhance the convergence of MGRIT, we propose the use of consecutive-step coarse-grid operators in MGRIT, rather than the standard rediscretized coarse-grid operators. The consecutive-step coarse-grid operator is defined as the multiplication of several fine-grid operators, which is able to track the advective characteristic more accurately than the standard rediscretized one. Numerical results show that multilevel MGRIT using the proposed operator is more efficient than the one using the standard rediscretized operator when applied to linear advection problems. Moreover, we perform time-parallel computing of the Euler equations and the Navier–Stokes equations by using the proposed method. Spatial coarsening is also considered. Compared with the MGRIT using the standard rediscretization approach, the developed method demonstrates enhanced robustness and efficiency in handling complex flow problems, including cases involving multidimensional shock waves and contact discontinuities.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Data Availability
The data that support the findings of this study are available from the corresponding author upon reasonable request.
References
Gander, M.J.: 50 years of time parallel time integration. In: Carraro, T., Geiger, M., Körkel, S., Rannacher, R. (eds.) Multiple Shooting and Time Domain Decomposition Methods, vol. 9, pp. 69–113. Springer, Cham (2015)
Nievergelt, J.: Parallel methods for integrating ordinary differential equations. Commun. ACM 7(12), 731–733 (1964)
Emmett, M., Minion, M.: Toward an efficient parallel in time method for partial differential equations. Commun. Appl. Math. Comput. Sci. 7(1), 105–132 (2012)
Falgout, R.D., Friedhoff, S., Kolev, T.V., MacLachlan, S.P., Schroder, J.B.: Parallel time integration with multigrid. SIAM J. Sci. Comput. 36(6), C635–C661 (2014)
Costanzo, S., Sayadi, T., de Pando, M.F., Schmid, P.J., Frey, P.: Parallel-in-time adjoint-based optimization application to unsteady incompressible flows. J. Comput. Phys. 471, 111664 (2022)
Hamon, F.P., Schreiber, M., Minion, M.L.: Parallel-in-time multi-level integration of the shallow-water equations on the rotating sphere. J. Comput. Phys. 407, 109210 (2020)
Chartier, P., Philippe, B.: A parallel shooting technique for solving dissipative ODE’s. Computing 51(3–4), 209–236 (1993)
Lions, J.-L., Maday, Y., Turinici, G.: Résolution d’edp par un schéma en temps pararéel. Comptes Rendus de l’Acad des Sci-Ser I-Math 332(7), 661–668 (2001)
Gander, M.J.: Overlapping Schwarz for linear and nonlinear parabolic problems. In: 9th International Conference on Domain Decomposition Methods, pp. 97–104 (1996)
Gander, M.J.: A waveform relaxation algorithm with overlapping splitting for reaction diffusion equations. Numer. Linear Algebra Appl. 6(2), 125–145 (1999)
Hackbusch, W.: Parabolic Multigrid Methods. Computing Methods in Applied Sciences and Engineering. VI, pp. 189–197 (1984)
Maday, Y., Rønquist, E.M.: Parallelization in time through tensor-product space-time solvers. C.R. Math. 346(1–2), 113–118 (2008)
Christlieb, A.J., Macdonald, C.B., Ong, B.W.: Parallel high-order integrators. SIAM J. Sci. Comput. 32(2), 818–835 (2010)
Christlieb, A., Ong, B.: Implicit parallel time integrators. J. Sci. Comput. 49, 167–179 (2011)
Güttel, S.: A parallel overlapping time-domain decomposition method for ODEs. In: Domain Decomposition Methods in Science and Engineering XX, pp. 459–466. Springer (2013)
Ong, B.W., Schroder, J.B.: Applications of time parallelization. Comput. Vis. Sci. 23(1–4), 11 (2020)
Lunet, T., Bodart, J., Gratton, S., Vasseur, X.: Time-parallel simulation of the decay of homogeneous turbulence using Parareal with spatial coarsening. Comput. Vis. Sci. 19(1–2), 31–44 (2018)
Gander, M.J., Kwok, F., Salomon, J.: PARAOPT: a Parareal algorithm for optimality systems. SIAM J. Sci. Comput. 42(5), A2773–A2802 (2020)
Liu, W., Rostami, M.W.: Parallel-in-time simulation of biofluids. J. Comput. Phys. 111366 (2022)
Farhat, C., Chandesris, M.: Time-decomposed parallel time-integrators: theory and feasibility studies for fluid, structure, and fluid–structure applications. Int. J. Numer. Methods Eng. 58(9), 1397–1434 (2003)
Falgout, R.D., Katz, A., Kolev, T.V., Schroder, J.B., Wissink, A., Yang, U.M.: Parallel time integration with multigrid reduction for a compressible fluid dynamics application. Lawrence Livermore National Laboratory Technical Report, LLNL-JRNL-663416 (2015)
Falgout, R.D., Manteuffel, T.A., O’Neill, B., Schroder, J.B.: Multigrid reduction in time for nonlinear parabolic problems: a case study. SIAM J. Sci. Comput. 39(5), S298–S322 (2017)
Christopher, J., Falgout, R.D., Schroder, J.B., Guzik, S.M., Gao, X.: A space–time parallel algorithm with adaptive mesh refinement for computational fluid dynamics. Comput. Vis. Sci. 23(1–4), 13 (2020)
Howse, A.J., Sterck, H.D., Falgout, R.D., MacLachlan, S., Schroder, J.: Parallel-in-time multigrid with adaptive spatial coarsening for the linear advection and inviscid Burgers equations. SIAM J. Sci. Comput. 41(1), A538–A565 (2019)
De Sterck, H., Falgout, R.D., Friedhoff, S., Krzysik, O.A., MacLachlan, S.P.: Optimizing multigrid reduction-in-time and Parareal coarse-grid operators for linear advection. Numer. Linear Algebra Appl. 28(4) (2021)
Ries, M., Trottenberg, U., Winter, G.: A note on MGR methods. Linear Algebra Appl. 49, 1–26 (1983)
XBraid: Parallel multigrid in time. http://llnl.gov/casc/xbraid
Hessenthaler, A., Southworth, B.S., Nordsletten, D., Röhrle, O., Falgout, R.D., Schroder, J.B.: Multilevel convergence analysis of multigrid-reduction-in-time. SIAM J. Sci. Comput. 42(2), A771–A796 (2020)
Jin, Y., Liao, F., Cai, J.: Convergence acceleration for subiterative DDADI/D3ADI using multiblock implicit boundary condition. J. Comput. Phys. 429, 110009 (2021)
Jameson, A.: Evaluation of fully implicit Runge–Kutta schemes for unsteady flow calculations. J. Sci. Comput. 73(2–3), 819–852 (2017)
Blazek, J.: Computational Fluid Dynamics: Principles and Applications. Butterworth-Heinemann (2015)
He, X., Wang, K., Feng, Y., Lv, L., Liu, T.: An implementation of MPI and hybrid OpenMP/MPI parallelization strategies for an implicit 3D DDG solver. Comput. Fluids 241, 105455 (2022)
Gorobets, A., Bakhvalov, P.: Heterogeneous cpu+ gpu parallelization for high-accuracy scale-resolving simulations of compressible turbulent flows on hybrid supercomputers. Comput. Phys. Commun. 271, 108231 (2022)
Jenny, P., Lee, S.H., Tchelepi, H.A.: Adaptive fully implicit multi-scale finite-volume method for multi-phase flow and transport in heterogeneous porous media. J. Comput. Phys. 217(2), 627–641 (2006)
Yang, C., Xue, W., Fu, H., You, H., Wang, X., Ao, Y., Liu, F., Gan, L., Xu, P., Wang, L. et al.: 10m-core scalable fully-implicit solver for nonhydrostatic atmospheric dynamics. In: SC’16: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 57–68. IEEE (2016)
De Sterck, H., Friedhoff, S., Howse, A.J.M., MacLachlan, S.P.: Convergence analysis for parallel-in-time solution of hyperbolic systems. Numer. Linear Algebra Appl. 27(1), e2271 (2020)
Jiang, G.-S., Shu, C.-W.: Efficient implementation of weighted ENO schemes. J. Comput. Phys. 126(1), 202–228 (1996)
Van Leer, B.: Towards the ultimate conservative difference scheme. v. a second-order sequel to Godunov’s method. J. Comput. Phys. 32(1), 101–136 (1979)
Jameson, A.: Time dependent calculations using multigrid, with applications to unsteady flows past airfoils and wings. In: 10th Computational Fluid Dynamics Conference, p. 1596 (1991)
Rieger, H., Jameson, A.: Solution of steady three-dimensional compressible Euler and Navier–Stokes equations by an implicit LU scheme. In: 26th Aerospace Sciences Meeting, p. 619 (1988)
Yee, H.C., Sandham, N.D., Djomehri, M.J.: Low-dissipative high-order shock-capturing methods using characteristic-based filters. J. Comput. Phys. 150(1), 199–238 (1999)
Lax, P.D., Liu, X.-D.: Solution of two-dimensional Riemann problems of gas dynamics by positive schemes. SIAM J. Sci. Comput. 19(2), 319–340 (1998)
Williamson, C.H.K.: Vortex dynamics in the cylinder wake. Annu. Rev. Fluid Mech. 28, 477–539 (1996)
LimaESilva, A.L.F., Silveira-Neto, A., Damasceno, J.J.R.: Numerical simulation of two-dimensional flows over a circular cylinder using the immersed boundary method. J. Comput. Phys. 189(2), 351–370 (2003)
Funda Kurtulus, D.: On the unsteady behavior of the flow around NACA0012 airfoil with steady external conditions at Re \(=\) 1000. Int. J. Micro Air Veh. 7(3), 301–326 (2015)
Hoarau, Y., Braza, M., Ventikos, Y., Faghani, D., Tzabiras, G.: Organized modes and the three-dimensional transition to turbulence in the incompressible flow around a NACA0012 wing. J. Fluid Mech. 496, 63–72 (2003)
Acknowledgements
The authors acknowledge the reviewers for their valuable comments, which have significantly improved the quality of the manuscript.
Funding
The work is supported by the National Natural Science Foundation of China (Grant Nos. 91952203 and 11902271), and 111 project on Aircraft Complex Flows and the Control (Grant No. B17037).
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendix
Appendix
The difference between the blocking MGRIT and the proposed non-blocking MGRIT is elaborated with the help of Fig. 9. The figure shows two iterations of blocking and non-blocking versions of MGRIT. For simplicity, V-cycle two-level MGRIT with F-relaxation is used for illustration. Four coarse time points are distributed on four processors. The coarse level is solved sequentially so there exists step-like feature in the figure. Each iteration is composed of F-relaxations, restrictions, coarse-level solving and finally prolongations. For the blocking MGRIT, the first processor completes the first V-cycle iteration and then waits until the last process finishes it. After that, processors will perform an MPI_Allreduce operation to obtain the current error, which is used for stopping the iteration. If not converged, the second iteration proceeds in the same way as the first one, as is shown in Fig. 9a. By contrast, if the blocking communication is removed, the second iteration on any processor starts immediately after the first iteration finishes, as is shown in Fig. 9b. It reduces considerable communication overhead especially when the number of processors is large.
Schematic diagram of the iteration processes of V-cycle two-level MGRIT methods
We give quantitative analysis of the speedup S achieved by the non-blocking version over the blocking one. Let \(T_F\) and \(T_C\) denote the time consumed by a relaxation on the fine level and by a solving step on the coarse level, respectively. Likewise, let \(T_R\) and \(T_P\) denote the time cost of a restriction and a prolongation, respectively. Define \(n_{iter}\) to be the number of iterations, and \(N_C\) to be the number of time points on the coarse level, which is the same as the number of processors in Fig. 9. Then, the total time cost of blocking MGRIT is
The total time consumed by non-blocking MGRIT is
The speedup S defined by \(T_{Block}/T_{NBlock}\) can be rearranged as
Algebra analysis indicates that the speedup increases as \(N_C\) or \(n_{iter}\) increase. Therefore, the benefit of non-blocking MGRIT is exploited when \(N_C\) and \(n_{iter}\) are large, which is often the case for hyperbolic equations. To stably advance hyperbolic equations, CFL number on the coarsest level cannot be intensively large, which means \(N_C\) is generally not very small.
One issue of the non-blocking version of MGRIT is that we still need a guideline to stop the iteration. To address this issue, one can perform a blocking communication every other certain number of iterations to obtain the error norm. The time cost of possible extra non-blocking iterations is generally much less than the blocking overhead. To add the non-blocking strategy in XBraid library, one has to modify two parts. The first part is in function braid_DriveCheckConvergence, where the convergence flag is modified to ensure that iterations do not stop too early. The second part is in function braid_FRestrict, where the global error norm is computed. A conditional statement is added to ensure that the MPI_Allreduce operation is performed only when needed.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Zhen, M., Ding, X., Qu, K. et al. Enhancing the Convergence of the Multigrid-Reduction-in-Time Method for the Euler and Navier–Stokes Equations. J Sci Comput 100, 40 (2024). https://doi.org/10.1007/s10915-024-02596-0
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10915-024-02596-0