Slides Schedule & Book of Abstracts Sponsors Participants Simulations
Friday
- 09:00-10:00 : Jan Hesthaven
Parareal for Transport-Dominated Problems. — AbstractJ. S. Hesthaven¹ and A. Nielsen¹
¹ EPFL-SB-MATH-MCSS, Ecole Polytechnique Fédérale de Lausanne, Lausanne, CH
In an attempt to overcome limits on strong scaling and take full advantage of large computing platforms, there has been substantial research devoted to the development of parallel-in-time methods during the last decade, Among several techniques, the Parareal method has been the topic of substantial attention and has been successfully applied to a range of different problems, including molecular dynamics and diffusion dominated problems.
However, the advances for transport dominated problems has been considerably slower with classic methods being plagued by stability problems or slow convergence.
We shall begin by discussing several past attempts that seek to enable the use of the Parareal method to accelerate the parallel solution of transport problems by overcoming what appears to be a stability problem. This leads to the initial conclusion that the quality of the coarse grid solver is particularly important for hyperbolic problems and must be developed with care. As we shall demonstrate, such strategies can either be based on replacing the coarse solver or by carefully managing the work flow of the Parareal method in a general parallel environment to ensure a sufficiently accurate coarse solver while maintaining the potential for parallel speedup.
A second look at the Parareal algorithm reveals that the scheme primarily corrects for amplitude errors while phase errors, often dominating the solution of transport problems, remain essentially uncorrected. This supports the initial observation that an accurate coarse solver allows for rapid convergence as that introduces the required phase error corrections. The challenge remains that a phase accurate coarse solver is not likely to be achievable at low computational cost.
Based on this insight, we proposed a phase-corrected Parareal method and demonstrate that this converges substantially faster for purely hyperbolic problems and transport dominated problems without requiring the use of complex coarse solvers. It also offers a different and more general approach to formulate parallel-in-time methods based on assumptions on the error behavior.
We shall discuss the performance of these new approaches through a number of examples, including the demonstration of time-parallel efficiency exceeding 30% for the fully parallel solution of nonlinear hyperbolic problems.
- 10:30-11:00 : Martin J. Gander
Why it is difficult to solve hyperbolic problems with parareal type algorithms. — AbstractMartin J. Gander¹
¹ University of Geneva
The convergence of the parareal algorithm [1] for the time parallel solution of evolution problems is well understood, see [2] for precise convergence estimates for parabolic and hyperbolic partial differential equations, and [3] for non-linear problems. In the hyperbolic case, the parareal algorithm is missing one of the essential convergence mechanisms that make it work well in the parabolic case. I will try to explain this in my presentation using both a precise convergence estimate, and also the method of characteristics from [4]. The difficulty is similar to the difficulty when solving time harmonic problems with iterative methods [5].
References
[1] Jacques-Louis Lions, Yvon Maday, and Gabriel Turinici. A "parareal" in time discretization of PDE’s. Comptes Rendus de l’Académie des Sciences- Series I-Mathematics, 332(7):661–668, 2001.
[2] Martin J. Gander and Stefan Vandewalle. Analysis of the parareal time- parallel time-integration method. SIAM Journal on Scientific Computing, 29(2):556–578, 2007.
[3] Martin J. Gander and Ernst Hairer. Nonlinear convergence analysis for the parareal algorithm. Lecture Notes in Computational Science and Engineering, 60:45–56, 2008.
[4] Martin J. Gander. Analysis of the parareal algorithm applied to hyperbolic problems using characteristics. Boletin de la Sociedad Espanola de Matemática Aplicada, 42:21–35, 2008.
[5] Oliver G. Ernst and Martin J. Gander. Why it is difficult to solve Helmholtz problems with classical iterative methods. In Numerical analysis of multiscale problems, pages 325–363. Springer, 2012. - 11:00-11:30 : Thibaut Lunet
Stable time-parallel integration of advection dominated problems using Parareal with space coarsening. — AbstractJ. Bodart¹, S. Gratton², X. Vasseur¹, T. Lunet³
¹ ISAE-SUPAERO
² Toulouse-INP-IRIT
³ University of Geneva
A common idea in the PinT community is that Parareal, one of the most popular time-parallel algorithm, is often numerically unstable when applied to hyperbolic problems, such as the advection equation. This has been both numerically observed and studied theoretically in the case of an implicit time integrator as a coarse solver (see, e.g, [1]). Such results could discourage the application of Parareal to Computational Fluid Dynamics (CFD) problems, especially for high Reynolds numbers (see, e.g, [2]). On the contrary, a recent application of Parareal with spatial coarsening to an explicit CFD solver [3] has shown that not only a stable numerical integration was obtained, but also that the Reynolds number played a minor role in the convergence behaviour, compared to other parameters of the parallel-in-time algorithm.
Hence, in this talk, we present numerical experiments related to the application of Parareal with spatial coarsening to the one-dimensional advection- diffusion problem. We investigate the influence of several parameters on the convergence (importance of the diffusion term, spatial resolution, order of interpolation, regularity of the initial solution, time-slice length, nonlinearity,...). We advocate that "a high Reynolds number" is not a good enough reason for not using Parareal, and that a stable and efficient parallel in time integration can be made possible, even for highly advective problems, provided that important algorithmic components are carefully chosen.
References
[1] Daniel Ruprecht. Wave propagation characteristics of Parareal. arXiv preprint arXiv:1701.01359, 2017.
[2] J. Steiner, D. Ruprecht, R. Speck, and R. Krause. Convergence of Parareal for the Navier-Stokes equations depending on the Reynolds number. In Numerical Mathematics and Advanced Applications - ENUMATH 2013, volume 103, pages 195–202. Springer, 2015.
[3] T. Lunet, J. Bodart, S. Gratton, and X. Vasseur. Time-parallel simulation of the decay of homogeneous turbulence using Parareal with spatial coarsening. Comput. Vis. Sci., (Accepted), 2017. - 11:30-12:00 : Duc Quang Bui
Coupled Parareal-Optimized Schwarz Waveform relaxation for advection-diffusion equation. — AbstractD.Q. Bui¹, C. Japhet¹, Y. Maday², P. Omnes¹³
¹ LAGA, Université Paris 13, Sorbonne Paris Cité
² LJLL, UPMC Sorbonne Université
³ CEA, DEN, DM2S-SFME
Parareal method [1, 2] is a numerical method to solve time - evolutional problems in parallel, which uses two propagators: the coarse - fast and inaccurate - and the fine - slow but more accurate. Instead of running the fine propagator on the whole time interval, we divide the time space into small time intervals, where we can run the fine propagator in parallel to obtain the desired solution, with the help of the coarse propagator and through parareal steps. Furthermore, each local subproblem can be solved by an iterative method, and instead of doing this local iterative method until convergence, one may perform only a few iterations of it, during parareal iter- ations. Propagators then become much cheaper but sharply lose their accuracy, and we hope that the convergence will be achieved across parareal iterations.
In this contribution, we propose to couple Parareal with a well-known iterative method - Optimized Schwarz Waveform Relaxation (OSWR) [3] - with only few OSWR iterations in the fine propagator and with a simple coarse propagator deduced from Backward Euler method. We present the analysis of this coupled method for 1-dimensional advection reaction diffusion equation, for this case the convergence is almost linear. We also give some numerical illustrations for 1D and 2D equations, which shows that the convergence is much faster in practice.
References
[1] Jacques-Louis Lions, Yvon Maday, and Gabriel Turinici. A parareal in time discretization of PDE's. C.R. Acad. Sci. Paris, Serie I, 332:661–668, 2001.
[2] Martin J. Gander and Stefan Vandewalle. Analysis of the parareal time-parallel time-integration method. SIAM J. Sci. Comp., 29(2):556–578, 2007.
[3] Martin J. Gander and Laurence Halpern. Optimized Schwarz wave- form relaxation methods for advection reaction diffusion problems. SIAM J. Numer. Anal., 45(2):666–697, 2007. - 12:00-12:30 : Julien Salomon
Time parallelisation for optimal control and data assimilation. — AbstractM.J. Gander¹, F. Kwok², S. Reyes-Riffo³, J. Salomon⁴
¹ University of Geneva
² Hong Kong Baptist University
³ Ceremade, Université Paris-Dauphine
⁴ INRIA-Paris and Laboratoire J-L. Lions, Sorbonne Université
In this talk, we introduce a method to solve approximately optimality systems associated with optimal control problems. Our approach is based on parareal algorithm idea, i.e., it consists in using a coarse solver to build an approximation of the Jacobian matrix involved in a Newton Loop. This method does not work on an bounded intervals, e.g., when the system needs to be controlled for all t ∈ [0,+ ∞). To deal with such a case, we focus on a data assimilation problem and present an adjoint-free version of the method. - 14:30-15:30 : Shu-Lin Wu
A Parallel-In-Time Algorithm For Time-Periodic PDE-constrained Optimal Control Problems. — AbstractShu-Lin Wu¹
¹ Sichuan University of Science and Engineering, Zigong 643000, Sichuan Province, P.R.China
References
[1] M. J. Gander, L. Halpern, J. Ryan, and T. T. B. Tran. A direct solver for time parallelization. LNCSE 104 (2016): 491-499.
[2] R. Herzog and E. Sachs. Preconditioned conjugate gradient method for optimal control problems with control and state constraints. SIAM J. Matrix Anal. Appl. 31 (2010): 2291-2317.
[3] Y. Maday and E. M. Rønquist. Parallelization in time through tensor product space- time solvers. CRM 346 (2008): 113-118.
[4] M. Stoll. One-shot solution of a time-dependent time-periodic PDE-constrained optimization problem. IMA J. Numer. Anal. 34 (2014): 1554-1577. - 15:30-16:00 : Discussion
-Lunch-
- 16:30-17:00 : Iryna Kulchytska
A New Parareal Algorithm for Problems with Discontinuous Sources. — AbstractI. Kulchytska-Ruchka¹, M. J. Gander², S. Schöps¹, I. Niyonzima³
¹ Technical University of Darmstadt
² University of Geneva
³ Columbia University
The Parareal algorithm [1] allows to solve time-dependent problems in a time-parallel manner. Its convergence rate for nonlinear problems was derived in [2] under the assumption of regular (smooth) inputs. In the present contribution we perform a convergence analysis of a modified Parareal method for systems, which involve discontinuous right-hand sides. Such situations occur, e.g., in power engineering when electric devices are supplied with a pulse-width-modulated signal. In order to develop the theory for such problems we propose to use a low-frequency smooth input for the coarse propagator, e.g., from Fourier analysis. The influence of the input reduction on the overall convergence rate of the algorithm is illustrated by the derived error estimate. Numerical verification complements the theoretical findings and supports the obtained error bounds. Furthermore, similarly to the recent results of [3] on Parareal for the eddy current problem, we applied our modified approach with reduced coarse dynamics to the simulation of an induction machine and compared its performance to that of the standard Parareal method.
Acknowledgments. The work of I. Kulchytska-Ruchka is supported by the Excellence Initiative of the German Federal and State Governments and the Graduate School of Computational Engineering at Technische Univer- sität Darmstadt, as well as by the BMBF (grant No. 05M2018RDA) in the framework of project PASIROM.
References
[1] Jacques-Louis Lions, Yvon Maday, and Gabriel Turinici. A parareal in time discretization of PDEs. Comptes Rendus de l’Académie des Sciences – Series I – Mathematics, 332(7):661–668, 2001.
[2] Martin J. Gander and Ernst Hairer. Nonlinear Convergence Analysis for the Parareal Algorithm, pages 45–56. Springer Berlin Heidelberg, Berlin, Heidelberg, 2008.
[3] Sebastian Schöps, Innocent Niyonzima, and Markus Clemens. Parallel- in-time simulation of eddy current problems using parareal. 54(3):1–4, 2018. - 17:00-17:30 : Asad Anees
Time Domain Finite Element Methods for Maxwell’s Equations. — AbstractA. Anees¹, L. Angermann¹
¹ Institute of Mathematics, Clausthal University of Technology, Clausthal-Zellerfeld, D-38678, Germany
In this presentation, we discuss a time-domain finite element methods to the solution of linear and nonlinear Maxwell’s equations. A weak formulation is derived for the electric and magnetic field with appropriate initial and boundary conditions, and the problem is discretised both in space and time. Nédeléc curl conforming and Raviart Thomas divergence conforming finite elements are used to discretized the electric and magnetic fields respectively in space. In time domain, problems are discretized by symplatic and backward Euler methods, and provide some numerical results to validate our simulation for fully discretized problems. The proposed methods are accurate in time up to order 4, in case of symplectic time integration and they are conditionally stable. Our methods also allow to treat a complex geometries of various physical system coupled to electromagnetics fields. Electric and magnetic fields are also visualized at each time step on tetrahedron meshes. Our proposed methods are also parallel, but time integration is not parallel. We are working to add parallel time integrations in our proposed mixed finite element methods for electromagnetic using XBraid.
References
[1] A. Anees and L. Angermann, Time Domain Finite Element Methods for Maxwell’s Equations in Three Dimensions, IEEE and International Applied Computational Electromagnetics Society (ACES) Symposium, March 24-29, 2018, Denver, Colorado, U.S.A,
[2] A. Anees and L. Angermann, Mixed Finite Element Methods for the Maxwell’s Equations with Matrix Parameters, IEEE and International Applied Computational Electromagnetics Society (ACES) Symposium, March 24-29, 2018, Denver, Colorado, U.S.A,
[3] G. Rodrigue and D. White, A vector finite element Time-Domain method for solving Maxwell’s equations on unstructured Hexeahedral grids, Society for Industrial and Applied Mathematics, 23, pp. 683-706, 2001. - 17:30-18:00 : Mikio Iizuka
Investigation of Convergence of Parareal Method forAdvection Equation using Accurate Phase Calculation Method. — AbstractM. Iizuka¹, K. Ono¹
¹ Research Institute for Information Technology, Kyushu University, 744 Motooka, Nishi-ku, Fukuoka, 819-0395 Japan
Applying the parareal method to hyperbolic PDEs, such as the advection equation, is strongly desired. However, it is still difficult to solve it even now. Reference [1] reported that the reason of the difficulty is identified as the beating between waves, which is introduced by the discrepancy of the phase between the fine and the coarse solvers, and leads the low convergence rate. So far, huge efforts have been performed to improve the phase accuracy of the hyperbolic PDEs. In this study, we introduce CIP (Constrained Interpolation Profile Scheme) scheme [2], and STRS-CIP scheme, which is the combination of STRS (Space-Time Reversal Symmetry Scheme) [3] and CIP, and try to improve the convergence rate of the parareal method for the advection equation. In this presentation, we show the numerical results of the convergence of the parareal method by the CIP-3rd, CIP-5th order schemes, and the STRS-CIP scheme. Then, we discuss the convergence of the parareal method with highly accurate phase treatment for the advection equation.
References
[1] M. Gander and M. Petcu. Analysis of a krylov subspace enhanced parareal algorithm for linear problems. volume 25, pages 114–129. ESAIM Proc, 2008.
[2] H. Takewaki and T. Yabe. The cubic-interpolated pseudo particle (cip) method: Application to nonlinear and multi-dimensional hyperbolic equations. J. Comput. Phys., 70:353372, 1987.
[3] K. Watanabe. a novel framework to construct amplitude preserving wave propagation schemes. pages 123–124, 2010. Japan Society for Industrial and Applied Mathematics, Annual meeting.