Summer school on advanced parallel-in-time methods

News

Registrations will close on 04.06.2023.

– Location

La Nave Building 14, Via Edoardo Bonardi, 9 (access from via Ampère or from via Ponzio 31), 20133 Milano MI.

Sala del Consiglio, 7th floor. See here.

A link will be provided soon to all registered participants to attend the lectures online.

– Program

(the abstracts can be found at the end of this page)

Tuesday 13.06
10:00-10:30 – Registration and Welcome
10:30-11:30 – Introduction to Time Parallel Time Integration (M.J. Gander)
11:30-12:30 – Optimized Schwarz waveform relaxation, algorithms and methods (L. Halpern)
12:30-14:30 – Lunch break
14:30-15:30 – Space-time discontinuous Galerkin methods for wave-type problems (P. Antonietti)
15:30-16:30 – On dG and Waveform Relaxation methods for wave-type equations (I. Mazzieri)

Wednesday 14.06
10:30-11:30 – Parareal (J. Salomon)
11:30-12:30 – Multilevel methods for parallel-in-time integration (F. Kwok)
12:30-14:30 – Lunch break
14:30-15:30 – Parareal methods for control and assimilation (J. Salomon)
15:30-16:00 – Coffee break
16:00-17:00 – Advances in hyperbolic solvers based on spacetime tents (J. Gopalakrishnan – online)

Thursday 15.06
10:30-11:30 – Parallelization of waveform relaxation methods (F. Kwok)
11:30-12:30 – ParaDiag: diagonalization-based parallel-in-time algorithms (S. Wu – online)
12:30-14:30 – Lunch break
14:30-15:30 – Advanced PinT methods (Y. Maday – online)
15:30-16:00 – Closing

General description

We are pleased to announce the Summer School on Advanced Parallel-in-Time Methods at the Politecnico di Milano, Milan, Italy, from 13.06.2023 to 15.06.2023. The event is funded by the European Mathematical Society and the Indam GNCS group.

The goal of this summer school is to introduce basic and advanced parallel-in-time methods to researchers interested in understanding these methods, and to give them detailed insight on how these methods reduce various error components and are used in practice.
The course will cover parallel-in-time methods for various time-dependent problems ranging from parabolic and hyperbolic partial differential equations (PDEs) to PDE-constrained optimization problems.
The school is suitable for young mathematicians (PhD students and highly motivated Master Students), who wish to either get in touch with parallel-in-time methods, as well as young researchers and Post-docs who desire to strengthen and broaden their knowledge on advanced time-parallelization techniques.

List of speakers

Registration

The registration is free of fees, but is mandatory. Participants can attend the lectures either in presence or online (further info will be available soon). To register fill in the online form at this link or send an email to Gabriele Ciaramella including the registration form (that you can download below) filled in and signed. Notice that the number of participants in presence is limited. Thus, if you apply for participation in presence, you will receive a confirmation email. Registrations will close on 04.06.2023.

registration_form-1Download

Organizer

Contacts

  • gabriele.ciaramella_at_polimi.it (Gabriele Ciaramella)
  • eventi-dmat_at_polimi.it (Events Office)

This event is part of the activities of the Department of Exellence 2023-27.

Abstracts

Tuesday 13.06

Introduction to Time Parallel Time Integration (M. J. Gander)

I will present an introduction to the research area of time parallel time integration, more recently also referred to as PinT (Parallel in Time) methods. I will explain the four main classes of such methods: multiple shooting type methods for initial value problems leading to Parareal, waveform relaxation methods based on domain decomposition leading to Schwarz waveform relaxation, space-time multigrid methods leading to a highly scalable method using standard components for parabolic problems, and also direct space-time parallel methods including ParaDiag and ParaExp.

Optimized Schwarz waveform relaxation, algorithms and methods (L. Halpern)

The Schwarz algorithm (Schwarz, 1872) is an overlapping domain decomposition algorithm applied to solving partial differential equations, whose properties are now well-known and widely used in the context of parallel computations. But the convergence of low frequency components deteriorates with the size of the overlap.
Optimized Schwarz algorithms have been developed in the last twenty years (starting with Caroline Japhet’s thesis, 1998), and improve drastically the convergence of the method. They modify the transmission conditions at the interfaces, using Robin or Ventcel operators. Through Fourier-type techniques, the best Robin coefficient is obtained through of a (possibly) complex best approximation problem. We present here a summary of advantages, techniques and results in various situations, including time dependent problems, optimal control problems, and coarsening.

Space-time discontinuous Galerkin methods for wave-type problems (P. Antonietti)

In this talks we discuss high-order discontinuous Galerkin finite element methods for both space and time integration of second-order hyperbolic-type differential problems, e.g., acoustic  and elastic wave equations. After introducing both space and time discrete formulations, we analyse well-posedness and prove a priori error estimates in suitable (mesh-dependent) norms. Numerical results are also presented to verify our theoretical estimates.

On dG and Waveform Relaxation methods for wave-type equations (I. Mazzieri)

