References

This list of publications closely related to parallel-in-time integration is probably not complete. Please feel free to add any missing publications through a pull request on GitHub .

Statistics

BibTeX

You need to activate JavaScript to see the awesome statistics and beautify below listings.

top

2024

AppelEtAl2024

M. Appel and J. Alexandersen, “One-shot Parareal Approach for Topology Optimisation of Transient Heat Flow,” arXiv:2411.19030v1 [cs.CE], 2024 [Online]. Available at: http://arxiv.org/abs/2411.19030v1
BibTeX entry AppelEtAl2024

@unpublished{AppelEtAl2024, author = {Appel, Magnus and Alexandersen, Joe}, howpublished = {arXiv:2411.19030v1 [cs.CE]}, title = {One-shot Parareal Approach for Topology Optimisation of Transient Heat Flow}, url = {http://arxiv.org/abs/2411.19030v1}, year = {2024} }
Abstract for BibTeX entry AppelEtAl2024

This paper presents a method of performing topology optimisation of transient heat conduction problems using the parallel-in-time method Parareal. To accommodate the adjoint analysis, the Parareal method was modified to store intermediate time steps. Preliminary tests revealed that Parareal requires many iterations to achieve accurate results and, thus, achieves no appreciable speedup. To mitigate this, a one-shot approach was used, where the time history is iteratively refined over the optimisation process. The method estimates objectives and sensitivities by introducing cumulative objectives and sensitivities and solving for these using a single iteration of Parareal, after which it updates the design using the Method of Moving Asymptotes. The resulting method was applied to a test problem where a power mean of the temperature was minimised. It achieved a peak speedup relative to a sequential reference method of 5\times using 16 threads. The resulting designs were similar to the one found by the reference method, both in terms of objective values and qualitative appearance. The one-shot Parareal method was compared to the Parallel Local-in-Time method of topology optimisation. This revealed that the Parallel Local-in-Time method was unstable for the considered test problem, but it achieved a peak speedup of 12\times using 32 threads. It was determined that the dominant bottleneck in the one-shot Parareal method was the time spent on computing coarse propagators.
BetckeEtAl2024

M. M. Betcke, L. M. Kreusser, and D. Murari, “Parallel-in-Time Solutions with Random Projection Neural Networks,” arXiv:2408.09756v1 [math.NA], 2024 [Online]. Available at: http://arxiv.org/abs/2408.09756v1
BibTeX entry BetckeEtAl2024

@unpublished{BetckeEtAl2024, author = {Betcke, Marta M. and Kreusser, Lisa Maria and Murari, Davide}, howpublished = {arXiv:2408.09756v1 [math.NA]}, title = {Parallel-in-Time Solutions with Random Projection Neural Networks}, url = {http://arxiv.org/abs/2408.09756v1}, year = {2024} }
Abstract for BibTeX entry BetckeEtAl2024

This paper considers one of the fundamental parallel-in-time methods for the solution of ordinary differential equations, Parareal, and extends it by adopting a neural network as a coarse propagator. We provide a theoretical analysis of the convergence properties of the proposed algorithm and show its effectiveness for several examples, including Lorenz and Burgers’ equations. In our numerical simulations, we further specialize the underpinning neural architecture to Random Projection Neural Networks (RPNNs), a 2-layer neural network where the first layer weights are drawn at random rather than optimized. This restriction substantially increases the efficiency of fitting RPNN’s weights in comparison to a standard feedforward network without negatively impacting the accuracy, as demonstrated in the SIR system example.
BossuytEtAl2024

I. Bossuyt, S. Vandewalle, and G. Samaey, “Micro-macro Parareal, from ODEs to SDEs and back again,” arXiv:2401.01798v1 [math.NA], 2024 [Online]. Available at: http://arxiv.org/abs/2401.01798v1
BibTeX entry BossuytEtAl2024

@unpublished{BossuytEtAl2024, author = {Bossuyt, Ignace and Vandewalle, Stefan and Samaey, Giovanni}, howpublished = {arXiv:2401.01798v1 [math.NA]}, title = {Micro-macro Parareal, from ODEs to SDEs and back again}, url = {http://arxiv.org/abs/2401.01798v1}, year = {2024} }
Abstract for BibTeX entry BossuytEtAl2024

In this paper, we are concerned with the micro-macro Parareal algorithm for the simulation of initial-value problems. In this algorithm, a coarse (fast) solver is applied sequentially over the time domain, and a fine (time-consuming) solver is applied as a corrector in parallel over smaller chunks of the time interval. Moreover, the coarse solver acts on a reduced state variable, which is coupled to the fine state variable through appropriate coupling operators. We first provide a contribution to the convergence analysis of the micro-macro Parareal method for multiscale linear ordinary differential equations (ODEs). Then, we extend a variant of the micro-macro Parareal algorithm for scalar stochastic differential equations (SDEs) to higher-dimensional SDEs.
CaoEtAl2024

R. Cao, S. Hou, and L. Ma, “A Pipeline-Based ODE Solving Framework,” IEEE Access, vol. 12, pp. 37995–38004, 2024, doi: 10.1109/ACCESS.2024.3375305.
BibTeX entry CaoEtAl2024

@article{CaoEtAl2024, author = {Cao, Ruixia and Hou, Shangjun and Ma, Lin}, doi = {10.1109/ACCESS.2024.3375305}, journal = {IEEE Access}, number = {}, pages = {37995-38004}, title = {A Pipeline-Based ODE Solving Framework}, volume = {12}, year = {2024} }
Abstract for BibTeX entry CaoEtAl2024

The traditional parallel solving methods of ordinary differential equations (ODE) are mainly classified into task-parallelism, data-parallelism, and instruction-level parallelism. Based on the RIDC (revisionist integral deferred correction) algorithm, a hybrid solver dispatched on both CPU and GPU is proposed, which realizes computing in a pipeline form and a remarkable parallelism is obtained both inside a single equation and among many different equations. The proposed framework can make full use of the multi-core advantage of GPU, which is conducive to load balancing within computing nodes. The efficiency and accuracy of the framework are verified in several experiments.
FreeseEtAl2024

P. Freese, S. Götschel, T. Lunet, D. Ruprecht, and M. Schreiber, “Parallel performance of shared memory parallel spectral deferred corrections,” arXiv:2403.20135v1 [cs.CE], 2024 [Online]. Available at: http://arxiv.org/abs/2403.20135v1
BibTeX entry FreeseEtAl2024

@unpublished{FreeseEtAl2024, author = {Freese, Philip and Götschel, Sebastian and Lunet, Thibaut and Ruprecht, Daniel and Schreiber, Martin}, howpublished = {arXiv:2403.20135v1 [cs.CE]}, title = {Parallel performance of shared memory parallel spectral deferred corrections}, url = {http://arxiv.org/abs/2403.20135v1}, year = {2024} }
Abstract for BibTeX entry FreeseEtAl2024

We investigate parallel performance of parallel spectral deferred corrections, a numerical approach that provides small-scale parallelism for the numerical solution of initial value problems. The scheme is applied to the shallow water equation and uses an IMEX splitting that integrates fast modes implicitly and slow modes explicitly in order to be efficient. We describe parallel \textttOpenMP-based implementations of parallel SDC in two well established simulation codes: the finite volume based operational ocean model \textttICON-O and the spherical harmonics based research code \textttSWEET. The implementations are benchmarked on a single node of the JUSUF (\textttSWEET) and JUWELS (\textttICON-O) system at Jülich Supercomputing Centre. We demonstrate a reduction of time-to-solution across a range of accuracies. For \textttICON-O, we show speedup over the currently used Adams–Bashforth-2 integrator with \textttOpenMP loop parallelization. For \textttSWEET, we show speedup over serial spectral deferred corrections and a second order implicit-explicit integrator.
FungEtAl2024

P. Y. Fung and S. Hon, “Block ω-circulant preconditioners for parabolic optimal control problems,” arXiv:2406.00952v1 [math.NA], 2024 [Online]. Available at: http://arxiv.org/abs/2406.00952v1
BibTeX entry FungEtAl2024

@unpublished{FungEtAl2024, author = {Fung, Po Yin and Hon, Sean}, howpublished = {arXiv:2406.00952v1 [math.NA]}, title = {Block $ω$-circulant preconditioners for parabolic optimal control problems}, url = {http://arxiv.org/abs/2406.00952v1}, year = {2024} }
Abstract for BibTeX entry FungEtAl2024

In this work, we propose a class of novel preconditioned Krylov subspace methods for solving an optimal control problem of parabolic equations. Namely, we develop a family of block ω-circulant based preconditioners for the all-at-once linear system arising from the concerned optimal control problem, where both first order and second order time discretization methods are considered. The proposed preconditioners can be efficiently diagonalized by fast Fourier transforms in a parallel-in-time fashion, and their effectiveness is theoretically shown in the sense that the eigenvalues of the preconditioned matrix are clustered around \pm 1, which leads to rapid convergence when the minimal residual method is used. When the generalized minimal residual method is deployed, the efficacy of the proposed preconditioners are justified in the way that the singular values of the preconditioned matrices are proven clustered around unity. Numerical results are provided to demonstrate the effectiveness of our proposed solvers.

P. Y. Fung and S. Hon, “Block $\boldsymbolω$-Circulant Preconditioners for Parabolic Optimal Control Problems,” SIAM Journal on Matrix Analysis and Applications, vol. 45, no. 4, pp. 2263–2286, Dec. 2024, doi: 10.1137/23m1601432. [Online]. Available at: http://dx.doi.org/10.1137/23M1601432

GanderEtAl2024

M. J. Gander, M. Ohlberger, and S. Rave, “A Parareal algorithm without Coarse Propagator?,” arXiv:2409.02673v1 [math.NA], 2024 [Online]. Available at: http://arxiv.org/abs/2409.02673v1
BibTeX entry GanderEtAl2024

@unpublished{GanderEtAl2024, author = {Gander, Martin J. and Ohlberger, Mario and Rave, Stephan}, howpublished = {arXiv:2409.02673v1 [math.NA]}, title = {A Parareal algorithm without Coarse Propagator?}, url = {http://arxiv.org/abs/2409.02673v1}, year = {2024} }
Abstract for BibTeX entry GanderEtAl2024

The Parareal algorithm was invented in 2001 in order to parallelize the solution of evolution problems in the time direction. It is based on parallel fine time propagators called F and sequential coarse time propagators called G, which alternatingly solve the evolution problem and iteratively converge to the fine solution. The coarse propagator G is a very important component of Parareal, as one sees in the convergence analyses. We present here for the first time a Parareal algorithm without coarse propagator, and explain why this can work very well for parabolic problems. We give a new convergence proof for coarse propagators approximating in space, in contrast to the more classical coarse propagators which are approximations in time, and our proof also applies in the absence of the coarse propagator. We illustrate our theoretical results with numerical experiments, and also explain why this approach can not work for hyperbolic problems.
GattiglioEtAl2024

G. Gattiglio, L. Grigoryeva, and M. Tamborrino, “Nearest Neighbors GParareal: Improving Scalability of Gaussian Processes for Parallel-in-Time Solvers,” arXiv:2405.12182v1 [stat.CO], 2024 [Online]. Available at: http://arxiv.org/abs/2405.12182v1
BibTeX entry GattiglioEtAl2024

@unpublished{GattiglioEtAl2024, author = {Gattiglio, Guglielmo and Grigoryeva, Lyudmila and Tamborrino, Massimiliano}, howpublished = {arXiv:2405.12182v1 [stat.CO]}, title = {Nearest Neighbors GParareal: Improving Scalability of Gaussian Processes for Parallel-in-Time Solvers}, url = {http://arxiv.org/abs/2405.12182v1}, year = {2024} }
Abstract for BibTeX entry GattiglioEtAl2024

With the advent of supercomputers, multi-processor environments and parallel-in-time (PinT) algorithms offer ways to solve initial value problems for ordinary and partial differential equations (ODEs and PDEs) over long time intervals, a task often unfeasible with sequential solvers within realistic time frames. A recent approach, GParareal, combines Gaussian Processes with traditional PinT methodology (Parareal) to achieve faster parallel speed-ups. The method is known to outperform Parareal for low-dimensional ODEs and a limited number of computer cores. Here, we present Nearest Neighbors GParareal (nnGParareal), a novel data-enriched PinT integration algorithm. nnGParareal builds upon GParareal by improving its scalability properties for higher-dimensional systems and increased processor count. Through data reduction, the model complexity is reduced from cubic to log-linear in the sample size, yielding a fast and automated procedure to integrate initial value problems over long time intervals. First, we provide both an upper bound for the error and theoretical details on the speed-up benefits. Then, we empirically illustrate the superior performance of nnGParareal, compared to GParareal and Parareal, on nine different systems with unique features (e.g., stiff, chaotic, high-dimensional, or challenging-to-learn systems).
GattiglioEtAl2024b

G. Gattiglio, L. Grigoryeva, and M. Tamborrino, “RandNet-Parareal: a time-parallel PDE solver using Random Neural Networks,” arXiv:2411.06225v1 [stat.CO], 2024 [Online]. Available at: http://arxiv.org/abs/2411.06225v1
BibTeX entry GattiglioEtAl2024b

@unpublished{GattiglioEtAl2024b, author = {Gattiglio, Guglielmo and Grigoryeva, Lyudmila and Tamborrino, Massimiliano}, howpublished = {arXiv:2411.06225v1 [stat.CO]}, title = {RandNet-Parareal: a time-parallel PDE solver using Random Neural Networks}, url = {http://arxiv.org/abs/2411.06225v1}, year = {2024} }
Abstract for BibTeX entry GattiglioEtAl2024b

Parallel-in-time (PinT) techniques have been proposed to solve systems of time-dependent differential equations by parallelizing the temporal domain. Among them, Parareal computes the solution sequentially using an inaccurate (fast) solver, and then "corrects" it using an accurate (slow) integrator that runs in parallel across temporal subintervals. This work introduces RandNet-Parareal, a novel method to learn the discrepancy between the coarse and fine solutions using random neural networks (RandNets). RandNet-Parareal achieves speed gains up to x125 and x22 compared to the fine solver run serially and Parareal, respectively. Beyond theoretical guarantees of RandNets as universal approximators, these models are quick to train, allowing the PinT solution of partial differential equations on a spatial mesh of up to 10^5 points with minimal overhead, dramatically increasing the scalability of existing PinT approaches. RandNet-Parareal’s numerical performance is illustrated on systems of real-world significance, such as the viscous Burgers’ equation, the Diffusion-Reaction equation, the two- and three-dimensional Brusselator, and the shallow water equation.
GuEtAl2024

X.-M. Gu, J. Liu, and C. W. Oosterlee, “Parallel-in-Time Iterative Methods for Pricing American Options,” arXiv:2405.08280v1 [math.NA], 2024 [Online]. Available at: http://arxiv.org/abs/2405.08280v1
BibTeX entry GuEtAl2024

@unpublished{GuEtAl2024, author = {Gu, Xian-Ming and Liu, Jun and Oosterlee, Cornelis W.}, howpublished = {arXiv:2405.08280v1 [math.NA]}, title = {Parallel-in-Time Iterative Methods for Pricing American Options}, url = {http://arxiv.org/abs/2405.08280v1}, year = {2024} }
Abstract for BibTeX entry GuEtAl2024

For pricing American options, %after suitable discretization in space and time, a sequence of discrete linear complementarity problems (LCPs) or equivalently Hamilton-Jacobi-Bellman (HJB) equations need to be solved in a sequential time-stepping manner. In each time step, the policy iteration or its penalty variant is often applied due to their fast convergence rates. In this paper, we aim to solve for all time steps simultaneously, by applying the policy iteration to an “all-at-once form" of the HJB equations, where two different parallel-in-time preconditioners are proposed to accelerate the solution of the linear systems within the policy iteration. Our proposed methods are generally applicable for such all-at-once forms of the HJB equation, arising from option pricing problems with optimal stopping and nontrivial underlying asset models. Numerical examples are presented to show the feasibility and robust convergence behavior of the proposed methodology.
GuEtAl2024b

H. Gu, M. Cai, and J. Li, “Crank-Nicolson-type iterative decoupled algorithms for Biot’s consolidation model using total pressure,” arXiv:2409.18391v1 [math.NA], 2024 [Online]. Available at: http://arxiv.org/abs/2409.18391v1
BibTeX entry GuEtAl2024b

@unpublished{GuEtAl2024b, author = {Gu, Huipeng and Cai, Mingchao and Li, Jingzhi}, howpublished = {arXiv:2409.18391v1 [math.NA]}, title = {Crank-Nicolson-type iterative decoupled algorithms for Biot's consolidation model using total pressure}, url = {http://arxiv.org/abs/2409.18391v1}, year = {2024} }
Abstract for BibTeX entry GuEtAl2024b

In this work, we develop Crank-Nicolson-type iterative decoupled algorithms for a three-field formulation of Biot’s consolidation model using total pressure. We begin by constructing an equivalent fully implicit coupled algorithm using the standard Crank-Nicolson method for the three-field formulation of Biot’s model. Employing an iterative decoupled scheme to decompose the resulting coupled system, we derive two distinctive forms of Crank-Nicolson-type iterative decoupled algorithms based on the order of temporal computation and iteration: a time-stepping iterative decoupled algorithm and a global-in-time iterative decoupled algorithm. Notably, the proposed global-in-time algorithm supports a partially parallel-in-time feature. Capitalizing on the convergence properties of the iterative decoupled scheme, both algorithms exhibit second-order time accuracy and unconditional stability. Through numerical experiments, we validate theoretical predictions and demonstrate the effectiveness and efficiency of these novel approaches.

T. He, J. Lu, and M. Li, “The parareal algorithm for Caputo-Hadamard fractional differential equations,” Communications on Analysis and Computation, vol. 0, no. 0, pp. 0–0, 2024, doi: 10.3934/cac.2024021. [Online]. Available at: http://dx.doi.org/10.3934/cac.2024021

M. Heinkenschloss and N. J. Kroeger, “A new diagonalization based method for parallel-in-time solution of linear-quadratic optimal control problems,” ESAIM: Control, Optimisation and Calculus of Variations, vol. 30, p. 62, 2024, doi: 10.1051/cocv/2024051. [Online]. Available at: http://dx.doi.org/10.1051/cocv/2024051

HeinzelreiterEtAl2024

B. Heinzelreiter and J. W. Pearson, “Diagonalization-Based Parallel-in-Time Preconditioners for Instationary Fluid Flow Control Problems,” arXiv:2405.18964v1 [math.NA], 2024 [Online]. Available at: http://arxiv.org/abs/2405.18964v1
BibTeX entry HeinzelreiterEtAl2024

@unpublished{HeinzelreiterEtAl2024, author = {Heinzelreiter, Bernhard and Pearson, John W.}, howpublished = {arXiv:2405.18964v1 [math.NA]}, title = {Diagonalization-Based Parallel-in-Time Preconditioners for Instationary Fluid Flow Control Problems}, url = {http://arxiv.org/abs/2405.18964v1}, year = {2024} }
Abstract for BibTeX entry HeinzelreiterEtAl2024

We derive a new parallel-in-time approach for solving large-scale optimization problems constrained by time-dependent partial differential equations arising from fluid dynamics. The solver involves the use of a block circulant approximation of the original matrices, enabling parallelization-in-time via the use of fast Fourier transforms, and we devise bespoke matrix approximations which may be applied within this framework. These make use of permutations, saddle-point approximations, commutator arguments, as well as inner solvers such as the Uzawa method, Chebyshev semi-iteration, and multigrid. Theoretical results underpin our strategy of applying a block circulant strategy, and numerical experiments demonstrate the effectiveness and robustness of our approach on Stokes and Oseen problems. Noteably, satisfying results for the strong and weak scaling of our methods are provided within a fully parallel architecture.
HonEtAl2024

S. Y. Hon, P. Y. Fung, and X.-lei Lin, “An optimal parallel-in-time preconditioner for parabolic optimal control problems,” arXiv:2410.22686v1 [math.NA], 2024 [Online]. Available at: http://arxiv.org/abs/2410.22686v1
BibTeX entry HonEtAl2024

@unpublished{HonEtAl2024, author = {Hon, Sean Y. and Fung, Po Yin and Lin, Xue-lei}, howpublished = {arXiv:2410.22686v1 [math.NA]}, title = {An optimal parallel-in-time preconditioner for parabolic optimal control problems}, url = {http://arxiv.org/abs/2410.22686v1}, year = {2024} }
Abstract for BibTeX entry HonEtAl2024

In this work, we propose a novel diagonalization-based preconditioner for the all-at-once linear system arising from the optimal control problem of parabolic equations. The proposed preconditioner is constructed based on an ε-circulant modification to the rotated block diagonal (RBD) preconditioning technique, which can be efficiently diagonalized by fast Fourier transforms in a parallel-in-time fashion. To our knowledge, this marks the first application of the ε-circulant modification to RBD preconditioning. Before our work, the studies of PinT preconditioning techniques for the optimal control problem are mainly focused on ε-circulant modification to Schur complement based preconditioners, which involves multiplication of forward and backward evolutionary processes and thus square the condition number. Compared with those Schur complement based preconditioning techniques in the literature, the advantage of the proposed ε-circulant modified RBD preconditioning is that it does not involve the multiplication of forward and backward evolutionary processes. When the generalized minimal residual method is deployed on the preconditioned system, we prove that when choosing ε=\mathcalO(\sqrtτ) with τbeing the temporal step-size , the convergence rate of the preconditioned GMRES solver is independent of the matrix size and the regularization parameter. Such restriction on εis more relax than the assumptions on εfrom other works related to ε-circulant based preconditioning techniques for the optimal control problem. Numerical results are provided to demonstrate the effectiveness of our proposed solvers.
Hope-CollinsEtAl2024

J. Hope-Collins, A. Hamdan, W. Bauer, L. Mitchell, and C. Cotter, “asQ: parallel-in-time finite element simulations using ParaDiag for geoscientific models and beyond,” arXiv:2409.18792v1 [math.NA], 2024 [Online]. Available at: http://arxiv.org/abs/2409.18792v1
BibTeX entry Hope-CollinsEtAl2024

@unpublished{Hope-CollinsEtAl2024, author = {Hope-Collins, Joshua and Hamdan, Abdalaziz and Bauer, Werner and Mitchell, Lawrence and Cotter, Colin}, howpublished = {arXiv:2409.18792v1 [math.NA]}, title = {asQ: parallel-in-time finite element simulations using ParaDiag for geoscientific models and beyond}, url = {http://arxiv.org/abs/2409.18792v1}, year = {2024} }
Abstract for BibTeX entry Hope-CollinsEtAl2024

Modern high performance computers are massively parallel; for many PDE applications spatial parallelism saturates long before the computer’s capability is reached. Parallel-in-time methods enable further speedup beyond spatial saturation by solving multiple timesteps simultaneously to expose additional parallelism. ParaDiag is a particular approach to parallel-in-time based on preconditioning the simultaneous timestep system with a perturbation that allows block diagonalisation via a Fourier transform in time. In this article, we introduce asQ, a new library for implementing ParaDiag parallel-in-time methods, with a focus on applications in the geosciences, especially weather and climate. asQ is built on Firedrake, a library for the automated solution of finite element models, and the PETSc library of scalable linear and nonlinear solvers. This enables asQ to build ParaDiag solvers for general finite element models and provide a range of solution strategies, making testing a wide array of problems straightforward. We use a quasi-Newton formulation that encompasses a range of ParaDiag methods, and expose building blocks for constructing more complex methods. The performance and flexibility of asQ is demonstrated on a hierarchy of linear and nonlinear atmospheric flow models. We show that ParaDiag can offer promising speedups and that asQ is a productive testbed for further developing these methods.

J. Huang, L. Ju, and Y. Xu, “A parareal exponential integrator finite element method for semilinear parabolic equations,” Numerical Methods for Partial Differential Equations, May 2024, doi: 10.1002/num.23116. [Online]. Available at: http://dx.doi.org/10.1002/num.23116

HuangEtAl2024b

Y.-Y. Huang, P. Y. Fung, S. Y. Hon, and X.-L. Lin, “An efficient preconditioner for evolutionary partial differential equations with θ-method in time discretization,” arXiv:2408.03535v1 [math.NA], 2024 [Online]. Available at: http://arxiv.org/abs/2408.03535v1
BibTeX entry HuangEtAl2024b

@unpublished{HuangEtAl2024b, author = {Huang, Yuan-Yuan and Fung, Po Yin and Hon, Sean Y. and Lin, Xue-Lei}, howpublished = {arXiv:2408.03535v1 [math.NA]}, title = {An efficient preconditioner for evolutionary partial differential equations with $θ$-method in time discretization}, url = {http://arxiv.org/abs/2408.03535v1}, year = {2024} }
Abstract for BibTeX entry HuangEtAl2024b

In this study, the θ-method is used for discretizing a class of evolutionary partial differential equations. Then, we transform the resultant all-at-once linear system and introduce a novel one-sided preconditioner, which can be fast implemented in a parallel-in-time way. By introducing an auxiliary two-sided preconditioned system, we provide theoretical insights into the relationship between the residuals of the generalized minimal residual (GMRES) method when applied to both one-sided and two-sided preconditioned systems. Moreover, we show that the condition number of the two-sided preconditioned matrix is uniformly bounded by a constant that is independent of the matrix size, which in turn implies that the convergence behavior of the GMRES method for the one-sided preconditioned system is guaranteed. Numerical experiments confirm the efficiency and robustness of the proposed preconditioning approach.
HuangEtAl2024c

Y.-Y. Huang, S. Y. Hon, L.-K. Chou, and S.-L. Lei, “Optimal preconditioners for nonsymmetric multilevel Toeplitz systems with application to solving non-local evolutionary partial differential equations,” arXiv:2409.15770v1 [math.NA], 2024 [Online]. Available at: http://arxiv.org/abs/2409.15770v1
BibTeX entry HuangEtAl2024c

@unpublished{HuangEtAl2024c, author = {Huang, Yuan-Yuan and Hon, Sean Y. and Chou, Lot-Kei and Lei, Siu-Long}, howpublished = {arXiv:2409.15770v1 [math.NA]}, title = {Optimal preconditioners for nonsymmetric multilevel Toeplitz systems with application to solving non-local evolutionary partial differential equations}, url = {http://arxiv.org/abs/2409.15770v1}, year = {2024} }
Abstract for BibTeX entry HuangEtAl2024c

Preconditioning for multilevel Toeplitz systems has long been a focal point of research in numerical linear algebra. In this work, we develop a novel preconditioning method for a class of nonsymmetric multilevel Toeplitz systems, which includes the all-at-once systems that arise from evolutionary partial differential equations. These systems have recently garnered considerable attention in the literature. To further illustrate our proposed preconditioning strategy, we specifically consider the application of solving a wide range of non-local, time-dependent partial differential equations in a parallel-in-time manner. For these equations, we propose a symmetric positive definite multilevel Tau preconditioner that is not only efficient to implement but can also be adapted as an optimal preconditioner. In this context, the proposed preconditioner is optimal in the sense that it enables mesh-independent convergence when using the preconditioned generalized minimal residual method. Numerical examples are provided to critically analyze the results and underscore the effectiveness of our preconditioning strategy.
IacobEtAl2024

C. Iacob, H. Abdulsamad, and S. Särkkä, “A Parallel-in-Time Newton’s Method for Nonlinear Model Predictive Control,” arXiv:2409.20027v2 [math.OC], 2024 [Online]. Available at: http://arxiv.org/abs/2409.20027v2
BibTeX entry IacobEtAl2024

@unpublished{IacobEtAl2024, author = {Iacob, Casian and Abdulsamad, Hany and Särkkä, Simo}, howpublished = {arXiv:2409.20027v2 [math.OC]}, title = {A Parallel-in-Time Newton's Method for Nonlinear Model Predictive Control}, url = {http://arxiv.org/abs/2409.20027v2}, year = {2024} }
Abstract for BibTeX entry IacobEtAl2024

Model predictive control (MPC) is a powerful framework for optimal control of dynamical systems. However, MPC solvers suffer from a high computational burden that restricts their application to systems with low sampling frequency. This issue is further amplified in nonlinear and constrained systems that require nesting MPC solvers within iterative procedures. In this paper, we address these issues by developing parallel-in-time algorithms for constrained nonlinear optimization problems that take advantage of massively parallel hardware to achieve logarithmic computational time scaling over the planning horizon. We develop time-parallel second-order solvers based on interior point methods and the alternating direction method of multipliers, leveraging fast convergence and lower computational cost per iteration. The parallelization is based on a reformulation of the subproblems in terms of associative operations that can be parallelized using the associative scan algorithm. We validate our approach on numerical examples of nonlinear and constrained dynamical systems.
IbrahimEtAl2024

A. Q. Ibrahim, S. Götschel, and D. Ruprecht, “Space-time parallel scaling of Parareal with a Fourier Neural Operator as coarse propagator,” arXiv:2404.02521v1 [math.NA], 2024 [Online]. Available at: http://arxiv.org/abs/2404.02521v1
BibTeX entry IbrahimEtAl2024

@unpublished{IbrahimEtAl2024, author = {Ibrahim, Abdul Qadir and Götschel, Sebastian and Ruprecht, Daniel}, howpublished = {arXiv:2404.02521v1 [math.NA]}, title = {Space-time parallel scaling of Parareal with a Fourier Neural Operator as coarse propagator}, url = {http://arxiv.org/abs/2404.02521v1}, year = {2024} }
Abstract for BibTeX entry IbrahimEtAl2024

Iterative parallel-in-time algorithms like Parareal can extend scaling beyond the saturation of purely spatial parallelization when solving initial value problems. However, they require the user to build coarse models to handle the inevitably serial transport of information in time.This is a time consuming and difficult process since there is still only limited theoretical insight into what constitutes a good and efficient coarse model. Novel approaches from machine learning to solve differential equations could provide a more generic way to find coarse level models for parallel-in-time algorithms. This paper demonstrates that a physics-informed Fourier Neural Operator (PINO) is an effective coarse model for the parallelization in time of the two-asset Black-Scholes equation using Parareal. We demonstrate that PINO-Parareal converges as fast as a bespoke numerical coarse model and that, in combination with spatial parallelization by domain decomposition, it provides better overall speedup than both purely spatial parallelization and space-time parallelizaton with a numerical coarse propagator.

S. Iqbal, H. Abdulsamad, T. Cator, U. Braga-Neto, and S. Särkkä, “Parallel-in-Time Probabilistic Solutions for Time-Dependent Nonlinear Partial Differential Equations,” in 2024 IEEE 34th International Workshop on Machine Learning for Signal Processing (MLSP), 2024, pp. 1–6, doi: 10.1109/mlsp58920.2024.10734739 [Online]. Available at: http://dx.doi.org/10.1109/MLSP58920.2024.10734739

JackamanEtAl2024

J. Jackaman and S. MacLachlan, “Space-time waveform relaxation multigrid for Navier-Stokes,” arXiv:2407.13997v1 [math.NA], 2024 [Online]. Available at: http://arxiv.org/abs/2407.13997v1
BibTeX entry JackamanEtAl2024

@unpublished{JackamanEtAl2024, author = {Jackaman, James and MacLachlan, Scott}, howpublished = {arXiv:2407.13997v1 [math.NA]}, title = {Space-time waveform relaxation multigrid for Navier-Stokes}, url = {http://arxiv.org/abs/2407.13997v1}, year = {2024} }
Abstract for BibTeX entry JackamanEtAl2024

Space-time finite-element discretizations are well-developed in many areas of science and engineering, but much work remains within the development of specialized solvers for the resulting linear and nonlinear systems. In this work, we consider the all-at-once solution of the discretized Navier-Stokes equations over a space-time domain using waveform relaxation multigrid methods. In particular, we show how to extend the efficient spatial multigrid relaxation methods from [37] to a waveform relaxation method, and demonstrate the efficiency of the resulting monolithic Newton-Krylov-multigrid solver. Numerical results demonstrate the scalability of the solver for varying discretization order and physical parameters.

N. Janssens and J. Meyers, “Parallel-in-time multiple shooting for optimal control problems governed by the Navier–Stokes equations,” Computer Physics Communications, vol. 296, p. 109019, Mar. 2024, doi: 10.1016/j.cpc.2023.109019. [Online]. Available at: http://dx.doi.org/10.1016/j.cpc.2023.109019

F. C. Joseph and G. Gurrala, “Adaptive Homotopy Based Coarse Solver for Parareal-in-Time Transient Stability Simulations,” IEEE Transactions on Power Systems, pp. 1–12, 2024, doi: 10.1109/tpwrs.2024.3424555. [Online]. Available at: http://dx.doi.org/10.1109/TPWRS.2024.3424555

KaiserEtAl2024

L. Kaiser, R. Tsai, and C. Klingenberg, “Efficient Numerical Wave Propagation Enhanced By An End-to-End Deep Learning Model,” arXiv:2402.02304v4 [math.AP], 2024 [Online]. Available at: http://arxiv.org/abs/2402.02304v4
BibTeX entry KaiserEtAl2024

@unpublished{KaiserEtAl2024, author = {Kaiser, Luis and Tsai, Richard and Klingenberg, Christian}, howpublished = {arXiv:2402.02304v4 [math.AP]}, title = {Efficient Numerical Wave Propagation Enhanced By An End-to-End Deep Learning Model}, url = {http://arxiv.org/abs/2402.02304v4}, year = {2024} }
Abstract for BibTeX entry KaiserEtAl2024

Recent advances in wave modeling use sufficiently accurate fine solver outputs to train a neural network that enhances the accuracy of a fast but inaccurate coarse solver. In this paper we build upon the work of Nguyen and Tsai (2023) and present a novel unified system that integrates a numerical solver with a deep learning component into an end-to-end framework. In the proposed setting, we investigate refinements to the network architecture and data generation algorithm. A stable and fast solver further allows the use of Parareal, a parallel-in-time algorithm to correct high-frequency wave components. Our results show that the cohesive structure improves performance without sacrificing speed, and demonstrate the importance of temporal dynamics, as well as Parareal, for accurate wave propagation.

A. Kumar, “Investigation of Second Order Taylor Series in the Coarse Operator of Parareal Algorithm for Power System Simulation,” IEEE Transactions on Circuits and Systems II: Express Briefs, pp. 1–1, 2024, doi: 10.1109/tcsii.2024.3381372. [Online]. Available at: http://dx.doi.org/10.1109/TCSII.2024.3381372

KwokEtAl2024

F. Kwok and D. N. Tognon, “A parallel in time algorithm based ParaExp for optimal control problems,” arXiv:2406.11478v1 [cs.DC], 2024 [Online]. Available at: http://arxiv.org/abs/2406.11478v1
BibTeX entry KwokEtAl2024

@unpublished{KwokEtAl2024, author = {Kwok, Felix and Tognon, Djahou N}, howpublished = {arXiv:2406.11478v1 [cs.DC]}, title = {A parallel in time algorithm based ParaExp for optimal control problems}, url = {http://arxiv.org/abs/2406.11478v1}, year = {2024} }
Abstract for BibTeX entry KwokEtAl2024

We propose a new parallel-in-time algorithm for solving optimal control problems constrained bypartial differential equations. Our approach, which is based on a deeper understanding of ParaExp,considers an overlapping time-domain decomposition in which we combine the solution of homogeneous problems using exponential propagation with the local solutions of inhomogeneous problems.The algorithm yields a linear system whose matrix-vector product can be fully performed in parallel.We then propose a preconditioner to speed up the convergence of GMRES in the special cases ofthe heat and wave equations. Numerical experiments are provided to illustrate the efficiency of ourpreconditioners.

F. Li and Y. Xu, “A Diagonalization-Based Parallel-in-Time Algorithm for Crank-Nicolson’s Discretization of the Viscoelastic Equation,” East Asian Journal on Applied Mathematics, vol. 14, no. 1, pp. 47–78, Jun. 2024, doi: 10.4208/eajam.2022-304.070323. [Online]. Available at: http://dx.doi.org/10.4208/eajam.2022-304.070323

MardalEtAl2024

K.-A. Mardal, J. Sogn, and S. Takacs, “A robust and time-parallel preconditioner for parabolic reconstruction problems using Isogeometric Analysis,” arXiv:2407.17964v1 [math.NA], 2024 [Online]. Available at: http://arxiv.org/abs/2407.17964v1
BibTeX entry MardalEtAl2024

@unpublished{MardalEtAl2024, author = {Mardal, Kent-Andre and Sogn, Jarle and Takacs, Stefan}, howpublished = {arXiv:2407.17964v1 [math.NA]}, title = {A robust and time-parallel preconditioner for parabolic reconstruction problems using Isogeometric Analysis}, url = {http://arxiv.org/abs/2407.17964v1}, year = {2024} }
Abstract for BibTeX entry MardalEtAl2024

We consider a PDE-constrained optimization problem of tracking type with parabolic state equation. The solution to the problem is characterized by the Karush-Kuhn-Tucker (KKT) system, which we formulate using a strong variational formulation of the state equation and a super weak formulation of the adjoined state equation. This allows us to propose a preconditioner that is robust both in the regularization and the diffusion parameter. In order to discretize the problem, we use Isogeometric Analysis since it allows the construction of sufficiently smooth basis functions effortlessly. To realize the preconditioner, one has to solve a problem over the whole space time cylinder that is elliptic with respect to certain non-standard norms. Using a fast diagonalization approach in time, we reformulate the problem as a collection of elliptic problems in space only. These problems are not only smaller, but our approach also allows to solve them in a time-parallel way. We show the efficiency of the preconditioner by rigorous analysis and illustrate it with numerical experiments.
MargenbergEtAl2024

N. Margenberg and P. Munch, “A Space-Time Multigrid Method for Space-Time Finite Element Discretizations of Parabolic and Hyperbolic PDEs,” arXiv:2408.04372v1 [math.NA], 2024 [Online]. Available at: http://arxiv.org/abs/2408.04372v1
BibTeX entry MargenbergEtAl2024

@unpublished{MargenbergEtAl2024, author = {Margenberg, Nils and Munch, Peter}, howpublished = {arXiv:2408.04372v1 [math.NA]}, title = {A Space-Time Multigrid Method for Space-Time Finite Element Discretizations of Parabolic and Hyperbolic PDEs}, url = {http://arxiv.org/abs/2408.04372v1}, year = {2024} }
Abstract for BibTeX entry MargenbergEtAl2024

We present a space-time multigrid method based on tensor-product space-time finite element discretizations. The method is facilitated by the matrix-free capabilities of the \ttfamily deal.II library. It addresses both high-order continuous and discontinuous variational time discretizations with spatial finite element discretizations. The effectiveness of multigrid methods in large-scale stationary problems is well established. However, their application in the space-time context poses significant challenges, mainly due to the construction of suitable smoothers. To address these challenges, we develop a space-time cell-wise additive Schwarz smoother and demonstrate its effectiveness on the heat and acoustic wave equations. The matrix-free framework of the \ttfamily deal.II library supports various multigrid strategies, including h-, p-, and hp-refinement across spatial and temporal dimensions. Extensive empirical evidence, provided through scaling and convergence tests on high-performance computing platforms, demonstrate high performance on perturbed meshes and problems with heterogeneous and discontinuous coefficients. Throughputs of over a billion degrees of freedom per second are achieved on problems with more than a trillion global degrees of freedom. The results prove that the space-time multigrid method can effectively solve complex problems in high-fidelity simulations and show great potential for use in coupled problems.

Z. Miao, B. W. null, and Y. Jiang, “Energy-Preserving Parareal-RKN Algorithms for Hamiltonian Systems,” Numerical Mathematics: Theory, Methods and Applications, vol. 17, no. 1, pp. 121–144, Jun. 2024, doi: 10.4208/nmtma.oa-2023-0081. [Online]. Available at: http://dx.doi.org/10.4208/nmtma.oa-2023-0081

Z. Miao, R.-H. Zhang, W.-W. Han, and Y.-L. Jiang, “Analysis of a fractional-step parareal algorithm for the incompressible Navier-Stokes equations,” Computers & Mathematics with Applications, vol. 161, pp. 78–89, May 2024, doi: 10.1016/j.camwa.2024.02.035. [Online]. Available at: http://dx.doi.org/10.1016/j.camwa.2024.02.035

MuralikrishnanEtAl2024

S. Muralikrishnan and R. Speck, “ParaPIF: A Parareal Approach for Parallel-in-Time Integration of Particle-in-Fourier schemes,” arXiv:2407.00485v1 [math.NA], 2024 [Online]. Available at: http://arxiv.org/abs/2407.00485v1
BibTeX entry MuralikrishnanEtAl2024

@unpublished{MuralikrishnanEtAl2024, author = {Muralikrishnan, Sriramkrishnan and Speck, Robert}, howpublished = {arXiv:2407.00485v1 [math.NA]}, title = {ParaPIF: A Parareal Approach for Parallel-in-Time Integration of Particle-in-Fourier schemes}, url = {http://arxiv.org/abs/2407.00485v1}, year = {2024} }
Abstract for BibTeX entry MuralikrishnanEtAl2024

We propose ParaPIF, a parareal based time parallelization scheme for the particle-in-Fourier (PIF) discretization of the Vlasov-Poisson system used in kinetic plasma simulations. Our coarse propagators are based on the coarsening of the numerical discretization scheme combined with, if possible, temporal coarsening rather than coarsening of particles and/or Fourier modes, which are not possible or effective for PIF schemes. Specifically, we use PIF with a coarse tolerance for nonuniform FFTs or even the standard particle-in-cell schemes as coarse propagators for the ParaPIF algorithm. We state and prove the convergence of the algorithm and verify the results numerically with Landau damping, two-stream instability, and Penning trap test cases in 3D-3V. We also implement the space-time parallelization of the PIF schemes in the open-source, performance-portable library IPPL and conduct scaling studies up to 1536 A100 GPUs on the JUWELS booster supercomputer. The space-time parallelization utilizing the ParaPIF algorithm for the time parallelization provides up to 4-6 times speedup compared to spatial parallelization alone and achieves a push rate of around 1 billion particles per second for the benchmark plasma mini-apps considered.
PamelaEtAl2024

S. J. P. Pamela et al., “Neural-Parareal: Dynamically Training Neural Operators as Coarse Solvers for Time-Parallelisation of Fusion MHD Simulations,” arXiv:2405.01355v1 [physics.plasm-ph], 2024 [Online]. Available at: http://arxiv.org/abs/2405.01355v1
BibTeX entry PamelaEtAl2024

@unpublished{PamelaEtAl2024, author = {Pamela, S. J. P. and Carey, N. and Brandstetter, J. and Akers, R. and Zanisi, L. and Buchanan, J. and Gopakumar, V. and Hoelzl, M. and Huijsmans, G. and Pentland, K. and James, T. and Antonucci, G. and the JOREK Team}, howpublished = {arXiv:2405.01355v1 [physics.plasm-ph]}, title = {Neural-Parareal: Dynamically Training Neural Operators as Coarse Solvers for Time-Parallelisation of Fusion MHD Simulations}, url = {http://arxiv.org/abs/2405.01355v1}, year = {2024} }
Abstract for BibTeX entry PamelaEtAl2024

The fusion research facility ITER is currently being assembled to demonstrate that fusion can be used for industrial energy production, while several other programmes across the world are also moving forward, such as EU-DEMO, CFETR, SPARC and STEP. The high engineering complexity of a tokamak makes it an extremely challenging device to optimise, and test-based optimisation would be too slow and too costly. Instead, digital design and optimisation must be favored, which requires strongly-coupled suites of High-Performance Computing calculations. In this context, having surrogate models to provide quick estimates with uncertainty quantification is essential to explore and optimise new design options. Furthermore, these surrogates can in turn be used to accelerate simulations in the first place. This is the case of Parareal, a time-parallelisation method that can speed-up large HPC simulations, where the coarse-solver can be replaced by a surrogate. A novel framework, Neural-Parareal, is developed to integrate the training of neural operators dynamically as more data becomes available. For a given input-parameter domain, as more simulations are being run with Parareal, the large amount of data generated by the algorithm is used to train new surrogate models to be used as coarse-solvers for future Parareal simulations, leading to progressively more accurate coarse-solvers, and thus higher speed-up. It is found that such neural network surrogates can be much more effective than traditional coarse-solver in providing a speed-up with Parareal. This study is a demonstration of the convergence of HPC and AI which simply has to become common practice in the world of digital engineering design.

B. Park, “Stochastic Power System Dynamic Simulation Using Parallel-in-Time Algorithm,” IEEE Access, vol. 12, pp. 28500–28510, 2024, doi: 10.1109/access.2024.3367358. [Online]. Available at: http://dx.doi.org/10.1109/ACCESS.2024.3367358

PeterssonEtAl2024

N. A. Petersson, S. Günther, and S. W. Chung, “A time-parallel multiple-shooting method for large-scale quantum optimal control,” arXiv:2407.13950v1 [quant-ph], 2024 [Online]. Available at: http://arxiv.org/abs/2407.13950v1
BibTeX entry PeterssonEtAl2024

@unpublished{PeterssonEtAl2024, author = {Petersson, N. Anders and Günther, Stefanie and Chung, Seung Whan}, howpublished = {arXiv:2407.13950v1 [quant-ph]}, title = {A time-parallel multiple-shooting method for large-scale quantum optimal control}, url = {http://arxiv.org/abs/2407.13950v1}, year = {2024} }
Abstract for BibTeX entry PeterssonEtAl2024

Quantum optimal control plays a crucial role in quantum computing by employing control pulses to steer quantum systems and realize logical gate transformations, essential for quantum algorithms. However, this optimization task is computationally demanding due to challenges such as the exponential growth in computational complexity with the system’s dimensionality and the deterioration of optimization convergence for multi-qubit systems. Various methods have been developed, including gradient-based and gradient-free reduced-space methods and full-space collocation methods. This paper introduces an intermediate approach based on multiple-shooting, aiming to balance solution accuracy and computational efficiency of previous approaches. Unlike conventional reduced-space methods, multiple-shooting divides the time domain into windows and introduces optimization variables for the initial state in each window. This enables parallel computation of state evolution across windows, significantly accelerating objective function and gradient evaluations. The initial state matrix in each window is only guaranteed to be unitary upon convergence of the optimization algorithm. For this reason the conventional gate trace infidelity is replaced by a generalized infidelity that is convex for non-unitary state matrices. Continuity of the state across window boundaries is enforced by equality constraints. A quadratic penalty optimization method is used to solve the constrained optimal control problem, and an efficient adjoint technique is employed to calculate the gradients in each iteration. We demonstrate the effectiveness of the proposed method through numerical experiments on quantum Fourier transform gates in systems with 2, 3, and 4 qubits. Parallel scalability and optimization performance are evaluated, highlighting the method’s potential for optimizing control pulses in multi-qubit quantum systems.

Y. Poirier, J. Salomon, A. Babarit, P. Ferrant, and G. Ducrozet, “Acceleration of a wave-structure interaction solver by the Parareal method,” Engineering Analysis with Boundary Elements, vol. 167, p. 105870, Oct. 2024, doi: 10.1016/j.enganabound.2024.105870. [Online]. Available at: http://dx.doi.org/10.1016/j.enganabound.2024.105870

SarpeEtAl2024

J. Sarpe, A. Klaedtke, and H. D. Gersem, “Periodic Adjoint Sensitivity Analysis,” arXiv:2405.19048v1 [math.NA], 2024 [Online]. Available at: http://arxiv.org/abs/2405.19048v1
BibTeX entry SarpeEtAl2024

@unpublished{SarpeEtAl2024, author = {Sarpe, Julian and Klaedtke, Andreas and Gersem, Herbert De}, howpublished = {arXiv:2405.19048v1 [math.NA]}, title = {Periodic Adjoint Sensitivity Analysis}, url = {http://arxiv.org/abs/2405.19048v1}, year = {2024} }
Abstract for BibTeX entry SarpeEtAl2024

This paper proposes the utilization of a periodic Parareal with a periodic coarse problem to efficiently perform adjoint sensitivity analysis for the steady state of time-periodic nonlinear circuits. In order to implement this method, a modified formulation for adjoint sensitivity analysis based on the transient approach is derived.
Scheiber2024

E. Scheiber, “A Convergence Theorem for the Parareal Algorithm Revisited,” arXiv:2405.06954v1 [math.NA], 2024 [Online]. Available at: http://arxiv.org/abs/2405.06954v1
BibTeX entry Scheiber2024

@unpublished{Scheiber2024, author = {Scheiber, Ernest}, howpublished = {arXiv:2405.06954v1 [math.NA]}, title = {A Convergence Theorem for the Parareal Algorithm Revisited}, url = {http://arxiv.org/abs/2405.06954v1}, year = {2024} }
Abstract for BibTeX entry Scheiber2024

The subject of the paper is to verify the convergence conditions for the parareal algorithm using Gander and Hairer’s theorem . The analysis is conducted in the case where the coarse integrator is the Euler method and the high-accuracy integrator is an explicit Runge-Kutta type method.
SchnaubeltEtAl2024

E. Schnaubelt, M. Wozniak, J. Dular, I. C. Garcia, A. Verweij, and S. Schöps, “Parallel-in-Time Integration of Transient Phenomena in No-Insulation Superconducting Coils Using Parareal,” arXiv:2404.13333v1 [cs.CE], 2024 [Online]. Available at: http://arxiv.org/abs/2404.13333v1
BibTeX entry SchnaubeltEtAl2024

@unpublished{SchnaubeltEtAl2024, author = {Schnaubelt, Erik and Wozniak, Mariusz and Dular, Julien and Garcia, Idoia Cortes and Verweij, Arjan and Schöps, Sebastian}, howpublished = {arXiv:2404.13333v1 [cs.CE]}, title = {Parallel-in-Time Integration of Transient Phenomena in No-Insulation Superconducting Coils Using Parareal}, url = {http://arxiv.org/abs/2404.13333v1}, year = {2024} }
Abstract for BibTeX entry SchnaubeltEtAl2024

High-temperature superconductors (HTS) have the potential to enable magnetic fields beyond the current limits of low-temperature superconductors in applications like accelerator magnets. However, the design of HTS-based magnets requires computationally demanding transient multi-physics simulations with highly non-linear material properties. To reduce the solution time, we propose using Parareal (PR) for parallel-in-time magneto-thermal simulation of magnets based on HTS, particularly, no-insulation coils without turn-to-turn insulation. We propose extending the classical PR method to automatically find a time partitioning using a first coarse adaptive propagator. The proposed PR method is shown to reduce the computing time when fine engineering tolerances are required despite the highly nonlinear character of the problem. The full software stack used is open-source.
SouzaEtAl2024

G. R. de Souza, S. Pezzuto, and R. Krause, “High-order parallel-in-time method for the monodomain equation in cardiac electrophysiology,” arXiv:2405.19994v1 [math.NA], 2024 [Online]. Available at: http://arxiv.org/abs/2405.19994v1
BibTeX entry SouzaEtAl2024

@unpublished{SouzaEtAl2024, author = {de Souza, Giacomo Rosilho and Pezzuto, Simone and Krause, Rolf}, howpublished = {arXiv:2405.19994v1 [math.NA]}, title = {High-order parallel-in-time method for the monodomain equation in cardiac electrophysiology}, url = {http://arxiv.org/abs/2405.19994v1}, year = {2024} }
Abstract for BibTeX entry SouzaEtAl2024

Simulation of the monodomain equation, crucial for modeling the heart’s electrical activity, faces scalability limits when traditional numerical methods only parallelize in space. To optimize the use of large multi-processor computers by distributing the computational load more effectively, time parallelization is essential. We introduce a high-order parallel-in-time method addressing the substantial computational challenges posed by the stiff, multiscale, and nonlinear nature of cardiac dynamics. Our method combines the semi-implicit and exponential spectral deferred correction methods, yielding a hybrid method that is extended to parallel-in-time employing the PFASST framework. We thoroughly evaluate the stability, accuracy, and robustness of the proposed parallel-in-time method through extensive numerical experiments, using practical ionic models such as the ten-Tusscher-Panfilov. The results underscore the method’s potential to significantly enhance real-time and high-fidelity simulations in biomedical research and clinical applications.
SterckEtAl2024

H. D. Sterck, R. D. Falgout, O. A. Krzysik, and J. B. Schroder, “Parallel-in-time solution of scalar nonlinear conservation laws,” arXiv:2401.04936v1 [math.NA], 2024 [Online]. Available at: http://arxiv.org/abs/2401.04936v1
BibTeX entry SterckEtAl2024

@unpublished{SterckEtAl2024, author = {Sterck, H. De and Falgout, R. D. and Krzysik, O. A. and Schroder, J. B.}, howpublished = {arXiv:2401.04936v1 [math.NA]}, title = {Parallel-in-time solution of scalar nonlinear conservation laws}, url = {http://arxiv.org/abs/2401.04936v1}, year = {2024} }
Abstract for BibTeX entry SterckEtAl2024

We consider the parallel-in-time solution of scalar nonlinear conservation laws in one spatial dimension. The equations are discretized in space with a conservative finite-volume method using weighted essentially non-oscillatory (WENO) reconstructions, and in time with high-order explicit Runge-Kutta methods. The solution of the global, discretized space-time problem is sought via a nonlinear iteration that uses a novel linearization strategy in cases of non-differentiable equations. Under certain choices of discretization and algorithmic parameters, the nonlinear iteration coincides with Newton’s method, although, more generally, it is a preconditioned residual correction scheme. At each nonlinear iteration, the linearized problem takes the form of a certain discretization of a linear conservation law over the space-time domain in question. An approximate parallel-in-time solution of the linearized problem is computed with a single multigrid reduction-in-time (MGRIT) iteration. The MGRIT iteration employs a novel coarse-grid operator that is a modified conservative semi-Lagrangian discretization and generalizes those we have developed previously for non-conservative scalar linear hyperbolic problems. Numerical tests are performed for the inviscid Burgers and Buckley–Leverett equations. For many test problems, the solver converges in just a handful of iterations with convergence rate independent of mesh resolution, including problems with (interacting) shocks and rarefactions.
SterckEtAl2024b

H. D. Sterck, R. D. Falgout, O. A. Krzysik, and J. B. Schroder, “Parallel-in-time solution of hyperbolic PDE systems via characteristic-variable block preconditioning,” arXiv:2407.03873v1 [math.NA], 2024 [Online]. Available at: http://arxiv.org/abs/2407.03873v1
BibTeX entry SterckEtAl2024b

@unpublished{SterckEtAl2024b, author = {Sterck, H. De and Falgout, R. D. and Krzysik, O. A. and Schroder, J. B.}, howpublished = {arXiv:2407.03873v1 [math.NA]}, title = {Parallel-in-time solution of hyperbolic PDE systems via characteristic-variable block preconditioning}, url = {http://arxiv.org/abs/2407.03873v1}, year = {2024} }
Abstract for BibTeX entry SterckEtAl2024b

We consider the parallel-in-time solution of hyperbolic partial differential equation (PDE) systems in one spatial dimension, both linear and nonlinear. In the nonlinear setting, the discretized equations are solved with a preconditioned residual iteration based on a global linearization. The linear(ized) equation systems are approximately solved parallel-in-time using a block preconditioner applied in the characteristic variables of the underlying linear(ized) hyperbolic PDE. This change of variables is motivated by the observation that inter-variable coupling for characteristic variables is weak relative to intra-variable coupling, at least locally where spatio-temporal variations in the eigenvectors of the associated flux Jacobian are sufficiently small. For an \ell-dimensional system of PDEs, applying the preconditioner consists of solving a sequence of \ell scalar linear(ized)-advection-like problems, each being associated with a different characteristic wave-speed in the underlying linear(ized) PDE. We approximately solve these linear advection problems using multigrid reduction-in-time (MGRIT); however, any other suitable parallel-in-time method could be used. Numerical examples are shown for the (linear) acoustics equations in heterogeneous media, and for the (nonlinear) shallow water equations and Euler equations of gas dynamics with shocks and rarefactions.

S.-L. Wu and T. Zhou, “Convergence Analysis of the Parareal Algorithm with Nonuniform Fine Time Grid,” SIAM Journal on Numerical Analysis, vol. 62, no. 5, pp. 2308–2330, Oct. 2024, doi: 10.1137/23m1592481. [Online]. Available at: http://dx.doi.org/10.1137/23M1592481

YamaleevEtAl2024

N. K. Yamaleev and S. Paudel, “A New Parallel-in-time Direct Inverse Method for Nonlinear Differential Equations,” arXiv:2406.00878v1 [math.NA], 2024 [Online]. Available at: http://arxiv.org/abs/2406.00878v1
BibTeX entry YamaleevEtAl2024

@unpublished{YamaleevEtAl2024, author = {Yamaleev, Nail K. and Paudel, Subhash}, howpublished = {arXiv:2406.00878v1 [math.NA]}, title = {A New Parallel-in-time Direct Inverse Method for Nonlinear Differential Equations}, url = {http://arxiv.org/abs/2406.00878v1}, year = {2024} }
Abstract for BibTeX entry YamaleevEtAl2024

We present a new approach to parallelization of the first-order backward difference discretization (BDF1) of the time derivative in partial differential equations, such as the nonlinear heat and viscous Burgers equations. The time derivative term is discretized by using the method of lines based on the implicit BDF1 scheme, while the inviscid and viscous terms are approximated by conventional 2nd-order 3-point central discretizations of the 1st- and 2nd-order derivatives in each spatial direction. The global system of nonlinear discrete equations in the space-time domain is solved by the Newton method for all time levels simultaneously. For the BDF1 discretization, this all-at-once system at each Newton iteration is block bidiagonal, which can be inverted directly in a blockwise manner, thus leading to a set of fully decoupled equations associated with each time level. This allows for an efficient parallel-in-time implementation of the implicit BDF1 discretization for nonlinear differential equations. The proposed parallel-in-time method preserves a quadratic rate of convergence of the Newton method of the sequential BDF1 scheme, so that the computational cost of solving each block matrix in parallel is nearly identical to that of the sequential counterpart at each time step. Numerical results show that the new parallel-in-time BDF1 scheme provides the speedup of up to 28 on 32 computing cores for the 2-D nonlinear partial differential equations with both smooth and discontinuous solutions.
YangEtAl2024

Z. Yang, Y. Wang, and W. T. Leung, “Parallel in time partially explicit splitting scheme for high contrast multiscale problems,” arXiv:2411.09244v1 [math.NA], 2024 [Online]. Available at: http://arxiv.org/abs/2411.09244v1
BibTeX entry YangEtAl2024

@unpublished{YangEtAl2024, author = {Yang, Zhengya and Wang, Yating and Leung, Wing Tat}, howpublished = {arXiv:2411.09244v1 [math.NA]}, title = {Parallel in time partially explicit splitting scheme for high contrast multiscale problems}, url = {http://arxiv.org/abs/2411.09244v1}, year = {2024} }
Abstract for BibTeX entry YangEtAl2024

Solving multiscale diffusion problems is often computationally expensive due to the spatial and temporal discretization challenges arising from high-contrast coefficients. To address this issue, a partially explicit temporal splitting scheme is proposed. By appropriately constructing multiscale spaces, the spatial multiscale property is effectively managed, and it has been demonstrated that the temporal step size is independent of the contrast. To enhance simulation speed, we propose a parallel algorithm for the multiscale flow problem that leverages the partially explicit temporal splitting scheme. The idea is first to evolve the partially explicit system using a coarse time step size, then correct the solution on each coarse time interval with a fine propagator, for which we consider both the sequential solver and all-at-once solver. This procedure is then performed iteratively till convergence. We analyze the stability and convergence of the proposed algorithm. The numerical experiments demonstrate that the proposed algorithm achieves high numerical accuracy for high-contrast problems and converges in a relatively small number of iterations. The number of iterations stays stable as the number of coarse intervals increases, thus significantly improving computational efficiency through parallel processing.

R. Yoda, M. Bolten, K. Nakajima, and A. Fujii, “Coarse-grid operator optimization in multigrid reduction in time for time-dependent Stokes and Oseen problems,” Japan Journal of Industrial and Applied Mathematics, Apr. 2024, doi: 10.1007/s13160-024-00652-8. [Online]. Available at: http://dx.doi.org/10.1007/s13160-024-00652-8

ZhangEtAl2024

L. Zhang and Q. Zhang, “Convergence analysis of the parareal algorithms for stochastic Maxwell equations driven by additive noise,” arXiv:2407.10907v1 [math.NA], 2024 [Online]. Available at: http://arxiv.org/abs/2407.10907v1
BibTeX entry ZhangEtAl2024

@unpublished{ZhangEtAl2024, author = {Zhang, Liying and Zhang, Qi}, howpublished = {arXiv:2407.10907v1 [math.NA]}, title = {Convergence analysis of the parareal algorithms for stochastic Maxwell equations driven by additive noise}, url = {http://arxiv.org/abs/2407.10907v1}, year = {2024} }
Abstract for BibTeX entry ZhangEtAl2024

In this paper, we investigate the strong convergence analysis of parareal algorithms for stochastic Maxwell equations with the damping term driven by additive noise. The proposed parareal algorithms proceed as two-level temporal parallelizable integrators with the stochastic exponential integrator as the coarse propagator and both the exact solution integrator and the stochastic exponential integrator as the fine propagator. It is proved that the convergence order of the proposed algorithms linearly depends on the iteration number. Numerical experiments are performed to illustrate the convergence order of the algorithms for different choices of the iteration number, the damping coefficient and the scale of noise.
ZhaoEtAl2024

Y.-L. Zhao, X.-M. Gu, and C. W. Oosterlee, “A parallel preconditioner for the all-at-once linear system from evolutionary PDEs with Crank-Nicolson discretization,” arXiv:2401.16113v1 [math.NA], 2024 [Online]. Available at: http://arxiv.org/abs/2401.16113v1
BibTeX entry ZhaoEtAl2024

@unpublished{ZhaoEtAl2024, author = {Zhao, Yong-Liang and Gu, Xian-Ming and Oosterlee, Cornelis W.}, howpublished = {arXiv:2401.16113v1 [math.NA]}, title = {A parallel preconditioner for the all-at-once linear system from evolutionary PDEs with Crank-Nicolson discretization}, url = {http://arxiv.org/abs/2401.16113v1}, year = {2024} }
Abstract for BibTeX entry ZhaoEtAl2024

The Crank-Nicolson (CN) method is a well-known time integrator for evolutionary partial differential equations (PDEs) arising in many real-world applications. Since the solution at any time depends on the solution at previous time steps, the CN method will be inherently difficult to parallelize. In this paper, we consider a parallel method for the solution of evolutionary PDEs with the CN scheme. Using an all-at-once approach, we can solve for all time steps simultaneously using a parallelizable over time preconditioner within a standard iterative method. Due to the diagonalization of the proposed preconditioner, we can prove that most eigenvalues of preconditioned matrices are equal to 1 and the others lie in the set: \left{z∈\mathbbC: 1/(1 + α) < |z| < 1/(1 - α) \rm and \Ree(z) > 0\right}, where 0 < α< 1 is a free parameter. Meanwhile, the efficient implementation of this proposed preconditioner is described and a mesh-independent convergence rate of the preconditioned GMRES method is derived under certain conditions. Finally, we will verify our theoretical findings via numerical experiments on financial option pricing partial differential equations.

M. Zhen, X. Liu, X. Ding, and J. Cai, “High-order space–time parallel computing of the Navier–Stokes equations,” Computer Methods in Applied Mechanics and Engineering, vol. 423, p. 116880, Apr. 2024, doi: 10.1016/j.cma.2024.116880. [Online]. Available at: http://dx.doi.org/10.1016/j.cma.2024.116880

M. Zhen, X. Ding, K. Qu, J. Cai, and S. Pan, “Enhancing the Convergence of the Multigrid-Reduction-in-Time Method for the Euler and Navier–Stokes Equations,” Journal of Scientific Computing, vol. 100, no. 2, Jun. 2024, doi: 10.1007/s10915-024-02596-0. [Online]. Available at: http://dx.doi.org/10.1007/s10915-024-02596-0

BaumannEtAl2024

T. Baumann, S. Götschel, T. Lunet, D. Ruprecht, and R. Speck, “Adaptive time step selection for spectral deferred correction,” Numerical Algorithms, Oct. 2024, doi: 10.1007/s11075-024-01964-z. [Online]. Available at: https://doi.org/10.1007/s11075-024-01964-z
BibTeX entry BaumannEtAl2024

@article{BaumannEtAl2024, title = {Adaptive time step selection for spectral deferred correction}, issn = {1572-9265}, url = {https://doi.org/10.1007/s11075-024-01964-z}, doi = {10.1007/s11075-024-01964-z}, journal = {Numerical Algorithms}, author = {Baumann, Thomas and G{\"o}tschel, Sebastian and Lunet, Thibaut and Ruprecht, Daniel and Speck, Robert}, month = oct, year = {2024} }
Abstract for BibTeX entry BaumannEtAl2024

Spectral Deferred Correction (SDC) is an iterative method for the numerical solution of ordinary differential equations. It works by refining the numerical solution for an initial value problem by approximately solving differential equations for the error, and can be interpreted as a preconditioned fixed-point iteration for solving the fully implicit collocation problem. We adopt techniques from embedded Runge-Kutta Methods (RKM) to SDC in order to provide a mechanism for adaptive time step size selection and thus increase computational efficiency of SDC. We propose two SDC-specific estimates of the local error that are generic and do not rely on problem specific quantities. We demonstrate a gain in efficiency over standard SDC with fixed step size and compare efficiency favorably against state-of-the-art adaptive RKM.

T. Baumann, S. Götschel, T. Lunet, D. Ruprecht, and R. Speck, “Resilience Against Soft Faults through Adaptivity in Spectral Deferred Correction.” 2024 [Online]. Available at: https://arxiv.org/abs/2412.00529

top

2023

A. Barman and A. Sharma, “A Space-Time framework for compressible flow simulations using Finite Volume Method,” in AIAA AVIATION 2023 Forum, 2023, doi: 10.2514/6.2023-3431 [Online]. Available at: https://doi.org/10.2514/6.2023-3431

M. Bolten, S. Friedhoff, and J. Hahne, “Task graph-based performance analysis of parallel-in-time methods,” Parallel Computing, vol. 118, p. 103050, Nov. 2023, doi: 10.1016/j.parco.2023.103050. [Online]. Available at: https://doi.org/10.1016/j.parco.2023.103050

BoschEtAl2023

N. Bosch, A. Corenflos, F. Yaghoobi, F. Tronarp, P. Hennig, and S. Särkkä, “Parallel-in-Time Probabilistic Numerical ODE Solvers,” arXiv:2310.01145v1 [math.NA], 2023 [Online]. Available at: http://arxiv.org/abs/2310.01145v1
BibTeX entry BoschEtAl2023

@unpublished{BoschEtAl2023, author = {Bosch, Nathanael and Corenflos, Adrien and Yaghoobi, Fatemeh and Tronarp, Filip and Hennig, Philipp and Särkkä, Simo}, howpublished = {arXiv:2310.01145v1 [math.NA]}, title = {Parallel-in-Time Probabilistic Numerical ODE Solvers}, url = {http://arxiv.org/abs/2310.01145v1}, year = {2023} }
Abstract for BibTeX entry BoschEtAl2023

Probabilistic numerical solvers for ordinary differential equations (ODEs) treat the numerical simulation of dynamical systems as problems of Bayesian state estimation. Aside from producing posterior distributions over ODE solutions and thereby quantifying the numerical approximation error of the method itself, one less-often noted advantage of this formalism is the algorithmic flexibility gained by formulating numerical simulation in the framework of Bayesian filtering and smoothing. In this paper, we leverage this flexibility and build on the time-parallel formulation of iterated extended Kalman smoothers to formulate a parallel-in-time probabilistic numerical ODE solver. Instead of simulating the dynamical system sequentially in time, as done by current probabilistic solvers, the proposed method processes all time steps in parallel and thereby reduces the span cost from linear to logarithmic in the number of time steps. We demonstrate the effectiveness of our approach on a variety of ODEs and compare it to a range of both classic and probabilistic numerical ODE solvers.
BossuytEtAl2023

I. Bossuyt, S. Vandewalle, and G. Samaey, “Monte-Carlo/Moments micro-macro Parareal method for unimodal and bimodal scalar McKean-Vlasov SDEs,” arXiv:2310.11365v1 [math.NA], 2023 [Online]. Available at: http://arxiv.org/abs/2310.11365v1
BibTeX entry BossuytEtAl2023

@unpublished{BossuytEtAl2023, author = {Bossuyt, Ignace and Vandewalle, Stefan and Samaey, Giovanni}, howpublished = {arXiv:2310.11365v1 [math.NA]}, title = {Monte-Carlo/Moments micro-macro Parareal method for unimodal and bimodal scalar McKean-Vlasov SDEs}, url = {http://arxiv.org/abs/2310.11365v1}, year = {2023} }
Abstract for BibTeX entry BossuytEtAl2023

We propose a micro-macro parallel-in-time Parareal method for scalar McKean-Vlasov stochastic differential equations (SDEs). In the algorithm, the fine Parareal propagator is a Monte Carlo simulation of an ensemble of particles, while an approximate ordinary differential equation (ODE) description of the mean and the variance of the particle distribution is used as a coarse Parareal propagator to achieve speedup. We analyse the convergence behaviour of our method for a linear problem and provide numerical experiments indicating the parallel weak scaling of the algorithm on a set of examples. We show that convergence typically takes place in a low number of iterations, depending on the quality of the ODE predictor. For bimodal SDEs, we avoid quality deterioration of the coarse predictor (compared to unimodal SDEs) through the usage of multiple ODEs, each describing the mean and variance of the particle distribution in locally unimodal regions of the phase space. The benefit of the proposed algorithm can be viewed through two lenses: (i) through the parallel-in-time lens, speedup is obtained through the use of a very cheap coarse integrator (an ODE moment model), and (ii) through the moment models lens, accuracy is iteratively gained through the use of parallel machinery as a corrector. In contrast to the isolated use of a moment model, the proposed method (iteratively) converges to the true distribution generated by the SDE.
BouillonEtAl2023

A. Bouillon, G. Samaey, and K. Meerbergen, “On generalized preconditioners for time-parallel parabolic optimal control,” arXiv:2302.06406v1 [math.NA], 2023 [Online]. Available at: http://arxiv.org/abs/2302.06406v1
BibTeX entry BouillonEtAl2023

@unpublished{BouillonEtAl2023, author = {Bouillon, Arne and Samaey, Giovanni and Meerbergen, Karl}, howpublished = {arXiv:2302.06406v1 [math.NA]}, title = {On generalized preconditioners for time-parallel parabolic optimal control}, url = {http://arxiv.org/abs/2302.06406v1}, year = {2023} }
Abstract for BibTeX entry BouillonEtAl2023

The ParaDiag family of algorithms solves differential equations by using preconditioners that can be inverted in parallel through diagonalization. In the context of optimal control of linear parabolic PDEs, the state-of-the-art ParaDiag method is limited to solving self-adjoint problems with a tracking objective. We propose three improvements to the ParaDiag method: the use of alpha-circulant matrices to construct an alternative preconditioner, a generalization of the algorithm for solving non-self-adjoint equations, and the formulation of an algorithm for terminal-cost objectives. We present novel analytic results about the eigenvalues of the preconditioned systems for all discussed ParaDiag algorithms in the case of self-adjoint equations, which proves the favorable properties the alpha-circulant preconditioner. We use these results to perform a theoretical parallel-scaling analysis of ParaDiag for self-adjoint problems. Numerical tests confirm our findings and suggest that the self-adjoint behavior, which is backed by theory, generalizes to the non-self-adjoint case. We provide a sequential, open-source reference solver in Matlab for all discussed algorithms.
BouillonEtAl2023b

A. Bouillon, G. Samaey, and K. Meerbergen, “Diagonalization-based preconditioners and generalized convergence bounds for ParaOpt,” arXiv:2304.09235v1 [math.NA], 2023 [Online]. Available at: http://arxiv.org/abs/2304.09235v1
BibTeX entry BouillonEtAl2023b

@unpublished{BouillonEtAl2023b, author = {Bouillon, Arne and Samaey, Giovanni and Meerbergen, Karl}, howpublished = {arXiv:2304.09235v1 [math.NA]}, title = {Diagonalization-based preconditioners and generalized convergence bounds for ParaOpt}, url = {http://arxiv.org/abs/2304.09235v1}, year = {2023} }
Abstract for BibTeX entry BouillonEtAl2023b

The ParaOpt algorithm was recently introduced as a time-parallel solver for optimal-control problems with a terminal-cost objective, and convergence results have been presented for the linear diffusive case with implicit-Euler time integrators. We reformulate ParaOpt for tracking problems and provide generalized convergence analyses for both objectives. We focus on linear diffusive equations and prove convergence bounds that are generic in the time integrators used. For large problem dimensions, ParaOpt’s performance depends crucially on having a good preconditioner to solve the arising linear systems. For the case where ParaOpt’s cheap, coarse-grained propagator is linear, we introduce diagonalization-based preconditioners, inspired by recent advances in the ParaDiag family of methods. These preconditioners not only lead to a weakly-scalable ParaOpt version, but are themselves invertible in parallel, making maximal use of available concurrency. They have proven convergence properties in the linear diffusive case that are generic in the time discretization used, similarly to our ParaOpt results. Numerical results confirm that the iteration count of the iterative solvers used for ParaOpt’s linear systems becomes constant in the limit of an increasing processor count. The paper is accompanied by a sequential MATLAB implementation.

L. D’Amore and R. Cacciapuoti, “Space-Time Decomposition of Kalman Filter,” Numerical Mathematics: Theory, Methods and Applications, vol. 0, no. 0, pp. 0–0, Sep. 2023, doi: 10.4208/nmtma.oa-2022-0203. [Online]. Available at: https://doi.org/10.4208/nmtma.oa-2022-0203

R. Cacciapuoti and L. D’Amore, “Scalability analysis of a two level domain decomposition approach in space and time solving data assimilation models,” Concurrency and Computation: Practice and Experience, Nov. 2023, doi: 10.1002/cpe.7937. [Online]. Available at: https://doi.org/10.1002/cpe.7937

CaldasEtAl2023

J. G. Caldas Steinstraesser, P. da Silva Peixoto, and M. Schreiber, “Parallel-in-time integration of the shallow water equations on the rotating sphere using Parareal and MGRIT,” arXiv:2306.09497v1 [math.NA], 2023 [Online]. Available at: https://arxiv.org/abs/2306.09497v1
BibTeX entry CaldasEtAl2023

@unpublished{CaldasEtAl2023, author = {Caldas Steinstraesser, Jo\~{a}o Guilherme and da Silva Peixoto, Pedro and Schreiber, Martin}, howpublished = {arXiv:2306.09497v1 [math.NA]}, title = {Parallel-in-time integration of the shallow water equations on the rotating sphere using Parareal and MGRIT}, url = {https://arxiv.org/abs/2306.09497v1}, year = {2023} }
Abstract for BibTeX entry CaldasEtAl2023

Despite the growing interest in parallel-in-time methods as an approach to accelerate numerical simulations in atmospheric modelling, improving their stability and convergence remains a substantial challenge for their application to operational models. In this work, we study the temporal parallelization of the shallow water equations on the rotating sphere combined with time-stepping schemes commonly used in atmospheric modelling due to their stability properties, namely an Eulerian implicit-explicit (IMEX) method and a semi-Lagrangian semi-implicit method (SL-SI-SETTLS). The main goal is to investigate the performance of parallel-in-time methods, namely Parareal and Multigrid Reduction in Time (MGRIT), when these well-established schemes are used on the coarse discretization levels and provide insights on how they can be improved for better performance. We begin by performing an analytical stability study of Parareal and MGRIT applied to a linearized ordinary differential equation depending on the choice of coarse scheme. Next, we perform numerical simulations of two standard tests to evaluate the stability, convergence and speedup provided by the parallel-in-time methods compared to a fine reference solution computed serially. We also conduct a detailed investigation on the influence of artificial viscosity and hyperviscosity approaches, applied on the coarse discretization levels, on the performance of the temporal parallelization. Both the analytical stability study and the numerical simulations indicate a poorer stability behaviour when SL-SI-SETTLS is used on the coarse levels, compared to the IMEX scheme. With the IMEX scheme, a better trade-off between convergence, stability and speedup compared to serial simulations can be obtained under proper parameters and artificial viscosity choices, opening the perspective of the potential competitiveness for realistic models.

B. Carrel, M. J. Gander, and B. Vandereycken, “Low-rank Parareal: a low-rank parallel-in-time integrator,” BIT Numerical Mathematics, vol. 63, no. 1, Feb. 2023, doi: 10.1007/s10543-023-00953-3. [Online]. Available at: https://doi.org/10.1007%2Fs10543-023-00953-3

ChenEtAl2023

Z. Chen and Y. Liu, “Efficient and Parallel Solution of High-order Continuous Time Galerkin for Dissipative and Wave Propagation Problems,” arXiv:2303.05008v1 [math.NA], 2023 [Online]. Available at: http://arxiv.org/abs/2303.05008v1
BibTeX entry ChenEtAl2023

@unpublished{ChenEtAl2023, author = {Chen, Zhiming and Liu, Yong}, howpublished = {arXiv:2303.05008v1 [math.NA]}, title = {Efficient and Parallel Solution of High-order Continuous Time Galerkin for Dissipative and Wave Propagation Problems}, url = {http://arxiv.org/abs/2303.05008v1}, year = {2023} }
Abstract for BibTeX entry ChenEtAl2023

We propose efficient and parallel algorithms for the implementation of the high-order continuous time Galerkin method for dissipative and wave propagation problems. By using Legendre polynomials as shape functions, we obtain a special structure of the stiffness matrix which allows us to extend the diagonal Padé approximation to solve ordinary differential equations with source terms. The unconditional stability, hp error estimates, and hp superconvergence at the nodes of the continuous time Galerkin method are proved. Numerical examples confirm our theoretical results.

T. Cheng, H. Yang, J. Huang, and C. Yang, “Nonlinear parallel-in-time simulations of multiphase flow in porous media,” Journal of Computational Physics, p. 112515, Sep. 2023, doi: 10.1016/j.jcp.2023.112515. [Online]. Available at: https://doi.org/10.1016/j.jcp.2023.112515

Cyr2023

E. C. Cyr, “A 2-Level Domain Decomposition Preconditioner for KKT Systems with Heat-Equation Constraints,” arXiv:2305.04421v1 [math.NA], 2023 [Online]. Available at: http://arxiv.org/abs/2305.04421v1
BibTeX entry Cyr2023

@unpublished{Cyr2023, author = {Cyr, Eric C.}, howpublished = {arXiv:2305.04421v1 [math.NA]}, title = {A 2-Level Domain Decomposition Preconditioner for KKT Systems with Heat-Equation Constraints}, url = {http://arxiv.org/abs/2305.04421v1}, year = {2023} }
Abstract for BibTeX entry Cyr2023

Solving optimization problems with transient PDE-constraints is computationally costly due to the number of nonlinear iterations and the cost of solving large-scale KKT matrices. These matrices scale with the size of the spatial discretization times the number of time steps. We propose a new two level domain decomposition preconditioner to solve these linear systems when constrained by the heat equation. Our approach leverages the observation that the Schur-complement is elliptic in time, and thus amenable to classical domain decomposition methods. Further, the application of the preconditioner uses existing time integration routines to facilitate implementation and maximize software reuse. The performance of the preconditioner is examined in an empirical study demonstrating the approach is scalable with respect to the number of time steps and subdomains.

C. Dajana, C. Eduardo, and V. Carmine, “Non-stationary wave relaxation methods for general linear systems of Volterra equations: convergence and parallel GPU implementation,” Numerical Algorithms, Jun. 2023, doi: 10.1007/s11075-023-01567-0. [Online]. Available at: https://doi.org/10.1007/s11075-023-01567-0

DanieliEtAl2023

F. Danieli, B. S. Southworth, and J. B. Schroder, “Space-Time Block Preconditioning for Incompressible Resistive Magnetohydrodynamics,” arXiv:2309.00768v1 [math.NA], 2023 [Online]. Available at: http://arxiv.org/abs/2309.00768v1
BibTeX entry DanieliEtAl2023

@unpublished{DanieliEtAl2023, author = {Danieli, Federico and Southworth, Ben S. and Schroder, Jacob B.}, howpublished = {arXiv:2309.00768v1 [math.NA]}, title = {Space-Time Block Preconditioning for Incompressible Resistive Magnetohydrodynamics}, url = {http://arxiv.org/abs/2309.00768v1}, year = {2023} }
Abstract for BibTeX entry DanieliEtAl2023

This work develops a novel all-at-once space-time preconditioning approach for resistive magnetohydrodynamics (MHD), with a focus on model problems targeting fusion reactor design. We consider parallel-in-time due to the long time domains required to capture the physics of interest, as well as the complexity of the underlying system and thereby computational cost of long-time integration. To ameliorate this cost by using many processors, we thus develop a novel approach to solving the whole space-time system that is parallelizable in both space and time. We develop a space-time block preconditioning for resistive MHD, following the space-time block preconditioning concept first introduced by Danieli et al. in 2022 for incompressible flow, where an effective preconditioner for classic sequential time-stepping is extended to the space-time setting. The starting point for our derivation is the continuous Schur complement preconditioner by Cyr et al. in 2021, which we proceed to generalise in order to produce, to our knowledge, the first space-time block preconditioning approach for the challenging equations governing incompressible resistive MHD. The numerical results are promising for the model problems of island coalescence and tearing mode, with the overhead computational cost associated with space-time preconditioning versus sequential time-stepping being modest and primarily in the range of 2x-5x, which is low for parallel-in-time schemes in general. Additionally, the scaling results for inner (linear) and outer (nonlinear) iterations are flat in the case of fixed time-step size and only grow very slowly in the case of time-step refinement.
Erlangga2023

Y. A. Erlangga, “Parallel-in-time Multilevel Krylov Methods: A Prototype,” arXiv:2401.00228v1 [math.NA], 2023 [Online]. Available at: http://arxiv.org/abs/2401.00228v1
BibTeX entry Erlangga2023

@unpublished{Erlangga2023, author = {Erlangga, Yogi A.}, howpublished = {arXiv:2401.00228v1 [math.NA]}, title = {Parallel-in-time Multilevel Krylov Methods: A Prototype}, url = {http://arxiv.org/abs/2401.00228v1}, year = {2023} }
Abstract for BibTeX entry Erlangga2023

This paper presents a parallel-in-time multilevel iterative method for solving differential algebraic equation, arising from a discretization of linear time-dependent partial differential equation. The core of the method is the multilevel Krylov method, introduced by Erlangga and Nabben \it [SIAM J. Sci. Comput., 30(2008), pp. 1572–1595]. In the method, special time restriction and interpolation operators are proposed to coarsen the time grid and to map functions between fine and coarse time grids. The resulting Galerkin coarse-grid system can be interpreted as time integration of an equivalent differential algebraic equation associated with a larger time step and a modified θ-scheme. A perturbed coarse time-grid matrix is used on the coarsest level to decouple the coarsest-level system, allowing full parallelization of the method. Within this framework, spatial coarsening can be included in a natural way, reducing further the size of the coarsest grid problem to solve. Numerical results are presented for the 1- and 2-dimensional heat equation using \it simulated parallel implementation, suggesting the potential computational speed-up of up to 9 relative to the single-processor implementation and the speed-up of about 3 compared to the sequential θ-scheme.

L. Fang, S. Vandewalle, and J. Meyers, “An SQP-based multiple shooting algorithm for large-scale PDE-constrained optimal control problems,” Journal of Computational Physics, vol. 477, p. 111927, Mar. 2023, doi: 10.1016/j.jcp.2023.111927. [Online]. Available at: https://doi.org/10.1016/j.jcp.2023.111927

FangEtAl2023b

R. Fang and R. Tsai, “Stabilization of parareal algorithms for long time computation of a class of highly oscillatory Hamiltonian flows using data,” arXiv:2309.01225v1 [math.NA], 2023 [Online]. Available at: http://arxiv.org/abs/2309.01225v1
BibTeX entry FangEtAl2023b

@unpublished{FangEtAl2023b, author = {Fang, Rui and Tsai, Richard}, howpublished = {arXiv:2309.01225v1 [math.NA]}, title = {Stabilization of parareal algorithms for long time computation of a class of highly oscillatory Hamiltonian flows using data}, url = {http://arxiv.org/abs/2309.01225v1}, year = {2023} }
Abstract for BibTeX entry FangEtAl2023b

Applying parallel-in-time algorithms to multiscale Hamiltonian systems to obtain stable long time simulations is very challenging. In this paper, we present novel data-driven methods aimed at improving the standard parareal algorithm developed by Lion, Maday, and Turinici in 2001, for multiscale Hamiltonian systems. The first method involves constructing a correction operator to improve a given inaccurate coarse solver through solving a Procrustes problem using data collected online along parareal trajectories. The second method involves constructing an efficient, high-fidelity solver by a neural network trained with offline generated data. For the second method, we address the issues of effective data generation and proper loss function design based on the Hamiltonian function. We show proof-of-concept by applying the proposed methods to a Fermi-Pasta-Ulum (FPU) problem. The numerical results demonstrate that the Procrustes parareal method is able to produce solutions that are more stable in energy compared to the standard parareal. The neural network solver can achieve comparable or better runtime performance compared to numerical solvers of similar accuracy. When combined with the standard parareal algorithm, the improved neural network solutions are slightly more stable in energy than the improved numerical coarse solutions.

S. Frei and A. Heinlein, “Towards parallel time-stepping for the numerical simulation of atherosclerotic plaque growth,” Journal of Computational Physics, vol. 491, p. 112347, Oct. 2023, doi: 10.1016/j.jcp.2023.112347. [Online]. Available at: https://doi.org/10.1016%2Fj.jcp.2023.112347

GanderEtAl2023

M. J. Gander and D. Palitta, “A new ParaDiag time-parallel time integration method,” arXiv:2304.12597v1 [math.NA], 2023 [Online]. Available at: http://arxiv.org/abs/2304.12597v1
BibTeX entry GanderEtAl2023

@unpublished{GanderEtAl2023, author = {Gander, Martin J. and Palitta, Davide}, howpublished = {arXiv:2304.12597v1 [math.NA]}, title = {A new ParaDiag time-parallel time integration method}, url = {http://arxiv.org/abs/2304.12597v1}, year = {2023} }
Abstract for BibTeX entry GanderEtAl2023

Time-parallel time integration has received a lot of attention in the high performance computing community over the past two decades. Indeed, it has been shown that parallel-in-time techniques have the potential to remedy one of the main computational drawbacks of parallel-in-space solvers. In particular, it is well-known that for large-scale evolution problems space parallelization saturates long before all processing cores are effectively used on today’s large scale parallel computers. Among the many approaches for time-parallel time integration, ParaDiag schemes have proved themselves to be a very effective approach. In this framework, the time stepping matrix or an approximation thereof is diagonalized by Fourier techniques, so that computations taking place at different time steps can be indeed carried out in parallel. We propose here a new ParaDiag algorithm combining the Sherman-Morrison-Woodbury formula and Krylov techniques. A panel of diverse numerical examples illustrates the potential of our new solver. In particular, we show that it performs very well compared to different ParaDiag algorithms recently proposed in the literature.
GanderEtAl2023b

M. J. Gander, T. Lunet, D. Ruprecht, and R. Speck, “A Unified Analysis Framework for Iterative Parallel-in-Time Algorithms,” SIAM Journal on Scientific Computing, vol. 45, no. 5, pp. A2275–A2303, 2023, doi: 10.1137/22M1487163. [Online]. Available at: https://doi.org/10.1137/22M1487163
BibTeX entry GanderEtAl2023b

@article{GanderEtAl2023b, author = {Gander, Martin J. and Lunet, Thibaut and Ruprecht, Daniel and Speck, Robert}, doi = {10.1137/22M1487163}, journal = {SIAM Journal on Scientific Computing}, number = {5}, pages = {A2275-A2303}, title = {A Unified Analysis Framework for Iterative Parallel-in-Time Algorithms}, url = {https://doi.org/10.1137/22M1487163}, volume = {45}, year = {2023} }
Abstract for BibTeX entry GanderEtAl2023b

Abstract. Parallel-in-time integration has been the focus of intensive research efforts over the past two decades due to the advent of massively parallel computer architectures and the scaling limits of purely spatial parallelization. Various iterative parallel-in-time algorithms have been proposed, like Parareal, PFASST, MGRIT, and Space-Time Multi-Grid (STMG). These methods have been described using different notation, and the convergence estimates that are available are difficult to compare. We describe Parareal, PFASST, MGRIT, and STMG for the Dahlquist model problem using a common notation and give precise convergence estimates using generating functions. This allows us, for the first time, to directly compare their convergence. We prove that all four methods eventually converge superlinearly, and we also compare them numerically. The generating function framework provides further opportunities to explore and analyze existing and new methods. Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: code and data available”, as a recognition that the authors have followed reproducibility principles valued by SISC and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https://github.com/parallel-in-Time/gfm.
GanglEtAl2023

P. Gangl, M. Gobrial, and O. Steinbach, “A space-time finite element method for the eddy current approximation of rotating electric machines,” arXiv:2307.00278v1 [math.NA], 2023 [Online]. Available at: http://arxiv.org/abs/2307.00278v1
BibTeX entry GanglEtAl2023

@unpublished{GanglEtAl2023, author = {Gangl, Peter and Gobrial, Mario and Steinbach, Olaf}, howpublished = {arXiv:2307.00278v1 [math.NA]}, title = {A space-time finite element method for the eddy current approximation of rotating electric machines}, url = {http://arxiv.org/abs/2307.00278v1}, year = {2023} }
Abstract for BibTeX entry GanglEtAl2023

In this paper we formulate and analyze a space-time finite element method for the numerical simulation of rotating electric machines where the finite element mesh is fixed in space-time domain. Based on the Babuška–Nečas theory we prove unique solvability both for the continuous variational formulation and for a standard Galerkin finite element discretization in the space-time domain. This approach allows for an adaptive resolution of the solution both in space and time, but it requires the solution of the overall system of algebraic equations. While the use of parallel solution algorithms seems to be mandatory, this also allows for a parallelization simultaneously in space and time. This approach is used for the eddy current approximation of the Maxwell equations which results in an elliptic-parabolic interface problem. Numerical results for linear and nonlinear constitutive material relations confirm the applicability, efficiency and accuracy of the proposed approach.
GaraiEtAl2023b

G. Garai and B. C. Mandal, “Linear and Nonlinear Parareal Methods for the Cahn-Hilliard Equation,” arXiv:2304.14074v1 [math.NA], 2023 [Online]. Available at: http://arxiv.org/abs/2304.14074v1
BibTeX entry GaraiEtAl2023b

@unpublished{GaraiEtAl2023b, author = {Garai, Gobinda and Mandal, Bankim C.}, howpublished = {arXiv:2304.14074v1 [math.NA]}, title = {Linear and Nonlinear Parareal Methods for the Cahn-Hilliard Equation}, url = {http://arxiv.org/abs/2304.14074v1}, year = {2023} }
Abstract for BibTeX entry GaraiEtAl2023b

In this paper, we propose, analyze and implement efficient time parallel methods for the Cahn-Hilliard (CH) equation. It is of great importance to develop efficient numerical methods for the CH equation, given the range of applicability of the CH equation has. The CH equation generally needs to be simulated for a very long time to get the solution of phase coarsening stage. Therefore it is desirable to accelerate the computation using parallel method in time. We present linear and nonlinear Parareal methods for the CH equation depending on the choice of fine approximation. We illustrate our results by numerical experiments.

G. Garai and B. C. Mandal, “Diagonalization based Parallel-in-Time method for a class of fourth order time dependent PDEs,” Mathematics and Computers in Simulation, Aug. 2023, doi: 10.1016/j.matcom.2023.07.028. [Online]. Available at: https://doi.org/10.1016%2Fj.matcom.2023.07.028

J. Hahne, B. Polenz, I. Kulchytska-Ruchka, S. Friedhoff, S. Ulbrich, and S. Schöps, “Parallel-in-time optimization of induction motors,” Journal of Mathematics in Industry, vol. 13, no. 1, Jun. 2023, doi: 10.1186/s13362-023-00134-5. [Online]. Available at: https://doi.org/10.1186/s13362-023-00134-5

S. Hon and S. Serra-Capizzano, “A block Toeplitz preconditioner for all-at-once systems from linear wave equations,” ETNA - Electronic Transactions on Numerical Analysis, vol. 58, pp. 177–195, 2023, doi: 10.1553/etna_vol58s177. [Online]. Available at: https://doi.org/10.1553/etna_vol58s177

HonEtAl2023b

S. Hon, J. Dong, and S. Serra-Capizzano, “A preconditioned MINRES method for optimal control of wave equations and its asymptotic spectral distribution theory,” arXiv:2307.12850v1 [math.NA], 2023 [Online]. Available at: http://arxiv.org/abs/2307.12850v1
BibTeX entry HonEtAl2023b

@unpublished{HonEtAl2023b, author = {Hon, Sean and Dong, Jiamei and Serra-Capizzano, Stefano}, howpublished = {arXiv:2307.12850v1 [math.NA]}, title = {A preconditioned MINRES method for optimal control of wave equations and its asymptotic spectral distribution theory}, url = {http://arxiv.org/abs/2307.12850v1}, year = {2023} }
Abstract for BibTeX entry HonEtAl2023b

In this work, we propose a novel preconditioned Krylov subspace method for solving an optimal control problem of wave equations, after explicitly identifying the asymptotic spectral distribution of the involved sequence of linear coefficient matrices from the optimal control problem. Namely, we first show that the all-at-once system stemming from the wave control problem is associated to a structured coefficient matrix-sequence possessing an eigenvalue distribution. Then, based on such a spectral distribution of which the symbol is explicitly identified, we develop an ideal preconditioner and two parallel-in-time preconditioners for the saddle point system composed of two block Toeplitz matrices. For the ideal preconditioner, we show that the eigenvalues of the preconditioned matrix-sequence all belong to the set \left(-\frac32,-\frac12\right)⋃\left(\frac12,\frac32\right) well separated from zero, leading to mesh-independent convergence when the minimal residual method is employed. The proposed parallel-in-time preconditioners can be implemented efficiently using fast Fourier transforms or discrete sine transforms, and their effectiveness is theoretically shown in the sense that the eigenvalues of the preconditioned matrix-sequences are clustered around \pm 1, which leads to rapid convergence. When these parallel-in-time preconditioners are not fast diagonalizable, we further propose modified versions which can be efficiently inverted. Several numerical examples are reported to verify our derived localization and spectral distribution result and to support the effectiveness of our proposed preconditioners and the related advantages with respect to the relevant literature.

A. Q. Ibrahim, S. Götschel, and D. Ruprecht, “Parareal with a Physics-Informed Neural Network as Coarse Propagator,” in Euro-Par 2023: Parallel Processing, Springer Nature Switzerland, 2023, pp. 649–663 [Online]. Available at: https://doi.org/10.1007/978-3-031-39698-4_44

Y. Jiang and J. Liu, “Fast parallel-in-time quasi-boundary value methods for backward heat conduction problems,” Applied Numerical Mathematics, vol. 184, pp. 325–339, Feb. 2023, doi: 10.1016/j.apnum.2022.10.006. [Online]. Available at: https://doi.org/10.1016%2Fj.apnum.2022.10.006

Y. Jiang, J. Liu, and X.-S. Wang, “A direct parallel-in-time quasi-boundary value method for inverse space-dependent source problems,” Journal of Computational and Applied Mathematics, vol. 423, p. 114958, May 2023, doi: 10.1016/j.cam.2022.114958. [Online]. Available at: https://doi.org/10.1016%2Fj.cam.2022.114958

JinEtAl2023

B. Jin, Q. Lin, and Z. Zhou, “Learning Coarse Propagators in Parareal Algorithm,” arXiv:2311.15320v1 [math.NA], 2023 [Online]. Available at: http://arxiv.org/abs/2311.15320v1
BibTeX entry JinEtAl2023

@unpublished{JinEtAl2023, author = {Jin, Bangti and Lin, Qingle and Zhou, Zhi}, howpublished = {arXiv:2311.15320v1 [math.NA]}, title = {Learning Coarse Propagators in Parareal Algorithm}, url = {http://arxiv.org/abs/2311.15320v1}, year = {2023} }
Abstract for BibTeX entry JinEtAl2023

The parareal algorithm represents an important class of parallel-in-time algorithms for solving evolution equations and has been widely applied in practice. To achieve effective speedup, the choice of the coarse propagator in the algorithm is vital. In this work, we investigate the use of learned coarse propagators. Building upon the error estimation framework, we present a systematic procedure for constructing coarse propagators that enjoy desirable stability and consistent order. Additionally, we provide preliminary mathematical guarantees for the resulting parareal algorithm. Numerical experiments on a variety of settings, e.g., linear diffusion model, Allen-Cahn model, and viscous Burgers model, show that learning can significantly improve parallel efficiency when compared with the more ad hoc choice of some conventional and widely used coarse propagators.
KraftEtAl2023

R. Kraft, S. Koraltan, M. Gattringer, F. Bruckner, D. Suess, and C. Abert, “Parallel-in-Time Integration of the Landau-Lifshitz-Gilbert Equation with the Parallel Full Approximation Scheme in Space and Time,” arXiv:2310.11819v1 [physics.comp-ph], 2023 [Online]. Available at: http://arxiv.org/abs/2310.11819v1
BibTeX entry KraftEtAl2023

@unpublished{KraftEtAl2023, author = {Kraft, Robert and Koraltan, Sabri and Gattringer, Markus and Bruckner, Florian and Suess, Dieter and Abert, Claas}, howpublished = {arXiv:2310.11819v1 [physics.comp-ph]}, title = {Parallel-in-Time Integration of the Landau-Lifshitz-Gilbert Equation with the Parallel Full Approximation Scheme in Space and Time}, url = {http://arxiv.org/abs/2310.11819v1}, year = {2023} }
Abstract for BibTeX entry KraftEtAl2023

Speeding up computationally expensive problems, such as numerical simulations of large micromagnetic systems, requires efficient use of parallel computing infrastructures. While parallelism across space is commonly exploited in micromagnetics, this strategy performs poorly once a minimum number of degrees of freedom per core is reached. We use magnum.pi, a finite-element micromagnetic simulation software, to investigate the Parallel Full Approximation Scheme in Space and Time (PFASST) as a space- and time-parallel solver for the Landau-Lifshitz-Gilbert equation (LLG). Numerical experiments show that PFASST enables efficient parallel-in-time integration of the LLG, significantly improving the speedup gained from using a given number of cores as well as allowing the code to scale beyond spatial limits.
LevequeEtAl2023

S. Leveque, L. Bergamaschi, Á. Martínez, and J. W. Pearson, “Fast Iterative Solver for the All-at-Once Runge–Kutta Discretization,” arXiv:2303.02090v1 [math.NA], 2023 [Online]. Available at: http://arxiv.org/abs/2303.02090v1
BibTeX entry LevequeEtAl2023

@unpublished{LevequeEtAl2023, author = {Leveque, Santolo and Bergamaschi, Luca and Martínez, Ángeles and Pearson, John W.}, howpublished = {arXiv:2303.02090v1 [math.NA]}, title = {Fast Iterative Solver for the All-at-Once Runge--Kutta Discretization}, url = {http://arxiv.org/abs/2303.02090v1}, year = {2023} }
Abstract for BibTeX entry LevequeEtAl2023

In this article, we derive fast and robust preconditioned iterative methods for the all-at-once linear systems arising upon discretization of time-dependent PDEs. The discretization we employ is based on a Runge–Kutta method in time, for which the development of robust solvers is an emerging research area in the literature of numerical methods for time-dependent PDEs. By making use of classical theory of block matrices, one is able to derive a preconditioner for the systems considered. An approximate inverse of the preconditioner so derived consists in a fixed number of linear solves for the system of the stages of the method. We thus propose a preconditioner for the latter system based on a singular value decomposition (SVD) of the (real) Runge–Kutta matrix A_\mathrmRK = U ΣV^⊤. Supposing A_\mathrmRK is invertible, we prove that the spectrum of the system for the stages preconditioned by our SVD-based preconditioner is contained within the right-half of the unit circle, under suitable assumptions on the matrix U^⊤V (which is well defined due to the polar decomposition of A_\mathrmRK). We show the numerical efficiency of our SVD-based preconditioner by solving the system of the stages arising from the discretization of the heat equation and the Stokes equations, with sequential time-stepping. Finally, we provide numerical results of the all-at-once approach for both problems.
Li2023

G. Li, “Wavelet-based Edge Multiscale Parareal Algorithm for subdiffusion equations with heterogeneous coefficients in a large time domain,” arXiv:2307.06529v1 [math.NA], 2023 [Online]. Available at: http://arxiv.org/abs/2307.06529v1
BibTeX entry Li2023

@unpublished{Li2023, author = {Li, Guanglian}, howpublished = {arXiv:2307.06529v1 [math.NA]}, title = {Wavelet-based Edge Multiscale Parareal Algorithm for subdiffusion equations with heterogeneous coefficients in a large time domain}, url = {http://arxiv.org/abs/2307.06529v1}, year = {2023} }
Abstract for BibTeX entry Li2023

We present the Wavelet-based Edge Multiscale Parareal (WEMP) Algorithm, recently proposed in [Li and Hu, \it J. Comput. Phys., 2021], for efficiently solving subdiffusion equations with heterogeneous coefficients in long time. This algorithm combines the benefits of multiscale methods, which can handle heterogeneity in the spatial domain, and the strength of parareal algorithms for speeding up time evolution problems when sufficient processors are available. Our algorithm overcomes the challenge posed by the nonlocality of the fractional derivative in previous parabolic problem work by constructing an auxiliary problem on each coarse temporal subdomain to completely uncouple the temporal variable. We prove the approximation properties of the correction operator and derive a new summation of exponential to generate a single-step time stepping scheme, with the number of terms of \mathcalO(|\log\tau_f|^2) independent of the final time, where \tau_f is the fine-scale time step size. We establish the convergence rate of our algorithm in terms of the mesh size in the spatial domain, the level parameter used in the multiscale method, the coarse-scale time step size, and the fine-scale time step size. Finally, we present several numerical tests that demonstrate the effectiveness of our algorithm and validate our theoretical results.

J. Li and Y. Jiang, “Analysis of a New Accelerated Waveform Relaxation Method Based on the Time-Parallel Algorithm,” Journal of Scientific Computing, vol. 96, no. 3, Jul. 2023, doi: 10.1007/s10915-023-02285-4. [Online]. Available at: https://doi.org/10.1007/s10915-023-02285-4

LinEtAl2023

X.-lei Lin and S. Hon, “A block α-circulant based preconditioned MINRES method for wave equations,” arXiv:2306.03574v1 [math.NA], 2023 [Online]. Available at: http://arxiv.org/abs/2306.03574v1
BibTeX entry LinEtAl2023

@unpublished{LinEtAl2023, author = {Lin, Xue-lei and Hon, Sean}, howpublished = {arXiv:2306.03574v1 [math.NA]}, title = {A block $α$-circulant based preconditioned MINRES method for wave equations}, url = {http://arxiv.org/abs/2306.03574v1}, year = {2023} }
Abstract for BibTeX entry LinEtAl2023

In this work, we propose an absolute value block α-circulant preconditioner for the minimal residual (MINRES) method to solve an all-at-once system arising from the discretization of wave equations. Since the original block α-circulant preconditioner shown successful by many recently is non-Hermitian in general, it cannot be directly used as a preconditioner for MINRES. Motivated by the absolute value block circulant preconditioner proposed in [E. McDonald, J. Pestana, and A. Wathen. SIAM J. Sci. Comput., 40(2):A1012-A1033, 2018], we propose an absolute value version of the block α-circulant preconditioner. Our proposed preconditioner is the first Hermitian positive definite variant of the block α-circulant preconditioner, which fills the gap between block α-circulant preconditioning and the field of preconditioned MINRES solver. The matrix-vector multiplication of the preconditioner can be fast implemented via fast Fourier transforms. Theoretically, we show that for properly chosen αthe MINRES solver with the proposed preconditioner has a linear convergence rate independent of the matrix size. To the best of our knowledge, this is the first attempt to generalize the original absolute value block circulant preconditioner in the aspects of both theory and performance. Numerical experiments are given to support the effectiveness of our preconditioner, showing that the expected optimal convergence can be achieved.

Z. Miao and Y.-L. Jiang, “A Fast Simulation Approach to Switched Systems,” IEEE Transactions on Circuits and Systems II: Express Briefs, pp. 1–1, 2023, doi: 10.1109/tcsii.2023.3332694. [Online]. Available at: http://dx.doi.org/10.1109/TCSII.2023.3332694

P. Munch, I. Dravins, M. Kronbichler, and M. Neytcheva, “Stage-Parallel Fully Implicit Runge–Kutta Implementations with Optimal Multilevel Preconditioners at the Scaling Limit,” SIAM Journal on Scientific Computing, pp. S71–S96, Jul. 2023, doi: 10.1137/22m1503270. [Online]. Available at: https://doi.org/10.1137%2F22m1503270

V.-T. Nguyen and L. Grigori, “Interpretation of parareal as a two-level additive Schwarz in time preconditioner and its acceleration with GMRES,” Numerical Algorithms, Mar. 2023, doi: 10.1007/s11075-022-01492-8. [Online]. Available at: https://doi.org/10.1007/s11075-022-01492-8

H. Nguyen and R. Tsai, “Numerical wave propagation aided by deep learning,” Journal of Computational Physics, vol. 475, p. 111828, Feb. 2023, doi: 10.1016/j.jcp.2022.111828. [Online]. Available at: https://doi.org/10.1016%2Fj.jcp.2022.111828

PhilippiEtAl2023

B. Philippi and T. Slawig, “A Micro-Macro Parareal Implementation for the Ocean-Circulation Model FESOM2,” arXiv:2306.17269v1 [math.NA], 2023 [Online]. Available at: http://arxiv.org/abs/2306.17269v1
BibTeX entry PhilippiEtAl2023

@unpublished{PhilippiEtAl2023, author = {Philippi, B. and Slawig, T.}, howpublished = {arXiv:2306.17269v1 [math.NA]}, title = {A Micro-Macro Parareal Implementation for the Ocean-Circulation Model FESOM2}, url = {http://arxiv.org/abs/2306.17269v1}, year = {2023} }
Abstract for BibTeX entry PhilippiEtAl2023

A micro-macro variant of the parallel-in-time algorithm Parareal has been applied to the ocean-circulation and sea-ice model model FESOM2. The state-of-the-art software in climate research has been developed by the Alfred-Wegener-Institut (AWI) in Bremen, Germany. The algorithm requires two meshes of low and high spatial resolution to define the coarse and fine propagator. As a first assessment we refined the PI mesh, increasing its resolution by factor 4. The main objective of this study was to demonstrate that micro-macro Parareal can provide convergence in diagnostic variables in complex climate research problems. After the introduction to FESOM2 we show how to generate the refined mesh and which interpolation methods were chosen. With the convergence results presented we discuss the success of this attempt and which steps have to be taken to extend the approach to current research problems.
PhilippiEtAl2023b

B. Philippi, M. S. Miraz, and T. Slawig, “A Micor-Macro parallel-in-time Implementation for the 2D Navier-Stokes Equations,” arXiv:2309.03037v1 [math.NA], 2023 [Online]. Available at: http://arxiv.org/abs/2309.03037v1
BibTeX entry PhilippiEtAl2023b

@unpublished{PhilippiEtAl2023b, author = {Philippi, Benedict and Miraz, Mahfuz Sarker and Slawig, Thomas}, howpublished = {arXiv:2309.03037v1 [math.NA]}, title = {A Micor-Macro parallel-in-time Implementation for the 2D Navier-Stokes Equations}, url = {http://arxiv.org/abs/2309.03037v1}, year = {2023} }
Abstract for BibTeX entry PhilippiEtAl2023b

In this paper the Micro-Macro Parareal algorithm was adapted to PDEs. The parallel-in-time approach requires two meshes of different spatial resolution in order to compute approximations in an iterative way to a predefined reference solution. When fast convergence in few iterations can be accomplished the algorithm is able to generate wall-time reduction in comparison to the serial computation. We chose the laminar flow around a cylinder benchmark on 2-dimensional domain which was simulated with the open-source software OpenFoam. The numerical experiments presented in this work aim to approximate states local in time and space and the diagnostic lift coefficient. The Reynolds number is gradually increased from 100 to 1,000, before the transition to turbulent flows sets in. After the results are presented the convergence behavior is discussed with respect to the Reynolds number and the applied interpolation schemes.
SarpeEtAl2023

J. Sarpe, A. Klaedtke, and H. D. Gersem, “A Parallel-In-Time Adjoint Sensitivity Analysis for a B6 Bridge-Motor Supply Circuit,” arXiv:2307.00802v1 [math.NA], 2023 [Online]. Available at: http://arxiv.org/abs/2307.00802v1
BibTeX entry SarpeEtAl2023

@unpublished{SarpeEtAl2023, author = {Sarpe, Julian and Klaedtke, Andreas and Gersem, Herbert De}, howpublished = {arXiv:2307.00802v1 [math.NA]}, title = {A Parallel-In-Time Adjoint Sensitivity Analysis for a B6 Bridge-Motor Supply Circuit}, url = {http://arxiv.org/abs/2307.00802v1}, year = {2023} }
Abstract for BibTeX entry SarpeEtAl2023

This paper presents a parallel-in-time adjoint sensitivity analysis which combines a transient adjoint sensitivity analysis with the parareal approach in order to significantly speed up the simulation. The adjoint method is the method of choice to calculate the sensitivities in a many-parameter setting. In order to obtain sensitivity information that is time-dependent, multiple adjoint problems must be solved. This slows down the simulation wall-clock time and leaves a large optimization potential for the analysis. The parareal is applied to the adjoint solution, significantly speeding up the adjoint solution for every timestep respectively.

J. Schleuß, K. Smetana, and L. ter Maat, “Randomized Quasi-Optimal Local Approximation Spaces in Time,” SIAM Journal on Scientific Computing, vol. 45, no. 3, pp. A1066–A1096, May 2023, doi: 10.1137/22m1481002. [Online]. Available at: https://doi.org/10.1137%2F22m1481002

X. Shan and M. B. van Gijzen, “Parareal Method for Anisotropic Diffusion Denoising,” in Parallel Processing and Applied Mathematics, Springer International Publishing, 2023, pp. 313–322 [Online]. Available at: https://doi.org/10.1007/978-3-031-30445-3_26

B. Song, J.-Y. Wang, and Y.-L. Jiang, “Analysis of a New Krylov subspace enhanced parareal algorithm for time-periodic problems,” Numerical Algorithms, Nov. 2023, doi: 10.1007/s11075-023-01704-9. [Online]. Available at: http://dx.doi.org/10.1007/s11075-023-01704-9

Y. Takahashi, K. Fujiwara, and T. Iwashita, “Parallel-in-Space-and-Time Finite-Element Method for Time-Periodic Magnetic Field Problems with Hysteresis,” IEEE Transactions on Magnetics, pp. 1–1, 2023, doi: 10.1109/tmag.2023.3307498. [Online]. Available at: https://doi.org/10.1109/tmag.2023.3307498

Trotti2023

K. Trotti, “A domain splitting strategy for solving PDEs,” arXiv:2303.01163v1 [math.NA], 2023 [Online]. Available at: http://arxiv.org/abs/2303.01163v1
BibTeX entry Trotti2023

@unpublished{Trotti2023, author = {Trotti, Ken}, howpublished = {arXiv:2303.01163v1 [math.NA]}, title = {A domain splitting strategy for solving PDEs}, url = {http://arxiv.org/abs/2303.01163v1}, year = {2023} }
Abstract for BibTeX entry Trotti2023

In this work we develop a novel domain splitting strategy for the solution of partial differential equations. Focusing on a uniform discretization of the d-dimensional advection-diffusion equation, our proposal is a two-level algorithm that merges the solutions obtained from the discretization of the equation over highly anisotropic submeshes to compute an initial approximation of the fine solution. The algorithm then iteratively refines the initial guess by leveraging the structure of the residual. Performing costly calculations on anisotropic submeshes enable us to reduce the dimensionality of the problem by one, and the merging process, which involves the computation of solutions over disjoint domains, allows for parallel implementation.

D. A. Vargas, R. D. Falgout, S. Günther, and J. B. Schroder, “Multigrid Reduction in Time for Chaotic Dynamical Systems,” SIAM Journal on Scientific Computing, vol. 45, no. 4, pp. A2019–A2042, Aug. 2023, doi: 10.1137/22m1518335. [Online]. Available at: https://doi.org/10.1137%2F22m1518335

Y. Wang, “Parallel Numerical Picard Iteration Methods,” Journal of Scientific Computing, vol. 95, no. 1, Mar. 2023, doi: 10.1007/s10915-023-02156-y. [Online]. Available at: https://doi.org/10.1007/s10915-023-02156-y

M. Wang and S. Zhang, “A Preconditioner for Galerkin–Legendre Spectral All-at-Once System from Time-Space Fractional Diffusion Equation,” Symmetry, vol. 15, no. 12, p. 2144, Dec. 2023, doi: 10.3390/sym15122144. [Online]. Available at: http://dx.doi.org/10.3390/sym15122144

S.-L. Wu, Z. Wang, and T. Zhou, “PinT Preconditioner for Forward-Backward Evolutionary Equations,” SIAM Journal on Matrix Analysis and Applications, vol. 44, no. 4, pp. 1771–1798, Nov. 2023, doi: 10.1137/22m1516476. [Online]. Available at: http://dx.doi.org/10.1137/22M1516476

H. Yamazaki, C. J. Cotter, and B. A. Wingate, “Time-parallel integration and phase averaging for the nonlinear shallow-water equations on the sphere,” Quarterly Journal of the Royal Meteorological Society, Jul. 2023, doi: 10.1002/qj.4517. [Online]. Available at: https://doi.org/10.1002%2Fqj.4517

X. Yue, Z. Wang, and S.-L. Wu, “Convergence Analysis of a Mixed Precision Parareal Algorithm,” SIAM Journal on Scientific Computing, vol. 45, no. 5, pp. A2483–A2510, Sep. 2023, doi: 10.1137/22m1510169. [Online]. Available at: https://doi.org/10.1137/22m1510169

J. Zeifang, A. T. Manikantan, and J. Schütz, “Time parallelism and Newton-adaptivity of the two-derivative deferred correction discontinuous Galerkin method,” Applied Mathematics and Computation, vol. 457, p. 128198, Nov. 2023, doi: 10.1016/j.amc.2023.128198. [Online]. Available at: https://doi.org/10.1016/j.amc.2023.128198

ZhouEtAl2023

Q. Zhou, Y. Liu, and S.-L. Wu, “Parareal algorithm via Chebyshev-Gauss spectral collocation method,” arXiv:2304.10152v1 [math.NA], 2023 [Online]. Available at: http://arxiv.org/abs/2304.10152v1
BibTeX entry ZhouEtAl2023

@unpublished{ZhouEtAl2023, author = {Zhou, Quan and Liu, Yicheng and Wu, Shu-Lin}, howpublished = {arXiv:2304.10152v1 [math.NA]}, title = {Parareal algorithm via Chebyshev-Gauss spectral collocation method}, url = {http://arxiv.org/abs/2304.10152v1}, year = {2023} }
Abstract for BibTeX entry ZhouEtAl2023

We present the Parareal-CG algorithm for time-dependent differential equations in this work. The algorithm is a parallel in time iteration algorithm utilizes Chebyshev-Gauss spectral collocation method for fine propagator F and backward Euler method for coarse propagator G. As far as we know, this is the first time that the spectral method used as the F propagator of the parareal algorithm. By constructing the stable function of the Chebyshev-Gauss spectral collocation method for the symmetric positive definite (SPD) problem, we find out that the Parareal-CG algorithm and the Parareal-TR algorithm, whose F propagator is chosen to be a trapezoidal ruler, converge similarly, i.e., the Parareal-CG algorithm converge as fast as Parareal-Euler algorithm with sufficient Chebyhsev-Gauss points in every coarse grid. Numerical examples including ordinary differential equations and time-dependent partial differential equations are given to illustrate the high efficiency and accuracy of the proposed algorithm.
ZhouEtAl2023b

Z. Zhou, H. Gu, G. Ju, and W. Xing, “A Parallel-in-time Method Based on Preconditioner for Biot’s Model,” arXiv:2310.10430v1 [math.NA], 2023 [Online]. Available at: http://arxiv.org/abs/2310.10430v1
BibTeX entry ZhouEtAl2023b

@unpublished{ZhouEtAl2023b, author = {Zhou, Zeyuan and Gu, Huipeng and Ju, Guoliang and Xing, Wei}, howpublished = {arXiv:2310.10430v1 [math.NA]}, title = {A Parallel-in-time Method Based on Preconditioner for Biot's Model}, url = {http://arxiv.org/abs/2310.10430v1}, year = {2023} }
Abstract for BibTeX entry ZhouEtAl2023b

We proposed a parallel-in-time method based on preconditioner for Biot’s consolidation model in poroelasticity. In order to achieve a fast and stable convergence for the matrix system of the Biot’s model, we design two preconditioners with approximations of the Schur complement. The parallel-in-time method employs an inverted time-stepping scheme that iterates to solve the preconditioned linear system in the outer loop and advances the time step in the inner loop. This allows us to parallelize the iterations with a theoretical parallel efficiency that approaches 1 as the number of time steps and spatial steps grows. We demonstrate the stability, accuracy, and linear speedup of our method on HPC platform through numerical experiments.

top

2022

AgbohEtAl2022

W. C. Agboh, D. Ruprecht, and M. R. Dogar, “Combining Coarse and Fine Physics for Manipulation using Parallel-in-Time Integration,” in Robotics Research, 2022, pp. 725–740, doi: 10.1007/978-3-030-95459-8_44 [Online]. Available at: https://doi.org/10.1007/978-3-030-95459-8_44
BibTeX entry AgbohEtAl2022

@inproceedings{AgbohEtAl2022, author = {Agboh, Wisdom C. and Ruprecht, Daniel and Dogar, Mehmet R.}, booktitle = {Robotics Research}, doi = {10.1007/978-3-030-95459-8_44}, editor = {Asfour, Tamim and Yoshida, Eiichi and Park, Jaeheung and Christensen, Henrik and Khatib, Oussama}, pages = {725 -- 740}, publisher = {Springer International Publishing}, title = {Combining Coarse and Fine Physics for Manipulation using Parallel-in-Time Integration}, url = {https://doi.org/10.1007/978-3-030-95459-8_44}, year = {2022} }
Abstract for BibTeX entry AgbohEtAl2022

We present a method for fast and accurate physics-based predictions during non-prehensile manipulation planning and control. Given an initial state and a sequence of controls, the problem of predicting the resulting sequence of states is a key component of a variety of model-based planning and control algorithms. We propose combining a coarse (i.e. computationally cheap but not very accurate) predictive physics model, with a fine (i.e. computationally expensive but accurate) predictive physics model, to generate a hybrid model that is at the required speed and accuracy for a given manipulation task. Our approach is based on the Parareal algorithm, a parallel-in-time integration method used for computing numerical solutions for general systems of ordinary differential equations. We use Parareal to combine a coarse pushing model with an off-the-shelf physics engine to deliver physics-based predictions that are as accurate as the physics engine but runs in substantially less wall-clock time, thanks to Parareal being amenable to parallelization. We use these physics-based predictions in a model-predictive-control framework based on trajectory optimization, to plan pushing actions that avoid an obstacle and reach a goal location. We show that by combining the two physics models, we can achieve the same success rates as the planner that uses the off-the-shelf physics engine directly, but significantly faster. We present experiments in simulation and on a real robotic setup.

A. Arrarás, F. J. Gaspar, L. Portero, and C. Rodrigo, “Space-Time Parallel Methods for Evolutionary Reaction-Diffusion Problems,” in Domain Decomposition Methods in Science and Engineering XXVI, Springer International Publishing, 2022, pp. 643–651 [Online]. Available at: https://doi.org/10.1007/978-3-030-95025-5_70

D. Q. Bui, C. Japhet, Y. Maday, and P. Omnes, “Coupling Parareal with Optimized Schwarz Waveform Relaxation for Parabolic Problems,” SIAM Journal on Numerical Analysis, vol. 60, no. 3, pp. 913–939, May 2022, doi: 10.1137/21m1419428. [Online]. Available at: https://doi.org/10.1137/21m1419428

T. Cheng, N. Lin, and V. Dinavahi, “Hybrid Parallel-in-Time-and-Space Transient Stability Simulation of Large-Scale AC/DC Grids,” IEEE Transactions on Power Systems, pp. 1–1, 2022, doi: 10.1109/tpwrs.2022.3153450. [Online]. Available at: https://doi.org/10.1109/tpwrs.2022.3153450

S. Costanzo, T. Sayadi, M. F. de Pando, P. J. Schmid, and P. Frey, “Parallel-in-time adjoint-based optimization – application to unsteady incompressible flows,” Journal of Computational Physics, p. 111664, Oct. 2022, doi: 10.1016/j.jcp.2022.111664. [Online]. Available at: https://doi.org/10.1016/j.jcp.2022.111664

L. D’Amore, E. Constantinescu, and L. Carracciuolo, “A Scalable Space-Time Domain Decomposition Approach for Solving Large Scale Nonlinear Regularized Inverse Ill Posed Problems in 4D Variational Data Assimilation,” Journal of Scientific Computing, vol. 91, no. 2, Apr. 2022, doi: 10.1007/s10915-022-01826-7. [Online]. Available at: https://doi.org/10.1007/s10915-022-01826-7

F. Danieli, B. S. Southworth, and A. J. Wathen, “Space-Time Block Preconditioning for Incompressible Flow,” SIAM Journal on Scientific Computing, vol. 44, no. 1, pp. A337–A363, Feb. 2022, doi: 10.1137/21m1390773. [Online]. Available at: https://doi.org/10.1137%2F21m1390773

F. Danieli and S. MacLachlan, “Multigrid reduction in time for non-linear hyperbolic equations,” ETNA - Electronic Transactions on Numerical Analysis, vol. 58, pp. 43–65, 2022, doi: 10.1553/etna_vol58s43. [Online]. Available at: https://doi.org/10.1553%2Fetna_vol58s43

FreiEtAl2022b

S. Frei and A. Heinlein, “Efficient coarse correction for parallel time-stepping in plaque growth simulations,” arXiv:2207.02081v1 [math.NA], 2022 [Online]. Available at: http://arxiv.org/abs/2207.02081v1
BibTeX entry FreiEtAl2022b

@unpublished{FreiEtAl2022b, author = {Frei, Stefan and Heinlein, Alexander}, howpublished = {arXiv:2207.02081v1 [math.NA]}, title = {Efficient coarse correction for parallel time-stepping in plaque growth simulations}, url = {http://arxiv.org/abs/2207.02081v1}, year = {2022} }
Abstract for BibTeX entry FreiEtAl2022b

In order to make the numerical simulation of atherosclerotic plaque growth feasible, a temporal homogenization approach is employed. The resulting macro-scale problem for the plaque growth can be further accelerated by using parallel time integration schemes, such as the parareal algorithm. However, the parallel scalability is dominated by the computational cost of the coarse propagator. Therefore, in this paper, an interpolation-based coarse propagator, which uses growth values from previously computed micro-scale problems, is introduced. For a simple model problem, it is shown that this approach reduces both the computational work for a single parareal iteration as well as the required number of parareal iterations.

I. C. Garcia, I. Kulchytska-Ruchka, and S. Schöps, “Parareal for index two differential algebraic equations,” Numerical Algorithms, Mar. 2022, doi: 10.1007/s11075-022-01267-1. [Online]. Available at: https://doi.org/10.1007%2Fs11075-022-01267-1

GoryninaEtAl2022

O. Gorynina, F. Legoll, T. Lelievre, and D. Perez, “Combining machine-learned and empirical force fields with the parareal algorithm: application to the diffusion of atomistic defects,” arXiv:2212.10508v1 [math.NA], 2022 [Online]. Available at: http://arxiv.org/abs/2212.10508v1
BibTeX entry GoryninaEtAl2022

@unpublished{GoryninaEtAl2022, author = {Gorynina, Olga and Legoll, Frederic and Lelievre, Tony and Perez, Danny}, howpublished = {arXiv:2212.10508v1 [math.NA]}, title = {Combining machine-learned and empirical force fields with the parareal algorithm: application to the diffusion of atomistic defects}, url = {http://arxiv.org/abs/2212.10508v1}, year = {2022} }
Abstract for BibTeX entry GoryninaEtAl2022

We numerically investigate an adaptive version of the parareal algorithm in the context of molecular dynamics. This adaptive variant has been originally introduced in [F. Legoll, T. Lelievre and U. Sharma, SISC 2022]. We focus here on test cases of physical interest where the dynamics of the system is modelled by the Langevin equation and is simulated using the molecular dynamics software LAMMPS. In this work, the parareal algorithm uses a family of machine-learning spectral neighbor analysis potentials (SNAP) as fine, reference, potentials and embedded-atom method potentials (EAM) as coarse potentials. We consider a self-interstitial atom in a tungsten lattice and compute the average residence time of the system in metastable states. Our numerical results demonstrate significant computational gains using the adaptive parareal algorithm in comparison to a sequential integration of the Langevin dynamics. We also identify a large regime of numerical parameters for which statistical accuracy is reached without being a consequence of trajectorial accuracy.

J. Hahne, B. S. Southworth, and S. Friedhoff, “Asynchronous Truncated Multigrid-Reduction-in-Time,” SIAM Journal on Scientific Computing, pp. S281–S306, Nov. 2022, doi: 10.1137/21m1433149. [Online]. Available at: https://doi.org/10.1137/21m1433149

G. He, “Time Parallel Denoising Algorithm Based on P-M Equation for Real Image,” Wireless Communications and Mobile Computing, vol. 2022, pp. 1–9, Aug. 2022, doi: 10.1155/2022/8008912. [Online]. Available at: https://doi.org/10.1155/2022/8008912

Y. He and J. Liu, “A Vanka-type multigrid solver for complex-shifted Laplacian systems from diagonalization-based parallel-in-time algorithms,” Applied Mathematics Letters, vol. 132, p. 108125, Oct. 2022, doi: 10.1016/j.aml.2022.108125. [Online]. Available at: https://doi.org/10.1016/j.aml.2022.108125

K. Herb and P. Welter, “Parallel time integration using Batched BLAS (Basic Linear Algebra Subprograms) routines,” Computer Physics Communications, vol. 270, p. 108181, Jan. 2022, doi: 10.1016/j.cpc.2021.108181. [Online]. Available at: https://doi.org/10.1016/j.cpc.2021.108181

Y. Jiang and J. Liu, “Fast Parallel-in-Time Quasi-Boundary Value Methods for Backward Heat Conduction Problems,” Applied Numerical Mathematics, Oct. 2022, doi: 10.1016/j.apnum.2022.10.006. [Online]. Available at: https://doi.org/10.1016/j.apnum.2022.10.006

E. Kazakov, D. Efremenko, V. Zemlyakov, and J. Gao, “A Time-Parallel Ordinary Differential Equation Solver with an Adaptive Step Size: Performance Assessment,” in Lecture Notes in Computer Science, Springer International Publishing, 2022, pp. 3–17 [Online]. Available at: https://doi.org/10.1007/978-3-031-22941-1_1

KressnerEtAl2022

D. Kressner, S. Massei, and J. Zhu, “Improved parallel-in-time integration via low-rank updates and interpolation,” arXiv:2204.03073v1 [math.NA], 2022 [Online]. Available at: http://arxiv.org/abs/2204.03073v1
BibTeX entry KressnerEtAl2022

@unpublished{KressnerEtAl2022, author = {Kressner, Daniel and Massei, Stefano and Zhu, Junli}, howpublished = {arXiv:2204.03073v1 [math.NA]}, title = {Improved parallel-in-time integration via low-rank updates and interpolation}, url = {http://arxiv.org/abs/2204.03073v1}, year = {2022} }
Abstract for BibTeX entry KressnerEtAl2022

This work is concerned with linear matrix equations that arise from the space-time discretization of time-dependent linear partial differential equations (PDEs). Such matrix equations have been considered, for example, in the context of parallel-in-time integration leading to a class of algorithms called ParaDiag. We develop and analyze two novel approaches for the numerical solution of such equations. Our first approach is based on the observation that the modification of these equations performed by ParaDiag in order to solve them in parallel has low rank. Building upon previous work on low-rank updates of matrix equations, this allows us to make use of tensorized Krylov subspace methods to account for the modification. Our second approach is based on interpolating the solution of the matrix equation from the solutions of several modifications. Both approaches avoid the use of iterative refinement needed by ParaDiag and related space-time approaches in order to attain good accuracy. In turn, our new approaches have the potential to outperform, sometimes significantly, existing approaches. This potential is demonstrated for several different types of PDEs.

Y. Lee, J. Park, and C.-O. Lee, “Parareal Neural Networks Emulating a Parallel-in-Time Algorithm,” IEEE Transactions on Neural Networks and Learning Systems, pp. 1–12, 2022, doi: 10.1109/tnnls.2022.3206797. [Online]. Available at: https://doi.org/10.1109/tnnls.2022.3206797

C.-O. Lee, Y. Lee, and J. Park, “A Parareal Architecture for Very Deep Convolutional Neural Networks,” in Lecture Notes in Computational Science and Engineering, Springer International Publishing, 2022, pp. 407–415 [Online]. Available at: http://dx.doi.org/10.1007/978-3-030-95025-5_43

F. Legoll, T. Lelièvre, and U. Sharma, “An Adaptive Parareal Algorithm: Application to the Simulation of Molecular Dynamics Trajectories,” SIAM Journal on Scientific Computing, vol. 44, no. 1, pp. B146–B176, Jan. 2022, doi: 10.1137/21m1412979. [Online]. Available at: https://doi.org/10.1137/21m1412979

S. Li, L. Xie, and L. Zhou, “Convergence analysis of space-time domain decomposition method for parabolic equations,” Computers &\mathsemicolon Mathematics with Applications, Aug. 2022, doi: 10.1016/j.camwa.2022.08.012. [Online]. Available at: https://doi.org/10.1016/j.camwa.2022.08.012

J. Liu and Z. Wang, “A ROM-accelerated parallel-in-time preconditioner for solving all-at-once systems in unsteady convection-diffusion PDEs,” vol. 416, p. 126750, Mar. 2022, doi: 10.1016/j.amc.2021.126750. [Online]. Available at: https://doi.org/10.1016/j.amc.2021.126750

J. Liu, X.-S. Wang, S.-L. Wu, and T. Zhou, “A well-conditioned direct PinT algorithm for first- and second-order evolutionary equations,” Advances in Computational Mathematics, vol. 48, no. 3, Apr. 2022, doi: 10.1007/s10444-022-09928-4. [Online]. Available at: https://doi.org/10.1007%2Fs10444-022-09928-4

C. Lohmann, J. Dünnebacke, and S. Turek, “Fourier analysis of a time-simultaneous two-grid algorithm using a damped Jacobi waveform relaxation smoother for the one-dimensional heat equation,” Journal of Numerical Mathematics, vol. 0, no. 0, Jun. 2022, doi: 10.1515/jnma-2021-0045. [Online]. Available at: https://doi.org/10.1515/jnma-2021-0045

MoonEtAl2022

G. E. Moon and E. C. Cyr, “Parallel Training of GRU Networks with a Multi-Grid Solver for Long Sequences,” arXiv:2203.04738v1 [cs.CV], 2022 [Online]. Available at: http://arxiv.org/abs/2203.04738v1
BibTeX entry MoonEtAl2022

@unpublished{MoonEtAl2022, author = {Moon, Gordon Euhyun and Cyr, Eric C.}, howpublished = {arXiv:2203.04738v1 [cs.CV]}, title = {Parallel Training of GRU Networks with a Multi-Grid Solver for Long Sequences}, url = {http://arxiv.org/abs/2203.04738v1}, year = {2022} }
Abstract for BibTeX entry MoonEtAl2022

Parallelizing Gated Recurrent Unit (GRU) networks is a challenging task, as the training procedure of GRU is inherently sequential. Prior efforts to parallelize GRU have largely focused on conventional parallelization strategies such as data-parallel and model-parallel training algorithms. However, when the given sequences are very long, existing approaches are still inevitably performance limited in terms of training time. In this paper, we present a novel parallel training scheme (called parallel-in-time) for GRU based on a multigrid reduction in time (MGRIT) solver. MGRIT partitions a sequence into multiple shorter sub-sequences and trains the sub-sequences on different processors in parallel. The key to achieving speedup is a hierarchical correction of the hidden state to accelerate end-to-end communication in both the forward and backward propagation phases of gradient descent. Experimental results on the HMDB51 dataset, where each video is an image sequence, demonstrate that the new parallel training scheme achieves up to 6.5\times speedup over a serial approach. As efficiency of our new parallelization strategy is associated with the sequence length, our parallel GRU algorithm achieves significant performance improvement as the sequence length increases.

K. Pentland, M. Tamborrino, D. Samaddar, and L. C. Appel, “Stochastic Parareal: An Application of Probabilistic Methods to Time-Parallelization,” SIAM Journal on Scientific Computing, pp. S82–S102, Jul. 2022, doi: 10.1137/21m1414231. [Online]. Available at: https://doi.org/10.1137%2F21m1414231

PentlandEtAl2022c

K. Pentland, M. Tamborrino, and T. J. Sullivan, “Error bound analysis of the stochastic parareal algorithm,” arXiv:2211.05496v1 [math.NA], 2022 [Online]. Available at: http://arxiv.org/abs/2211.05496v1
BibTeX entry PentlandEtAl2022c

@unpublished{PentlandEtAl2022c, author = {Pentland, Kamran and Tamborrino, Massimiliano and Sullivan, T. J.}, howpublished = {arXiv:2211.05496v1 [math.NA]}, title = {Error bound analysis of the stochastic parareal algorithm}, url = {http://arxiv.org/abs/2211.05496v1}, year = {2022} }
Abstract for BibTeX entry PentlandEtAl2022c

Stochastic parareal (SParareal) is a probabilistic variant of the popular parallel-in-time algorithm known as parareal. Similarly to parareal, it combines fine- and coarse-grained solutions to an ordinary differential equation (ODE) using a predictor-corrector (PC) scheme. The key difference is that carefully chosen random perturbations are added to the PC to try to accelerate the location of a stochastic solution to the ODE. In this paper, we derive superlinear and linear mean-square error bounds for SParareal applied to nonlinear systems of ODEs using different types of perturbations. We illustrate these bounds numerically on a linear system of ODEs and a scalar nonlinear ODE, showing a good match between theory and numerics.

K. Pentland, M. Tamborrino, T. J. Sullivan, J. Buchanan, and L. C. Appel, “GParareal: a time-parallel ODE solver using Gaussian process emulation,” Statistics and Computing, vol. 33, no. 1, Dec. 2022, doi: 10.1007/s11222-022-10195-y. [Online]. Available at: https://doi.org/10.1007%2Fs11222-022-10195-y

PhilippiEtAl2022

B. Philippi and T. Slawig, “The Parareal Algorithm Applied to the FESOM 2 Ocean Circulation Model,” arXiv:2208.07598v1 [math.NA], 2022 [Online]. Available at: http://arxiv.org/abs/2208.07598v1
BibTeX entry PhilippiEtAl2022

@unpublished{PhilippiEtAl2022, author = {Philippi, Benedict and Slawig, Thomas}, howpublished = {arXiv:2208.07598v1 [math.NA]}, title = {The Parareal Algorithm Applied to the FESOM 2 Ocean Circulation Model}, url = {http://arxiv.org/abs/2208.07598v1}, year = {2022} }
Abstract for BibTeX entry PhilippiEtAl2022

In this work the parallel-in-time algorithm Parareal was applied to the ocean-circulation and sea-ice model FESOM2 developed by the Alfred-Wegener Institut (AWI). The climate model provides one time integration method and hence, the coarse and fine propagators were defined by time step width. The coarse method was executed at the CFL condition limit, while fine step-sizes where gradually refined. As a first assessment of the performance of Parareal a low-resolution test mesh was used with default settings provided by the AWI. An introduction to FESOM2 and the straightforward implementation of Parareal on the DKRZ cluster is given. The evaluation of numerical results for different simulation intervals and fine propagator configurations shows strong dependence on the simulation time and time step-size of the fine propagator. Increasing the latter leads to stagnation and eventually divergence of the Parareal algorithm.

M. K. Riahi, “PiTSBiCG: Parallel in time Stable Bi-Conjugate gradient algorithm,” Applied Numerical Mathematics, vol. 181, pp. 225–233, Nov. 2022, doi: 10.1016/j.apnum.2022.06.004. [Online]. Available at: https://doi.org/10.1016%2Fj.apnum.2022.06.004

RiffoEtAl2022

S. Riffo, F. Kwok, and J. Salomon, “Time-parallelization of sequential data assimilation problems,” arXiv:2212.02377v1 [math.OC], 2022 [Online]. Available at: http://arxiv.org/abs/2212.02377v1
BibTeX entry RiffoEtAl2022

@unpublished{RiffoEtAl2022, author = {Riffo, Sebastián and Kwok, Félix and Salomon, Julien}, howpublished = {arXiv:2212.02377v1 [math.OC]}, title = {Time-parallelization of sequential data assimilation problems}, url = {http://arxiv.org/abs/2212.02377v1}, year = {2022} }
Abstract for BibTeX entry RiffoEtAl2022

This paper is devoted to the problem of time parallelization of assimilation methods applying on unbounded time domain. In this way, we present a general procedure to couple the Luenberger observer with time parallelization algorithm. Our approach is based on a posteriori error estimates of the latter and preserves the rate of the non-parallelized observer. We then focus on the case where the Parareal algorithm is used as time parallelization algorithm, and derive a bound of the efficiency of our procedure. A variant devoted to the case a large number of processors is also proposed. We illustrate the performance of our approach with numerical experiments.
RosemeierEtAl2022

J. Rosemeier, T. Haut, and B. Wingate, “Multi-level Parareal algorithm with Averaging,” arXiv:2211.17239v1 [math.NA], 2022 [Online]. Available at: http://arxiv.org/abs/2211.17239v1
BibTeX entry RosemeierEtAl2022

@unpublished{RosemeierEtAl2022, author = {Rosemeier, Juliane and Haut, Terry and Wingate, Beth}, howpublished = {arXiv:2211.17239v1 [math.NA]}, title = {Multi-level Parareal algorithm with Averaging}, url = {http://arxiv.org/abs/2211.17239v1}, year = {2022} }
Abstract for BibTeX entry RosemeierEtAl2022

The present study is an extension of the work done in [16] and [10], where a two-level Parareal method with averaging was examined. The method proposed in this paper is a multi-level Parareal method with arbitrarily many levels, which is not restricted to the two-level case. We give an asymptotic error estimate which reduces to the two-level estimate for the case when only two levels are considered. Introducing more than two levels has important consequences for the averaging procedure, as we choose separate averaging windows for each of the different levels, which is an additional new feature of the present study. The different averaging windows make the proposed method especially appropriate for multi-scale problems, because we can introduce a level for each intrinsic scale of the problem and adapt the averaging procedure such that we reproduce the behavior of the model on the particular scale resolved by the level.
SaerkkaeEtAl2022

S. Särkkä and Á. F. García-Fernández, “Temporal Parallelisation of the HJB Equation and Continuous-Time Linear Quadratic Control,” arXiv:2212.11744v1 [math.OC], 2022 [Online]. Available at: http://arxiv.org/abs/2212.11744v1
BibTeX entry SaerkkaeEtAl2022

@unpublished{SaerkkaeEtAl2022, author = {Särkkä, Simo and García-Fernández, Ángel F.}, howpublished = {arXiv:2212.11744v1 [math.OC]}, title = {Temporal Parallelisation of the HJB Equation and Continuous-Time Linear Quadratic Control}, url = {http://arxiv.org/abs/2212.11744v1}, year = {2022} }
Abstract for BibTeX entry SaerkkaeEtAl2022

This paper presents a mathematical formulation to perform temporal parallelisation of continuous-time optimal control problems, which are solved via the Hamilton–Jacobi–Bellman (HJB) equation. We divide the time interval of the control problem into sub-intervals, and define a control problem in each sub-interval, conditioned on the start and end states, leading to conditional value functions for the sub-intervals. By defining an associative operator as the minimisation of the sum of conditional value functions, we obtain the elements and associative operators for a parallel associative scan operation. This allows for solving the optimal control problem on the whole time interval in parallel in logarithmic time complexity in the number of sub-intervals. We derive the HJB-type of backward and forward equations for the conditional value functions and solve them in closed form for linear quadratic problems. We also discuss other numerical methods for computing the conditional value functions and present closed form solutions for selected special cases. The computational advantages of the proposed parallel methods are demonstrated via simulations run on a multi-core central processing unit and a graphics processing unit.
SterckEtAl2022

H. D. Sterck, R. D. Falgout, and O. A. Krzysik, “Fast multigrid reduction-in-time for advection via modified semi-Lagrangian coarse-grid operators,” arXiv:2203.13382v1 [math.NA], 2022 [Online]. Available at: http://arxiv.org/abs/2203.13382v1
BibTeX entry SterckEtAl2022

@unpublished{SterckEtAl2022, author = {Sterck, H. De and Falgout, R. D. and Krzysik, O. A.}, howpublished = {arXiv:2203.13382v1 [math.NA]}, title = {Fast multigrid reduction-in-time for advection via modified semi-Lagrangian coarse-grid operators}, url = {http://arxiv.org/abs/2203.13382v1}, year = {2022} }
Abstract for BibTeX entry SterckEtAl2022

Many iterative parallel-in-time algorithms have been shown to be highly efficient for diffusion-dominated partial differential equations (PDEs), but are inefficient or even divergent when applied to advection-dominated PDEs. We consider the application of the multigrid reduction-in-time (MGRIT) algorithm to linear advection PDEs. The key to efficient time integration with this method is using a coarse-grid operator that provides a sufficiently accurate approximation to the the so-called ideal coarse-grid operator. For certain classes of semi-Lagrangian discretizations, we present a novel semi-Lagrangian-based coarse-grid operator that leads to fast and scalable multilevel time integration of linear advection PDEs. The coarse-grid operator is composed of a semi-Lagrangian discretization followed by a correction term, with the correction designed so that the leading-order truncation error of the composite operator is approximately equal to that of the ideal coarse-grid operator. Parallel results show substantial speed-ups over sequential time integration for variable-wave-speed advection problems in one and two spatial dimensions, and using high-order discretizations up to order five. The proposed approach establishes the first practical method that provides small and scalable MGRIT iteration counts for advection problems.
SterckEtAl2022b

H. D. Sterck, S. Friedhoff, O. A. Krzysik, and S. P. MacLachlan, “Multigrid reduction-in-time convergence for advection problems: A Fourier analysis perspective,” arXiv:2208.01526v1 [math.NA], 2022 [Online]. Available at: http://arxiv.org/abs/2208.01526v1
BibTeX entry SterckEtAl2022b

@unpublished{SterckEtAl2022b, author = {Sterck, H. De and Friedhoff, S. and Krzysik, O. A. and MacLachlan, Scott P.}, howpublished = {arXiv:2208.01526v1 [math.NA]}, title = {Multigrid reduction-in-time convergence for advection problems: A Fourier analysis perspective}, url = {http://arxiv.org/abs/2208.01526v1}, year = {2022} }
Abstract for BibTeX entry SterckEtAl2022b

A long-standing issue in the parallel-in-time community is the poor convergence of standard iterative parallel-in-time methods for hyperbolic partial differential equations (PDEs), and for advection-dominated PDEs more broadly. Here, a local Fourier analysis (LFA) convergence theory is derived for the two-level variant of the iterative parallel-in-time method of multigrid reduction-in-time (MGRIT). This closed-form theory allows for new insights into the poor convergence of MGRIT for advection-dominated PDEs when using the standard approach of rediscretizing the fine-grid problem on the coarse grid. Specifically, we show that this poor convergence arises, at least in part, from inadequate coarse-grid correction of certain smooth Fourier modes known as characteristic components, which was previously identified as causing poor convergence of classical spatial multigrid on steady-state advection-dominated PDEs. We apply this convergence theory to show that, for certain semi-Lagrangian discretizations of advection problems, MGRIT convergence using rediscretized coarse-grid operators cannot be robust with respect to CFL number or coarsening factor. A consequence of this analysis is that techniques developed for improving convergence in the spatial multigrid context can be re-purposed in the MGRIT context to develop more robust parallel-in-time solvers. This strategy has been used in recent work to great effect; here, we provide further theoretical evidence supporting the effectiveness of this approach.
SterckEtAl2022c

H. D. Sterck, R. D. Falgout, O. A. Krzysik, and J. B. Schroder, “Efficient multigrid reduction-in-time for method-of-lines discretizations of linear advection,” arXiv:2209.06916v1 [math.NA], 2022 [Online]. Available at: http://arxiv.org/abs/2209.06916v1
BibTeX entry SterckEtAl2022c

@unpublished{SterckEtAl2022c, author = {Sterck, H. De and Falgout, R. D. and Krzysik, O. A. and Schroder, J. B.}, howpublished = {arXiv:2209.06916v1 [math.NA]}, title = {Efficient multigrid reduction-in-time for method-of-lines discretizations of linear advection}, url = {http://arxiv.org/abs/2209.06916v1}, year = {2022} }
Abstract for BibTeX entry SterckEtAl2022c

Parallel-in-time methods for partial differential equations (PDEs) have been the subject of intense development over recent decades, particularly for diffusion-dominated problems. It has been widely reported in the literature, however, that many of these methods perform quite poorly for advection-dominated problems. Here we analyze the particular iterative parallel-in-time algorithm of multigrid reduction-in-time (MGRIT) for discretizations of constant-wave-speed linear advection problems. We focus on common method-of-lines discretizations that employ upwind finite differences in space and Runge-Kutta methods in time. Using a convergence framework we developed in previous work, we prove for a subclass of these discretizations that, if using the standard approach of rediscretizing the fine-grid problem on the coarse grid, robust MGRIT convergence with respect to CFL number and coarsening factor is not possible. This poor convergence and non-robustness is caused, at least in part, by an inadequate coarse-grid correction for smooth Fourier modes known as characteristic components.We propose an alternative coarse-grid that provides a better correction of these modes. This coarse-grid operator is related to previous work and uses a semi-Lagrangian discretization combined with an implicitly treated truncation error correction. Theory and numerical experiments show the coarse-grid operator yields fast MGRIT convergence for many of the method-of-lines discretizations considered, including for both implicit and explicit discretizations of high order.

J. Strake, D. Döhring, and A. Benigni, “MGRIT-Based Multi-Level Parallel-in-Time Electromagnetic Transient Simulation,” Energies, vol. 15, no. 21, p. 7874, Oct. 2022, doi: 10.3390/en15217874. [Online]. Available at: https://doi.org/10.3390/en15217874

M. Sugiyama, J. B. Schroder, B. S. Southworth, and S. Friedhoff, “Weighted relaxation for multigrid reduction in time,” Numerical Linear Algebra with Applications, Sep. 2022, doi: 10.1002/nla.2465. [Online]. Available at: https://doi.org/10.1002%2Fnla.2465

M. A. Sultanov, V. E. Misilov, and Y. Nurlanuly, “Efficient Parareal algorithm for solving time-fractional diffusion equation,” Dal nevostochnyi Matematicheskii Zhurnal, vol. 22, no. 2, pp. 245–251, 2022, doi: 10.47910/femj202233. [Online]. Available at: https://doi.org/10.47910/femj202233

Y. Takahashi, K. Fujiwara, and T. Iwashita, “Parallel-in-space-and-time finite-element analysis of electric machines using time step overlapping in a massively parallel computing environment,” COMPEL - The international journal for computation and mathematics in electrical and electronic engineering, Jul. 2022, doi: 10.1108/compel-04-2022-0161. [Online]. Available at: https://doi.org/10.1108/compel-04-2022-0161

R. Tielen, M. Möller, and C. Vuik, “Combining p-multigrid and Multigrid Reduction in Time methods to obtain a scalable solver for Isogeometric Analysis,” SN Applied Sciences, vol. 4, no. 6, May 2022, doi: 10.1007/s42452-022-05043-7. [Online]. Available at: https://doi.org/10.1007%2Fs42452-022-05043-7

Utkarsh, C. Elrod, Y. Ma, K. Althaus, and C. Rackauckas, “Parallelizing Explicit and Implicit Extrapolation Methods for Ordinary Differential Equations,” in 2022 IEEE High Performance Extreme Computing Conference (HPEC), 2022, doi: 10.1109/hpec55821.2022.9926357 [Online]. Available at: https://doi.org/10.1109%2Fhpec55821.2022.9926357

C.-Y. Wang, Y.-L. Jiang, and Z. Miao, “Time domain decomposition of parabolic control problems based on discontinuous Galerkin semi-discretization,” Applied Numerical Mathematics, Feb. 2022, doi: 10.1016/j.apnum.2022.02.016. [Online]. Available at: https://doi.org/10.1016/j.apnum.2022.02.016

R. Watschinger, M. Merta, G. Of, and J. Zapletal, “A Parallel Fast Multipole Method for a Space-Time Boundary Element Method for the Heat Equation,” SIAM Journal on Scientific Computing, vol. 44, no. 4, pp. C320–C345, Aug. 2022, doi: 10.1137/21m1430157. [Online]. Available at: https://doi.org/10.1137%2F21m1430157

J. Yang, Z. Yuan, and Z. Zhou, “Robust Convergence of Parareal Algorithms with Arbitrarily High-Order Fine Propagators,” SSRN Electronic Journal, 2022, doi: 10.2139/ssrn.4097528. [Online]. Available at: https://doi.org/10.2139%2Fssrn.4097528

L. Yang and H. Li, “A hybrid algorithm based on parareal and Schwarz waveform relaxation,” Electronic Research Archive, vol. 30, no. 11, pp. 4086–4107, 2022, doi: 10.3934/era.2022207. [Online]. Available at: https://doi.org/10.3934/era.2022207

R. Yoda, M. Bolten, K. Nakajima, and A. Fujii, “Assignment of idle processors to spatial redistributed domains on coarse levels in multigrid reduction in time,” in International Conference on High Performance Computing in Asia-Pacific Region, 2022, doi: 10.1145/3492805.3492810 [Online]. Available at: https://doi.org/10.1145/3492805.3492810

R. Yoda, M. Bolten, K. Nakajima, and A. Fujii, “Acceleration of Optimized Coarse-Grid Operators by Spatial Redistribution for Multigrid Reduction in Time,” in Computational Science – ICCS 2022, Springer International Publishing, 2022, pp. 214–221 [Online]. Available at: https://doi.org/10.1007/978-3-031-08754-7_29

R.-H. Zhang, Y.-L. Jiang, J. Li, and B. Song, “Analysis of the parareal algorithm for linear parametric differential equations,” International Journal of Computer Mathematics, pp. 1–0, Nov. 2022, doi: 10.1080/00207160.2022.2153225. [Online]. Available at: https://doi.org/10.1080/00207160.2022.2153225

top

2021

AngelEtAl2021

J. Angel, S. Götschel, and D. Ruprecht, “Impact of spatial coarsening on Parareal convergence,” arXiv:2111.10228v1 [math.NA], 2021 [Online]. Available at: http://arxiv.org/abs/2111.10228v1
BibTeX entry AngelEtAl2021

@unpublished{AngelEtAl2021, author = {Angel, Judith and Götschel, Sebastian and Ruprecht, Daniel}, howpublished = {arXiv:2111.10228v1 [math.NA]}, title = {Impact of spatial coarsening on Parareal convergence}, url = {http://arxiv.org/abs/2111.10228v1}, year = {2021} }
Abstract for BibTeX entry AngelEtAl2021

We study the impact of spatial coarsening on the convergence of the Parareal algorithm, both theoretically and numerically. For initial value problems with a normal system matrix, we prove a lower bound for the Euclidean norm of the iteration matrix. When there is no physical or numerical diffusion, an immediate consequence is that the norm of the iteration matrix cannot be smaller than unoty as soon as the coarse problem has fewer degrees-of-freedom than the fine. This prevents a theoretical guarantee for monotonic convergence, which is necessary to obtain meaningful speedups. For diffusive problems, in the worst-case where the iteration error contracts only as fast as the powers of the iteration matrix norm, making Parareal as accurate as the fine method will take about as many iterations as there are processors, making meaningful speedup impossible. Numerical examples with a non-normal system matrix show that for diffusive problems good speedup is possible, but that for non-diffusive problems the negative impact of spatial coarsening on convergence is big.

P. Benedusi, M. L. Minion, and R. Krause, “An experimental comparison of a space-time multigrid method with PFASST for a reaction-diffusion problem,” Computers & Mathematics with Applications, vol. 99, pp. 162–170, Oct. 2021, doi: 10.1016/j.camwa.2021.07.008. [Online]. Available at: https://doi.org/10.1016%2Fj.camwa.2021.07.008

S. Blanes, “Novel parallel in time integrators for ODEs,” Applied Mathematics Letters, p. 107542, Jul. 2021, doi: 10.1016/j.aml.2021.107542. [Online]. Available at: https://doi.org/10.1016/j.aml.2021.107542

A. L. Blumers, M. Yin, H. Nakajima, Y. Hasegawa, Z. Li, and G. E. Karniadakis, “Multiscale parareal algorithm for long-time mesoscopic simulations of microvascular blood flow in zebrafish,” Computational Mechanics, Aug. 2021, doi: 10.1007/s00466-021-02062-w. [Online]. Available at: https://doi.org/10.1007%2Fs00466-021-02062-w

T. Buvoli and M. Minion, “IMEX Runge-Kutta Parareal for Non-diffusive Equations,” in Springer Proceedings in Mathematics &\mathsemicolon Statistics, Springer International Publishing, 2021, pp. 95–127 [Online]. Available at: https://doi.org/10.1007%2F978-3-030-75933-9_5

M. Cai, J. Mahseredjian, I. Kocar, X. Fu, and A. Haddadi, “A parallelization-in-time approach for accelerating EMT simulations,” Electric Power Systems Research, vol. 197, p. 107346, Aug. 2021, doi: 10.1016/j.epsr.2021.107346. [Online]. Available at: https://doi.org/10.1016/j.epsr.2021.107346

CaldasEtAl2021

J. G. Caldas Steinstraesser, “Coupling large and small scale shallow water models with porosity in the presence of anisotropy,” PhD thesis, Université de Montpellier, 2021 [Online]. Available at: https://www.theses.fr/2021MONTS040
BibTeX entry CaldasEtAl2021

@phdthesis{CaldasEtAl2021, author = {Caldas Steinstraesser, Jo\~{a}o Guilherme}, school = {Universit\'{e} de Montpellier}, title = {Coupling large and small scale shallow water models with porosity in the presence of anisotropy}, url = {https://www.theses.fr/2021MONTS040}, year = {2021} }
Abstract for BibTeX entry CaldasEtAl2021

This PhD thesis aims to study the coupling of nonlinear shallow water models at different scales, with application to the numerical simulation of urban floods. Accurate simulations in this domain are usually prohibitively expensive due to the small mesh sizes necessary for the spatial discretization of the urban geometry and the associated small time steps constrained by stability conditions. Porosity-based shallow water models have been proposed in the past two decades as an alternative approach, consisting of upscaled models using larger mesh sizes and time steps and being able to provide good global approximations for the solution of the fine shallow water equations, with much smaller computational times. However, small-scale phenomena are not captured by this type of model. Therefore, we seek to formulate a numerical model coupling the fine and upscaled ones, in order to obtain more accurate solutions inside the urban zone, always with reduced computational costs relatively to the simulation of the fine model. The guideline for this objective lays on the use of predictor-corrector iterative parallel-in-time numerical methods, which naturally fit to this fine/coarse formulation. We focus on the parareal, one of the most popular parallel-in-time methods. As a main challenge, temporal parallelization suffers from instabilities and/or slow convergence when applied to hyperbolic or advection-dominated problems, such as the shallow water equations. Therefore, we consider a variant of the method using reduced-order models (ROMs) formulated on-the-fly along parareal iterations, using Proper Orthogonal Decomposition (POD) and the Empirical Interpolation Method (EIM), being able to improve the stability and convergence of the parareal method for solving nonlinear hyperbolic problems. We investigate the limitations of this ROM-based parareal method and we propose a number of modifications that provide further stability and convergence improvements: enrichment of the input snapshot sets used for the model reduction procedure; formulation of local-in-time ROMs; and incorporation of an adaptive parareal approach recently presented in the literature. The original and ROM-based parareal methods, including the proposed improvements, are compared and evaluated in terms of stability, convergence towards the fine solution and numerical speedup obtained in a parallel implementation. In a first part, the methods are formulated, studied and implemented considering a set of numerical simulations coupling the classical shallow water equations (without the porosity concept) at different scales. After this initial study, we implement them for coupling the classical and the porosity-based shallow water models, for the simulation of urban floods.
CaldasEtAl2021b

J. G. Caldas Steinstraesser, V. Guinot, and A. Rousseau, “Modified parareal method for solving the two-dimensional nonlinear shallow water equations using finite volumes,” The SMAI journal of computational mathematics, vol. 7, pp. 159–184, 2021, doi: 10.5802/smai-jcm.75. [Online]. Available at: https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.75/
BibTeX entry CaldasEtAl2021b

@article{CaldasEtAl2021b, author = {Caldas Steinstraesser, Jo\~{a}o Guilherme and Guinot, Vincent and Rousseau, Antoine}, doi = {10.5802/smai-jcm.75}, journal = {The SMAI journal of computational mathematics}, language = {en}, pages = {159--184}, publisher = {Soci\'et\'e de Math\'ematiques Appliqu\'ees et Industrielles}, title = {Modified parareal method for solving the two-dimensional nonlinear shallow water equations using finite volumes}, url = {https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.75/}, volume = {7}, year = {2021} }
Abstract for BibTeX entry CaldasEtAl2021b

In this work, the POD-DEIM-based parareal method introduced in [8] is implemented for solving the two-dimensional nonlinear shallow water equations using a finite volume scheme. This method is a variant of the traditional parareal method, first introduced by [22], that improves the stability and convergence for nonlinear hyperbolic problems, and uses reduced-order models constructed via the Proper Orthogonal Decomposition - Discrete Empirical Interpolation Method (POD-DEIM) applied to snapshots of the solution of the parareal iterations. We propose a modification of this parareal method for further stability and convergence improvements. It consists in enriching the snapshots set for the POD-DEIM procedure with extra snapshots whose computation does not require any additional computational cost. The performances of the classical parareal method, the POD-DEIM-based parareal method and our proposed modification are compared using numerical tests with increasing complexity. Our modified method shows a more stable behaviour and converges in fewer iterations than the other two methods.

M. Caliari, L. Einkemmer, A. Moriggl, and A. Ostermann, “An accurate and time-parallel rational exponential integrator for hyperbolic and oscillatory PDEs,” Journal of Computational Physics, vol. 437, p. 110289, Jul. 2021, doi: 10.1016/j.jcp.2021.110289. [Online]. Available at: https://doi.org/10.1016%2Fj.jcp.2021.110289

ChaudhryEtAl2021

J. Chaudhry, D. Estep, and S. Tavener, “A posteriori error analysis for a space-time parallel discretization of parabolic partial differential equations,” arXiv:2111.00606v1 [math.NA], 2021 [Online]. Available at: http://arxiv.org/abs/2111.00606v1
BibTeX entry ChaudhryEtAl2021

@unpublished{ChaudhryEtAl2021, author = {Chaudhry, Jehanzeb and Estep, Donald and Tavener, Simon}, howpublished = {arXiv:2111.00606v1 [math.NA]}, title = {A posteriori error analysis for a space-time parallel discretization of parabolic partial differential equations}, url = {http://arxiv.org/abs/2111.00606v1}, year = {2021} }
Abstract for BibTeX entry ChaudhryEtAl2021

We construct a space-time parallel method for solving parabolic partial differential equations by coupling the Parareal algorithm in time with overlapping domain decomposition in space. Reformulating the original Parareal algorithm as a variational method and implementing a finite element discretization in space enables an adjoint-based a posteriori error analysis to be performed. Through an appropriate choice of adjoint problems and residuals the error analysis distinguishes between errors arising due to the temporal and spatial discretizations, as well as between the errors arising due to incomplete Parareal iterations and incomplete iterations of the domain decomposition solver. We first develop an error analysis for the Parareal method applied to parabolic partial differential equations, and then refine this analysis to the case where the associated spatial problems are solved using overlapping domain decomposition. These constitute our Time Parallel Algorithm (TPA) and Space-Time Parallel Algorithm (STPA) respectively. Numerical experiments demonstrate the accuracy of the estimator for both algorithms and the iterations between distinct components of the error.

Y.-C. Chen and K. Nakajima, “Optimized Cascadic Multigrid Parareal Method for Explicit Time-Marching Schemes,” in 2021 12th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems (ScalA), 2021, doi: 10.1109/scala54577.2021.00007 [Online]. Available at: https://doi.org/10.1109/scala54577.2021.00007

T. Cheng, N. Lin, T. Liang, and V. Dinavahi, “Parallel-in-time-and-space electromagnetic transient simulation of multi-terminal DC grids with device-level switch modelling,” IET Generation, Transmission & Distribution, Sep. 2021, doi: 10.1049/gtd2.12285. [Online]. Available at: https://doi.org/10.1049/gtd2.12285

F. Danieli and A. J. Wathen, “All-at-once solution of linear wave equations,” Numerical Linear Algebra with Applications, May 2021, doi: 10.1002/nla.2386. [Online]. Available at: https://doi.org/10.1002/nla.2386

V. Dinavahi and N. Lin, “Parallel-in-Time EMT and Transient Stability Simulation of AC-DC Grids,” in Parallel Dynamic and Transient Simulation of Large-Scale Power Systems, Springer International Publishing, 2021, pp. 313–357 [Online]. Available at: https://doi.org/10.1007/978-3-030-86782-9_7

M. Donatelli, R. Krause, M. Mazza, and K. Trotti, “All-at-once multigrid approaches for one-dimensional space-fractional diffusion equations,” vol. 58, no. 4, Oct. 2021, doi: 10.1007/s10092-021-00436-3. [Online]. Available at: https://doi.org/10.1007/s10092-021-00436-3

A. C. Ellison and B. Fornberg, “A parallel-in-time approach for wave-type PDEs,” Numerische Mathematik, Apr. 2021, doi: 10.1007/s00211-021-01197-5. [Online]. Available at: https://doi.org/10.1007/s00211-021-01197-5

R. D. Falgout, T. A. Manteuffel, B. O’Neill, and J. B. Schroder, “Multigrid reduction in time with Richardson extrapolation,” ETNA - Electronic Transactions on Numerical Analysis, vol. 54, pp. 210–233, 2021, doi: 10.1553/etna_vol54s210. [Online]. Available at: https://doi.org/10.1553%2Fetna_vol54s210

L. Fang, S. Vandewalle, and J. Meyers, “A parallel-in-time multiple shooting algorithm for large-scale PDE-constrained optimal control problems,” Journal of Computational Physics, p. 110926, Dec. 2021, doi: 10.1016/j.jcp.2021.110926. [Online]. Available at: https://doi.org/10.1016/j.jcp.2021.110926

GanderEtAl2021

M. J. Gander, J. Liu, S.-L. Wu, X. Yue, and T. Zhou, “ParaDiag: parallel-in-time algorithms based on the diagonalization technique,” arXiv preprint arXiv:2005.09158, 2021 [Online]. Available at: http://arxiv.org/abs/2005.09158
BibTeX entry GanderEtAl2021

@unpublished{GanderEtAl2021, author = {Gander, Martin J and Liu, Jun and Wu, Shu-Lin and Yue, Xiaoqiang and Zhou, Tao}, howpublished = {arXiv preprint arXiv:2005.09158}, title = {ParaDiag: parallel-in-time algorithms based on the diagonalization technique}, url = {http://arxiv.org/abs/2005.09158}, year = {2021} }
Abstract for BibTeX entry GanderEtAl2021

In 2008, Maday and Rønquist introduced an interesting new approach for the direct parallel-in-time (PinT) solution of time-dependent PDEs. The idea is to diagonalize the time stepping matrix, keeping the matrices for the space discretization unchanged, and then to solve all time steps in parallel. Since then, several variants appeared, and we call these closely related algorithms \em ParaDiag algorithms. ParaDiag algorithms in the literature can be classified into two groups: \beginitemize \item ParaDiag-I: direct standalone solvers, \item ParaDiag-II: iterative solvers. \enditemize We will explain the basic features of each group in this note. To have concrete examples, we will introduce ParaDiag-I and ParaDiag-II for the advection-diffusion equation. We will also introduce ParaDiag-II for the wave equation and an optimal control problem for the wave equation. We could have used the advection-diffusion equation as well to illustrate ParaDiag-II, but wave equations are known to cause problems for certain PinT algorithms and thus constitute an especially interesting example for which ParaDiag algorithms were tested. We show the main known theoretical results in each case, and also provide Matlab codes for testing. The goal of the Matlab codes is to help the interested reader understand the key features of the ParaDiag algorithms, without intention to be highly tuned for efficiency and/or low memory use. We also provide speedup measurements of ParaDiag algorithms for a 2D linear advection-diffusion equation. These results are obtained on the Tianhe-1 supercomputer in China and the SIUE Campus Cluster in the US, which is a multi-array, configurable and cooperative parallel system, and we compare these results to the performance of parareal and MGRiT, two widely used PinT algorithms. In a forthcoming update of this note, we will provide more material on ParaDiag algorithms, in particular further Matlab codes and parallel computing results, also for more realistic applications.

S. Götschel, M. Minion, D. Ruprecht, and R. Speck, “Twelve Ways to Fool the Masses When Giving Parallel-in-Time Results,” in Springer Proceedings in Mathematics & Statistics, Springer International Publishing, 2021, pp. 81–94 [Online]. Available at: https://doi.org/10.1007/978-3-030-75933-9_4

L. Grigori, S. A. Hirstoaga, V.-T. Nguyen, and J. Salomon, “Reduced model-based parareal simulations of oscillatory singularly perturbed ordinary differential equations,” Journal of Computational Physics, vol. 436, p. 110282, Jul. 2021, doi: 10.1016/j.jcp.2021.110282. [Online]. Available at: https://doi.org/10.1016/j.jcp.2021.110282

R. Kumari, S. Prasad, A. Kumari, and A. Kumar, “Parallel in Time Simulation of Automatic Generation Control System for Near Real-Time Transient Stability Analysis,” in 2021 International Conference on Control, Automation, Power and Signal Processing (CAPS), 2021, doi: 10.1109/caps52117.2021.9730716 [Online]. Available at: https://doi.org/10.1109/caps52117.2021.9730716

S. Lakshmiranganatha and S. S. Muknahallipatna, “Performance Analysis of Accelerator Architectures and Programming Models for Parareal Algorithm Solutions of Ordinary Differential Equations,” Journal of Computer and Communications, vol. 09, no. 02, pp. 29–56, 2021, doi: 10.4236/jcc.2021.92003. [Online]. Available at: https://doi.org/10.4236/jcc.2021.92003

U. Langer and M. Zank, “Efficient Direct Space-Time Finite Element Solvers for Parabolic Initial-Boundary Value Problems in Anisotropic Sobolev Spaces,” SIAM Journal on Scientific Computing, vol. 43, no. 4, pp. A2714–A2736, Jan. 2021, doi: 10.1137/20m1358128. [Online]. Available at: https://doi.org/10.1137%2F20m1358128

S. Li, X. Shao, and R. Chen, “Multilevel space-time multiplicative Schwarz preconditioner for parabolic equations,” Numerical Linear Algebra with Applications, May 2021, doi: 10.1002/nla.2390. [Online]. Available at: https://doi.org/10.1002/nla.2390

X. Li and Y. Su, “A parallel in time/spectral collocation combined with finite difference method for the time fractional differential equations,” Journal of Algorithms & Computational Technology, vol. 15, p. 174830262110084, Jan. 2021, doi: 10.1177/17483026211008409. [Online]. Available at: https://doi.org/10.1177/17483026211008409

J. Li, P. Liu, and V. Dinavahi, “Space-Time-Parallel 3-D Finite Element Transformer Model with Adaptive TLM and Parareal Techniques for Electromagnetic Transient Analysis,” IEEE Open Journal of Industry Applications, pp. 1–1, 2021, doi: 10.1109/ojia.2021.3091557. [Online]. Available at: https://doi.org/10.1109/ojia.2021.3091557

J. Li, Y.-L. Jiang, and Z. Miao, “Analysis of the parareal approach based on discontinuous Galerkin method for time-dependent Stokes equations,” Numerical Methods for Partial Differential Equations, Jul. 2021, doi: 10.1002/num.22782. [Online]. Available at: https://doi.org/10.1002/num.22782

G. Li and J. Hu, “Wavelet-based Edge Multiscale Parareal Algorithm for Parabolic Equations with Heterogeneous Coefficients and Rough Initial Data,” Journal of Computational Physics, p. 110572, Jul. 2021, doi: 10.1016/j.jcp.2021.110572. [Online]. Available at: https://doi.org/10.1016/j.jcp.2021.110572

J. Li and Y.-L. Jiang, “The study of parareal algorithm for the linear switched systems,” p. 107763, Oct. 2021, doi: 10.1016/j.aml.2021.107763. [Online]. Available at: https://doi.org/10.1016/j.aml.2021.107763

X.-lei Lin, M. K. Ng, and Y. Zhi, “A parallel-in-time two-sided preconditioning for all-at-once system from a non-local evolutionary equation with weakly singular kernel,” Journal of Computational Physics, vol. 434, p. 110221, Jun. 2021, doi: 10.1016/j.jcp.2021.110221. [Online]. Available at: https://doi.org/10.1016%2Fj.jcp.2021.110221

LinEtAl2021b

X.-L. Lin and Z. Zhang, “A Parallel-in-Time Preconditioner for the Schur Complement of Parabolic Optimal Control Problems,” arXiv:2109.12524v2 [math.NA], 2021 [Online]. Available at: http://arxiv.org/abs/2109.12524v2
BibTeX entry LinEtAl2021b

@unpublished{LinEtAl2021b, author = {Lin, Xue-Lei and Zhang, Zhimin}, howpublished = {arXiv:2109.12524v2 [math.NA]}, title = {A Parallel-in-Time Preconditioner for the Schur Complement of Parabolic Optimal Control Problems}, url = {http://arxiv.org/abs/2109.12524v2}, year = {2021} }
Abstract for BibTeX entry LinEtAl2021b

For optimal control problems constrained by a initial-valued parabolic PDE, we have to solve a large scale saddle point algebraic system consisting of considering the discrete space and time points all together. A popular strategy to handle such a system is the Krylov subspace method, for which an efficient preconditioner plays a crucial role. The matching-Schur-complement preconditioner has been extensively studied in literature and the implementation of this preconditioner lies in solving the underlying PDEs twice, sequentially in time. In this paper, we propose a new preconditioner for the Schur complement, which can be used parallel-in-time (PinT) via the so called diagonalization technique. We show that the eigenvalues of the preconditioned matrix are low and upper bounded by positive constants independent of matrix size and the regularization parameter. The uniform boundedness of the eigenvalues leads to an optimal linear convergence rate of conjugate gradient solver for the preconditioned Schur complement system. To the best of our knowledge, it is the first time to have an optimal convergence analysis for a PinT preconditioning technique of the optimal control problem. Numerical results are reported to show that the performance of the proposed preconditioner is robust with respect to the discretization step-sizes and the regularization parameter.
LiuEtAl2021

J. Liu and S.-L. Wu, “Parallel-in-time preconditioners for the Sinc-Nyström method,” arXiv:2108.01700v1 [math.NA], 2021 [Online]. Available at: http://arxiv.org/abs/2108.01700v1
BibTeX entry LiuEtAl2021

@unpublished{LiuEtAl2021, author = {Liu, Jun and Wu, Shu-Lin}, howpublished = {arXiv:2108.01700v1 [math.NA]}, title = {Parallel-in-time preconditioners for the Sinc-Nyström method}, url = {http://arxiv.org/abs/2108.01700v1}, year = {2021} }
Abstract for BibTeX entry LiuEtAl2021

The Sinc-Nyström method in time is a high-order spectral method for solving evolutionary differential equations and it has wide applications in scientific computation. But in this method we have to solve all the time steps implicitly at one-shot, which may results in a large-scale nonsymmetric dense system that is expensive to solve. In this paper, we propose and analyze a parallel-in-time (PinT) preconditioner for solving such Sinc-Nyström systems, where both the parabolic and hyperbolic PDEs are investigated. Attributed to the special Toeplitz-like structure of the Sinc-Nyström systems, the proposed PinT preconditioner is indeed a low-rank perturbation of the system matrix and we show that the spectrum of the preconditioned system is highly clustered around one, especially when the time step size is refined. Such a clustered spectrum distribution matches very well with the numerically observed mesh-independent GMRES convergence rates in various examples. Several linear and nonlinear ODE and PDE examples are presented to illustrate the convergence performance of our proposed PinT preconditioners, where the achieved exponential order of accuracy are especially attractive to those applications in need of high accuracy.

C. Lyu, N. Lin, and V. Dinavahi, “Device-Level Parallel-in-time Simulation of MMC-Based Energy System for Electric Vehicles,” IEEE Transactions on Vehicular Technology, pp. 1–1, 2021, doi: 10.1109/tvt.2021.3081534. [Online]. Available at: https://doi.org/10.1109/tvt.2021.3081534

N. Margenberg and T. Richter, “Parallel time-stepping for fluid–structure interactions,” Mathematical Modelling of Natural Phenomena, vol. 16, p. 20, 2021, doi: 10.1051/mmnp/2021005. [Online]. Available at: https://doi.org/10.1051/mmnp/2021005

B. Park, K. Sun, A. Dimitrovski, Y. Liu, and S. Simunovic, “Examination of Semi-Analytical Solution Methods in the Coarse Operator of Parareal Algorithm for Power System Simulation,” IEEE Transactions on Power Systems, pp. 1–1, 2021, doi: 10.1109/tpwrs.2021.3069136. [Online]. Available at: https://doi.org/10.1109/tpwrs.2021.3069136

M. Patil and A. Datta, “Time-Parallel Scalable Solution of Periodic Rotor Dynamics for Large-Scale 3D Structures,” in AIAA Scitech 2021 Forum, 2021, doi: 10.2514/6.2021-1079 [Online]. Available at: https://doi.org/10.2514/6.2021-1079

A. Pels, I. Kulchytska-Ruchka, and S. Schöps, “Parallel-in-Time Simulation of Power Converters Using Multirate PDEs,” in Scientific Computing in Electrical Engineering, Springer International Publishing, 2021, pp. 33–41 [Online]. Available at: https://doi.org/10.1007%2F978-3-030-84238-3_4

J. Schütz, D. C. Seal, and J. Zeifang, “Parallel-in-Time High-Order Multiderivative IMEX Solvers,” Journal of Scientific Computing, vol. 90, no. 1, Dec. 2021, doi: 10.1007/s10915-021-01733-3. [Online]. Available at: https://doi.org/10.1007%2Fs10915-021-01733-3

A. A. Sivas, B. S. Southworth, and S. Rhebergen, “AIR Algebraic Multigrid for a Space-Time Hybridizable Discontinuous Galerkin Discretization of Advection(-Diffusion),” vol. 43, no. 5, pp. A3393–A3416, Jan. 2021, doi: 10.1137/20m1375103. [Online]. Available at: https://doi.org/10.1137%2F20m1375103

C. S. Skene, M. F. Eggl, and P. J. Schmid, “A parallel-in-time approach for accelerating direct-adjoint studies,” Journal of Computational Physics, vol. 429, p. 110033, Mar. 2021, doi: 10.1016/j.jcp.2020.110033. [Online]. Available at: https://doi.org/10.1016/j.jcp.2020.110033

Y. Sun, S.-L. Wu, and Y. Xu, “A Parallel-in-Time Implementation of the Numerov Method For Wave Equations,” Journal of Scientific Computing, vol. 90, no. 1, Nov. 2021, doi: 10.1007/s10915-021-01701-x. [Online]. Available at: https://doi.org/10.1007/s10915-021-01701-x

Y. Takahashi, K. Fujiwara, T. Iwashita, and H. Nakashima, “Comparison of Parallel-in-Space-and-Time Finite-Element Methods for Magnetic Field Analysis of Electric Machines,” IEEE Transactions on Magnetics, pp. 1–1, 2021, doi: 10.1109/tmag.2021.3064320. [Online]. Available at: https://doi.org/10.1109/tmag.2021.3064320

R. van Venetië and J. Westerdiep, “A Parallel Algorithm for Solving Linear Parabolic Evolution Equations,” Springer International Publishing, 2021, pp. 33–50 [Online]. Available at: https://doi.org/10.1007/978-3-030-75933-9_2

A. S. Walker and K. E. Niemeyer, “Applying the Swept Rule for Solving Two-Dimensional Partial Differential Equations on Heterogeneous Architectures,” Mathematical and Computational Applications, vol. 26, no. 3, p. 52, Jul. 2021, doi: 10.3390/mca26030052. [Online]. Available at: https://doi.org/10.3390/mca26030052

S.-L. Wu and T. Zhou, “Parallel implementation for the two-stage SDIRK methods via diagonalization,” Journal of Computational Physics, vol. 428, p. 110076, Mar. 2021, doi: 10.1016/j.jcp.2020.110076. [Online]. Available at: https://doi.org/10.1016/j.jcp.2020.110076

WuEtAl2021b

S. Wu, T. Zhou, and Z. Zhou, “Stability implies robust convergence of a class of preconditioned parallel-in-time iterative algorithms,” arXiv:2102.04646v2 [math.NA], 2021 [Online]. Available at: https://arxiv.org/abs/2102.04646v2
BibTeX entry WuEtAl2021b

@unpublished{WuEtAl2021b, author = {Wu, Shulin and Zhou, Tao and Zhou, Zhi}, howpublished = {arXiv:2102.04646v2 [math.NA]}, title = {Stability implies robust convergence of a class of preconditioned parallel-in-time iterative algorithms}, url = {https://arxiv.org/abs/2102.04646v2}, year = {2021} }
Abstract for BibTeX entry WuEtAl2021b

Solving evolutionary equations in a parallel-in-time manner is an attractive topic and many algorithms are proposed in recent two decades. The algorithm based on the block α-circulant preconditioning technique has shown promising advantages, especially for wave propagation problems. By fast Fourier transform for factorizing the involved circulant matrices, the preconditioned iteration can be computed efficiently via the so-called diagonalization technique, which yields a direct parallel implementation across all time levels. In recent years, considerable efforts have been devoted to exploring the convergence of the preconditioned iteration by studying the spectral radius of the iteration matrix, and this leads to many case-by-case studies depending on the used time-integrator. In this paper, we propose a unified convergence analysis for the algorithm applied to u’+Au=f, where σ(A)⊂\mathbbC^+ with σ(A) being the spectrum of A∈\mathbbC^m\times m. For any one-step method (such as the Runge-Kutta methods) with stability function \mathcalR(z), we prove that the decay rate of the global error is bounded by α/(1-α), provided the method is stable, i.e., \max_λ∈σ(A)|\mathcalR(∆tλ)|\leq1. For any linear multistep method, such a bound becomes cα/(1-cα), where c\geq1 is a constant specified by the multistep method itself. Our proof only relies on the stability of the time-integrator and the estimate is independent of the step size ∆t and the spectrum σ(A).

S. Wu and Z. Zhou, “A Parallel-in-Time Algorithm for High-Order BDF Methods for Diffusion and Subdiffusion Equations,” vol. 43, no. 6, pp. A3627–A3656, Jan. 2021, doi: 10.1137/20m1355690. [Online]. Available at: https://doi.org/10.1137/20m1355690

D. Xue, Y. Hou, and Y. Li, “Analysis of the local and parallel space-time algorithm for the heat equation,” Computers & Mathematics with Applications, vol. 100, pp. 167–181, Oct. 2021, doi: 10.1016/j.camwa.2021.09.008. [Online]. Available at: https://doi.org/10.1016/j.camwa.2021.09.008

X. Yue, K. Pan, J. Zhou, Z. Weng, S. Shu, and J. Tang, “A multigrid-reduction-in-time solver with a new two-level convergence for unsteady fractional Laplacian problems,” Computers & Mathematics with Applications, vol. 89, pp. 57–67, May 2021, doi: 10.1016/j.camwa.2021.02.020. [Online]. Available at: https://doi.org/10.1016/j.camwa.2021.02.020

Y. Zeng, Y. Duan, and B.-S. Liu, “Solving 2D parabolic equations by using time parareal coupling with meshless collocation RBFs methods,” Engineering Analysis with Boundary Elements, vol. 127, pp. 102–112, Jun. 2021, doi: 10.1016/j.enganabound.2021.03.008. [Online]. Available at: https://doi.org/10.1016/j.enganabound.2021.03.008

Y.-L. Zhao, X.-M. Gu, and A. Ostermann, “A Preconditioning Technique for an All-at-once System from Volterra Subdiffusion Equations with Graded Time Steps,” Journal of Scientific Computing, vol. 88, no. 1, May 2021, doi: 10.1007/s10915-021-01527-7. [Online]. Available at: https://doi.org/10.1007/s10915-021-01527-7

ZhaoEtAl2021b

Y.-L. Zhao, J. Wu, and X.-M. Gu, “On the bilateral preconditioning for a L2-type all-at-once system arising from time-space fractional Bloch-Torrey equations,” arXiv:2109.06510v1 [math.NA], 2021 [Online]. Available at: http://arxiv.org/abs/2109.06510v1
BibTeX entry ZhaoEtAl2021b

@unpublished{ZhaoEtAl2021b, author = {Zhao, Yong-Liang and Wu, Jing and Gu, Xian-Ming}, howpublished = {arXiv:2109.06510v1 [math.NA]}, title = {On the bilateral preconditioning for a L2-type all-at-once system arising from time-space fractional Bloch-Torrey equations}, url = {http://arxiv.org/abs/2109.06510v1}, year = {2021} }
Abstract for BibTeX entry ZhaoEtAl2021b

Time-space fractional Bloch-Torrey equations are developed by some researchers to investigate the relationship between diffusion and fractional-order dynamics. In this paper, we first propose a second-order scheme for this equation by employing the recently proposed L2-type formula [A. A. Alikhanov, C. Huang, Appl. Math. Comput. (2021) 126545]. Then, we prove the stability and the convergence of this scheme. Based on such the numerical scheme, a L2-type all-at-once system is derived. In order to solve this system in a parallel-in-time pattern, a bilateral preconditioning technique is designed according to the special structure of the system. We theoretically show that the condition number of the preconditioned matrix is uniformly bounded by a constant for the time fractional order α∈(0,0.3624). Numerical results are reported to show the efficiency of our method.

top

2020

AgbohEtAl2020

W. Agboh, O. Grainger, D. Ruprecht, and M. Dogar, “Parareal with a Learned Coarse Model for Robotic Manipulation,” Computing and Visualization in Science, vol. 23, no. 8, 2020 [Online]. Available at: https://doi.org/10.1007/s00791-020-00327-0
BibTeX entry AgbohEtAl2020

@article{AgbohEtAl2020, author = {Agboh, Wisdom and Grainger, Oliver and Ruprecht, Daniel and Dogar, Mehmet}, journal = {Computing and Visualization in Science}, number = {8}, title = {Parareal with a Learned Coarse Model for Robotic Manipulation}, url = {https://doi.org/10.1007/s00791-020-00327-0}, volume = {23}, year = {2020} }
Abstract for BibTeX entry AgbohEtAl2020

A key component of many robotics model-based planning and control algorithms is physics predictions, that is, forecasting a sequence of states given an initial state and a sequence of controls. This process is slow and a major computational bottleneck for robotics planning algorithms. Parallel-in-time integration methods can help to leverage parallel computing to accelerate physics predictions and thus planning. The Parareal algorithm iterates between a coarse serial integrator and a fine parallel integrator. A key challenge is to devise a coarse level model that is computationally cheap but accurate enough for Parareal to converge quickly. Here, we investigate the use of a deep neural network physics model as a coarse model for Parareal in the context of robotic manipulation. In simulated experiments using the physics engine Mujoco as fine propagator we show that the learned coarse model leads to faster Parareal convergence than a coarse physics-based model. We further show that the learned coarse model allows to apply Parareal to scenarios with multiple objects, where the physics-based coarse model is not applicable. Finally, We conduct experiments on a real robot and show that Parareal predictions are close to real-world physics predictions for robotic pushing of multiple objects. Some real robot manipulation plans using Parareal can be found at https://www.youtube.com/watch?v=wCh2o1rf-gA .

D. Bast, I. Kulchytska-Ruchka, S. Schoeps, and O. Rain, “Accelerated Steady-State Torque Computation for Induction Machines Using Parallel-In-Time Algorithms,” IEEE Transactions on Magnetics, pp. 1–1, 2020, doi: 10.1109/tmag.2019.2945510. [Online]. Available at: https://doi.org/10.1109/tmag.2019.2945510

C.-E. Brehier and X. Wang, “On Parareal Algorithms for Semilinear Parabolic Stochastic PDEs,” SIAM Journal on Numerical Analysis, vol. 58, no. 1, pp. 254–278, Jan. 2020, doi: 10.1137/19m1251011. [Online]. Available at: https://doi.org/10.1137/19m1251011

Buvoli2020

T. Buvoli, “Exponential Polynomial Time Integrators,” arXiv:2011.00670v1 [math.NA], 2020 [Online]. Available at: http://arxiv.org/abs/2011.00670v1
BibTeX entry Buvoli2020

@unpublished{Buvoli2020, author = {Buvoli, Tommaso}, howpublished = {arXiv:2011.00670v1 [math.NA]}, title = {Exponential Polynomial Time Integrators}, url = {http://arxiv.org/abs/2011.00670v1}, year = {2020} }
Abstract for BibTeX entry Buvoli2020

In this paper we extend the polynomial time integration framework to include exponential integration for both partitioned and unpartitioned initial value problems. We then demonstrate its utility by constructing a new class of parallel exponential block methods based on the Legendre points. These new integrators can be constructed at arbitrary orders of accuracy, have improved stability compared to existing polynomial based exponential linear multistep methods, and can offer significant computational savings compared to current state-of-the-art methods.
BuvoliEtAl2020

T. Buvoli and M. L. Minion, “IMEX Parareal Integrators,” arXiv:2011.01604v1 [math.NA], 2020 [Online]. Available at: http://arxiv.org/abs/2011.01604v1
BibTeX entry BuvoliEtAl2020

@unpublished{BuvoliEtAl2020, author = {Buvoli, Tommaso and Minion, Michael L.}, howpublished = {arXiv:2011.01604v1 [math.NA]}, title = {IMEX Parareal Integrators}, url = {http://arxiv.org/abs/2011.01604v1}, year = {2020} }
Abstract for BibTeX entry BuvoliEtAl2020

Parareal is a widely studied parallel-in-time method that can achieve meaningful speedup on certain problems. However, it is well known that the method typically performs poorly on dispersive equations. This paper analyzes linear stability and convergence for IMEX Runge-Kutta parareal methods on dispersive equations. By combining standard linear stability analysis with a simple convergence analysis, we find that certain parareal configurations can achieve parallel speedup on dispersive equations. These stable configurations all posses low iteration counts, large block sizes, and a large number of processors.

T. Cheng, T. Duan, and V. Dinavahi, “Parallel-in-Time Object-Oriented Electromagnetic Transient Simulation of Power Systems,” IEEE Open Access Journal of Power and Energy, pp. 1–1, 2020, doi: 10.1109/oajpe.2020.3012636. [Online]. Available at: https://doi.org/10.1109/oajpe.2020.3012636

C.-K. Cheng, C.-T. Ho, C. Jia, X. Wang, Z. Zen, and X. Zha, “A Parallel-in-Time Circuit Simulator for Power Delivery Networks with Nonlinear Load Models,” in 2020 IEEE 29th Conference on Electrical Performance of Electronic Packaging and Systems (EPEPS), 2020, doi: 10.1109/epeps48591.2020.9231406 [Online]. Available at: https://doi.org/10.1109/epeps48591.2020.9231406

J. Christopher, R. D. Falgout, J. B. Schroder, S. M. Guzik, and X. Gao, “A space-time parallel algorithm with adaptive mesh refinement for computational fluid dynamics,” Computing and Visualization in Science, vol. 23, no. 1-4, Sep. 2020, doi: 10.1007/s00791-020-00334-1. [Online]. Available at: https://doi.org/10.1007/s00791-020-00334-1

ClarkeEtAl2020a

A. T. Clarke, C. J. Davies, D. Ruprecht, and S. M. Tobias, “Parallel-in-time integration of Kinematic Dynamos,” Journal of Computational Physics: X, vol. 7, p. 100057, 2020, doi: 10.1016/j.jcpx.2020.100057. [Online]. Available at: https://doi.org/10.1016/j.jcpx.2020.100057
BibTeX entry ClarkeEtAl2020a

@article{ClarkeEtAl2020a, author = {Clarke, Andrew T. and Davies, Christopher J. and Ruprecht, Daniel and Tobias, Steven M.}, doi = {10.1016/j.jcpx.2020.100057}, journal = {Journal of Computational Physics: X}, pages = {100057}, title = {Parallel-in-time integration of Kinematic Dynamos}, url = {https://doi.org/10.1016/j.jcpx.2020.100057}, volume = {7}, year = {2020} }
Abstract for BibTeX entry ClarkeEtAl2020a

The precise mechanisms responsible for the natural dynamos in the Earth and Sun are still not fully understood. Numerical simulations of natural dynamos are extremely computationally intensive, and are carried out in parameter regimes many orders of magnitude away from real conditions. Parallelization in space is a common strategy to speed up simulations on high performance computers, but eventually hits a scaling limit. Additional directions of parallelization are desirable to utilise the high number of processor cores now available. Parallel-in-time methods can deliver speed up in addition to that offered by spatial partitioning but have not yet been applied to dynamo simulations. This paper investigates the feasibility of using the parallel-in-time algorithm Parareal to speed up initial value problem simulations of the kinematic dynamo, using the open source Dedalus spectral solver. Both the time independent Roberts and time dependent Galloway-Proctor 2.5D dynamos are investigated over a range of magnetic Reynolds numbers. Speedups beyond those possible from spatial parallelisation are found in both cases. Results for the Galloway-Proctor flow are promising, with Parareal efficiency found to be close to 0.3. Roberts flow results are less efficient, but Parareal still shows some speed up over spatial parallelisation alone. Parallel in space and time speed ups of ∼300 were found for 1600 cores for the Galloway-Proctor flow, with total parallel efficiency of ∼0.16.
ClarkeEtAl2020b

A. Clarke, C. Davies, D. Ruprecht, S. Tobias, and J. S. Oishi, “Performance of parallel-in-time integration for Rayleigh Bénard Convection,” Computing and Visualization in Science, vol. 23, no. 10, 2020 [Online]. Available at: https://doi.org/10.1007/s00791-020-00332-3
BibTeX entry ClarkeEtAl2020b

@article{ClarkeEtAl2020b, author = {Clarke, Andrew and Davies, Chris and Ruprecht, Daniel and Tobias, Steven and Oishi, Jeffrey S.}, journal = {Computing and Visualization in Science}, number = {10}, title = {Performance of parallel-in-time integration for {R}ayleigh {B}énard Convection}, url = {https://doi.org/10.1007/s00791-020-00332-3}, volume = {23}, year = {2020} }
Abstract for BibTeX entry ClarkeEtAl2020b

Rayleigh-Bénard convection (RBC) is a fundamental problem of fluid dynamics, with many applications to geophysical, astrophysical, and industrial flows. Understanding RBC at parameter regimes of interest requires complex physical or numerical experiments. Numerical simulations require large amounts of computational resources; in order to more efficiently use the large numbers of processors now available in large high performance computing clusters, novel parallelisation strategies are required. To this end, we investigate the performance of the parallel-in-time algorithm Parareal when used in numerical simulations of RBC. We present the first parallel-in-time speedups for RBC simulations at finite Prandtl number. We also investigate the problem of convergence of Parareal with respect to to statistical numerical quantities, such as the Nusselt number, and discuss the importance of reliable online stopping criteria in these cases.

L. D’Amore and R. Cacciapuoti, “Model Reduction in Space and Time for the ab initio decomposition of 4D Variational Data Assimilation Problems,” Applied Numerical Mathematics, Oct. 2020, doi: 10.1016/j.apnum.2020.10.003. [Online]. Available at: https://doi.org/10.1016/j.apnum.2020.10.003

FlamantEtAl2020

C. Flamant, P. Protopapas, and D. Sondak, “Solving Differential Equations Using Neural Network Solution Bundles,” arXiv:2006.14372v1 [cs.LG], 2020 [Online]. Available at: http://arxiv.org/abs/2006.14372v1
BibTeX entry FlamantEtAl2020

@unpublished{FlamantEtAl2020, author = {Flamant, Cedric and Protopapas, Pavlos and Sondak, David}, howpublished = {arXiv:2006.14372v1 [cs.LG]}, title = {Solving Differential Equations Using Neural Network Solution Bundles}, url = {http://arxiv.org/abs/2006.14372v1}, year = {2020} }
Abstract for BibTeX entry FlamantEtAl2020

The time evolution of dynamical systems is frequently described by ordinary differential equations (ODEs), which must be solved for given initial conditions. Most standard approaches numerically integrate ODEs producing a single solution whose values are computed at discrete times. When many varied solutions with different initial conditions to the ODE are required, the computational cost can become significant. We propose that a neural network be used as a solution bundle, a collection of solutions to an ODE for various initial states and system parameters. The neural network solution bundle is trained with an unsupervised loss that does not require any prior knowledge of the sought solutions, and the resulting object is differentiable in initial conditions and system parameters. The solution bundle exhibits fast, parallelizable evaluation of the system state, facilitating the use of Bayesian inference for parameter estimation in real dynamical systems.

M. J. Gander and T. Lunet, “ParaStieltjes: Parallel computation of Gauss quadrature rules using a Parareal-like approach for the Stieltjes procedure,” Numerical Linear Algebra with Applications, Jun. 2020, doi: 10.1002/nla.2314. [Online]. Available at: https://doi.org/10.1002/nla.2314

M. J. Gander, F. Kwok, and J. Salomon, “PARAOPT: A Parareal Algorithm for Optimality Systems,” SIAM Journal on Scientific Computing, vol. 42, no. 5, pp. A2773–A2802, Jan. 2020, doi: 10.1137/19m1292291. [Online]. Available at: https://doi.org/10.1137/19m1292291

M. J. Gander and S.-L. Wu, “A Diagonalization-Based Parareal Algorithm for Dissipative and Wave Propagation Problems,” SIAM Journal on Numerical Analysis, vol. 58, no. 5, pp. 2981–3009, Jan. 2020, doi: 10.1137/19m1271683. [Online]. Available at: https://doi.org/10.1137/19m1271683

M. J. Gander, I. Kulchytska-Ruchka, and S. Schöps, “A New Parareal Algorithm for Time-Periodic Problems with Discontinuous Inputs,” in Lecture Notes in Computational Science and Engineering, Springer International Publishing, 2020, pp. 243–250 [Online]. Available at: https://doi.org/10.1007/978-3-030-56750-7_27

I. C. Garcia, I. Kulchytska-Ruchka, M. Clemens, and S. Schops, “Parallel-in-Time Solution of Eddy Current Problems Using Implicit and Explicit Time-stepping Methods,” in 2020 IEEE 19th Biennial Conference on Electromagnetic Field Computation (CEFC), 2020, doi: 10.1109/cefc46938.2020.9451465 [Online]. Available at: https://doi.org/10.1109%2Fcefc46938.2020.9451465

A. Garmon and D. Perez, “Exploiting Model Uncertainty to Improve the Scalability of Long-Time Simulations using Parallel Trajectory Splicing,” Modelling and Simulation in Materials Science and Engineering, Jul. 2020, doi: 10.1088/1361-651x/aba511. [Online]. Available at: https://doi.org/10.1088/1361-651x/aba511

X.-M. Gu and S.-L. Wu, “A parallel-in-time iterative algorithm for Volterra partial integro-differential problems with weakly singular kernel,” Journal of Computational Physics, vol. 417, p. 109576, Sep. 2020, doi: 10.1016/j.jcp.2020.109576. [Online]. Available at: https://doi.org/10.1016/j.jcp.2020.109576

S. Günther, L. Ruthotto, J. B. Schroder, E. C. Cyr, and N. R. Gauger, “Layer-Parallel Training of Deep Residual Neural Networks,” SIAM Journal on Mathematics of Data Science, vol. 2, no. 1, pp. 1–23, Jan. 2020, doi: 10.1137/19m1247620. [Online]. Available at: https://doi.org/10.1137/19m1247620

HahneEtAl2020

J. Hahne, S. Friedhoff, and M. Bolten, “PyMGRIT: A Python Package for the parallel-in-time method MGRIT,” arXiv:2008.05172v1 [cs.MS], 2020 [Online]. Available at: http://arxiv.org/abs/2008.05172v1
BibTeX entry HahneEtAl2020

@unpublished{HahneEtAl2020, author = {Hahne, Jens and Friedhoff, Stephanie and Bolten, Matthias}, howpublished = {arXiv:2008.05172v1 [cs.MS]}, title = {PyMGRIT: A Python Package for the parallel-in-time method MGRIT}, url = {http://arxiv.org/abs/2008.05172v1}, year = {2020} }
Abstract for BibTeX entry HahneEtAl2020

In this paper, we introduce the Python framework PyMGRIT, which implements the multigrid-reduction-in-time (MGRIT) algorithm for solving the (non-)linear systems arising from the discretization of time-dependent problems. The MGRIT algorithm is a reduction-based iterative method that allows parallel-in-time simulations, i. e., calculating multiple time steps simultaneously in a simulation, by using a time-grid hierarchy. The PyMGRIT framework features many different variants of the MGRIT algorithm, ranging from different multigrid cycle types and relaxation schemes, as well as various coarsening strategies, including time-only and space-time coarsening, to using different time integrators on different levels in the multigrid hierachy. PyMGRIT allows serial runs for prototyping and testing of new approaches, as well as parallel runs using the Message Passing Interface (MPI). Here, we describe the implementation of the MGRIT algorithm in PyMGRIT and present the usage from both user and developer point of views. Three examples illustrate different aspects of the package, including pure time parallelism as well as space-time parallelism by coupling PyMGRIT with PETSc or Firedrake, which enable spatial parallelism through MPI.

F. P. Hamon, M. Schreiber, and M. L. Minion, “Parallel-in-time multi-level integration of the shallow-water equations on the rotating sphere,” Journal of Computational Physics, vol. 407, p. 109210, Apr. 2020, doi: 10.1016/j.jcp.2019.109210. [Online]. Available at: https://doi.org/10.1016/j.jcp.2019.109210

A. Hessenthaler, B. S. Southworth, D. Nordsletten, O. Röhrle, R. D. Falgout, and J. B. Schroder, “Multilevel Convergence Analysis of Multigrid-Reduction-in-Time,” SIAM Journal on Scientific Computing, vol. 42, no. 2, pp. A771–A796, Jan. 2020, doi: 10.1137/19m1238812. [Online]. Available at: https://doi.org/10.1137/19m1238812

N. E. Hodge, “Towards Improved Speed and Accuracy of Laser Powder Bed FusionSimulations via Representation of Multiple Time Scales,” Additive Manufacturing, p. 101600, Oct. 2020, doi: 10.1016/j.addma.2020.101600. [Online]. Available at: https://doi.org/10.1016/j.addma.2020.101600

X. Hu, C. Rodrigo, and F. J. Gaspar, “Using hierarchical matrices in the solution of the time-fractional heat equation by multigrid waveform relaxation,” Journal of Computational Physics, p. 109540, May 2020, doi: 10.1016/j.jcp.2020.109540. [Online]. Available at: https://doi.org/10.1016/j.jcp.2020.109540

K. Jałowiecki, A. Więckowski, P. Gawron, and B. Gardas, “Parallel in time dynamics with quantum annealers,” Scientific Reports, vol. 10, no. 1, Aug. 2020, doi: 10.1038/s41598-020-70017-x. [Online]. Available at: https://doi.org/10.1038/s41598-020-70017-x

A. Kirby, S. Samsi, M. Jones, A. Reuther, J. Kepner, and V. Gadepally, “Layer-Parallel Training with GPU Concurrency of Deep Residual Neural Networks via Nonlinear Multigrid,” in 2020 IEEE High Performance Extreme Computing Conference (HPEC), 2020, doi: 10.1109/hpec43674.2020.9286180 [Online]. Available at: https://doi.org/10.1109/hpec43674.2020.9286180

S. Lakshmiranganatha and S. S. Muknahallipatna, “Graphical Processing Unit Based Time-Parallel Numerical Method for Ordinary Differential Equations,” Journal of Computer and Communications, vol. 08, no. 02, pp. 39–63, 2020, doi: 10.4236/jcc.2020.82004. [Online]. Available at: https://doi.org/10.4236/jcc.2020.82004

F. Legoll, T. Lelièvre, K. Myerscough, and G. Samaey, “Parareal computation of stochastic differential equations with time-scale separation: a numerical convergence study,” Computing and Visualization in Science, vol. 23, no. 1-4, Sep. 2020, doi: 10.1007/s00791-020-00329-y. [Online]. Available at: https://doi.org/10.1007/s00791-020-00329-y

H. Liu, A. Cheng, and H. Wang, “A Parareal Finite Volume Method for Variable-Order Time-Fractional Diffusion Equations,” Journal of Scientific Computing, vol. 85, no. 1, Oct. 2020, doi: 10.1007/s10915-020-01321-x. [Online]. Available at: https://doi.org/10.1007/s10915-020-01321-x

LiuEtAl2020b

J. Liu and Z. Wang, “A ROM-accelerated parallel-in-time preconditioner for solving all-at-once systems from evolutionary PDEs,” arXiv:2012.09148v1 [math.NA], 2020 [Online]. Available at: http://arxiv.org/abs/2012.09148v1
BibTeX entry LiuEtAl2020b

@unpublished{LiuEtAl2020b, author = {Liu, Jun and Wang, Zhu}, howpublished = {arXiv:2012.09148v1 [math.NA]}, title = {A ROM-accelerated parallel-in-time preconditioner for solving all-at-once systems from evolutionary PDEs}, url = {http://arxiv.org/abs/2012.09148v1}, year = {2020} }
Abstract for BibTeX entry LiuEtAl2020b

In this paper we propose to use model reduction techniques for speeding up the diagonalization-based parallel-in-time (ParaDIAG) preconditioner, for iteratively solving all-at-once systems from evolutionary PDEs. In particular, we use the reduced basis method to seek a low-dimensional approximation to the sequence of complex-shifted systems arising from Step-(b) of the ParaDIAG preconditioning procedure. Different from the standard reduced order modeling that uses the separation of offline and online stages, we have to build the reduced order model (ROM) online for the considered systems at each iteration. Therefore, several heuristic acceleration techniques are introduced in the greedy basis generation algorithm, that is built upon a residual-based error indicator, to further boost up its computational efficiency. Several numerical experiments are conducted, which illustrate the favorable computational efficiency of our proposed ROM-accelerated ParaDIAG preconditioner, in comparison with the state of the art multigrid-based ParaDIAG preconditioner.

J. Liu and S.-L. Wu, “A Fast Block \textdollar}alpha\textdollar-Circulant Preconditoner for All-at-Once Systems From Wave Equations,” SIAM Journal on Matrix Analysis and Applications, vol. 41, no. 4, pp. 1912–1943, Jan. 2020, doi: 10.1137/19m1309869. [Online]. Available at: https://doi.org/10.1137/19m1309869

E. Lorin, “Derivation and analysis of parallel-in-time neural ordinary differential equations,” Annals of Mathematics and Artificial Intelligence, Jul. 2020, doi: 10.1007/s10472-020-09702-6. [Online]. Available at: https://doi.org/10.1007/s10472-020-09702-6

Y. Maday and O. Mula, “An adaptive parareal algorithm,” Journal of Computational and Applied Mathematics, vol. 377, p. 112915, Oct. 2020, doi: 10.1016/j.cam.2020.112915. [Online]. Available at: https://doi.org/10.1016/j.cam.2020.112915

X. Meng, Z. Li, D. Zhang, and G. E. Karniadakis, “PPINN: Parareal physics-informed neural network for time-dependent PDEs,” Computer Methods in Applied Mechanics and Engineering, vol. 370, p. 113250, Oct. 2020, doi: 10.1016/j.cma.2020.113250. [Online]. Available at: https://doi.org/10.1016/j.cma.2020.113250

NguyenTsai2020

H. Nguyen and R. Tsai, “A stable parareal-like method for the second order wave equation,” Journal of Computational Physics, vol. 405, p. 109156, 2020, doi: https://doi.org/10.1016/j.jcp.2019.109156. [Online]. Available at: http://www.sciencedirect.com/science/article/pii/S0021999119308617
BibTeX entry NguyenTsai2020

@article{NguyenTsai2020, author = {Nguyen, Hieu and Tsai, Richard}, doi = {https://doi.org/10.1016/j.jcp.2019.109156}, issn = {0021-9991}, journal = {Journal of Computational Physics}, keywords = {Parallel-in-time, Wave equation, Procrustes problem}, pages = {109156}, title = {A stable parareal-like method for the second order wave equation}, url = {http://www.sciencedirect.com/science/article/pii/S0021999119308617}, volume = {405}, year = {2020} }
Abstract for BibTeX entry NguyenTsai2020

A new parallel-in-time iterative method is proposed for solving the homogeneous second-order wave equation. The new method involves a coarse scale propagator, allowing for larger time steps, and a fine scale propagator which fully resolves the medium using finer spatial grid and uses shorter time steps. The fine scale propagator is run in parallel for short time intervals. The two propagators are coupled in an iterative way that resembles the standard parareal method [24]. We present a data-driven strategy in which the computed data gathered from each iteration are re-used to stabilize the coupling by minimizing the wave energy residual of the fine and coarse propagated solutions. Several examples, including a wave speed with discontinuities, are provided to demonstrate the effectiveness of the proposed method.

B. W. Ong and J. B. Schroder, “Applications of time parallelization,” Computing and Visualization in Science, vol. 23, no. 1-4, Sep. 2020, doi: 10.1007/s00791-020-00331-4. [Online]. Available at: https://doi.org/10.1007/s00791-020-00331-4

B. Park et al., “Performance and Feature Improvements in Parareal-based Power System Dynamic Simulation,” in 2020 IEEE International Conference on Power Systems Technology (POWERCON), 2020, doi: 10.1109/powercon48463.2020.9230544 [Online]. Available at: https://doi.org/10.1109/powercon48463.2020.9230544

H. Rittich and R. Speck, “Time-parallel simulation of the Schrödinger Equation,” Computer Physics Communications, vol. 255, p. 107363, Oct. 2020, doi: 10.1016/j.cpc.2020.107363. [Online]. Available at: https://doi.org/10.1016/j.cpc.2020.107363

R. Schöbel and R. Speck, “PFASST-ER: combining the parallel full approximation scheme in space and time with parallelization across the method,” Computing and Visualization in Science, vol. 23, no. 1-4, Sep. 2020, doi: 10.1007/s00791-020-00330-5. [Online]. Available at: https://doi.org/10.1007/s00791-020-00330-5

L. Z. sci, “Convergence Analysis of Parareal Algorithm Based on Milstein Scheme for Stochastic Differential Equations,” Journal of Computational Mathematics, vol. 38, no. 3, pp. 487–501, Jun. 2020, doi: 10.4208/jcm.1901-m2018-0085. [Online]. Available at: https://doi.org/10.4208/jcm.1901-m2018-0085

B. Song, Y.-L. Jiang, and X. Wang, “Analysis of two new parareal algorithms based on the Dirichlet-Neumann/Neumann-Neumann waveform relaxation method for the heat equation,” Numerical Algorithms, Jun. 2020, doi: 10.1007/s11075-020-00949-y. [Online]. Available at: https://doi.org/10.1007/s11075-020-00949-y

B. Stump and A. Plotkowski, “Spatiotemporal parallelization of an analytical heat conduction model for additive manufacturing via a hybrid OpenMP \mathplus MPI approach,” Computational Materials Science, vol. 184, p. 109861, Nov. 2020, doi: 10.1016/j.commatsci.2020.109861. [Online]. Available at: https://doi.org/10.1016/j.commatsci.2020.109861

S.-L. Wu and J. Liu, “A Parallel-In-Time Block-Circulant Preconditioner for Optimal Control of Wave Equations,” SIAM Journal on Scientific Computing, vol. 42, no. 3, pp. A1510–A1540, Jan. 2020, doi: 10.1137/19m1289613. [Online]. Available at: https://doi.org/10.1137/19m1289613

WuEtAl2020b

S. Wu and Z. Zhou, “Parallel-in-time high-order BDF schemes for diffusion and subdiffusion equations,” arXiv:2007.13125v1 [math.NA], 2020 [Online]. Available at: http://arxiv.org/abs/2007.13125v1
BibTeX entry WuEtAl2020b

@unpublished{WuEtAl2020b, author = {Wu, Shuonan and Zhou, Zhi}, howpublished = {arXiv:2007.13125v1 [math.NA]}, title = {Parallel-in-time high-order BDF schemes for diffusion and subdiffusion equations}, url = {http://arxiv.org/abs/2007.13125v1}, year = {2020} }
Abstract for BibTeX entry WuEtAl2020b

In this paper, we propose a parallel-in-time algorithm for approximately solving parabolic equations. In particular, we apply the k-step backward differentiation formula, and then develop an iterative solver by using the waveform relaxation technique. Each resulting iterate represents a periodic-like system, which could be further solved in parallel by using the diagonalization technique. The convergence of the waveform relaxation iteration is theoretically examined by using the generating function method. The approach we established in this paper extends the existing argument of single-step methods in Gander and Wu [Numer. Math., 143 (2019), pp. 489–527] to general BDF methods up to order 6. The argument could be further applied to the time-fractional subdiffusion equation, whose discretization shares common properties of the standard BDF methods, because of the nonlocality of the fractional differential operator. Illustrative numerical results are presented to complement the theoretical analysis.

S.-L. Wu and T. Zhou, “Diagonalization-based parallel-in-time algorithms for parabolic PDE-constrained optimization problems,” ESAIM: Control, Optimisation and Calculus of Variations, vol. 26, p. 88, 2020, doi: 10.1051/cocv/2020012. [Online]. Available at: https://doi.org/10.1051/cocv/2020012

Y.-L. Zhao, X.-M. Gu, M. Li, and H.-Y. Jian, “Preconditioners for all-at-once system from the fractional mobile/immobile advection–diffusion model,” Journal of Applied Mathematics and Computing, Jul. 2020, doi: 10.1007/s12190-020-01410-y. [Online]. Available at: https://doi.org/10.1007/s12190-020-01410-y

ZhaoEtAl2020b

Y.-L. Zhao, X.-M. Gu, and A. Ostermann, “A parallel preconditioning technique for an all-at-once system from subdiffusion equations with variable time steps,” arXiv:2007.14636v1 [math.NA], 2020 [Online]. Available at: http://arxiv.org/abs/2007.14636v1
BibTeX entry ZhaoEtAl2020b

@unpublished{ZhaoEtAl2020b, author = {Zhao, Yong-Liang and Gu, Xian-Ming and Ostermann, Alexander}, howpublished = {arXiv:2007.14636v1 [math.NA]}, title = {A parallel preconditioning technique for an all-at-once system from subdiffusion equations with variable time steps}, url = {http://arxiv.org/abs/2007.14636v1}, year = {2020} }
Abstract for BibTeX entry ZhaoEtAl2020b

Volterra subdiffusion problems with weakly singular kernel describe the dynamics of subdiffusion processes well.The graded L1 scheme is often chosen to discretize such problems since it can handle the singularity of the solution near t = 0. In this paper, we propose a modification. We first split the time interval [0, T] into [0, T_0] and [T_0, T], where T_0 (0 < T_0 < T) is reasonably small. Then, the graded L1 scheme is applied in [0, T_0], while the uniform one is used in [T_0, T]. Our all-at-once system is derived based on this strategy. In order to solve the arising system efficiently, we split it into two subproblems and design two preconditioners. Some properties of these two preconditioners are also investigated. Moreover, we extend our method to solve semilinear subdiffusion problems. Numerical results are reported to show the efficiency of our method.

top

2019

BlumersEtAl2019

A. L. Blumers, Z. Li, and G. E. Karniadakis, “Supervised parallel-in-time algorithm for long-time Lagrangian simulations of stochastic dynamics: Application to hydrodynamics,” Journal of Computational Physics, vol. 393, pp. 214–228, 2019, doi: 10.1016/j.jcp.2019.05.016. [Online]. Available at: https://doi.org/10.1016/j.jcp.2019.05.016
BibTeX entry BlumersEtAl2019

@article{BlumersEtAl2019, author = {Blumers, Ansel L. and Li, Zhen and Karniadakis, George Em}, doi = {10.1016/j.jcp.2019.05.016}, journal = {Journal of Computational Physics}, pages = {214 - 228}, title = {Supervised parallel-in-time algorithm for long-time Lagrangian simulations of stochastic dynamics: Application to hydrodynamics}, url = {https://doi.org/10.1016/j.jcp.2019.05.016}, volume = {393}, year = {2019} }
Abstract for BibTeX entry BlumersEtAl2019

Lagrangian particle methods based on detailed atomic and molecular models are powerful computational tools for studying the dynamics of microscale and nanoscale systems. However, the maximum time step is limited by the smallest oscillation period of the fastest atomic motion, rendering long-time simulations very expensive. To resolve this bottleneck, we propose a supervised parallel-in-time algorithm for stochastic dynamics (SPASD) to accelerate long-time Lagrangian particle simulations. Our method is inspired by bottom-up coarse-graining projections that yield mean-field hydrodynamic behavior in the continuum limit. Here as an example, we use the dissipative particle dynamics (DPD) as the Lagrangian particle simulator that is supervised by its macroscopic counterpart, i.e., the Navier-Stokes simulator. The low-dimensional macroscopic system (here, the Navier-Stokes solver) serves as a predictor to supervise the high-dimensional Lagrangian simulator, in a predictor-corrector type algorithm. The results of the Lagrangian simulation then correct the mean-field prediction and provide the proper microscopic details (e.g., consistent fluctuations, correlations, etc.). The unique feature that sets SPASD apart from other multiscale methods is the use of a low-fidelity macroscopic model as a predictor. The macro-model can be approximate and even inconsistent with the microscale description, but SPASD anticipates the deviation and corrects it internally to recover the true dynamics. We first present the algorithm and analyze its theoretical speedup, and subsequently we present the accuracy and convergence of the algorithm for the time-dependent plane Poiseuille flow, demonstrating that SPASD converges exponentially fast over iterations, irrespective of the accuracy of the predictor. Moreover, the fluctuating characteristics of the stochastic dynamics are identical to the unsupervised (serial in time) DPD simulation. We also compare the performance of SPASD to the conventional spatial decomposition method, which is one of the most parallel-efficient methods for particle simulations. We find that the parallel efficiency of SPASD and the conventional spatial decomposition method are similar for a small number of computing cores, but for a large number of cores the performance of SPASD is superior. Furthermore, SPASD can be used in conjunction with spatial decomposition for enhanced performance. Lastly, we simulate a two-dimensional cavity flow that requires more iterations to converge compared to the Poiseuille flow, and we observe that SPASD converges to the correct solution. Although a DPD solver is used to demonstrate the results, SPASD is a general framework and can be readily applied to other Lagrangian approaches including molecular dynamics and Langevin dynamics.

K. Carlberg, L. Brencher, B. Haasdonk, and A. Barth, “Data-Driven Time Parallelism via Forecasting,” SIAM Journal on Scientific Computing, vol. 41, no. 3, pp. B466–B496, Jan. 2019, doi: 10.1137/18m1174362. [Online]. Available at: https://doi.org/10.1137/18m1174362

DohrEtAl2019

S. Dohr, J. Zapletal, G. Of, M. Merta, and M. Kravčenko, “A parallel space–time boundary element method for the heat equation,” Computers & Mathematics with Applications, 2019, doi: https://doi.org/10.1016/j.camwa.2018.12.031. [Online]. Available at: http://www.sciencedirect.com/science/article/pii/S0898122118307296
BibTeX entry DohrEtAl2019

@article{DohrEtAl2019, author = {Dohr, Stefan and Zapletal, Jan and Of, Günther and Merta, Michal and Kravčenko, Michal}, doi = {https://doi.org/10.1016/j.camwa.2018.12.031}, journal = {Computers \& Mathematics with Applications}, title = {A parallel space–time boundary element method for the heat equation}, url = {http://www.sciencedirect.com/science/article/pii/S0898122118307296}, year = {2019} }
Abstract for BibTeX entry DohrEtAl2019

In this paper we introduce a new parallel solver for the weakly singular space–time boundary integral equation for the heat equation. The space–time boundary mesh is decomposed into a given number of submeshes. Pairs of the submeshes represent dense blocks in the system matrices, which are distributed among computational nodes by an algorithm based on a cyclic decomposition of complete graphs ensuring load balance. In addition, we employ vectorization and threading in shared memory to ensure intra-node efficiency. We present scalability experiments on different CPU architectures to evaluate the performance of the proposed parallelization techniques. All levels of parallelism allow us to tackle large problems and lead to an almost optimal speedup.

S. Friedhoff, J. Hahne, I. Kulchytska-Ruchka, and S. Schöps, “Exploring Parallel-in-Time Approaches for Eddy Current Problems,” in Progress in Industrial Mathematics at ECMI 2018, Springer International Publishing, 2019, pp. 373–379 [Online]. Available at: https://doi.org/10.1007/978-3-030-27550-1_47

S. Friedhoff, J. Hahne, and S. Schöps, “Multigrid-reduction-in-time for Eddy Current problems,” PAMM, vol. 19, no. 1, Nov. 2019, doi: 10.1002/pamm.201900262. [Online]. Available at: https://doi.org/10.1002/pamm.201900262

FriedhoffSouthworth2019

S. Friedhoff and B. S. Southworth, “On ‘Optimal’ h-Independent Convergence of Parareal and MGRIT Using Runge-Kutta Time Integration,” arXiv:1906.06672 [math.NA], 2019 [Online]. Available at: https://arxiv.org/abs/1906.06672
BibTeX entry FriedhoffSouthworth2019

@unpublished{FriedhoffSouthworth2019, author = {Friedhoff, Stephanie and Southworth, Ben S.}, howpublished = {arXiv:1906.06672 [math.NA]}, title = {On ``{O}ptimal'' h-{I}ndependent {C}onvergence of {P}arareal and {MGRIT} {U}sing {R}unge-{K}utta {T}ime {I}ntegration}, url = {https://arxiv.org/abs/1906.06672}, year = {2019} }
Abstract for BibTeX entry FriedhoffSouthworth2019

Parareal algorithms are studied for semilinear parabolic stochastic partial differential equations. These algorithms proceed as two-level integrators, with fine and coarse schemes, and have been designed to achieve a ‘parallel in real time’ implementation. In this work, the fine integrator is given by the exponential Euler scheme. Two choices for the coarse integrator are considered: the linear implicit Euler scheme, and the exponential Euler scheme. The influence on the performance of the parareal algorithm, of the choice of the coarse integrator, of the regularity of the noise, and of the number of parareal iterations, is investigated, with theoretical analysis results and with extensive numerical experiments.
GanderEtAl2019

M. Gander, L. Halpern, J. Rannou, and J. Ryan, “A Direct Time Parallel Solver by Diagonalization for the Wave Equation,” SIAM Journal on Scientific Computing, vol. 41, no. 1, pp. A220–A245, 2019, doi: 10.1137/17M1148347. [Online]. Available at: https://doi.org/10.1137/17M1148347
BibTeX entry GanderEtAl2019

@article{GanderEtAl2019, author = {Gander, M. and Halpern, L. and Rannou, J. and Ryan, J.}, doi = {10.1137/17M1148347}, journal = {SIAM Journal on Scientific Computing}, number = {1}, pages = {A220--A245}, title = {A Direct Time Parallel Solver by Diagonalization for the Wave Equation}, url = {https://doi.org/10.1137/17M1148347}, volume = {41}, year = {2019} }
Abstract for BibTeX entry GanderEtAl2019

With the advent of very large scale parallel computers, it has become more and more important to also use the time direction for parallelization when solving evolution problems. While there are many successful algorithms for diffusive problems, only some of them are also effective for hyperbolic problems. We present here a mathematical analysis of a new method based on the diagonalization of the time stepping matrix proposed by Maday and Rønquist in 2007. Like many time-parallelization methods, at first this does not seem to be a very promising approach: the matrix is essentially triangular, or, for equidistant time steps, actually a Jordan block, and thus not diagonalizable. If one chooses however different time steps, diagonalization is possible, and one has to trade off between the accuracy due to necessarily having different time steps, and numerical errors in the diagonalization process of these almost nondiagonalizable matrices. We present for the first time such a diagonalization technique for the Newmark scheme for solving wave equations, and derive a mathematically rigorous optimization strategy for the choice of the parameters in the special case when the Newmark scheme becomes Crank–Nicolson. Our analysis shows that small to medium scale time parallelization is possible with this approach. We illustrate our results with numerical experiments for model wave equations in various dimensions and also an industrial test case for the elasticity equations with variable coefficients.
GanderEtAl2019b

M. Gander, Y. Jiang, and B. Song, “A Superlinear Convergence Estimate for the Parareal Schwarz Waveform Relaxation Algorithm,” SIAM Journal on Scientific Computing, vol. 41, no. 2, pp. A1148–A1169, 2019, doi: 10.1137/18M1177226. [Online]. Available at: https://doi.org/10.1137/18M1177226
BibTeX entry GanderEtAl2019b

@article{GanderEtAl2019b, author = {Gander, M. and Jiang, Y. and Song, B.}, doi = {10.1137/18M1177226}, journal = {SIAM Journal on Scientific Computing}, number = {2}, pages = {A1148--A1169}, title = {A Superlinear Convergence Estimate for the Parareal Schwarz Waveform Relaxation Algorithm}, url = {https://doi.org/10.1137/18M1177226}, volume = {41}, year = {2019} }
Abstract for BibTeX entry GanderEtAl2019b

The parareal Schwarz waveform relaxation algorithm is a new space-time parallel algorithm for the solution of evolution partial differential equations. It is based on a decomposition of the entire space-time domain both in space and in time into smaller space-time subdomains, and then computes by an iteration in parallel on all these small space-time subdomains a better and better approximation of the overall solution in space-time. The initial conditions in the space-time subdomains are updated using a parareal mechanism, while the boundary conditions are updated using Schwarz waveform relaxation techniques. A first precursor of this algorithm was presented 15 years ago, and while the method works well in practice, the convergence of the algorithm is not yet understood, and to analyze it is technically difficult. We present in this paper for the first time an accurate superlinear convergence estimate when the algorithm is applied to the heat equation. We illustrate our analysis with numerical experiments including cases not covered by the analysis, which opens up many further research directions.
GanderEtAl2019c

M. J. Gander, I. Kulchytska-Ruchka, I. Niyonzima, and S. Schöps, “A New Parareal Algorithm for Problems with Discontinuous Sources,” SIAM Journal on Scientific Computing, vol. 41, no. 2, pp. B375–B395, 2019, doi: 10.1137/18M1175653. [Online]. Available at: https://doi.org/10.1137/18M1175653
BibTeX entry GanderEtAl2019c

@article{GanderEtAl2019c, author = {Gander, Martin J. and Kulchytska-Ruchka, Iryna and Niyonzima, Innocent and Schöps, Sebastian}, doi = {10.1137/18M1175653}, journal = {SIAM Journal on Scientific Computing}, number = {2}, pages = {B375--B395}, title = {A New Parareal Algorithm for Problems with Discontinuous Sources}, url = {https://doi.org/10.1137/18M1175653}, volume = {41}, year = {2019} }
Abstract for BibTeX entry GanderEtAl2019c

The Parareal algorithm allows to solve evolution problems exploiting parallelization in time. Its convergence and stability have been proved under the assumption of regular (smooth) inputs. We present and analyze here a new Parareal algorithm for ordinary differential equations which involve discontinuous right-hand sides. Such situations occur in various applications, e.g., when an electric device is supplied with a pulse-width-modulated signal. Our new Parareal algorithm uses a smooth input for the coarse problem with reduced dynamics. We derive error estimates that show how the input reduction influences the overall convergence rate of the algorithm. We support our theoretical results by numerical experiments, and also test our new Parareal algorithm in an eddy current simulation of an induction machine.

M. J. Gander and S.-L. Wu, “Convergence analysis of a periodic-like waveform relaxation method for initial-value problems via the diagonalization technique,” Numerische Mathematik, vol. 143, no. 2, pp. 489–527, Jun. 2019, doi: 10.1007/s00211-019-01060-8. [Online]. Available at: https://doi.org/10.1007/s00211-019-01060-8

S. Götschel and M. L. Minion, “An Efficient Parallel-in-Time Method for Optimization with Parabolic PDEs,” SIAM Journal on Scientific Computing, vol. 41, no. 6, pp. C603–C626, Jan. 2019, doi: 10.1137/19m1239313. [Online]. Available at: https://doi.org/10.1137/19m1239313

HedinLelievre2019

F. Hédin and T. Lelièvre, “gen.parRep: A first implementation of the Generalized Parallel Replica dynamics for the long time simulation of metastable biochemical systems,” Computer Physics Communications, 2019, doi: 10.1016/j.cpc.2019.01.005. [Online]. Available at: https://doi.org/10.1016/j.cpc.2019.01.005
BibTeX entry HedinLelievre2019

@article{HedinLelievre2019, author = {Hédin, Florent and Lelièvre, Tony}, doi = {10.1016/j.cpc.2019.01.005}, journal = {Computer Physics Communications}, title = {gen.parRep: A first implementation of the Generalized Parallel Replica dynamics for the long time simulation of metastable biochemical systems}, url = {https://doi.org/10.1016/j.cpc.2019.01.005}, year = {2019} }
Abstract for BibTeX entry HedinLelievre2019

Metastability is one of the major encountered obstacles when performing long molecular dynamics simulations, and many methods were developed to address this challenge. The “Parallel Replica”(ParRep) dynamics is known for allowing to simulate very long trajectories of metastable Langevin dynamics in the materials science community, but it relies on assumptions that can hardly be transposed to the world of biochemical simulations. The later developed “Generalized ParRep” variant solves those issues, but it was not applied to significant systems of interest so far. In this article, we present the program gen.parRep, the first publicly available implementation of the Generalized Parallel Replica method (BSD 3-Clause license), targeting frequently encountered metastable biochemical systems, such as conformational equilibria or dissociation of protein–ligand complexes. It will be shown that the resulting C++ implementation exhibits a strong linear scalability, providing up to 70% of the maximum possible speedup on several hundreds of CPUs.

J. Hong, X. Wang, and L. Zhang, “Parareal Exponential \textdollar}theta\textdollar-Scheme for Longtime Simulation of Stochastic Schrödinger Equations with Weak Damping,” SIAM Journal on Scientific Computing, vol. 41, no. 6, pp. B1155–B1177, Jan. 2019, doi: 10.1137/18m1176749. [Online]. Available at: https://doi.org/10.1137/18m1176749

HowseEtAl2019

A. Howse, H. Sterck, R. Falgout, S. MacLachlan, and J. Schroder, “Parallel-In-Time Multigrid with Adaptive Spatial Coarsening for The Linear Advection and Inviscid Burgers Equations,” SIAM Journal on Scientific Computing, vol. 41, no. 1, pp. A538–A565, 2019, doi: 10.1137/17M1144982. [Online]. Available at: https://dx.doi.org/10.1137/17M1144982
BibTeX entry HowseEtAl2019

@article{HowseEtAl2019, author = {Howse, A. and Sterck, H. and Falgout, R. and MacLachlan, S. and Schroder, J.}, doi = {10.1137/17M1144982}, journal = {SIAM Journal on Scientific Computing}, number = {1}, pages = {A538--A565}, title = {Parallel-In-Time Multigrid with Adaptive Spatial Coarsening for The Linear Advection and Inviscid Burgers Equations}, url = {https://dx.doi.org/10.1137/17M1144982}, volume = {41}, year = {2019} }
Abstract for BibTeX entry HowseEtAl2019

We apply a multigrid reduction-in-time (MGRIT) algorithm to hyperbolic partial differential equations in one spatial dimension. This study is motivated by the observation that sequential time-stepping is a computational bottleneck when attempting to implement highly concurrent algorithms, thus parallel-in-time methods are desirable. MGRIT adds parallelism by using a hierarchy of successively coarser temporal levels to accelerate the solution on the finest level. In the case of explicit time-stepping, spatial coarsening is a suitable approach to ensure that stability conditions are satisfied on all levels, and it may be useful for implicit time-stepping by producing cheaper multigrid cycles. Unfortunately, uniform spatial coarsening results in extremely slow convergence when the wave speed is near zero, even if only locally. We present an adaptive spatial coarsening strategy that addresses this issue for the variable coefficient linear advection equation and the inviscid Burgers equation using first-order explicit or implicit time-stepping methods. Serial numerical results show this method offers significant improvements over uniform coarsening and is convergent for the inviscid Burgers equation with and without shocks. Parallel scaling tests on up to 128K cores indicate that run-time improvements over serial time-stepping strategies are possible when spatial parallelism alone saturates, and that scalability is robust for oscillatory solutions which change on the scale of the grid spacing.
KrzysikEtAl2019

O. A. Krzysik, H. D. Sterck, S. P. MacLachlan, and S. Friedhoff, “On selecting coarse-grid operators for Parareal and MGRIT applied to linear advection,” arXiv:1902.07757 [math.NA], 2019 [Online]. Available at: https://arxiv.org/abs/1902.07757
BibTeX entry KrzysikEtAl2019

@unpublished{KrzysikEtAl2019, author = {Krzysik, Oliver A. and Sterck, Hans De and MacLachlan, Scott P. and Friedhoff, Stephanie}, howpublished = {arXiv:1902.07757 [math.NA]}, title = {On selecting coarse-grid operators for Parareal and MGRIT applied to linear advection}, url = {https://arxiv.org/abs/1902.07757}, year = {2019} }
Abstract for BibTeX entry KrzysikEtAl2019

We consider the parallel time integration of the linear advection equation with the Parareal and two-level multigrid-reduction-in-time (MGRIT) algorithms. Our aim is to develop a better understanding of the convergence behaviour of these algorithms for this problem, which is known to be poor relative to the diffusion equation, its model parabolic counterpart. Using Fourier analysis, we derive new convergence estimates for these algorithms which, in conjunction with existing convergence theory, provide insight into the origins of this poor performance. We then use this theory to explore improved coarse-grid time-stepping operators. For several high-order discretizations of the advection equation, we demonstrate that there exist non-standard coarse-grid time stepping operators that yield significant improvements over the standard choice of rediscretization.
KwokOng2019

F. Kwok and B. Ong, “Schwarz Waveform Relaxation with Adaptive Pipelining,” SIAM Journal on Scientific Computing, vol. 41, no. 1, pp. A339–A364, 2019, doi: 10.1137/17M115311X. [Online]. Available at: https://doi.org/10.1137/17M115311X
BibTeX entry KwokOng2019

@article{KwokOng2019, author = {Kwok, F. and Ong, B.}, doi = {10.1137/17M115311X}, journal = {SIAM Journal on Scientific Computing}, number = {1}, pages = {A339--A364}, title = {Schwarz Waveform Relaxation with Adaptive Pipelining}, url = {https://doi.org/10.1137/17M115311X}, volume = {41}, year = {2019} }
Abstract for BibTeX entry KwokOng2019

Schwarz waveform relaxation (SWR) methods have been developed to solve a wide range of diffusion-dominated and reaction-dominated equations. The appeal of these methods stems primarily from their ability to use nonconforming space-time discretizations; SWR methods are consequently well-adapted for coupling models with highly varying spatial and time scales. The efficacy of SWR methods is questionable, however, since in each iteration, one propagates an error across the entire time interval. In this manuscript, we introduce an adaptive pipeline approach wherein one subdivides the computational domain into space-time blocks, and adaptively selects the waveform iterates which should be updated given a fixed number of computational workers. Our method is complementary to existing space and time parallel methods, and can be used to obtain additional speedup when the saturation point is reached for other types of parallelism. We analyze these waveform relaxation with adaptive pipelining (WRAP) methods to show convergence and the theoretical speedup that can be expected. Numerical experiments on solutions to the linear heat equation, the advection-diffusion equation, and a reaction-diffusion equation illustrate features and efficacy of WRAP methods for various transmission conditions.
LiEtAl2019

S. Li, R. Chen, and X. Shao, “Parallel two-level space–time hybrid Schwarz method for solving linear parabolic equations,” Applied Numerical Mathematics, vol. 139, pp. 120–135, 2019, doi: 10.1016/j.apnum.2019.01.016. [Online]. Available at: https://doi.org/10.1016/j.apnum.2019.01.016
BibTeX entry LiEtAl2019

@article{LiEtAl2019, author = {Li, Shishun and Chen, Rongliang and Shao, Xinping}, doi = {10.1016/j.apnum.2019.01.016}, journal = {Applied Numerical Mathematics}, pages = {120--135}, title = {Parallel two-level space–time hybrid Schwarz method for solving linear parabolic equations}, url = {https://doi.org/10.1016/j.apnum.2019.01.016}, volume = {139}, year = {2019} }
Abstract for BibTeX entry LiEtAl2019

In this paper, we present a two-level space–time hybrid Schwarz preconditioner for GMRES based on the classical hybrid Schwarz method and the second-order backward differentiation formula. In the proposed method, the parabolic equations are solved in parallel on both of the space and time directions. Under some reasonable assumptions, the optimal convergence theory is developed for the proposed space–time method, i.e., the convergence rate is independent of the mesh parameters, the number of subdomains and the window size. Some numerical results are given to confirm the theory very well in terms of the convergence rate and accuracy. And the strong/weak scalability obtained with 4096 processors is also reported to show the efficiency of the proposed method.
LiEtAl2019b

S. Li, X. Shao, and X.-C. Cai, “Highly parallel space-time domain decomposition methods for parabolic problems,” CCF Transactions on High Performance Computing, 2019, doi: 10.1007/s42514-019-00003-x. [Online]. Available at: https://doi.org/10.1007/s42514-019-00003-x
BibTeX entry LiEtAl2019b

@article{LiEtAl2019b, author = {Li, Shishun and Shao, Xinping and Cai, Xiao-Chuan}, doi = {10.1007/s42514-019-00003-x}, journal = {CCF Transactions on High Performance Computing}, title = {Highly parallel space-time domain decomposition methods for parabolic problems}, url = {https://doi.org/10.1007/s42514-019-00003-x}, year = {2019} }
Abstract for BibTeX entry LiEtAl2019b

In the past few years, the number of processor cores of top ranked supercomputers has increased drastically. It is challenging to design efficient parallel algorithms that offer such a high degree of parallelism, especially for certain time-dependent problems because of the sequential nature of “time”. To increase the degree of parallelization, some parallel-in-time algorithms have been developed. In this paper, we give an overview of some recently introduced parallel-in-time methods, and present in detail the class of space-time Schwarz methods, including the standard and the restricted versions, for solving parabolic partial differential equations. Some numerical experiments carried out on a parallel computer with a large number of processor cores for three-dimensional problems are given to show the parallel scalability of the methods. In the end of the paper, we provide a comparison of the parallel-in-time algorithms with a traditional algorithm that is parallelized only in space.
MeleEtAl2019

V. Mele, D. Romano, E. M. Constantinescu, L. Carracciuolo, and L. D’Amore, “Performance Evaluation for a PETSc Parallel-in-Time Solver Based on the MGRIT Algorithm,” in Euro-Par 2018: Parallel Processing Workshops, 2019, pp. 716–728, doi: 10.1002/cpe.4928 [Online]. Available at: https://doi.org/10.1002/cpe.4928
BibTeX entry MeleEtAl2019

@inproceedings{MeleEtAl2019, author = {Mele, Valeria and Romano, Diego and Constantinescu, Emil M. and Carracciuolo, Luisa and D'Amore, Luisa}, booktitle = {Euro-Par 2018: Parallel Processing Workshops}, doi = {10.1002/cpe.4928}, editor = {Mencagli, Gabriele and B. Heras, Dora and Cardellini, Valeria and Casalicchio, Emiliano and Jeannot, Emmanuel and Wolf, Felix and Salis, Antonio and Schifanella, Claudio and Manumachu, Ravi Reddy and Ricci, Laura and Beccuti, Marco and Antonelli, Laura and Garcia Sanchez, Jos{\'e} Daniel and Scott, Stephen L.}, pages = {716--728}, publisher = {Springer International Publishing}, title = {Performance Evaluation for a PETSc Parallel-in-Time Solver Based on the MGRIT Algorithm}, url = {https://doi.org/10.1002/cpe.4928}, year = {2019} }
Abstract for BibTeX entry MeleEtAl2019

We herein describe the performance evaluation of a modular implementation of the MGRIT (MultiGrid-In-Time) algorithm within the context of the PETSc (the Portable, Extensible Toolkit for Scientific computing) library. Our aim is to give the PETSc users the opportunity of testing the MGRIT parallel-in-time approach as an alternative to the Time Stepping integrator (TS), when solving their problems arising from the discretization of linear evolutionary models. To this end, we analyzed the performance parameters of the algorithm in order to underline the relationship between the configuration factors and problem characteristics, intentionally overlooking any accuracy issue and spacial parallelism.
NeumuellerSmears2019

M. Neumüller and I. Smears, “Time-Parallel Iterative Solvers for Parabolic Evolution Equations,” SIAM Journal on Scientific Computing, vol. 41, no. 1, pp. C28–C51, 2019, doi: 10.1137/18M1172466. [Online]. Available at: https://doi.org/10.1137/18M1172466
BibTeX entry NeumuellerSmears2019

@article{NeumuellerSmears2019, author = {Neum{\"u}ller, M. and Smears, I.}, doi = {10.1137/18M1172466}, journal = {SIAM Journal on Scientific Computing}, number = {1}, pages = {C28--C51}, title = {Time-Parallel Iterative Solvers for Parabolic Evolution Equations}, url = {https://doi.org/10.1137/18M1172466}, volume = {41}, year = {2019} }
Abstract for BibTeX entry NeumuellerSmears2019

We present original time-parallel algorithms for the solution of the implicit Euler discretization of general linear parabolic evolution equations with time-dependent self-adjoint spatial operators. Motivated by the inf-sup theory of parabolic problems, we show that the standard nonsymmetric time-global system can be equivalently reformulated as an original symmetric saddle-point system that remains inf-sup stable with respect to the same natural parabolic norms. We then propose and analyse an efficient and readily implementable parallel-in-time preconditioner to be used with an inexact Uzawa method. The proposed preconditioner is non-intrusive and easy to implement in practice, and also features the key theoretical advantages of robust spectral bounds, leading to convergence rates that are independent of the number of time-steps, final time, or spatial mesh sizes, and also a theoretical parallel complexity that grows only logarithmically with respect to the number of time-steps. Numerical experiments with large-scale parallel computations show the effectiveness of the method, along with its good weak and strong scaling properties.

A. G. Peddle, T. Haut, and B. Wingate, “Parareal Convergence for Oscillatory PDEłowercases with Finite Time-Scale Separation,” SIAM Journal on Scientific Computing, vol. 41, no. 6, pp. A3476–A3497, Jan. 2019, doi: 10.1137/17m1131611. [Online]. Available at: https://doi.org/10.1137/17m1131611

Rosa-Raı́ces Jorge L., B. Zhang, and T. F. Miller, “Path-accelerated stochastic molecular dynamics: Parallel-in-time integration using path integrals,” The Journal of Chemical Physics, vol. 151, no. 16, p. 164120, Oct. 2019, doi: 10.1063/1.5125455. [Online]. Available at: https://doi.org/10.1063/1.5125455

SamaddarEtAl2019

D. Samaddar, D. P. Coster, X. Bonnin, L. A. Berry, W. R. Elwasif, and D. B. Batchelor, “Application of the parareal algorithm to simulations of ELMs in ITER plasma,” Computer Physics Communications, vol. 235, pp. 246–257, 2019, doi: 10.1016/j.cpc.2018.08.007. [Online]. Available at: https://doi.org/10.1016/j.cpc.2018.08.007
BibTeX entry SamaddarEtAl2019

@article{SamaddarEtAl2019, author = {Samaddar, D. and Coster, D.P. and Bonnin, X. and Berry, L.A. and Elwasif, W.R. and Batchelor, D.B.}, doi = {10.1016/j.cpc.2018.08.007}, journal = {Computer Physics Communications}, pages = {246--257}, title = {Application of the parareal algorithm to simulations of {ELM}s in {ITER} plasma}, url = {https://doi.org/10.1016/j.cpc.2018.08.007}, volume = {235}, year = {2019} }
Abstract for BibTeX entry SamaddarEtAl2019

This paper explores the application of the parareal algorithm to simulations of ELMs in ITER plasma. The primary focus of this research is identifying the parameters that lead to optimum performance. Since the plasma dynamics vary extremely fast during an ELM cycle, a straightforward application of the algorithm is not possible and a modification to the standard parareal correction is implemented. The size of the time chunks also have an impact on the performance and needs to be optimized. A computational gain of 7.8 is obtained with 48 processors to illustrate that the parareal algorithm can be successfully applied to ELM plasma.
SchreiberLoft2019

M. Schreiber, N. Schaeffer, and R. Loft, “Exponential Integrators with Parallel-in-Time Rational Approximations for Shallow-Water Equations on the Rotating Sphere,” Parallel Computing, 2019, doi: 10.1016/j.parco.2019.01.005. [Online]. Available at: https://dx.doi.org/10.1016/j.parco.2019.01.005
BibTeX entry SchreiberLoft2019

@article{SchreiberLoft2019, author = {Schreiber, M. and Schaeffer, N. and Loft, R.}, doi = {10.1016/j.parco.2019.01.005}, journal = {Parallel Computing}, title = {Exponential Integrators with Parallel-in-Time Rational Approximations for Shallow-Water Equations on the Rotating Sphere}, url = {https://dx.doi.org/10.1016/j.parco.2019.01.005}, year = {2019} }
Abstract for BibTeX entry SchreiberLoft2019

High-performance computing trends towards many-core systems are expected to continue over the next decade. As a result, parallel-in-time methods, mathematical formulations which exploit additional degrees of parallelism in the time dimension, have gained increasing interest in recent years. In this work we study a massively parallel rational approximation of exponential integrators (REXI). This method replaces a time integration of stiff linear oscillatory and diffusive systems by the sum of the solutions of many decoupled systems, which can be solved in parallel. Previous numerical studies showed that this reformulation allows taking arbitrarily long time steps for the linear oscillatory parts. The present work studies the non-linear shallow-water equations on the rotating sphere, a simplified system of equations used to study properties of space and time discretization methods in the context of atmospheric simulations. After introducing time integrators, we first compare the time step sizes to the errors in the simulation, discussing pros and cons of different formulations of REXI. Here, REXI already shows superior properties compared to explicit and implicit time stepping methods. Additionally, we present wallclock-time-to-error results revealing the sweet spots of REXI obtaining either an over 6 ×  higher accuracy within the same time frame or an about 3 ×  reduced time-to-solution for a similar error threshold. Our results motivate further explorations of REXI for operational weather/climate systems.

M. Schreiber and R. Loft, “A parallel time integrator for solving the linearized shallow water equations on the rotating sphere,” Numerical Linear Algebra with Applications, vol. 26, no. 2, p. e2220, 2019, doi: 10.1002/nla.2220. [Online]. Available at: https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2220

B. S. Southworth, “Necessary Conditions and Tight Two-level Convergence Bounds for Parareal and Multigrid Reduction in Time,” SIAM J. Matrix Anal. Appl., vol. 40, no. 2, pp. 564–608, 2019, doi: https://doi.org/10.1137/18M1226208.