In the first part of the talk, we discuss analogies and differences between discontinuous Galerkin (dG) methods and time-stepping schemes for the integration of Cauchy problems. In the second part, we focus on the dG space-time formulation of the wave equation and discuss possible resolution strategies based on the waveform relaxation method.

Wednesday 14.06

Parareal (J. Salomon)

In this lecture, I will recall basics on the Parareal algorithm and discuss how its principles can be used to design efficient time-parallelized solvers for optimality systems. The precise formulation of these “ParaOpt” procedures will be derived from a standard Newton fixed-point iteration. I will then focus on the analysis of convergence of the method. Applications to specific example will conclude this part.

Multilevel methods for parallel-in-time integration (F. Kwok)

The invention of the multigrid methods was a breakthrough for the numerical solution of elliptic problems. By creating a hierarchy of coarser discretizations and cycling between the different levels, these methods expose opportunities for parallelization and makes the operation count scale linearly with the number of unknowns for a large class of elliptic problems. Multigrid ideas have been extended to discretizations in time; this leads to the multigrid-reduction in time (MGRIT) method of Falgout, Friedhoff, Kolev, MacLachlan and Schroder (SISC 2014), where the directional nature of time requires a different treatment when data are passed between the different time grid levels. In this talk, we will explain the basic ideas behind MGRIT and analyze its convergence properties for time dependent problems. We will also show how Parareal is equivalent to MGRIT for a certain choice of restriction/interpolation operators and relaxation schemes.

Parareal methods for control and assimilation (J. Salomon)

In this lecture, I will focus on methods to couple time parallelization and data assimilation. A usual approach to tackle assimilation problem consists in using an
Luenberger observer, i.e. adding a data attachment term to the model. Suitable assumptions can then be made to prove the convergence of the observer to the observed system. We will present a time parallelization method adapted to this type of problem. Our approach is based on a two-stage partitioning of the information flow which allows to obtain convergence without additional assumptions. In addition and despite the addition of a parallelization loop, this method preserves the convergence rate of the observer under consideration.

Advances in hyperbolic solvers based on spacetime tents (J. Gopalakrishnan)

This talk is concerned with techniques to advance the numerical solution of a hyperbolic problem by progressively meshing a spacetime simulation region by tent-shaped objects. Tents are natural for solving hyperbolic equations, because by constraining the height of the tent pole, one can ensure causality. Namely, the domain of dependence of all points within the tent can be guaranteed to be contained within the tent, by constraining the tent pole height. Such tent pitching schemes have the ability to naturally advance in time by different amounts at different spatial locations. Local time stepping without losing high order accuracy in space and time is thus possible on such unstructured tent meshes. Moreover, the solution process can proceed asynchronously, in parallel, in non-interacting tents. Provided that an approximate solution is available at the tent bottom, we show the solution can be locally evolved up to the top of the tent. This can be understood by mapping tents to a domain which is a tensor product of a spatial domain with a pseudotime interval. For discretizing this process, we focus on discontinuous Galerkin spatial discretization on the mapped tents, combined with fully explicit (pseudo)time-stepping schemes. Construction of specialized time-stepping schemes suitable for such mapped equations, as well as their currently known stability results, will be presented.

Thursday 15.06

Parallelization of waveform relaxation methods (F. Kwok)

In this talk, we consider the parallel implementation of Schwarz waveform relaxation (WR) methods for solving time-dependent PDEs. Mathematically, each SWR iteration requires the parallel solution of space-time subdomain problems, followed by an exchange of interface data defined over the whole time window; the process is then repeated at the next iteration. However, in practice, one does not need to integrate the space-time problem to completion before starting the next iteration: data from the first few time steps can already be passed to neighbouring processors, which can then start a new iteration while the previous one is being completed. In other words, several iterations can run simultaneously.

Based on this observation, we propose two ways of parallelizing WR methods in time. The first one uses a fixed time window and is mathematically equivalent to the original WR method. The second one chooses the time-window size dynamically based on how many free processors are available; this leads to a method with different convergence behaviour. We demonstrate the effectiveness of both approaches by comparing their running times against those obtained from classical time-stepping methods, where the same number of processors is used to parallelize in space only.

ParaDiag: diagonalization-based parallel-in-time algorithms (S. Wu)

In this lecture, I will introduce two diagonalization based parallel-in-time algorithms, the direct algoirthm and the iterative algorithm. The direct algorithm lies in using a non-uniform time grid and then directly diagonalizing the time stepping matrix. This idea works well if the number of time steps is not large. For large number of time steps, roundoff error arising from the diagonalization would seriously pollute the accuracy of the obtained solution. In this case, we use uniform time grid and solve the all-at-once system iteratively by preconditioning the time stepping matrix by a circulant matrix. Then, by using a Fourier spectral factorization of the circulant matrix the preconditiong step in each iteration can be solved parallel. The preconditioned matrix has mesh-independent lower and upper eigenvalue bounds if the time-integrator is stable. At last, I will introduce the applicability of the preconditioning idea to parabolic optimal control problems.

Advanced PinT methods (Y. Maday)

T.B.A.