---
---
%% NOTE
%% The two lines above are required for Jekyll and the jekyll-scholar plugin to correctly parse
%% and render the references on the web page.
%% You may remove them when using this file with BibTeX natively in your publications.
%
%
% Extensive BibTeX source containing many references to works dealing with parallel-in-time methods.
%
% The entries in this file are sorted by YEAR (ascending).
% If inserting new entries, please put them accordingly.
%
% Please, treat this file not different from usual source code files.
% Thus, stick to the concisely used formatting pattern with tab indention, lower cased keywords,
% curly brackets for value enclosure and alphabetical sorted keywords within one BibTeX entry.
%
% Feel free to use this collection wherever you want.
% We would very much appreciate a link/reference to parallel-in-time.org.
%
%
% 1964
%
@article{Nievergelt1964,
author = {Nievergelt, J.},
journal = {Commun. ACM},
number = {12},
pages = {731--733},
title = {{Parallel methods for integrating ordinary differential equations}},
url = {http://dx.doi.org/10.1145/355588.365137},
doi = {10.1145/355588.365137},
volume = {7},
year = {1964}
}
%
% 1967
%
@article{MirankerLiniger1967,
author = {Miranker, Willard L and Liniger, Werner},
journal = {Mathematics of Computation},
number = {99},
pages = {303--320},
title = {{Parallel methods for the numerical integration of ordinary differential equations}},
url = {http://dx.doi.org/10.1090/S0025-5718-1967-0223106-8},
doi = {10.1090/S0025-5718-1967-0223106-8},
volume = {21},
year = {1967}
}
%
% 1976
%
@article{Worland1976,
author = {Worland, P.~B.},
journal = {Computers, IEEE Transactions on},
number = {10},
pages = {1045--1048},
title = {{Parallel Methods for the Numerical Solution of Ordinary Differential Equations}},
url = {http://dx.doi.org/10.1109/TC.1976.1674545},
doi = {10.1109/TC.1976.1674545},
volume = {C-25},
year = {1976}
}
%
% 1978
%
@article{Franklin1978,
abstract = {{This paper presents a performance comparison of three parallel algorithms for the solution of sets of coupled first-order differential equations. A general format for comparison of the algorithms is given, and performance equations for the two processor cases are developed. The equations take into account both the computational and intercommunications requirements of the processors. These equations are applied to a benchmark of six problems and a simple, single bus multiprocessor architecture. The more than two processor case is considered for one of the parallel algorithms.}},
author = {M. A. Franklin},
journal = {IEEE Transactions on Computers},
title = {Parallel Solution of Ordinary Differential Equations},
year = {1978},
volume = {C-27},
number = {5},
pages = {413--420},
doi = {10.1109/TC.1978.1675121},
url = {http://dx.doi.org/10.1109/TC.1978.1675121}
}
%
% 1984
%
@article{Hackbusch1984,
author = {Hackbusch, W.},
journal = {Computing Methods in Applied Sciences and Engineering, VI},
pages = {189--197},
title = {{Parabolic multi-grid methods}},
url = {http://dl.acm.org/citation.cfm?id=4673.4714},
year = {1984}
}
%
% 1987
%
@article{ChuHamilton1987,
author = {Chu, M. and Hamilton, H.},
journal = {SIAM Journal on Scientific and Statistical Computing},
number = {3},
pages = {342--353},
title = {{Parallel Solution of {ODE}'s by Multiblock Methods}},
url = {http://dx.doi.org/10.1137/0908039},
doi = {10.1137/0908039},
volume = {8},
year = {1987}
}
@article{LubichOstermann1987,
author = {Lubich, Ch. and Ostermann, A.},
journal = {BIT Numerical Mathematics},
number = {2},
pages = {216--234},
title = {{Multi-grid dynamic iteration for parabolic equations}},
url = {http://dx.doi.org/10.1007/BF01934186},
doi = {10.1007/BF01934186},
volume = {27},
year = {1987}
}
%
% 1988
%
@article{Gear1988,
author = {Gear, C.~W.},
journal = {CALCOLO},
number = {1-2},
pages = {1--20},
title = {{Parallel methods for ordinary differential equations}},
url = {http://dx.doi.org/10.1007/BF02575744},
doi = {10.1007/BF02575744},
volume = {25},
year = {1988}
}
%
% 1989
%
@article{BellenZennaro1989,
author = {Bellen, Alfredo and Zennaro, Marino},
journal = {Journal of Computational and Applied Mathematics},
number = {3},
pages = {341--350},
title = {{Parallel algorithms for initial-value problems for difference and differential equations}},
url = {http://dx.doi.org/10.1016/0377-0427(89)90037-X},
doi = {10.1016/0377-0427(89)90037-X},
volume = {25},
year = {1989}
}
@inproceedings{GallopoulosEtAl1989,
abstract = {{We propose new parallel algorithms for the solution of linear parabolic problems. The first of these methods is based on using polynomial approximation to the exponential. It does not require solving any linear systems and is highly parallelizable. The two other methods proposed are based on Padé and Chebyshev approximations to the matrix exponential. The parallelization of these methods is achieved by using partial fraction decomposition techniques to solve the resulting systems and thus offers the potential for increased time parallelism in time dependent problems. We also present experimental results from the Alliant FX/8 and the Cray Y-MP/832 vector multiprocessors.}},
author = {Gallopoulos, E. and Saad, Y.},
title = {On the Parallel Solution of Parabolic Equations},
booktitle = {Proceedings of the 3rd International Conference on Supercomputing},
series = {ICS '89},
year = {1989},
pages = {17--28},
numpages = {12},
url = {http://doi.acm.org/10.1145/318789.318793},
doi = {10.1145/318789.318793},
acmid = {318793},
publisher = {ACM},
address = {New York, NY, USA},
}
%
% 1990
%
@article{ScalaEtAl1990,
abstract = {{A method for transient stability simulation is presented that aims to exploit the maximum degree of parallelism that the problem presents. The transient stability problem is viewed as a coupled set of nonlinear algebraic and differential equations; by applying a discretization method such as the trapezoidal rule, the overall algebraic-differential set of equations is thus transformed into an unique algebraic problem at each time step. A solution that considers every time step, not in a sequential way but concurrently, is suggested. The solution of this set of equations with a relaxation-type indirect method gives rise to a highly parallel algorithm. The method can handle all the typical dynamic models of realistic power system components. Test results are presented and shown to favorably compare with those obtained with the sequential dishonest Newton algorithm for realistic power systems}},
author={M. {La Scala} and A. {Bose} and D. J. {Tylavsky} and J. S. {Chai}},
journal={IEEE Transactions on Power Systems},
title={A highly parallel method for transient stability analysis},
year={1990},
volume={5},
number={4},
pages={1439--1446},
url={http://dx.doi.org/10.1109/59.99398},
doi={10.1109/59.99398},
}
@article{VanderHouwen1990,
title = {{Parallel iteration of high-order Runge-Kutta methods with stepsize control}},
journal = {Journal of Computational and Applied Mathematics},
volume = {29},
number = {1},
pages = {111--127},
year = {1990},
url = {http://dx.doi.org/10.1016/0377-0427(90)90200-J},
doi = {10.1016/0377-0427(90)90200-J},
author = {Van Der Houwen, P.~J. and Sommeijer, B.~P.},
abstract = {{This paper investigates iterated Runge-Kutta methods of high order designed in such a way that the right-hand side evaluations can be computed in parallel. Using stepsize control based on embedded formulas a highly efficient code is developed. On parallel computers, the 8th-order mode of this code is more efficient than the DOPR18 implementation of the formulas of Prince and Dormand. The 10th-order mode is about twice as cheap for comparable accuracies.}}
}
@article{Womble1990,
author = {Womble, D.~E},
journal = {SIAM Journal on Scientific and Statistical Computing},
number = {5},
pages = {824--837},
title = {{A time-stepping algorithm for parallel computers}},
url = {http://dx.doi.org/10.1137/0911049},
doi = {10.1137/0911049},
volume = {11},
year = {1990}
}
%
% 1991
%
@inproceedings {Gear1991,
author = {Gear, C.~W.},
title = {{Waveform methods for space and time parallelism}},
booktitle = {Proceedings of the {I}nternational {S}ymposium on {C}omputational {M}athematics ({M}atsuyama, 1990)},
journal = {Journal of Computational and Applied Mathematics},
volume = {38},
year = {1991},
pages = {137--147}}
@incollection{Horton1991,
author = {Horton, Graham},
booktitle = {{Applications of Supercomputers in Engineering II}},
editor = {Brebbia, C.A. and Peters, A. and Howard, D.},
pages = {435--445},
publisher = {Springer Netherlands},
title = {{Time-Parallel Multigrid Solution of the {N}avier-{S}tokes Equations}},
url = {http://dx.doi.org/10.1007/978-94-011-3660-0_31},
doi = {10.1007/978-94-011-3660-0_31},
year = {1991}
}
@article{Jackson1991,
abstract = {{The parallel solution of Initial Value Problems for Ordinary Differential Equations has become an active area of research during the past few years. We briefly survey the recent developments in this area, with particular emphasis on traditional forward-step methods that offer the potential for effective small-scale parallelism on currently existing machines.}},
author = {Jackson, Kenneth R.},
title = {A SURVEY OF PARALLEL NUMERICAL METHODS FOR INITIAL VALUE PROBLEMS FOR ORDINARY DIFFERENTIAL EQUATIONS},
journal = {IEEE Transactions on Magnetics},
volume = {27},
issue = {5},
year = {1991},
pages = {3792--3797},
doi = {10.1109/20.104928},
url = {http://dx.doi.org/10.1109/20.104928}
}
@article{MurataEtAl1991,
author = {Murata, S. and Satofuka, N. and Kushiyama, T.},
journal = {Computers \& Fluids},
number = {1},
pages = {33--41},
title = {{Parabolic multi-grid method for incompressible viscous flows using a group explicit relaxation scheme}},
url = {http://dx.doi.org/10.1016/0045-7930(91)90005-3},
doi = {10.1016/0045-7930(91)90005-3},
volume = {19},
year = {1991}
}
@article{VanderHouwen1991,
author = {van der Houwen, P.~J. and Sommeijer, B.~P.},
title = {Iterated Runge--Kutta Methods on Parallel Computers},
journal = {SIAM Journal on Scientific and Statistical Computing},
volume = {12},
number = {5},
pages = {1000--1028},
year = {1991},
doi = {10.1137/0912054},
URL = {http://dx.doi.org/10.1137/0912054}
}
%
% 1992
%
@article{Horton1992,
author = {Horton, Graham},
journal = {Communications in Applied Numerical Methods},
number = {9},
pages = {585--595},
title = {The time-parallel multigrid method},
url = {http://dx.doi.org/10.1002/cnm.1630080906},
doi = {10.1002/cnm.1630080906},
volume = {8},
year = {1992}
}
@article{HortonKnirsch1992,
author = {Horton, Graham and Knirsch, Ralf},
journal = {Parallel Computing},
number = {1},
pages = {21--29},
title = {A time-parallel multigrid-extrapolation method for parabolic partial differential equations},
url = {http://dx.doi.org/10.1016/0167-8191(92)90108-J},
doi = {10.1016/0167-8191(92)90108-J},
volume = {18},
year = {1992}
}
@incollection{HortonEtAl1992,
author = {Horton, Graham and Knirsch, Ralf and Vollath, Hermann},
booktitle = {{Parallel Processing: CONPAR 92 --VAPP V}},
editor = {Bougé, Luc and Cosnard, Michel and Robert, Yves and Trystram, Denis},
pages = {205--216},
publisher = {Springer Berlin Heidelberg},
series = {Lecture Notes in Computer Science},
title = {The time-parallel solution of parabolic partial differential equations using the frequency-filtering method},
url = {http://dx.doi.org/10.1007/3-540-55895-0_415},
doi = {10.1007/3-540-55895-0_415},
volume = {634},
year = {1992}
}
@article{VandewallePiessens1992,
author = {Vandewalle, Stefan and Piessens, R.},
journal = {SIAM Journal on Scientific and Statistical Computing},
number = {6},
pages = {1330--1346},
title = {{Efficient Parallel Algorithms for Solving Initial-Boundary Value and Time-Periodic Parabolic Partial Differential Equations}},
url = {http://dx.doi.org/10.1137/0913075},
doi = {10.1137/0913075},
volume = {13},
year = {1992}
}
%
% 1993
%
@article{Burrage1993,
author = {Burrage, Kevin},
journal = {Applied Numerical Mathematics},
number = {1--3},
pages = {5--25},
title = {{Parallel methods for initial value problems}},
url = {http://dx.doi.org/10.1016/0168-9274(93)90037-R},
doi = {10.1016/0168-9274(93)90037-R},
volume = {11},
year = {1993}
}
@article{ChartierPhilippe1993,
author = {Chartier, P. and Philippe, B.},
journal = {Computing},
number = {3-4},
pages = {209--236},
title = {{A parallel shooting technique for solving dissipative {ODE}'s}},
url = {http://dx.doi.org/10.1007/BF02238534},
doi = {10.1007/BF02238534},
volume = {51},
year = {1993}
}
@inproceedings{Fijany1993,
author = {Fijany, Amir},
booktitle = {{Parallel Processing, 1993. ICPP 1993. International Conference on}},
pages = {51--56},
title = {{Time Parallel Algorithms for Solution of Linear Parabolic {PDE}s}},
url = {http://dx.doi.org/10.1109/ICPP.1993.179},
doi = {10.1109/ICPP.1993.179},
volume = {3},
year = {1993}
}
@article {GearXuhai1993,
author = {Gear, C.~W. and Xuhai, Xu},
title = {Parallelism across time in {ODE}s},
note = {Parallel methods for ordinary differential equations (Grado, 1991)},
journal = {Applied Numerical Mathematics. An IMACS Journal},
volume = {11},
year = {1993},
number = {1-3},
pages = {45--68}}
@article{OosterleeWesseling1993,
author = {Oosterlee, C. and Wesseling, P.},
journal = {IMPACT of Computing in Science and Engineering},
number = {3},
pages = {153--175},
title = {{Multigrid schemes for time-dependent incompressible {N}avier-{S}tokes equations}},
url = {http://dx.doi.org/10.1006/icse.1993.1007},
doi = {10.1006/icse.1993.1007},
volume = {5},
year = {1993}
}
@article{ScalaBose1993,
abstract = {{A class of algorithms that exploits the concurrent solution of many time steps is presented. By applying a stable integration method, the overall algebraic-differential set of equations can be transformed into a unique algebraic problem at each time step. The dynamic behavior of the system can be obtained by solving an enlarged set of algebraic equations relative to the simultaneous solution of many time steps. A class of relaxation/Newton algorithms can be used to solve this problem efficiently. This formulation permits easy implementation of multigrid techniques. The convergence rates and computational complexity of the algorithms are discussed. Test results for realistic power systems confirm theoretical expectations and show the promise of a several-fold increase in speed over that obtainable by traditional parallel-in-space approaches. The synergism obtainable by parallelism in time and in space can provide speed-up adequate for online implementations of transient stability analysis}},
author={M. {La Scala} and A. {Bose}},
journal={IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications},
title={{Relaxation/Newton methods for concurrent time step solution of differential-algebraic equations in power system dynamic simulations}},
year={1993},
volume={40},
number={5},
pages={317--330},
url={http://dx.doi.org/10.1109/81.232576},
doi={10.1109/81.232576},
}
@article{Sommeijer1993,
title = {{Parallel-iterated Runge-Kutta methods for stiff ordinary differential equations}},
journal = {{Journal of Computational and Applied Mathematics}},
volume = {45},
number = {1},
pages = {151--168},
year = {1993},
url = {http://dx.doi.org/10.1016/0377-0427(93)90271-C},
doi = {10.1016/0377-0427(93)90271-C},
author = {Sommeijer, B.P.},
abstract = {For the numerical integration of a stiff ordinary differential equation, fully implicit Runge-Kutta methods offer nice properties, like a high classical order and high stage order as well as an excellent stability behaviour. However, such methods need the solution of a set of highly coupled equations for the stage values and this is a considerable computational task. This paper discusses an iteration scheme to tackle this problem. By means of a suitable choice of the iteration parameters, the implicit relations for the stage values, as they occur in each iteration, can be uncoupled so that they can be solved in parallel. The resulting scheme can be cast into the class of Diagonally Implicit Runge-Kutta (DIRK) methods and, similar to these methods, requires only one LU factorization per step (per processor). The stability as well as the computational efficiency of the process strongly depends on the particular choice of the iteration parameters and on the number of iterations performed. We discuss several choices to obtain good stability and fast convergence. Based on these approaches, we wrote two codes possessing local error control and stepsize variation. We have implemented both codes on an ALLIANT FX/4 machine (four parallel vector processors and shared memory) and measured their speedup factors for a number of test problems. Furthermore, the performance of these codes is compared with the performance of the best stiff ODE codes for sequential computers, like SIMPLE, LSODE and RADAU5.}
}
@article{VanderHouwen1993,
title = {{Analysis of parallel diagonally implicit iteration of Runge-Kutta methods}},
journal = {Applied Numerical Mathematics},
volume = {11},
number = {1},
pages = {169--188},
year = {1993},
url = {http://dx.doi.org/10.1016/0168-9274(93)90047-U},
doi = {10.1016/0168-9274(93)90047-U},
author = {van der Houwen, P.J. and Sommeijer, B.P.},
abstract = {In this paper, we analyze parallel, diagonally implicit iteration of Runge-Kutta methods (PDIRK methods) for solving large systems of stiff equations on parallel computers. Like Newton-iterated backward differentiation formulas (BDFs), these PDIRK methods are such that in each step the (sequential) costs consist of solving a number of linear systems with the same matrix of coefficients and with the same dimension as the system of differential equations. Although for PDIRK methods the number of linear systems is usually higher than for Newton iteration of BDFs, the more computationally intensive work of computing the matrix of coefficients and its LU-decomposition are identical. The advantage of PDIRK methods over Newton-iterated BDFs is their unconditional stability (A-stability for Gauss-based methods and L-stability for Radau-based methods) for any order of accuracy. Special characteristics of the PDIRK methods will be studied, such as the rate of convergence, the influence of particular predictors on the resulting stability properties, and the stiff error constants in the global error.}
}
@book{Vandewalle1993,
address = {Stuttgart},
address2 = {Stuttgart},
editor = {Bock, H. G. and Hackbusch, W. and Rannacher, W.},
publisher = {B.~G.~Teubner},
series = {{Teubner Skripten zur Numerik}},
title = {{Parallel multigrid waveform relaxation for parabolic problems}},
url = {{http://dx.doi.org/10.1007/978-3-322-94761-1}},
doi = {10.1007/978-3-322-94761-1}},
year = {1993},
}
%
% 1994
%
@incollection{JanssenVandewalle1994,
address = {Amsterdam},
author = {J. Janssen and S. Vandewalle},
booktitle = {Contributions to multigrid ({A}msterdam, 1993)},
pages = {75--86},
publisher = {Math. Centrum Centrum Wisk. Inform.},
series = {CWI Tract},
title = {{Multigrid waveform relaxation on spatial finite element meshes}},
volume = {103},
year = {1994}
}
@article{Kiehl1994,
author = {Kiehl, M.},
journal = {Parallel Computing},
number = {3},
pages = {275--295},
title = {{Parallel multiple shooting for the solution of initial value problems}},
url = {http://dx.doi.org/10.1016/S0167-8191(06)80013-X},
doi = {10.1016/S0167-8191(06)80013-X},
volume = {20},
year = {1994}
}
@article{Toomarian1994,
author = {Toomarian, Nikzad and Fijany, Amir and Barmen, Jacob},
journal = {Concurrency: Practice and Experience},
number = {8},
pages = {641--652},
title = {{Time-parallel solution of linear partial differential equations on the {I}ntel {T}ouchstone {D}elta supercomputer}},
url = {http://dx.doi.org/10.1002/cpe.4330060803},
doi = {10.1002/cpe.4330060803},
volume = {6},
year = {1994}
}
@incollection{VandewalleHorton1994,
author = {Vandewalle, Stefan and Horton, Graham},
booktitle = {{Multigrid Methods IV}},
editor = {Hemker, P.W. and Wesseling, P.},
pages = {97--109},
publisher = {Birkhäuser Basel},
series = {{ISNM International Series of Numerical Mathematics}},
title = {{Multicomputer-Multigrid Solution of Parabolic Partial Differential Equations}},
url = {http://dx.doi.org/10.1007/978-3-0348-8524-9_7},
doi = {10.1007/978-3-0348-8524-9_7},
volume = {116},
year = {1994}
}
@article{VandewalleVandeVelde1994,
author = {Vandewalle, {Stefan G.} and {Van de Velde}, {Eric F.}},
journal = {Annals of Numerical Mathematics},
number = {1-4},
pages = {347--360},
title = {{Space-time concurrent multigrid waveform relaxation}},
url = {http://dx.doi.org/10.13140/2.1.1146.1761},
doi = {10.13140/2.1.1146.1761},
volume = {1},
year = {1994}
}
%
% 1995
%
@book {Burrage1995,
author = {Burrage, Kevin},
series = {{Numerical Mathematics and Scientific Computation}},
note = {{Oxford Science Publications}},
pages = {xvi+446},
publisher = {{The Clarendon Press, Oxford University Press, New York}},
title = {{Parallel and sequential methods for ordinary differential equations}},
isbn = {0-19-853432-9},
year = {1995}
}
@article{DeshpandeEtAl1995,
author = {Deshpande, A. and Malhotra, S. and Schultz, M. and Douglas, C.},
journal = {Parallel Algorithms and Applications},
number = {1},
pages = {53--62},
title = {{A rigorous analysis of time domain parallelism}},
url = {http://dx.doi.org/10.1080/10637199508915498},
doi = {10.1080/10637199508915498},
volume = {6},
year = {1995}
}
@article{HortonEtAl1995,
author = {Horton, Graham and Vandewalle, Stefan and Worley, P.},
journal = {SIAM Journal on Scientific Computing},
number = {3},
pages = {531--541},
title = {{An Algorithm with Polylog Parallel Complexity for Solving Parabolic Partial Differential Equations}},
url = {http://dx.doi.org/10.1137/0916034},
doi = {10.1137/0916034},
volume = {16},
year = {1995}
}
@article{HortonVandewalle1995,
author = {Horton, Graham and Vandewalle, Stefan},
journal = {SIAM Journal on Scientific Computing},
number = {4},
pages = {848--864},
title = {{A Space-Time Multigrid Method for Parabolic Partial Differential Equations}},
url = {http://dx.doi.org/10.1137/0916050},
doi = {10.1137/0916050},
volume = {16},
year = {1995}
}
@article{JacksonEtAl1995,
abstract = {{The authors examine the potential for parallelism in Runge–Kutta (RK) methods based on formulas in standard one-step form. Both negative and positive results are presented. Many of the negative results are based on a theorem that bounds the order of an RK formula in terms of the minimal polynomial associated with its coefficient matrix. The positive results are largely examples of prototypical formulas that offer a potential for effective “coarse-grain” parallelism on machines with a few processors.}},
author = {K. R. Jackson and S. P. N{\o}rsett},
title = {The Potential for Parallelism in Runge–Kutta Methods. Part 1: RK Formulas in Standard Form},
journal = {SIAM Journal on Numerical Analysis},
volume = {32},
number = {1},
pages = {49--82},
year = {1995},
doi = {10.1137/0732002},
URL = {http://dx.doi.org/10.1137/0732002},
}
@article{VandewalleHorton1995,
author = {Vandewalle, Stefan and Horton, Graham},
journal = {Computing},
number = {4},
pages = {317--330},
title = {{Fourier mode analysis of the multigrid waveform relaxation and time-parallel multigrid methods}},
url = {http://dx.doi.org/10.1007/BF02238230},
doi = {10.1007/BF02238230},
volume = {54},
year = {1995}
}
%
% 1996
%
@incollection{Burrage1996,
author = {Burrage, Kevin},
booktitle = {{Applications on Advanced Architecture Computers}},
editor = {Astfalk, Greg},
location = {Philadelphia},
pages = {101--120},
publisher = {Society for Industrial and Applied Mathematics},
title = {{Parallel methods for systems of ordinary differential equations}},
url = {{http://dx.doi.org/10.1137/1.9780898719659.ch10}},
doi = {{10.1137/1.9780898719659.ch10}},
year = {1996},
}
@article{JanssenVandewalle1996,
author = {Janssen, J. and Vandewalle, Stefan},
journal = {SIAM Journal on Scientific Computing},
number = {1},
pages = {133--155},
title = {{Multigrid Waveform Relaxation on Spatial Finite Element Meshes: The Discrete-Time Case}},
url = {{http://dx.doi.org/10.1137/0917011}},
doi = {{10.1137/0917011}},
volume = {17},
year = {1996},
}
@article{TaasanZhang1996,
author = {Ta'asan, Shlomo and Zhang, Hong},
journal = {BIT Numerical Mathematics},
number = {4},
pages = {831--841},
title = {{Fourier-Laplace analysis of the multigrid waveform relaxation method for hyperbolic equations}},
url = {http://dx.doi.org/10.1007/BF01733794},
doi = {10.1007/BF01733794},
volume = {36},
year = {1996}
}
%
% 1997
%
@article{Burrage1997,
author = {Burrage, Kevin},
journal = {Advances in Computational Mathematics},
pages = {1--3},
title = {{Parallel methods for {ODE}s}},
url = {http://dx.doi.org/10.1023/A:1018997130884},
doi = {10.1023/A:1018997130884},
volume = {7},
year = {1997}
}
%
% 1998
%
@article{Gander1998,
author = {Gander, Martin J. and Stuart, Andrew M.},
journal = {SIAM Journal on Scientific Computing},
number = {6},
pages = {2014--2031},
title = {{Space-Time Continuous Analysis of Waveform Relaxation for the Heat Equation}},
url = {http://dx.doi.org/10.1137/S1064827596305337},
doi = {10.1137/S1064827596305337},
volume = {19},
year = {1998}
}
@ARTICLE{Wang1998,
abstract={{The paper presents a new parallel method for the transient stability analysis of power systems. For simplicity, the classical power system model is adopted. The implicit trapezoidal rule is used to discretise the set of differential equations which describes the transient stability problem. As is well known, these discretised nonlinear algebraic equations are almost invariably solved by a Newton procedure. A parallel-in-time relaxed Newton method is proposed to solve the overall set of discretised equations concurrently on all the time steps. The proposed method has been tested on Cray-T3D by the use of PVM system. The test results show that the proposed method presents a good compromise between parallelism-in-time and convergence. Some important aspects for parallel transient stability analysis have been clarified}},
author={F.~Z. Wang},
doi={10.1049/ip-gtd:19981836},
journal={IEE Proceedings - Generation, Transmission and Distribution},
number={2},
pages={155--159},
title={Parallel-in-time relaxed Newton method for transient stability analysis},
url = {https://dx.doi.org/10.1049/ip-gtd:19981836},
volume={145},
year={1998},
}
%
% 2000
%
@article {SheenEtAl2000,
author = {Sheen, Dongwoo and Sloan, Ian H. and Thom\'{e}e, Vidar},
title = {{A parallel method for time-discretization of parabolic problems based on contour integral representation and quadrature}},
journal = {Mathematics of Computation},
volume = {69},
year = {2000},
number = {229},
pages = {177--195},
doi = {10.1090/S0025-5718-99-01098-4},
url = {https://doi.org/10.1090/S0025-5718-99-01098-4},
}
%
% 2001
%
@article{BotchevVorst2001,
author = {Botchev, M.~A. and van der Vorst, H.~A.},
journal = {Journal of Computational and Applied Mathematics},
number = {2},
pages = {229--243},
title = {{A parallel nearly implicit time-stepping scheme}},
url = {http://dx.doi.org/10.1016/S0377-0427(01)00358-2},
doi = {10.1016/S0377-0427(01)00358-2},
volume = {137},
year = {2001}
}
@article{LionsEtAl2001,
abstract = {{The purpose of this Note is to propose a time discretization of a partial differential evolution equation that allows for parallel implementations. The method, based on an Euler scheme, combines coarse resolutions and independent fine resolutions in time in the same spirit as standard spacial approximations. The resulting parallel implementation is done in the non standard time direction. Its main goal concerns real time problems, hence the proposed terminology of “parareal” algorithm.}},
author = {Lions, J.-L. and Maday, Yvon and Turinici, Gabriel},
journal = {Comptes Rendus de l'Académie des Sciences - Series I - Mathematics},
pages = {661--668},
title = {{A "parareal" in time discretization of {PDE}'s}},
url = {http://dx.doi.org/10.1016/S0764-4442(00)01793-6},
doi = {10.1016/S0764-4442(00)01793-6},
volume = {332},
year = {2001}
}
%
% 2002
%
@article{BafficoEtAl2002,
author = {Baffico, L. and Bernard, S. and Maday, Yvon and Turinici, Gabriel and Zérah, G.},
issue = {5},
journal = {Phys. Rev. E},
numpages = {4},
pages = {057701},
title = {{Parallel-in-time molecular-dynamics simulations}},
url = {http://link.aps.org/doi/10.1103/PhysRevE.66.057701},
doi = {10.1103/PhysRevE.66.057701},
volume = {66},
year = {2002}
}
@incollection{BalMaday2002,
author = {Bal, Guillaume and Maday, Yvon},
booktitle = {{Recent Developments in Domain Decomposition Methods}},
editor = {Pavarino, L. and Toselli, A.},
pages = {189--202},
publisher = {Springer Berlin},
series = {{Lecture Notes in Computational Science and Engineering}},
title = {{A "Parareal" time discretization for non-linear {PDE}'s with application to the pricing of an American Put}},
url = {http://dx.doi.org/10.1007/978-3-642-56118-4_12},
doi = {10.1007/978-3-642-56118-4_12},
volume = {23},
year = {2002}
}
@article{GiladiKeller2002,
author = {Giladi, Eldar and Keller, Herbert B.},
title = {Space-time domain decomposition for parabolic problems},
journal = {Numerische Mathematik},
volume = {93},
year = {2002},
number = {2},
pages = {279--313},
doi = {10.1007/s002110100345},
url = {https://doi.org/10.1007/s002110100345},
}
@article{MadayTurinici2002,
author = {Maday, Yvon and Turinici, Gabriel},
journal = {Comptes Rendus Mathématique},
number = {4},
pages = {387--392},
title = {{A parareal in time procedure for the control of partial differential equations}},
url = {http://dx.doi.org/10.1016/S1631-073X(02)02467-6},
doi = {10.1016/S1631-073X(02)02467-6},
volume = {335},
year = {2002}
}
%
% 2003
%
@article{FarhatEtAl2003,
author = {Farhat, Charbel and Chandesris, M.},
journal = {International Journal for Numerical Methods in Engineering},
number = {9},
pages = {1397--1434},
title = {{Time-decomposed parallel time-integrators: theory and feasibility studies for fluid, structure, and fluid-structure applications}},
url = {http://dx.doi.org/10.1002/nme.860},
doi = {10.1002/nme.860},
volume = {58},
year = {2003}
}
@article{MadayTurinici2003,
author = {Maday, Yvon and Turinici, Gabriel},
journal = {Int. J. Quant. Chem.},
number = {3},
pages = {223--228},
title = {{Parallel in time algorithms for quantum control: Parareal time discretization scheme}},
doi = {10.1002/qua.10554},
url = {http://dx.doi.org/10.1002/qua.10554},
volume = {93},
year = {2003}
}
@article {SheenEtAl2003,
author = {Sheen, Dongwoo and Sloan, Ian H. and Thom\'{e}e, Vidar},
title = {{A parallel method for time discretization of parabolic equations based on {L}aplace transformation and quadrature}},
journal = {IMA Journal of Numerical Analysis},
volume = {23},
year = {2003},
number = {2},
pages = {269--299},
doi = {10.1093/imanum/23.2.269},
url = {https://doi.org/10.1093/imanum/23.2.269},
}
%
% 2004
%
@article{Trindade2004,
author = {Trindade, J.~M.~F. and Pereira, J.~C.~F.},
journal = {International Journal for Numerical Methods in Fluids},
number = {10},
pages = {1123--1136},
title = {{Parallel-in-time simulation of the unsteady {N}avier-{S}tokes equations for incompressible flow}},
url = {http://dx.doi.org/10.1002/fld.732},
doi = {10.1002/fld.732},
volume = {45},
year = {2004}
}
%
% 2005
%
@inproceedings{Bal2005,
address = {Berlin},
author = {Bal, Guillaume},
booktitle = {{Domain Decomposition Methods in Science and Engineering}},
editor = {Kornhuber, Ralf and {et al.}},
pages = {426--432},
publisher = {Springer},
series = {{Lecture Notes in Computational Science and Engineering}},
title = {{On the convergence and the stability of the parareal algorithm to solve partial differential equations}},
url = {http://dx.doi.org/10.1007/3-540-26825-1_43},
doi = {10.1007/3-540-26825-1_43},
volume = {40},
year = {2005}
}
@article{Borzi2005,
author = {Borzì, Alfio and Griesse, R.},
journal = {International Journal for Numerical Methods in Fluids},
number = {8-9},
pages = {879--885},
title = {{Experiences with a space--time multigrid method for the optimal control of a chemical turbulence model}},
url = {http://dx.doi.org/10.1002/fld.904},
doi = {10.1002/fld.904},
volume = {47},
year = {2005}
}
@inproceedings{FischerEtAl2005,
address = {Berlin},
author = {Fischer, P.~F. and Hecht, F. and Maday, Yvon},
booktitle = {{Domain Decomposition Methods in Science and Engineering}},
editor = {Kornhuber, Ralf and {et al.}},
pages = {433--440},
publisher = {Springer},
series = {{Lecture Notes in Computational Science and Engineering}},
title = {{A parareal in time semi-implicit approximation of the {N}avier-{S}tokes equations}},
url = {{http://dx.doi.org/10.1007/3-540-26825-1_44}},
doi = {{10.1007/3-540-26825-1_44}},
volume = {40},
year = {2005}
}
@incollection{GarridoEtAl2005,
author = {Garrido, Izaskun and Espedal, Magne S. and Fladmark, Gunnar E.},
booktitle = {{Domain Decomposition Methods in Science and Engineering}},
editor = {Barth, Timothy J. and {al.}},
pages = {469--476},
publisher = {Springer Berlin Heidelberg},
series = {{Lecture Notes in Computational Science and Engineering}},
title = {{A Convergent Algorithm for Time Parallelization Applied to Reservoir Simulation}},
url = {http://dx.doi.org/10.1007/3-540-26825-1_48},
doi = {10.1007/3-540-26825-1_48},
volume = {40},
year = {2005}
}
@inproceedings{MadayTurinici2005,
address = {Berlin},
author = {Maday, Yvon and Turinici, Gabriel},
booktitle = {{Domain Decomposition Methods in Science and Engineering}},
editor = {Kornhuber, Ralf and {et al.}},
pages = {441--448},
publisher = {Springer},
series = {{Lecture Notes in Computational Science and Engineering}},
title = {{The parareal in time iterative solver: A further direction to parallel implementation}},
url = {{http://dx.doi.org/10.1007/3-540-26825-1_45}},
doi = {{10.1007/3-540-26825-1_45}},
volume = {40},
year = {2005},
}
@article{SchmittEtAl2005,
abstract = {{Peer two-step W-methods are designed for integration of stiff initial value problems with parallelism
across the method.
The essential feature is that in each time step $s$ 'peer' approximations are employed having similar properties.
In fact, no primary solution variable is distinguished.
Parallel implementation of these stages is easy since information from one previous time step is used only and
the different linear systems may be solved simultaneously.
This paper introduces a subclass having order $s-1$ where optimal damping for stiff problems is obtained by using
different system parameters in different stages.
Favourable properties of this subclass are uniform stability for realistic stepsize sequences and a
superconvergence property which is proved using a polynomial collocation formulation.
Numerical tests on a shared memory computer of a matrix-free implementation with Krylov methods are included.}},
author = {Schmitt, Bernhard A. and Weiner, Ruediger and Podhaisky, Helmut},
doi = {10.1007/s10543-005-2635-y},
journal = {BIT Numerical Mathematics},
number = {1},
pages = {197--217},
title = {Multi-Implicit Peer Two-Step W-Methods for Parallel Time Integration},
url = {http://dx.doi.org/10.1007/s10543-005-2635-y},
volume = {45},
year = {2005},
}
@article{SrinivasanChandra2005,
author = {Srinivasan, Ashok and Chandra, Namas},
journal = {Parallel Computing},
number = {7},
pages = {777--796},
title = {{Latency tolerance through parallelization of time in scientific applications}},
url = {http://dx.doi.org/10.1016/j.parco.2005.04.008},
doi = {10.1016/j.parco.2005.04.008},
volume = {31},
year = {2005}
}
@incollection{SrinivasanEtAl2005,
author = {Srinivasan, Ashok and Yu, Yanan and Chandra, Namas},
booktitle = {{High Performance Computing -- HiPC 2005}},
editor = {Bader, David A. and Parashar, Manish and Sridhar, Varadarajan and Prasanna, Viktor K.},
isbn = {978-3-540-30936-9},
pages = {106--117},
publisher = {Springer Berlin Heidelberg},
series = {{Lecture Notes in Computer Science}},
title = {{Application of Reduce Order Modeling to Time Parallelization}},
url = {http://dx.doi.org/10.1007/11602569_15},
doi = {10.1007/11602569_15},
volume = {3769},
year = {2005}
}
@inproceedings{StaffRonquist2005,
address = {Berlin},
author = {Staff, G.~A. and Rønquist, Einar M.},
booktitle = {{Domain Decomposition Methods in Science and Engineering}},
editor = {Kornhuber, Ralf and {et al.}},
pages = {449--456},
publisher = {Springer},
series = {{Lecture Notes in Computational Science and Engineering}},
title = {{Stability of the parareal algorithm}},
url = {http://dx.doi.org/10.1007/3-540-26825-1_46},
doi = {10.1007/3-540-26825-1_46},
volume = {40},
year = {2005}
}
@article {Thome2005,
author = {Thom\'{e}e, Vidar},
title = {A high order parallel method for time discretization of parabolic type equations based on {L}aplace transformation and quadrature},
journal = {International Journal of Numerical Analysis and Modeling},
volume = {2},
year = {2005},
number = {1},
pages = {85--96},
}
%
% 2006
%
@article{FarhatEtAl2006,
author = {Farhat, Charbel and Cortial, Julien and Dastillung, C. and Bavestrello, H.},
issue = {5},
journal = {International Journal for Numerical Methods in Engineering},
pages = {697--724},
title = {{Time-parallel implicit integrators for the near-real-time prediction of linear structural dynamic responses}},
url = {http://dx.doi.org/10.1002/nme.1653},
doi = {10.1002/nme.1653},
volume = {67},
year = {2006}
}
@incollection{NassifEtAl2006,
author = {Nassif, Nabil R. and Karam, Noha Makhoul and Soukiassian, Yeran},
booktitle = {{Computational Science -- ICCS 2006}},
editor = {Alexandrov, Vassil N. and Albada, Geert Dick and Sloot, Peter M.A. and Dongarra, Jack},
pages = {148--155},
publisher = {Springer Berlin Heidelberg},
series = {{Lecture Notes in Computer Science}},
title = {{A New Approach for Solving Evolution Problems in Time-Parallel Way}},
url = {{http://dx.doi.org/10.1007/11758501_24}},
doi = {{10.1007/11758501_24}},
volume = {3991},
year = {2006}
}
@article{Trindade2006,
author = {Trindade, J.~M.~F. and Pereira, J.~C.~F.},
journal = {Numerical Heat Transfer, Part B: Fundamentals},
number = {1},
pages = {25--40},
title = {{Parallel-in-Time Simulation of Two-Dimensional, Unsteady, Incompressible Laminar Flows}},
url = {http://dx.doi.org/10.1080/10407790500459379},
doi = {10.1080/10407790500459379},
volume = {50},
year = {2006}
}
@inproceedings{Yu2006,
author = {Yu, Yanan and Srinivasan, Ashok and Chandra, Namas},
booktitle = {{Parallel Processing, 2006. ICPP 2006. International Conference on}},
pages = {119--126},
title = {{Scalable Time-Parallelization of Molecular Dynamics Simulations in Nano Mechanics}},
url = {http://dx.doi.org/10.1109/ICPP.2006.64},
doi = {10.1109/ICPP.2006.64},
year = {2006}
}
%
% 2007
%
@incollection{Daoud2007,
author = {Daoud, Daoud S.},
booktitle = {{Domain Decomposition Methods in Science and Engineering {XVI}}},
editor = {Widlund, Olof B. and Keyes, David E.},
pages = {275--282},
publisher = {Springer Berlin Heidelberg},
series = {{Lecture Notes in Computational Science and Engineering}},
title = {{Stability of the Parareal Time Discretization for Parabolic Inverse Problems}},
url = {{http://dx.doi.org/10.1007/978-3-540-34469-8_32}},
doi = {{10.1007/978-3-540-34469-8_32}},
volume = {55},
year = {2007}
}
@inproceedings{GanderPetcu2007,
author = {Gander, Martin J. and Petcu, M.},
booktitle = {{AIP Conference Proceedings}},
pages = {233},
title = {{Analysis of a Modified Parareal Algorithm for Second-Order Ordinary Differential Equations}},
url = {{http://dx.doi.org/10.1063/1.2790116}},
doi = {{10.1063/1.2790116}},
volume = {936},
year = {2007},
}
@article{GanderVandewalle2007_SISC,
author = {Gander, Martin J. and Vandewalle, Stefan},
journal = {SIAM Journal on Scientific Computing},
number = {2},
pages = {556--578},
title = {{Analysis of the Parareal Time-Parallel Time-Integration Method}},
url = {http://dx.doi.org/10.1137/05064607X},
doi = {10.1137/05064607X},
volume = {29},
year = {2007}
}
@incollection{GanderVandewalle2007,
author = {Gander, Martin J. and Vandewalle, Stefan},
booktitle = {{Domain Decomposition Methods in Science and Engineering}},
editor = {Widlund, Olof B. and Keyes, David E.},
pages = {291--298},
publisher = {Springer Berlin Heidelberg},
series = {{Lecture Notes in Computational Science and Engineering}},
title = {{On the Superlinear and Linear Convergence of the Parareal Algorithm}},
url = {http://dx.doi.org/10.1007/978-3-540-34469-8_34},
doi = {10.1007/978-3-540-34469-8_34},
volume = {55},
year = {2007}
}
@incollection{GuibertTromeur2007,
author = {Guibert, David and Tromeur-Dervout, Damien},
booktitle = {{Domain Decomposition Methods in Science and Engineering {XVI}}},
editor = {Widlund, OlofB. and Keyes, DavidE.},
pages = {587--594},
publisher = {Springer Berlin Heidelberg},
series = {{Lecture Notes in Computational Science and Engineering}},
title = {{Adaptive Parareal for Systems of {ODE}s}},
url = {http://dx.doi.org/10.1007/978-3-540-34469-8_73},
doi = {10.1007/978-3-540-34469-8_73},
volume = {55},
year = {2007}
}
@article{GuibertTromeur2007_CAS,
author = {Guibert, David and Tromeur-Dervout, Damien},
journal = {Computers \& Structures},
number = {9},
pages = {553--562},
title = {{Parallel adaptive time domain decomposition for stiff systems of {ODE}s/{DAE}s}},
url = {http://dx.doi.org/10.1016/j.compstruc.2006.08.040},
doi = {10.1016/j.compstruc.2006.08.040},
volume = {85},
year = {2007}
}
@incollection{GuibertTromeur2007_PCFD,
address = {Amsterdam},
author = {Guibert, David and Tromeur-Dervout, Damien},
booktitle = {{Parallel Computational Fluid Dynamics 2006}},
editor = {Kwon, J.H. and Ecer, A. and Satofuka, N. and Periaux, J. and Fox, P.},
pages = {131--138},
title = {{Parallel deferred correction method for {CFD} problems}},
url = {http://dx.doi.org/10.1016/B978-044453035-6/50019-5},
doi = {10.1016/B978-044453035-6/50019-5},
year = {2007},
publisher = {Elsevier}
}
@article{KaberMaday2007,
author = {Kaber, S. M. and Maday, Yvon},
issue = {1},
journal = {PAMM},
pages = {1026403--1026404},
title = {{Parareal in time approximation of the {Korteveg-deVries-Burgers}' equations}},
url = {{http://dx.doi.org/10.1002/pamm.200700574}},
doi = {{10.1002/pamm.200700574}},
volume = {7},
year = {2007},
}
@article{MadayEtAl2007,
author = {Maday, Yvon and Salomon, Julien and Turinici, Gabriel},
journal = {SIAM Journal on Numerical Analysis},
number = {6},
pages = {2468--2482},
title = {{Monotonic parareal control for quantum systems}},
url = {http://dx.doi.org/10.1137/050647086},
doi = {10.1137/050647086},
volume = {45},
year = {2007},
}
@inbook{Ulbrich2007,
author = {Stefan Ulbrich},
title = {7. Generalized SQP Methods with ``Parareal'' Time-Domain Decomposition for Time-Dependent PDE-Constrained Optimization},
booktitle = {Real-Time PDE-Constrained Optimization},
chapter = {},
pages = {145--168},
doi = {10.1137/1.9780898718935.ch7},
url = {https://dx.doi.org/10.1137/1.9780898718935.ch7},
year = {2007},
publisher = {SIAM}
}
%
% 2008
%
@article{AmodioBrugnano2008,
author = {Amodio, Pierluigi and Brugnano, Luigi},
editor = {Simos, Theodore E. and Psihoyios, George and Tsitouras, Ch.},
journal = {AIP Conference Proceedings},
number = {1},
pages = {867--870},
title = {{Recent Advances in the Parallel Solution in Time of {ODE}s}},
url = {{http://dx.doi.org/10.1063/1.2991069}},
doi = {{10.1063/1.2991069}},
volume = {1048},
year = {2008},
}
@incollection{BalEtAl2008,
author = {Bal, Guillaume and Wu, Qi},
booktitle = {{Domain Decomposition Methods in Science and Engineering {XVII}}},
editor = {Langer, Ulrich and Discacciati, Marco and Keyes, DavidE. and Widlund, OlofB. and Zulehner, Walter},
pages = {401--408},
publisher = {Springer Berlin Heidelberg},
series = {{Lecture Notes in Computational Science and Engineering}},
title = {{Symplectic Parareal}},
url = {http://dx.doi.org/10.1007/978-3-540-75199-1_51},
doi = {10.1007/978-3-540-75199-1_51},
volume = {60},
year = {2008}
}
@article{Gander2008,
author = {Gander, Martin J.},
journal = {Bol. Soc. Esp. Mat. Apl.},
pages = {21--35},
title = {{Analysis of the Parareal Algorithm Applied to Hyperbolic Problems using Characteristics}},
volume = {42},
year = {2008}
}
@inproceedings{GanderHairer2008,
author = {Gander, Martin J. and Hairer, Ernst},
booktitle = {{Domain Decomposition Methods in Science and Engineering}},
editor = {Langer, U. and Widlund, O. and Keyes, D.},
pages = {45--56},
publisher = {Springer},
series = {{Lecture Notes in Computational Science and Engineering}},
title = {{Nonlinear Convergence Analysis for the Parareal Algorithm}},
url = {http://dx.doi.org/10.1007/978-3-540-75199-1_4},
doi = {10.1007/978-3-540-75199-1_4},
volume = {60},
year = {2008}
}
@article{GanderPetcu2008,
author = {Gander, Martin J. and Petcu, M.},
journal = {ESAIM: Proc.},
pages = {114--129},
title = {{Analysis of a {K}rylov Subspace Enhanced Parareal Algorithm for Linear Problem}},
url = {http://dx.doi.org/10.1051/proc:082508},
doi = {10.1051/proc:082508},
volume = {25},
year = {2008}
}
@article{Liu2008,
author = {Liu, Y. and Hu, J.},
journal = {Int. J. for Numerical Methods in Fluids},
number = {12},
pages = {1793--1804},
title = {{Modified propagators of parareal in time algorithm and application to {P}rinceton Ocean model}},
url = {http://dx.doi.org/10.1002/fld.1703},
doi = {10.1002/fld.1703},
volume = {57},
year = {2008}
}
@article{MadayRonquist2008,
author = {Maday, Yvon and Rønquist, Einar M.},
journal = {Comptes Rendus Mathematique},
number = {1--2},
pages = {113--118},
title = {{Parallelization in time through tensor-product space-time solvers}},
url = {{http://dx.doi.org/10.1016/j.crma.2007.09.012}},
doi = {{10.1016/j.crma.2007.09.012}},
volume = {346},
year = {2008},
}
@inproceedings{MinionEtAl2008,
author = {Minion, Michael L. and Williams, Sarah A.},
booktitle = {{AIP Conference Proceedings}},
pages = {388},
title = {{Parareal and spectral deferred corrections}},
url = {http://dx.doi.org/10.1063/1.2990941},
doi = {10.1063/1.2990941},
volume = {1048},
year = {2008}
}
@incollection{SarkisEtAl2008,
author = {Sarkis, Marcus and Schaerer, Christian E. and Mathew, Tarek},
booktitle = {{Domain Decomposition Methods in Science and Engineering {XVII}}},
editor = {Langer, Ulrich and {al.}},
pages = {409--416},
publisher = {Springer Berlin Heidelberg},
series = {{Lecture Notes in Computational Science and Engineering}},
title = {{Block Diagonal Parareal Preconditioner for Parabolic Optimal Control Problems}},
url = {{http://dx.doi.org/10.1007/978-3-540-75199-1_52}},
doi = {{10.1007/978-3-540-75199-1_52}},
volume = {60},
year = {2008}
}
%
% 2009
%
@article{AmodioBrugnano2009,
author = {Amodio, Pierluigi and Brugnano, Luigi},
journal = {Applied Numerical Mathematics},
number = {3--4},
pages = {424--435},
title = {{Parallel solution in time of {ODE}s: some achievements and perspectives}},
url = {http://dx.doi.org/10.1016/j.apnum.2008.03.024},
doi = {10.1016/j.apnum.2008.03.024},
volume = {59},
year = {2009}
}
@article{BorziWinckel2009,
author = {Borzì, Alfio and von Winckel, G.},
journal = {SIAM Journal on Scientific Computing},
number = {3},
pages = {2172--2192},
title = {{Multigrid Methods and Sparse-Grid Collocation Techniques for Parabolic Optimal Control Problems with Random Coefficients}},
url = {{http://dx.doi.org/10.1137/070711311}},
doi = {{10.1137/070711311}},
volume = {31},
year = {2009},
}
@article{Celledoni2009,
author = {Celledoni, E. and Kvamsdal, T.},
journal = {International Journal for Numerical Methods in Engineering},
number = {5},
pages = {576--598},
title = {{Parallelization in time for thermo-viscoplastic problems in extrusion of aluminium}},
url = {http://dx.doi.org/10.1002/nme.2585},
doi = {10.1002/nme.2585},
volume = {79},
year = {2009}
}
@article{CortialFarhat2009,
author = {Cortial, Julien and Farhat, Charbel},
journal = {International Journal for Numerical Methods in Engineering},
number = {4},
pages = {451--470},
title = {{A time-parallel implicit method for accelerating the solution of non-linear structural dynamics problems}},
url = {http://dx.doi.org/10.1002/nme.2418},
doi = {10.1002/nme.2418},
volume = {77},
year = {2009}
}
@article{Engblom2009,
author = {Engblom, S.},
journal = {Multiscale Modeling \& Simulation},
number = {1},
pages = {46--68},
title = {{Parallel in Time Simulation of Multiscale Stochastic Chemical Kinetics}},
url = {{http://dx.doi.org/10.1137/080733723}},
doi = {{10.1137/080733723}},
volume = {8},
year = {2009},
}
@article{FrantziskonisEtAl2009,
author = {Frantziskonis, G. and Muralidharan, K. and Deymier, P. and Simunovic, S. and Nukala, P. and Pannala, S.},
journal = {Journal of Computational Physics},
number = {21},
pages = {8085--8092},
title = {{Time-parallel multiscale/multiphysics framework}},
url = {{http://dx.doi.org/10.1016/j.jcp.2009.07.035}},
doi = {{10.1016/j.jcp.2009.07.035}},
volume = {228},
year = {2009},
}
@article{Maday2009,
author = {Maday, Yvon},
editor = {Simos, Theodore E. and Psihoyios, George and Tsitouras, Ch.},
journal = {AIP Conference Proceedings},
number = {1},
pages = {1515--1516},
title = {{Symposium: Recent Advances on the Parareal in Time Algorithms}},
url = {{http://dx.doi.org/10.1063/1.3241386}},
doi = {{10.1063/1.3241386}},
volume = {1168},
year = {2009},
}
@inproceedings{Mercerat2009,
author = {Mercerat, Diego and Guillot, Laurent and Vilotte, Jean-Pierre},
booktitle = {{AIP Conference Proceedings}},
pages = {1521--1524},
title = {{Application of the parareal algorithm for acoustic wave propagation}},
url = {{http://dx.doi.org/10.1063/1.3241388}},
doi = {{10.1063/1.3241388}},
volume = {1168},
year = {2009},
}
@article{NassifEtAl2009,
author = {Nassif, Nabil R. and Makhoul-Karam, Noha and Soukiassian, Yeran},
journal = {Journal of Computational and Applied Mathematics},
number = {1},
pages = {185--195},
title = {{Computation of blowing-up solutions for second-order differential equations using re-scaling techniques}},
url = {http://dx.doi.org/10.1016/j.cam.2008.07.020},
doi = {10.1016/j.cam.2008.07.020},
volume = {227},
year = {2009}
}
@article{Wu2009,
abstract = {{The parareal algorithm, proposed firstly by Lions et al., is an effective algorithm to
solve the time-dependent problems parallel in time.
This algorithm has received much interest from many researchers in the past years.
We present in this paper a new variant of the parareal algorithm, which is derived by combining the
original parareal algorithm and the Richardson extrapolation, for the numerical solution of the
nonlinear ODEs and PDEs.
Several nonlinear problems are tested to show the advantage of the new algorithm.
The accuracy of the obtained numerical solution is compared with that of its original version (i.e.,
the parareal algorithm based on the same numerical method).}},
author = {Wu, Shulin and Shi, Baochang and Huang, Chengming},
issue = {4},
journal = {Communications in Computational Physics},
pages = {883--902},
title = {Parareal-Richardson Algorithm for Solving Nonlinear ODEs and PDEs},
url = {http://dx.doi.org/10.4208/cicp.2009.v6.p883},
doi = {10.4208/cicp.2009.v6.p883},
volume = {6},
year = {2009},
}
%
% 2010
%
@article{BlouzaEtAl2010,
author = {Blouza, A. and Laurent, B. and Kaber, S.~M.},
journal = {Communications in Applied Mathematics and Computational Science},
number = {2},
pages = {241--263},
title = {{Parallel in time algorithms with reduction methods for solving chemical kinetics}},
url = {http://dx.doi.org/10.2140/camcos.2010.5.241},
doi = {10.2140/camcos.2010.5.241},
volume = {5},
year = {2010}
}
@article{ChristliebEtAl2010,
author = {Christlieb, Andrew J. and Macdonald, Colin B and Ong, Benjamin W.},
journal = {SIAM Journal on Scientific Computing},
number = {2},
pages = {818--835},
title = {{Parallel high-order integrators}},
url = {http://dx.doi.org/10.1137/09075740X},
doi = {10.1137/09075740X},
volume = {32},
year = {2010}
}
@article{FuEtAl2010,
abstract = {{Time stepping algorithm with spatial parallelisation is commonly used to solve time dependent partial differential equations. Computation in each time step is carried out using all processors available before sequentially advancing to the next time step. In cases where few spatial components are involved and there are relatively many processors available for use, this will result in fine granularity and decreased scalability. Naturally one alternative is to parallelise the temporal domain. Several time parallelisation algorithms have been suggested for the past two decades. One of them is the pipelined iterations across time steps. In this pipelined time stepping method, communication however is extensive between time steps during the pipelining process. This causes a decrease in performance on distributed memory environment which often has high message latency. We present a modified pipelined time stepping algorithm based on delayed pipelining and reduced communication strategies to improve overall execution time on a distributed memory environment using MPI. Our goal is to reduce the inter-time step communications while providing adequate information for the next time step to converge. Numerical result confirms that the improved algorithm is faster than the original pipelined algorithm and sequential time stepping algorithm with spatial parallelisation alone. The improved algorithm is most beneficial for fine granularity time dependent problems with limited spatial parallelisation.}},
author = {Ng Kok Fu and Norhashidah Hj. Mohd Ali},
journal = {Sains Malaysiana},
pages = {1041--1048},
title = {Improving Pipelined Time Stepping Algorithm for Distributed Memory Multicomputers},
volume = {39},
number = {6},
year = {2010},
url = {http://www.ukm.my/jsm/pdf_files/SM-PDF-39-6-2010/25%20Ng%20Kok%20Fu.pdf}
}
@inproceedings{LepsaSandu2010,
abstract = {{'Parareal' attempts to speed up the solution of ordinary differential equations (ODEs) by
parallelizing the time dimension.
Different solutions are obtained in parallel on different subintervals.
An iterative procedure is employed to match the solution values at the end of each subinterval with
those at the beginning of the next one.
It has been shown that insufficient 'parareal' iterations lead to an inaccurate solution, while too
many iterations waste CPU cycles without bringing any improvement to the solution.
In this paper we discuss an error control mechanism for both the classical 'parareal' time
discretization method and its adaptive variant.
This mechanism can be effectively used as a mean of controlling the number of 'parareal' iterations.
We show that bounding the difference between the solution of the fine integrator and the 'parareal'
solution by the local truncation error of the fine grid leads to a sufficient convergence criterion that
guaranties a solution that is accurate enough in a minimum number of iterations.
Tests on a nonlinear problem illustrate the effectiveness of the proposed error control mechanism on
the classical automatic adaptive time stepping formulation of an embedded method on the two-level
'parareal' algorithm.}},
acmid = {1878628},
address = {San Diego, CA, USA},
articleno = {87},
author = {Lepsa, Bianca and Sandu, Adrian},
booktitle = {{Proceedings of the 2010 Spring Simulation Multiconference}},
location = {Orlando, Florida},
numpages = {7},
pages = {87:1--87:7},
publisher = {Society for Computer Simulation International},
series = {{SpringSim '10}},
title = {{An efficient error control mechanism for the adaptive 'parareal' time discretization algorithm}},
url = {http://dx.doi.org/10.1145/1878537.1878628},
doi = {10.1145/1878537.1878628},
year = {2010},
}
@inproceedings{Lai2010,
author={Lai, C.~H.},
booktitle={{Substructing Techniques and Domain Decomposition Methods}},
pages={45--70},
series={Computational Science, Engineering \& Technology Series},
title={{On Transformation Methods and the Induced Parallel Properties for the Temporal Domain}},
url={http://dx.doi.org/10.4203/csets.24.3},
doi={10.4203/csets.24.3},
year={2010}
}
@article{MathewEtAl2010,
abstract = {{In this paper, we describe block matrix algorithms for the iterative solution of a
large-scale linear-quadratic optimal control problem involving a parabolic partial differential
equation over a finite control horizon.
We consider an "all at once" discretization of the problem and formulate three iterative algorithms.
The first algorithm is based on preconditioning a symmetric positive definite reduced linear system
involving only the unknown control variables; however inner-outer iterations are required.
The second algorithm modifies the first algorithm to avoid inner-outer iterations by introducing an
auxiliary variable.
It yields a symmetric indefinite system with a positive definite block preconditioner.
The third algorithm is the central focus of this paper.
It modifies the preconditioner in the second algorithm by a parallel-in-time preconditioner based on
the parareal algorithm.
Theoretical results show that the preconditioned algorithms have optimal convergence properties and
parallel scalability.
Numerical experiments confirm the theoretical results.}},
author = {Mathew, Tarek and Sarkis, Marcus and Schaerer, Christian E.},
journal = {SIAM Journal on Scientific Computing},
number = {3},
pages = {1180--1200},
title = {{Analysis of Block Parareal Preconditioners for Parabolic Optimal Control Problems}},
volume = {32},
year = {2010},
url = {http://dx.doi.org/10.1137/080717481},
doi = {10.1137/080717481},
}
@article{Minion2010,
author = {Minion, Michael L.},
journal = {Communications in Applied Mathematics and Computational Science},
number = {2},
pages = {265--301},
title = {{A Hybrid Parareal Spectral Deferred Corrections Method}},
url = {http://dx.doi.org/10.2140/camcos.2010.5.265},
doi = {10.2140/camcos.2010.5.265},
volume = {5},
year = {2010}
}
@article{Mitran2010,
author = {Mitran, Sorin},
journal = {Procedia Computer Science},
number = {1},
pages = {745--752},
title = {{Time parallel kinetic-molecular interaction algorithm for {CPU}/{GPU} computers}},
url = {http://dx.doi.org/10.1016/j.procs.2010.04.080},
doi = {10.1016/j.procs.2010.04.080},
volume = {1},
year = {2010}
}
@article{SamaddarEtAl2010,
author = {Samaddar, Debasmita and Newman, David E. and S\'{a}nchez, Raul S.},
issue = {18},
journal = {Journal of Computational Physics},
pages = {6558--6573},
title = {{Parallelization in time of numerical simulations of fully-developed plasma turbulence using the parareal algorithm}},
url = {http://dx.doi.org/10.1016/j.jcp.2010.05.012},
doi = {10.1016/j.jcp.2010.05.012},
volume = {229},
year = {2010}
}
%
% 2011
%
@article{Aubanel2011,
author = {Aubanel, E.},
journal = {Parallel Computing},
pages = {172--182},
title = {{Scheduling of Tasks in the Parareal Algorithm}},
url = {http://dx.doi.org/10.1016/j.parco.2010.10.004},
doi = {10.1016/j.parco.2010.10.004},
volume = {37},
year = {2011}
}
@inproceedings{Cadeau2011,
author = {Cadeau, T. and Magoules, F.},
booktitle = {{Distributed Computing and Applications to Business, Engineering and Science (DCABES), 2011 Tenth International Symposium on}},
pages = {15--19},
title = {{Coupling the Parareal Algorithm with the Waveform Relaxation Method for the Solution of Differential Algebraic Equations}},
url = {http://dx.doi.org/10.1109/DCABES.2011.34},
doi = {10.1109/DCABES.2011.34},
year = {2011}
}
@article{ChristliebEtAl2011,
author = {Christlieb, Andrew J. and Ong, Benjamin W.},
journal = {Journal of Scientific Computing},
number = {2},
pages = {167--179},
title = {{Implicit parallel time integrators}},
url = {http://dx.doi.org/10.1007/s10915-010-9452-4},
doi = {10.1007/s10915-010-9452-4},
volume = {49},
year = {2011}
}
@article{DouglasEtAl2011,
author = {Douglas, C. and Kim, I. and Lee, H. and Sheen, D.},
title = {{Higher-order schemes for the {L}aplace transformation method for parabolic problems}},
journal = {Computing and Visualization in Science},
volume = {14},
year = {2011},
number = {1},
pages = {39--47},
doi = {10.1007/s00791-011-0156-6},
url = {https://doi.org/10.1007/s00791-011-0156-6},
}
@article{DuarteEtAl2011,
author = {Duarte, Max and Massot, Marc and Descombes, Stéphane},
issue = {05},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis},
month = {8},
pages = {825--852},
title = {{Parareal operator splitting techniques for multi-scale reaction waves: Numerical analysis and strategies}},
url = {http://dx.doi.org/10.1051/m2an/2010104},
doi = {10.1051/m2an/2010104},
volume = {45},
year = {2011}
}
@inproceedings{ElwasifEtAl2011,
author = {Elwasif, Wael R. and Foley, Samantha S. and Bernholdt, David E. and Berry, Lee A. and Samaddar, Debasmita and Newman, David E. and Sánchez, Raul S.},
booktitle = {{Proceedings of the 2011 ACM international workshop on many task computing on grids and supercomputers}},
pages = {15--24},
title = {{A dependency-driven formulation of parareal: parallel-in-time solution of {PDE}s as a many-task application}},
url = {http://dx.doi.org/10.1145/2132876.2132883},
doi = {10.1145/2132876.2132883},
year = {2011}
}
%
% 2012
%
@incollection{ArbenzEtAl2012,
author = {Arbenz, Peter and Hiltebrand, Andreas and Obrist, Dominik},
booktitle = {{Parallel Processing and Applied Mathematics}},
editor = {Wyrzykowski, Roman and Dongarra, Jack and Karczewski, Konrad and Waśniewski, Jerzy},
pages = {302--312},
publisher = {Springer Berlin Heidelberg},
series = {{Lecture Notes in Computer Science}},
title = {{A Parallel Space-Time Finite Difference Solver for Periodic Solutions of the Shallow-Water Equation}},
url = {http://dx.doi.org/10.1007/978-3-642-31500-8_31},
doi = {10.1007/978-3-642-31500-8_31},
volume = {7204},
year = {2012}
}
@article{BerryEtAl2012,
author = {Berry, Lee A. and Elwasif, Wael R. and Reynolds-Barredo, J.~M. and Samaddar, Debasmita and Sánchez, Raul S. and Newman, David E.},
journal = {Journal of Computational Physics},
number = {17},
pages = {5945--5954},
title = {{Event-based parareal: A data-flow based implementation of parareal}},
url = {http://dx.doi.org/10.1016/j.jcp.2012.05.016},
doi = {10.1016/j.jcp.2012.05.016},
volume = {231},
year = {2012}
}
@article{ChristliebEtAl2012,
author = {Christlieb, Andrew J. and Haynes, Ronald D. and Ong, Benjamin W.},
journal = {SIAM Journal on Scientific Computing},
number = {5},
pages = {C233--C248},
title = {{A Parallel Space-Time Algorithm}},
url = {http://dx.doi.org/10.1137/110843484},
doi = {10.1137/110843484},
volume = {34},
year = {2012}
}
@article{EmmettMinion2012,
author = {Emmett, Matthew and Minion, Michael L.},
journal = {Communications in Applied Mathematics and Computational Science},
pages = {105--132},
title = {{Toward an Efficient Parallel in Time Method for Partial Differential Equations}},
url = {http://dx.doi.org/10.2140/camcos.2012.7.105},
doi = {10.2140/camcos.2012.7.105},
volume = {7},
year = {2012}
}
@techreport{FoleyEtAl2012,
author = {Foley, Samantha S. and Elwasif, Wael R. and Bernholdt, David E.},
institution = {Oak Ridge National Laboratory},
number = {ORNL/TM-2012/57},
title = {{The integrated plasma simulator: A flexible python framework for coupled multiphysics simulation}},
url = {http://info.ornl.gov/sites/publications/files/Pub34832.pdf},
year = {2012}
}
@article{GeiserGuettel2012,
author = {Geiser, Jürgen and G{\"u}ttel, Stefan},
journal = {Journal of Mathematical Analysis and Applications},
number = {2},
pages = {873--887},
title = {{Coupling methods for heat transfer and heat flow: Operator splitting and the parareal algorithm}},
url = {http://dx.doi.org/10.1016/j.jmaa.2011.10.030},
doi = {10.1016/j.jmaa.2011.10.030},
volume = {388},
year = {2012}
}
@article{He2012,
abstract = {{In this paper, a reduced morphological transformation model with spatially dependent composition and
elastic modulus is considered.
The parareal in time algorithm introduced by Lions et al. is developed for longer-time simulation.
The fine solver is based on a second-order scheme in reciprocal space, and the coarse solver is based on a
multi-model backward Euler scheme, which is fast and less expensive.
Numerical simulations concerning the composition with a random noise and a discontinuous curve are performed.
Some microstructure characteristics at very low temperature are obtained by a variable temperature technique.}},
author = {He,Li-Ping and He,Minxin},
doi = {10.4208/cicp.110310.090911a},
issue = {5},
journal = {Communications in Computational Physics},
pages = {1697--1717},
title = {Parareal in Time Simulation Of Morphological Transformation in Cubic Alloys with Spatially Dependent Composition},
url = {http://dx.doi.org/10.4208/cicp.110310.090911a},
volume = {11},
year = {2012},
}
@article{LiuJiang2012,
author = {Liu, Jun and Jiang, Yao-Lin},
journal = {Mathematics and Computers in Simulation},
number = {11},
pages = {2167--2181},
title = {{A parareal algorithm based on waveform relaxation}},
url = {http://dx.doi.org/10.1016/j.matcom.2012.05.017},
doi = {10.1016/j.matcom.2012.05.017},
volume = {82},
year = {2012}
}
@article{LiuJiang2012_JCAM,
author = {Liu, Jun and Jiang, Yao-Lin},
journal = {Journal of Computational and Applied Mathematics},
number = {17},
pages = {4245--4263},
title = {{A parareal waveform relaxation algorithm for semi-linear parabolic partial differential equations}},
url = {http://dx.doi.org/10.1016/j.cam.2012.05.014},
doi = {10.1016/j.cam.2012.05.014},
volume = {236},
year = {2012}
}
@unpublished{Loic2012,
abstract = {{The Parareal algorithm is used to solve time-dependent problems considering multiple solvers that may work in parallel. The key feature is a initial rough approximation of the solution that is iteratively refined by the parallel solvers. We report a derivation of the Parareal method that uses a convergence acceleration technique to improve the accuracy of the solution. Our approach uses firstly an explicit ODE solver to perform the parallel computations with different time-steps and then, a decomposition of the solution into specific convergent series, based on an extrapolation method, allows to refine the precision of the solution. Our proposed method exploits basic explicit integration methods, such as for example the explicit Euler scheme, in order to preserve the simplicity of the global parallel algorithm. The first part of the paper outlines the proposed method applied to the simple explicit Euler scheme and then the derivation of the classical Parareal algorithm is discussed and illustrated with numerical examples.}},
author = {Lo{\"i}c, Michel},
title = {Semi-explicit Parareal method based on convergence acceleration technique},
howpublished = {arXiv:1212.4703 [cs.SY]},
url = {https://arxiv.org/abs/1212.4703},
year = {2012},
}
@unpublished{OngEtAl2012,
author = {Ong, Benjamin W. and Melfi, Andrew and Christlieb, Andrew J.},
note = {arXiv:1209.4297 [cs.DC]},
title = {{Parallel Semi-Implicit Time Integrators}},
url = {http://arxiv.org/abs/1209.4297},
year = {2012}
}
@inproceedings{RaoEtAl2012,
author = {Rao, Vishwas and Cioaca, Alexandru and Sandu, Adrian},
booktitle = {{High Performance Computing, Networking, Storage and Analysis (SCC), 2012 SC Companion:}},
pages = {609--616},
title = {{A Highly Scalable Approach for Time Parallelization of Long Range Forecasts}},
url = {http://dx.doi.org/10.1109/SC.Companion.2012.85},
doi = {10.1109/SC.Companion.2012.85},
year = {2012}
}
@article{ReynoldsEtAl2012,
author = {Reynolds-Barredo, J.~M. and Newman, David E. and Sánchez, Raul S. and Samaddar, Debasmita and Berry, Lee A. and Elwasif, Wael R.},
journal = {Journal of Computational Physics},
number = {23},
pages = {7851--7867},
title = {{Mechanisms for the convergence of time-parallelized, parareal turbulent plasma simulations}},
url = {http://dx.doi.org/10.1016/j.jcp.2012.07.028},
doi = {10.1016/j.jcp.2012.07.028},
volume = {231},
year = {2012}
}
@inproceedings{ReynoldsEtAl2012_HPCS,
author = {Reynolds-Barredo, J. M. and Newman, David E. and Sánchez, Raul S. and Berry, Lee A.},
booktitle = {{High Performance Computing and Simulation (HPCS), 2012 International Conference on}},
pages = {726--727},
title = {{Modelling parareal convergence in 2D drift wave plasma turbulence}},
url = {http://dx.doi.org/10.1109/HPCSim.2012.6267004},
doi = {10.1109/HPCSim.2012.6267004},
year = {2012}
}
@article{RuprechtKrause2012,
abstract = {{The applicability of the Parareal parallel-in-time integration scheme for the solution of a linear,
two-dimensional hyperbolic acoustic-advection system, which is often used as a test case for integration schemes
for numerical weather prediction (NWP), is addressed.
Parallel-in-time schemes are a possible way to increase, on the algorithmic level, the amount of parallelism, a
requirement arising from the rapidly growing number of CPUs in high performance computer systems.
A recently introduced modification of the "parallel implicit time-integration algorithm" could successfully
solve hyperbolic problems arising in structural dynamics.
It has later been cast into the framework of Parareal.
The present paper adapts this modified Parareal and employs it for the solution of a hyperbolic flow problem,
where the initial value problem solved in parallel arises from the spatial discretization of a partial
differential equation by a finite difference method.
It is demonstrated that the modified Parareal is stable and can produce reasonably accurate solutions while
allowing for a noticeable reduction of the time-to-solution.
The implementation relies on integration schemes already widely used in NWP (RK-3, partially split forward
Euler, forward-backward).
It is demonstrated that using an explicit partially split scheme for the coarse integrator allows to avoid the
use of an implicit scheme while still achieving speedup.}},
author = {Ruprecht, Daniel and Krause, Rolf},
journal = {Computers \& Fluids},
number = {0},
pages = {72--83},
title = {{Explicit parallel-in-time integration of a linear acoustic-advection system}},
url = {http://dx.doi.org/10.1016/j.compfluid.2012.02.015},
doi = {10.1016/j.compfluid.2012.02.015},
volume = {59},
year = {2012}
}
@inproceedings{SpeckEtAl2012,
abstract = {{We present a novel space-time parallel version of the Barnes-Hut tree code PEPC using PFASST, the
Parallel Full Approximation Scheme in Space and Time.
The naive use of increasingly more processors for a fixed-size N-body problem is prone to saturate as soon as
the number of unknowns per core becomes too small.
To overcome this intrinsic strong-scaling limit, we introduce temporal parallelism on top of pepc's existing
hybrid MPI/PThreads spatial decomposition.
Here, we use PFASST which is based on a combination of the iterations of the parallel-in-time algorithm parareal
with the sweeps of spectral deferred correction (SDC) schemes.
By combining these sweeps with multiple space-time discretization levels, PFASST relaxes the theoretical bound
on parallel efficiency in parareal.
We present results from runs on up to 262,144 cores on the IBM Blue Gene/P installation JUGENE, demonstrating
that the space-time parallel code provides speedup beyond the saturation of the purely space-parallel approach.}},
address = {Los Alamitos, CA, USA},
articleno = {92},
author = {Speck, Robert and Ruprecht, Daniel and Krause, Rolf and Emmett, Matthew and Minion, Michael L. and Winkel, Mathias and Gibbon, Paul},
booktitle = {Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis},
location = {Salt Lake City, Utah},
numpages = {11},
pages = {92:1--92:11},
publisher = {IEEE Computer Society Press},
series = {{SC '12}},
title = {{A massively space-time parallel {N}-body solver}},
url = {http://dx.doi.org/10.1109/SC.2012.6},
doi = {10.1109/SC.2012.6},
year = {2012}
}
@article{Samuel2012,
author = {Samuel, H.},
journal = {Geochemistry, Geophysics, Geosystems},
number = {1},
title = {{Time domain parallelization for computational geodynamics}},
url = {http://dx.doi.org/10.1029/2011GC003905},
doi = {10.1029/2011GC003905},
volume = {13},
year = {2012}
}
@inproceedings{Takami2012,
author = {Takami, Toshiya and Nishida, A.},
booktitle = {{Applications, Tools and Techniques on the Road to Exascale Computing}},
pages = {437--444},
series = {{Advances in Parallel Computing}},
title = {{Parareal Acceleration of Matrix Multiplication}},
url = {http://dx.doi.org/10.3233/978-1-61499-041-3-437},
doi = {10.3233/978-1-61499-041-3-437},
volume = {22},
year = {2012}
}
@inproceedings{XiaoAubanel2012,
abstract = {{Parallelization of time-dependent partial differential equations (PDEs) can be accomplished by time
decomposition using the parareal algorithm.
While the parareal algorithm was designed to enable real-time simulations, it holds particular promise for long
time simulations on computational grids and clouds, due its low communication overhead and potential for
adaptation to heterogeneous processors.
This contribution extends previous work on the scheduling of tasks of the parareal algorithm to resources with
heterogeneous CPU performance.
Experiments on Amazon's EC2 show the suitability of this algorithm for execution on a heterogeneous cloud
platform and its insensitivity to network latency.}},
author = {Xiao, Hongtao and Aubanel, E.},
booktitle = {{Parallel and Distributed Processing Symposium Workshops PhD Forum (IPDPSW), 2012 IEEE 26th International}},
pages = {1440--1448},
title = {{Scheduling of Tasks in the Parareal Algorithm for Heterogeneous Cloud Platforms}},
url = {http://dx.doi.org/10.1109/IPDPSW.2012.181},
doi = {10.1109/IPDPSW.2012.181},
year = {2012},
}
%
% 2013
%
@article{BylaskaEtAl2013,
author = {Bylaska, Eric J. and Weare, Jonathan Q. and Weare, John H.},
journal = {The Journal of Chemical Physics},
number = {7},
pages = {074114},
title = {{Extending molecular simulation time scales: Parallel in time integrations for high-level quantum chemistry and complex force representations}},
url = {http://dx.doi.org/10.1063/1.4818328},
doi = {10.1063/1.4818328},
volume = {139},
year = {2013}
}
@article{DaiEtAl2013_ESAIM,
author = {Dai, X. and {Le Bris}, C. and Legoll, F. and Maday, Yvon},
issue = {03},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis},
month = {4},
pages = {717--742},
title = {{Symmetric parareal algorithms for {H}amiltonian systems}},
url = {http://dx.doi.org/10.1051/m2an/2012046},
doi = {10.1051/m2an/2012046},
volume = {47},
year = {2013}
}
@article{DaiEtAl2013,
author = {Dai, X. and Maday, Yvon},
journal = {SIAM Journal on Scientific Computing},
number = {1},
pages = {A52--A78},
title = {{Stable Parareal in Time Method for First- and Second-Order Hyperbolic Systems}},
url = {http://dx.doi.org/10.1137/110861002},
doi = {10.1137/110861002},
volume = {35},
year = {2013}
}
@article{DuEtAl2013,
author = {Du, X. and Sarkis, Marcus and Schaerer, Christian E. and Szyld, D. B.},
journal = {Electrontic Transactions on Numerical Analysis},
pages = {36--57},
title = {{Inexact and truncated parareal-in-time {K}rylov subspace methods for parabolic optimal control problems}},
url = {http://etna.mcs.kent.edu/vol.40.2013/pp36-57.dir/pp36-57.pdf},
volume = {40},
year = {2013}
}
@inproceedings{FriedhoffEtAl2013,
author = {Friedhoff, S. and Falgout, R.~D. and Kolev, T.~V. and MacLachlan, Scott P. and Schroder, Jacob B.},
booktitle = {{Presented at: Sixteenth Copper Mountain Conference on Multigrid Methods, Copper Mountain, CO, United States, Mar 17 - Mar 22, 2013}},
title = {{A Multigrid-in-Time Algorithm for Solving Evolution Equations in Parallel}},
url = {http://www.osti.gov/scitech/servlets/purl/1073108},
year = {2013}
}
@inproceedings{FukudomeTakami2013,
address = {New York, NY, USA},
author = {Fukudome, Daiki and Takami, Toshiya},
booktitle = {{Proceedings of the 20th European MPI Users' Group Meeting}},
isbn = {978-1-4503-1903-4},
location = {Madrid, Spain},
numpages = {2},
pages = {135--136},
publisher = {ACM},
series = {{EuroMPI '13}},
title = {{Parallel bucket-brigade communication interface for scientific applications}},
url = {http://dx.doi.org/10.1145/2488551.2488595},
doi = {10.1145/2488551.2488595},
year = {2013}
}
@incollection{GanderEtAl2013_DDM,
author = {Gander, Martin J. and Jiang, Yao-Lin and Li, Rong-Jian},
booktitle = {{Domain Decomposition Methods in Science and Engineering {XX}}},
editor = {Bank, Randolph and Holst, Michael and Widlund, Olof and Xu, Jinchao},
pages = {451--458},
publisher = {Springer Berlin Heidelberg},
series = {{Lecture Notes in Computational Science and Engineering}},
title = {{Parareal Schwarz Waveform Relaxation Methods}},
url = {http://dx.doi.org/10.1007/978-3-642-35275-1_53},
doi = {10.1007/978-3-642-35275-1_53},
volume = {91},
year = {2013}
}
@article{GuttelGander2013,
author = {Gander, Martin J. and G{\"u}ttel, Stefan},
journal = {SIAM Journal on Scientific Computing},
number = {2},
pages = {C123--C142},
title = {{PARAEXP: A Parallel Integrator for Linear Initial-Value Problems}},
url = {http://dx.doi.org/10.1137/110856137},
doi = {10.1137/110856137},
volume = {35},
year = {2013}
}
@article{LegollEtAl2013,
author = {Legoll, F. and Lelièvre, T. and Samaey, G.},
journal = {SIAM Journal on Scientific Computing},
number = {4},
pages = {A1951--A1986},
title = {{A Micro-Macro Parareal Algorithm: Application to Singularly Perturbed Ordinary Differential Equations}},
url = {http://dx.doi.org/10.1137/120872681},
doi = {10.1137/120872681},
volume = {35},
year = {2013}
}
@article{McCleanEtAl2013,
author = {McClean, Jarrod R. and Parkhill, John A. and Aspuru-Guzik, Alán},
journal = {Proceedings of the National Academy of Sciences},
number = {41},
pages = {E3901--E3909},
title = {{Feynman's clock, a new variational principle, and parallel-in-time quantum dynamics}},
url = {http://dx.doi.org/10.1073/pnas.1308069110},
doi = {10.1073/pnas.1308069110},
volume = {110},
year = {2013}
}
@inproceedings{RuprechtEtAl2013_SC,
author = {Ruprecht, Daniel and Speck, Robert and Emmett, Matthew and Bolten, Matthias and Krause, Rolf},
booktitle = {Proceedings of the 2013 Conference on High Performance Computing Networking, Storage and Analysis Companion},
location = {Denver, Colorado, USA},
series = {{SC '13 Companion}},
title = {Poster: Extreme-scale space-time parallelism},
url = {http://sc13.supercomputing.org/sites/default/files/PostersArchive/tech_posters/post148s2-file3.pdf},
year = {2013}
}
@article{SamaddarEtAl2013,
author = {Samaddar, Debasmita and Casper, T.~A. and Kim, S.~H. and Berry, Lee A. and Elwasif, Wael R. and Batchelor, D.~B. and Houlberg, W.~A.},
journal = {Journal of Physics: Conference Series},
number = {1},
pages = {012032},
title = {{Time parallelization of advanced operation scenario simulations of {ITER} plasma}},
url = {http://dx.doi.org/10.1088/1742-6596/410/1/012032},
doi = {10.1088/1742-6596/410/1/012032},
volume = {410},
year = {2013}
}
@article{WangEtAl2013,
abstract = {{We present a reformulation of unsteady turbulent flow simulations. The initial condition is relaxed and information is allowed to propagate both forward and backward in time. Simulations of chaotic dynamical systems with this reformulation can be proven to be well-conditioned time domain boundary value problems. The reformulation can enable scalable parallel-in-time simulation of turbulent flows.}},
author = {Wang, Qiqi and Gomez, Steven A and Blonigan, Patrick J and Gregory, Alastair L and Qian, Elizabeth Y},
journal = {Physics of Fluids (1994-present)},
number = {11},
pages = {110818},
title = {Towards scalable parallel-in-time turbulent flow simulations},
volume = {25},
year = {2013},
url = {https://doi.org/10.1063/1.4819390},
doi = {10.1063/1.4819390}
}
%
% 2014
%
@incollection{ArbenzEtAl2014,
author = {Arbenz, Peter and Hupp, Daniel and Obrist, Dominik},
booktitle = {{Parallel Processing and Applied Mathematics}},
editor = {Wyrzykowski, Roman and Dongarra, Jack and Karczewski, Konrad and Waśniewski, Jerzy},
pages = {291--300},
publisher = {Springer Berlin Heidelberg},
series = {{Lecture Notes in Computer Science}},
title = {{A Parallel Solver for the Time-Periodic {N}avier-{S}tokes Equations}},
url = {http://dx.doi.org/10.1007/978-3-642-55195-6_27},
doi = {10.1007/978-3-642-55195-6_27},
year = {2014}
}
@article{Barker2014,
author = {Barker, Andrew T.},
issue = {3},
journal = {International Journal of Computer Mathematics},
pages = {601--615},
title = {{A minimal communication approach to parallel time integration}},
url = {http://dx.doi.org/10.1080/00207160.2013.800193},
doi = {10.1080/00207160.2013.800193},
volume = {91},
year = {2014}
}
@inproceedings{BaudronEtAl2014_DDM,
author = {Baudron, Anne-Marie and Lautard, Jean-Jacques and Maday, Yvon and Mula, Olga},
booktitle = {{Domain Decomposition Methods in Science and Engineering XXI}},
editors = {Erhel, J. and Gander, M. J. and Halpern, L. and Pichot, G. and Sassi, T. and Widlund, O.},
pages = {437--445},
publisher = {Springer International Publishing},
series = {{Lecture Notes in Computational Science and Engineering}},
title = {{The parareal in time algorithm applied to the kinetic neutron diffusion equation}},
url = {http://dx.doi.org/10.1007/978-3-319-05789-7_41},
doi = {10.1007/978-3-319-05789-7_41},
year = {2014}
}
@article{Baudron2014,
author = {Baudron, Anne-Marie and Lautard, Jean-Jacques and Maday, Yvon and Riahi, Mohamed Kamel and Salomon, Julien},
journal = {Journal of Computational Physics},
number = {0},
pages = {67--79},
title = {{Parareal in time 3D numerical solver for the {LWR} Benchmark neutron diffusion transient model}},
url = {http://dx.doi.org/10.1016/j.jcp.2014.08.037},
doi = {10.1016/j.jcp.2014.08.037},
volume = {279},
year = {2014}
}
@article{BuLee2014,
author = {Bu, Sunyoung and Lee, June-Yub},
journal = {Journal of Computational and Applied Mathematics},
number = {0},
pages = {297--305},
title = {{An enhanced parareal algorithm based on the deferred correction methods for a stiff system}},
url = {http://dx.doi.org/10.1016/j.cam.2013.05.001},
doi = {10.1016/j.cam.2013.05.001},
volume = {255},
year = {2014}
}
@inproceedings{Caceres2014,
author = {{Caceres Silva}, J.~J. and Baran, B. and Schaerer, Christian E.},
booktitle = {{Computer Science and Information Systems (FedCSIS), 2014 Federated Conference on}},
pages = {577--586},
title = {{Implementation of a distributed parallel in time scheme using {PETSc} for a parabolic optimal control problem}},
url = {http://dx.doi.org/10.15439/2014F340},
doi = {10.15439/2014F340},
year = {2014}
}
@incollection{ChenEtAl2014,
author = {Chen, Feng and Hesthaven, Jan S. and Zhu, Xueyu},
booktitle = {{Reduced Order Methods for Modeling and Computational Reduction}},
editor = {Quarteroni, Alfio and Rozza, Gianluigi},
pages = {187--214},
publisher = {Springer International Publishing},
series = {{MS\&A - Modeling, Simulation and Applications}},
title = {{On the Use of Reduced Basis Methods to Accelerate and Stabilize the Parareal Method}},
url = {http://dx.doi.org/10.1007/978-3-319-02090-7_7},
doi = {10.1007/978-3-319-02090-7_7},
volume = {9},
year = {2014}
}
@article{Chouly2014,
author = {Chouly, Franz and Lozinski, Alexei},
journal = {Comptes Rendus Mathematique},
number = {6},
pages = {535--540},
title = {{Parareal multi-model numerical zoom for parabolic multiscale problems}},
url = {http://dx.doi.org/10.1016/j.crma.2014.03.018},
doi = {10.1016/j.crma.2014.03.018},
volume = {352},
year = {2014}
}
@incollection{CroceEtAl2014,
abstract = {{In this paper we combine the Parareal parallel-in-time method together with spatial parallelization and
investigate this space-time parallel scheme by means of solving the three-dimensional incompressible
Navier-Stokes equations.
Parallelization of time stepping provides a new direction of parallelization and allows to employ additional
cores to further speed up simulations after spatial parallelization has saturated.
We report on numerical experiments performed on a Cray XE6, simulating a driven cavity flow with and without
obstacles.
Distributed memory parallelization is used in both space and time, featuring up to 2,048 cores in total.
It is confirmed that the space-time-parallel method can provide speedup beyond the saturation of the spatial
parallelization.}},
author = {Croce, Roberto and Ruprecht, Daniel and Krause, Rolf},
booktitle = {Modeling, Simulation and Optimization of Complex Processes -- {HPSC} 2012},
editor = {Bock, Hans Georg and Hoang, Xuan Phu and Rannacher, Rolf and Schlöder, Johannes P.},
pages = {13--23},
publisher = {Springer International Publishing},
title = {{Parallel-in-Space-and-Time Simulation of the Three-Dimensional, Unsteady {N}avier-{S}tokes Equations for Incompressible Flow}},
url = {http://dx.doi.org/10.1007/978-3-319-09063-4_2},
doi = {10.1007/978-3-319-09063-4_2},
year = {2014}
}
@techreport{DongarraEtAl2014,
author = {Dongarra, J. and al.},
institution = {Lawrence Livermore National Laboratory},
number = {LLNL-TR-651000},
title = {{Applied Mathematics Research for Exascale Computing}},
url = {{http://science.energy.gov/%7E/media/ascr/pdf/research/am/docs/EMWGreport.pdf}},
year = {2014}
}
@inproceedings{EmmettMinion2014_DDM,
author = {Emmett, Matthew and Minion, Michael L.},
booktitle = {{Domain Decomposition Methods in Science and Engineering XXI}},
editors = {Erhel, J. and Gander, M. J. and Halpern, L. and Pichot, G. and Sassi, T. and Widlund, O.},
pages = {359--366},
publisher = {Springer International Publishing},
series = {{Lecture Notes in Computational Science and Engineering}},
title = {{Efficient implementation of a multi-level parallel in time algorithm}},
url = {http://dx.doi.org/10.1007/978-3-319-05789-7_33},
doi = {10.1007/978-3-319-05789-7_33},
volume = {98},
year = {2014}
}
@article{FalgoutEtAl2014_MGRIT,
author = {Falgout, R.~D. and Friedhoff, S. and Kolev, T.~V. and MacLachlan, Scott P. and Schroder, Jacob B.},
issue = {6},
journal = {SIAM Journal on Scientific Computing},
pages = {C635--C661},
title = {{Parallel time integration with multigrid}},
url = {http://dx.doi.org/10.1137/130944230},
doi = {10.1137/130944230},
volume = {36},
year = {2014},
}
@techreport{FalgoutEtAl2014,
author = {Falgout, R. D. and Katz, A. and Kolev, T.~V. and Schroder, Jacob B. and Wissink, A.~M. and Yang, U.~M.},
institution = {Lawrence Livermore National Laboratory},
title = {{Parallel Time Integration with Multigrid Reduction for a Compressible Fluid Dynamics Application}},
url = {https://computation.llnl.gov/project/parallel-time-integration/pubs/strand2d-pit.pdf},
year = {2014}
}
@article{GanderHairer2014,
author = {Gander, Martin J. and Hairer, Ernst},
journal = {Journal of Computational and Applied Mathematics},
note = {Proceedings of the Sixteenth International Congress on Computational and Applied Mathematics (ICCAM-2012), Ghent, Belgium, 9-13 July, 2012},
number = {0},
pages = {2--13},
title = {{Analysis for parareal algorithms applied to {H}amiltonian differential equations}},
url = {http://dx.doi.org/10.1016/j.cam.2013.01.011},
doi = {10.1016/j.cam.2013.01.011},
volume = {259, Part A},
year = {2014}
}
@article{HautWingate2014,
author = {Haut, T. and Wingate, B.},
journal = {SIAM Journal on Scientific Computing},
number = {2},
pages = {A693--A713},
title = {{An asymptotic parallel-in-time method for highly oscillatory {PDE}s}},
url = {http://dx.doi.org/10.1137/130914577},
doi = {10.1137/130914577},
volume = {36},
year = {2014}
}
@inproceedings{HaynesOng2014,
author = {Haynes, Ronald D. and Ong, Benjamin W.},
booktitle = {{Domain Decomposition Methods in Science and Engineering XXI}},
editors = {Erhel, J. and Gander, M. J. and Halpern, L. and Pichot, G. and Sassi, T. and Widlund, O.},
pages = {179--187},
publisher = {Springer International Publishing},
series = {{Lecture Notes in Computational Science and Engineering}},
title = {{{MPI}-{O}pen{MP} algorithms for the parallel space-time solution of time dependent {PDE}s}},
url = {http://dx.doi.org/10.1007/978-3-319-05789-7_14},
doi = {10.1007/978-3-319-05789-7_14},
volume = {98},
year = {2014}
}
@inproceedings{MakhoulEtAl2014_DDM,
author = {Makhoul-Karam, Noha and Nassif, Nabil R. and Erhel, Jocelyne},
booktitle = {{Domain Decomposition Methods in Science and Engineering XXI}},
editors = {Erhel, J. and Gander, M. J. and Halpern, L. and Pichot, G. and Sassi, T. and Widlund, O.},
pages = {707--717},
publisher = {Springer International Publishing},
series = {{Lecture Notes in Computational Science and Engineering}},
title = {{An Adaptive Parallel-in-Time Method with application to a membrane problem}},
url = {http://dx.doi.org/10.1007/978-3-319-05789-7_68},
doi = {10.1007/978-3-319-05789-7_68},
volume = {98},
year = {2014}
}
@phdthesis{Mula2014,
author = {Mula, Olga},
title = {Some contributions towards the parallel simulation of time dependent neutron transport and the integration of observed data in real time},
school = {Universit\'{e} Pierre et Marie Curie - Paris VI},
url = {https://tel.archives-ouvertes.fr/tel-01081601},
year = {2014},
}
@article{Loderer2014,
author = {Loderer, Thomas and Heuveline, Vincent and Lohner, Rudolf},
journal = {PAMM},
number = {1},
pages = {1027--1030},
title = {{The parareal algorithm as a new approach for numerical integration of {ODE}s in real-time simulations in automotive industry}},
url = {http://dx.doi.org/10.1002/pamm.201410489},
doi = {10.1002/pamm.201410489},
volume = {14},
year = {2014}
}
@unpublished{Neumueller2014,
abstract={{We present and analyze for a scalar linear evolution model problem a time multigrid algorithm for DG-discretizations in time. We derive asymptotically optimized parameters for the smoother, and also an asymptotically sharp convergence estimate for the two grid cycle. Our results hold for any A-stable time stepping scheme and represent the core component for space-time multigrid methods for parabolic partial differential equations. Our time multigrid method has excellent strong and weak scaling properties for parallelization in time, which we show with numerical experiments.}},
author = {Gander, Martin J. and Neumueller, M.},
title = {{Analysis of a Time Multigrid Algorithm for {DG}-Discretizations in Time}},
url = {http://arxiv.org/abs/1409.5254},
year = {2014}
}
@article{Randles2014,
abstract = {{Fluid dynamics simulations using grid-based methods, such as the lattice Boltzmann equation, can benefit from parallel-in-space computation. However, for a fixed-size simulation of this type, the efficiency of larger processor counts will saturate when the number of grid points per core becomes too small. To overcome this fundamental strong scaling limit in space-parallel approaches, we present a novel time-parallel version of the lattice Boltzmann method using the parareal algorithm. This method is based on a predictor–corrector scheme combined with mesh refinement to enable the simulation of larger number of time steps. We present results of up to a 32× increase in speed for a model system consisting of a cylinder with conditions for laminar flow. The parallel gain obtainable is predicted with strong accuracy, providing a quantitative understanding of the potential impact of this method.}},
author = {Randles, Amanda and Kaxiras, Efthimios},
journal = {Journal of Computational Physics},
pages = {577--586},
title = {{Parallel in time approximation of the lattice {B}oltzmann method for laminar flows}},
url = {http://dx.doi.org/10.1016/j.jcp.2014.04.006},
doi = {10.1016/j.jcp.2014.04.006},
volume = {270},
year = {2014}
}
@inproceedings{Randles2014_b,
author = {Randles, A. and Kaxiras, Efthimios},
booktitle = {{Parallel and Distributed Processing Symposium, 2014 IEEE 28th International}},
month = {May},
pages = {593--602},
title = {{A Spatio-temporal Coupling Method to Reduce the Time-to-Solution of Cardiovascular Simulations}},
url = {http://dx.doi.org/10.1109/IPDPS.2014.68},
doi = {10.1109/IPDPS.2014.68},
year = {2014}
}
@article{Rao2014,
author = {Rao, Vishwas and Sandu, Adrian},
journal = {Journal of Computational Science},
number = {2},
pages = {76--84},
title = {{An adjoint-based scalable algorithm for time-parallel integration}},
url = {http://dx.doi.org/10.1016/j.jocs.2013.03.004},
doi = {10.1016/j.jocs.2013.03.004},
volume = {5},
year = {2014}
}
@article{Ruprecht2014_GAMM,
abstract = {{The effect is investigated of using a reduced spatial resolution in the coarse propagator of the
time-parallel Parareal method for a finite difference discretization of the linear advection-diffusion equation.
It is found that convergence can critically depend on the order of the interpolation used to transfer the coarse
propagator solution to the fine mesh in the correction step.
The effect also strongly depends on the employed spatial and temporal resolution.}},
author = {Ruprecht, Daniel},
journal = {PAMM},
number = {1},
pages = {1031--1034},
title = {{Convergence of Parareal with spatial coarsening}},
url = {http://dx.doi.org/10.1002/pamm.201410490},
doi = {10.1002/pamm.201410490},
volume = {14},
year = {2014}
}
@inproceedings{RuprechtKrause2014_DDM,
abstract = {{An OpenMP-based shared memory implementation of the Parareal parallel-in-time integration scheme using
explicit integrators is combined with a standard MPI-based spatial parallelization of a finite difference method
into a hybrid space-time parallel scheme.
The capability of this approach to achieve speedups beyond the saturation of the pure space-parallel scheme is
demonstrated for the two-dimensional Burgers equation.}},
author = {Krause, Rolf and Ruprecht, Daniel},
booktitle = {Domain Decomposition Methods in Science and Engineering {XXI}},
editors = {Erhel, J. and Gander, M.~J. and Halpern, L. and Pichot, G. and Sassi, T. and Widlund, O.},
pages = {647--655},
publisher = {Springer International Publishing},
series = {{Lecture Notes in Computational Science and Engineering}},
title = {{Hybrid Space-Time Parallel Solution of {B}urgers' Equation}},
url = {http://dx.doi.org/10.1007/978-3-319-05789-7_62},
doi = {10.1007/978-3-319-05789-7_62},
volume = {98},
year = {2014}
}
@inproceedings{Samaddar2014,
author = {Samaddar, Debasmita and Coster, D.~P. and Bonnin, X. and Bergmeister, C. and Havl{\'i}\u{c}kov{\'a}, E. and Berry, Lee A. and Elwasif, Wael R. and Batchelor, D.~B.},
booktitle = {{Proceedings of the 2014 Conference on High Performance Computing Networking, Storage and Analysis Companion}},
location = {New Orleans, Louisiana, USA},
series = {{SC '14 Companion}},
title = {{Poster: Greater than 10x Acceleration of fusion plasma edge simulations using the Parareal algorithm}},
url = {http://sc14.supercomputing.org/sites/all/themes/sc14/files/archive/tech_poster/poster_files/post163s2-file3.pdf},
year = {2014}
}
@article{Song2014,
author = {Song, Bo and Jiang, Yao-Lin},
journal = {Numerical Algorithms},
number = {3},
pages = {599--622},
title = {{Analysis of a new parareal algorithm based on waveform relaxation method for time-periodic problems}},
url = {http://dx.doi.org/10.1007/s11075-013-9810-z},
doi = {10.1007/s11075-013-9810-z},
volume = {67},
year = {2014}
}
@inproceedings{SpeckEtAl2014_Parco,
abstract = {{The paper presents a combination of the time-parallel ``parallel full approximation scheme in space and
time'' (PFASST) with a parallel multigrid method (PMG) in space, resulting in a mesh-based solver for the
three-dimensional heat equation with a uniquely high degree of efficient concurrency.
Parallel scaling tests are reported on the Cray XE6 machine ``Monte Rosa'' on up to $16,384$ cores and on the
IBM Blue Gene/Q system ``JUQUEEN'' on up to $65,536$ cores.
The efficacy of the combined spatial- and temporal parallelization is shown by demonstrating that using PFASST
in addition to PMG significantly extends the strong-scaling limit.
Implications of using spatial coarsening strategies in PFASST's multi-level hierarchy in large-scale parallel
simulations are discussed.}},
author = {Speck, Robert and Ruprecht, Daniel and Emmett, Matthew and Bolten, Matthias and Krause, Rolf},
booktitle = {Parallel Computing: Accelerating Computational Science and Engineering ({CSE})},
editors = {Bader, M. and Bode, A. and Bungartz, H.-J. and Gerndt, M. and Joubert, G.R. and Peters, F.},
pages = {263--272},
publisher = {IOS Press},
series = {{Advances in Parallel Computing}},
title = {{A space-time parallel solver for the three-dimensional heat equation}},
url = {http://dx.doi.org/10.3233/978-1-61499-381-0-263},
doi = {10.3233/978-1-61499-381-0-263},
volume = {25},
year = {2014}
}
@inproceedings{SpeckEtAl2014_DDM2012,
abstract = {{Vortex methods for the Navier-Stokes equations are based on a Lagrangian particle discretization, which
reduces the governing equations to a first-order initial value system of ordinary differential equations for the
position and vorticity of $N$ particles.
In this paper, the accuracy of solving this system by time-serial spectral deferred corrections (SDC) as well as
by the time-parallel Parallel Full Approximation Scheme in Space And Time (PFASST) is investigated.
PFASST is based on intertwining SDC iterations with differing resolution in a manner similar to the Parareal
algorithm and uses a Full Approximation Scheme (FAS) correction to improve the accuracy of coarser SDC
iterations.
It is demonstrated that SDC and PFASST can generate highly accurate solutions, and the performance in terms of
function evaluations required for a certain accuracy is analyzed and compared to a standard Runge-Kutta method.}},
author = {Speck, Robert and Ruprecht, Daniel and Krause, Rolf and Emmett, Matthew and Minion, Michael L. and Winkel, Mathias and Gibbon, Paul},
booktitle = {Domain Decomposition Methods in Science and Engineering {XXI}},
editors = {Erhel, J. and Gander, M.~J. and Halpern, L. and Pichot, G. and Sassi, T. and Widlund, O.},
pages = {637--645},
publisher = {Springer International Publishing},
series = {{Lecture Notes in Computational Science and Engineering}},
title = {{Integrating an {N}-body problem with {SDC} and {PFASST}}},
url = {http://dx.doi.org/10.1007/978-3-319-05789-7_61},
doi = {10.1007/978-3-319-05789-7_61},
volume = {98},
year = {2014}
}
@incollection{Takami2014,
author = {Takami, Toshiya and Fukudome, Daiki},
booktitle = {{Parallel Processing and Applied Mathematics}},
editor = {Wyrzykowski, Roman and Dongarra, Jack and Karczewski, Konrad and Waśniewski, Jerzy},
pages = {67--75},
publisher = {Springer Berlin Heidelberg},
series = {{Lecture Notes in Computer Science}},
title = {{An Identity Parareal Method for Temporal Parallel Computations}},
url = {http://dx.doi.org/10.1007/978-3-642-55224-3_7},
doi = {10.1007/978-3-642-55224-3_7},
year = {2014}
}
@incollection{Takami2014_b,
author = {Takami, Toshiya and Fukudome, Daiki},
booktitle = {{Parallel Computing: Accelerating Computational Science and Engineering (CSE)}},
editor = {Bader, Michael and Bode, Arndt and Bungartz, Hans-Joachim and Gerndt, Michael and Joubert, Gerhard R. and Peters, Frans},
pages = {273--281},
series = {{Advances in Parallel Computing}},
title = {{An Efficient Pipelined Implementation of Space-Time Parallel Applications}},
url = {http://dx.doi.org/10.3233/978-1-61499-381-0-273},
doi = {10.3233/978-1-61499-381-0-273},
volume = {25},
year = {2014}
}
@Inbook{VanDerValkEtAl2014,
author = {van der Valk, Paul L. C. and Rixen, Daniel J.},
editor = {Allen, Matt and Mayes, Randy and Rixen, Daniel},
title = {Towards a Parallel Time Integration Method for Nonlinear Systems},
booktitle = {Dynamics of Coupled Structures, Volume 1: Proceedings of the 32nd IMAC, A Conference and Exposition on Structural Dynamics, 2014},
year = {2014},
publisher = {Springer International Publishing},
address = {Cham},
pages = {135--145},
doi = {10.1007/978-3-319-04501-6_12},
url = {http://dx.doi.org/10.1007/978-3-319-04501-6_12}
}
@article{Wu2014,
author = {Wu, Shu-Lin},
journal = {IMA Journal of Numerical Analysis},
title = {{Convergence analysis of some second-order parareal algorithms}},
url = {http://dx.doi.org/10.1093/imanum/dru031},
doi = {10.1093/imanum/dru031},
year = {2014}
}
@article{Xu2014,
author = {Xu, Qinwu and Hesthaven, Jan S. and Chen, Feng},
journal = {Journal of Computational Physics},
title = {{A parareal method for time-fractional differential equations}},
url = {http://dx.doi.org/10.1016/j.jcp.2014.11.034},
doi = {10.1016/j.jcp.2014.11.034},
year = {2014}
}
%
% 2015
%
@misc{Ariel2015,
abstract = {{We introduce a new parallel in time (parareal) algorithm which couples multiscale integrators with
fully resolved fine scale integration and computes highly oscillatory solutions for a class of ordinary
differential equations in parallel.
The algorithm computes a low-cost approximation of all slow variables in the system.
Then, fast phase-like variables are obtained using the parareal iterative methodology and an alignment algorithm.
The method may be used either to enhance the accuracy and range of applicability of the multiscale method in
approximating only the slow variables, or to resolve all the state variables.
The numerical scheme does not require that the system is split into slow and fast coordinates.
Moreover, the dynamics may involve hidden slow variables, for example, due to resonances.
Convergence of the parareal iterations is proved and demonstrated in numerical examples.}},
author = {Ariel, G. and Kim, Seong Jun and Tsai, Richard},
howpublished = {arXiv:1503.02094 [math.NA]},
title = {{Parareal methods for highly oscillatory ordinary differential equations}},
url = {http://arxiv.org/abs/1503.02094v1},
year = {2015}
}
@article{ArteagaEtAl2015,
abstract = {{In view of the rapid rise of the number of cores in modern supercomputers, time-parallel methods that
introduce concurrency along the temporal axis are becoming increasingly popular.
For the solution of time-dependent partial differential equations, these methods can add another direction for
concurrency on top of spatial parallelization.
The paper presents an implementation of the time-parallel Parareal method in a C++ domain specific language for
stencil computations (STELLA).
STELLA provides both an OpenMP and a CUDA backend for a shared memory parallelization, using the CPU or GPU
inside a node for the spatial stencils.
Here, we intertwine this node-wise spatial parallelism with the time-parallel Parareal.
This is done by adding an MPI-based implementation of Parareal, which allows us to parallelize in time across
nodes.
The performance of Parareal with both backends is analyzed in terms of speedup, parallel efficiency and
energy-to-solution for an advection-diffusion problem with a time-dependent diffusion coefficient.}},
author = {Arteaga, A. and Ruprecht, Daniel and Krause, Rolf},
journal = {Applied Mathematics and Computation},
volume = {267},
pages = {727--741},
title = {{A stencil-based implementation of Parareal in the {C++} domain specific embedded language {STELLA}}},
url = {http://dx.doi.org/10.1016/j.amc.2014.12.055},
doi = {10.1016/j.amc.2014.12.055},
year = {2015}
}
@article{Bedez2015,
abstract = {{The resolution of a model describing the electrical activity of neural tissue and its
propagation within this tissue is highly consuming in term of computing time and requires strong
computing power to achieve good results.
New method in this study, we present a method to solve a model describing the electrical
propagation in neuronal tissue, using parareal algorithm, coupling with parallelization space using
CUDA in graphical processing unit (GPU).
Results we applied the method of resolution to different dimensions of the geometry of our model
(1-D, 2-D and 3-D).
The GPU results are compared with simulations from a multi-core processor cluster, using
message-passing interface (MPI), where the spatial scale was parallelized in order to reach a
comparable calculation time than that of the presented method using GPU.
A gain of a factor 100 in term of computational time between sequential results and those obtained
using the GPU has been obtained, in the case of 3-D geometry.
Given the structure of the GPU, this factor increases according to the fineness of the geometry used
in the computation.
Comparison with existing method(s) To the best of our knowledge, it is the first time such a method
is used, even in the case of neuroscience.
Conclusion Parallelization time coupled with GPU parallelization space allows for drastically
reducing computational time with a fine resolution of the model describing the propagation of the
electrical signal in a neuronal tissue.}},
author = {Mathieu Bedez and Zakaria Belhachmi and Olivier Haeberl\'e and Renaud Greget and Saliha Moussaoui and Jean-Marie Bouteiller and Serge Bischoff},
journal = {{Journal of Neuroscience Methods}},
note = {in press},
pages = {17--25},
title = {A fully parallel in time and space algorithm for simulating the electrical activity of a neural tissue},
url = {http://dx.doi.org/10.1016/j.jneumeth.2015.09.017},
doi = {10.1016/j.jneumeth.2015.09.017},
volume = {257},
year = {2015},
}
@inproceedings{CarracciuoloEtAl2015,
abstract = {{We consider linear systems that arise from the discretization of evolutionary models. Typically, solution algorithms are based on a time-stepping approach, solving for one time step after the other. Parallelism is limited to the spatial dimension only. Because time is sequential in nature, the idea of simultaneously solving along time steps is not intuitive. One approach to achieve parallelism in time direction is MGRIT algorithm [7], based on multigrid reduction (MGR) techniques. Here we refer to this approach as MGR-1D. Other kind of approach is the space-time multigrid, where time is simply another dimension in the grid. Analougsly, we refer to this approach as MGR-4D. In this work, motivated by the need of maximizing the availability of new algorithms to climate science, we propose a new parallel approach that mixes both the MGR-1D idea and classical space multigrid methods. We refer to it as the MGR3D+1 approach. Moreover, we discuss their implementation in the high performance scientific library PETSc, as starting point to develope more efficient and scalable algorithms in ocean models.}},
author = {L. Carracciuolo and L. D'Amore and V. Mele},
booktitle = {High Performance Computing Simulation (HPCS), 2015 International Conference on},
pages = {595--598},
title = {Toward a fully parallel multigrid in time algorithm in PETSc environment: A case study in ocean models},
url = {http://dx.doi.org/10.1109/HPCSim.2015.7237098},
doi = {10.1109/HPCSim.2015.7237098},
year = {2015},
}
@article{ChristliebEtAl2015,
abstract ={{Adaptive step-size control is a critical feature for the robust and efficient numerical solution of initial-value problems in ordinary differential equations. In this paper, we show that adaptive step-size control can be incorporated within a family of parallel time integrators known as revisionist integral deferred correction (RIDC) methods. The RIDC framework allows for various strategies to implement step-size control, and we report results from exploring a few of them.}},
author = {Christlieb, Andrew J. and MacDonald, Colin B. and Ong, Benjamin W. and Spiteri, Raymond J.},
title = {Revisionist integral deferred correction with adaptive step-size control},
journal = {Communications in Applied Mathematics and Computational Science},
volume = {10},
issue = {1},
pages = {1--25},
year = {2015},
url = {http://dx.doi.org/10.2140/camcos.2015.10.1},
doi = {10.2140/camcos.2015.10.1}
}
@unpublished{FengEtAl2015,
abstract = {{The parareal algorithm seeks to extract parallelism in the time-integration direction of
time-dependent differential equations.
While it has been applied with success to a wide range of problems, it suffers from some stability
issues when applied to non-dissipative problems.
We express the method through an iteration matrix and show that the problematic behavior is related
to the non-normal structure of the iteration matrix.
To enforce monotone convergence we propose an adjoint parareal algorithm, accelerated by the
Conjugate Gradient Method.
Numerical experiments confirm the stability and suggest directions for further improving the
performance.}},
author = {Chen, Feng and Hesthaven, Jan S. and Maday, Yvon and Nielsen, Allan S.},
howpublished = {EPFL-ARTICLE-211097},
title = {An Adjoint Approach for Stabilizing the Parareal Method},
url = {http://infoscience.epfl.ch/record/211097},
year = {2015},
}
@incollection{Gander2015_Review,
abstract = {{Time parallel time integration methods have received renewed interest over the last decade because of
the advent of massively parallel computers, which is mainly due to the clock speed limit reached on today's
processors.
When solving time dependent partial differential equations, the time direction is usually not used for
parallelization.
But when parallelization in space saturates, the time direction offers itself as a further direction for
parallelization.
The time direction is however special, and for evolution problems there is a causality principle: the solution
later in time is affected (it is even determined) by the solution earlier in time, but not the other way round.
Algorithms trying to use the time direction for parallelization must therefore be special, and take this very
different property of the time dimension into account.
We show in this chapter how time domain decomposition methods were invented, and give an overview of the
existing techniques.
Time parallel methods can be classified into four different groups: methods based on multiple shooting, methods
based on domain decomposition and waveform relaxation, space-time multigrid methods and direct time parallel
methods.
We show for each of these techniques the main inventions over time by choosing specific publications and
explaining the core ideas of the authors.
This chapter is for people who want to quickly gain an overview of the exciting and rapidly developing area of
research of time parallel methods.}},
author = {Gander, Martin J.},
booktitle = {Multiple Shooting and Time Domain Decomposition},
editors = {Carraro, T. and Geiger, M. and K\"orkel, S. and Rannacher, R.},
publisher = {Springer},
title = {{50 years of Time Parallel Time Integration}},
url = {http://dx.doi.org/10.1007/978-3-319-23321-5_3},
doi = {10.1007/978-3-319-23321-5_3},
year = {2015},
}
@inproceedings{GurralaEtAl2015,
abstract = {{In recent years, there have been significant developments in parallel algorithms and high performance
parallelm computing platforms.
Parareal in time algorithm has become popular for long transient simulations (e.g., molecular dynamics, fusion,
reacting flows).
Parareal is a arallel algorithm which divides the time interval into sub-intervals and solves them concurrently.
This paper investigates the applicability of the parareal algorithm to power system dynamic simulations.
Preliminary results on the application of parareal for multi-machine power systems are reported in this paper.
Two widely used test systems, WECC 3-generator 9-bus system, New England 10-generator 39-bus system, is used to
explore the effectiveness of the parareal.
Severe 3 phase bus faults are simulated using both the classical and detailed models of multi-machine power
systems.
Actual Speedup of 5-7 times is observed assuming ideal parallelization.
It has been observed that the speedup factors of the order of 20 can be achieved by using fast coarse
approximations of power system models.
Dependency of parareal convergence on fault duration and location has been observed.}},
author = {Gurunath Gurrala and Aleksandar Dimitrovski and Pannala Sreekanth and Srdjan Simunovic and Michael Starke},
booktitle = {{Proceedings of the International Conference on Power Systems Transients (IPST2015) in Cavtat, Croatia June 15-18, 2015}},
title = {{Parareal in Time for Dynamic Simulations of Power Systems}},
url = {http://www.ipstconf.org/papers/Proc_IPST2015/15IPST073.pdf},
year = {2015},
}
@article{HautEtAl2015,
abstract ={{The manuscript presents a technique for efficiently solving the classical wave equation, the shallow water equations, and, more generally, equations of the form $\partial u /\partial t = \mathcal {L}u$, where $\mathcal {L}$ is a skew-Hermitian differential operator. The idea is to explicitly construct an approximation to the time-evolution operator $\exp (\tau \mathcal {L})$ for a relatively large time-step $\tau $. Recently developed techniques for approximating oscillatory scalar functions by rational functions, and accelerated algorithms for computing functions of discretized differential operators are exploited. Principal advantages of the proposed method include: stability even for large time-steps, the possibility to parallelize in time over many characteristic wavelengths and large speed-ups over existing methods in situations where simulation over long times are required. Numerical examples involving the 2D rotating shallow water equations and the 2D wave equation in an inhomogenous medium are presented, and the method is compared to the 4th order Runge?Kutta (RK4) method and to the use of Chebyshev polynomials. The new method achieved high accuracy over long-time intervals, and with speeds that are orders of magnitude faster than both RK4 and the use of Chebyshev polynomials.}},
author = {Haut, T.~S. and Babb, T. and Martinsson, P.~G. and Wingate, B.~A.},
doi = {10.1093/imanum/drv021},
journal = {IMA Journal of Numerical Analysis},
url = {http://dx.doi.org/10.1093/imanum/drv021},
title = {A high-order time-parallel scheme for solving wave propagation problems via the direct construction of an approximate time-evolution operator},
year = {2015},
}
@article{KreienbuehlEtAl2015,
abstract = {{In-silico investigation of skin permeation is an important but also computationally demanding problem.
To resolve all scales involved in full detail will not only require exascale computing capacities but also
suitable parallel algorithms.
This article investigates the applicability of the time-parallel Parareal algorithm to a brick and mortar setup,
a precursory problem to skin permeation.
The C++ library Lib4PrM implementing Parareal is combined with the UG4 simulation framework, which provides the
spatial discretization and parallelization.
The combination's performance is studied with respect to convergence and speedup.
It is confirmed that anisotropies in the domain and jumps in diffusion coefficients only have a minor impact on
Parareal's convergence.
The influence of load imbalances in time due to differences in number of iterations required by the spatial
solver as well as spatio-temporal weak scaling is discussed.}},
author = {Kreienbuehl, Andreas and Naegel, Arne and Ruprecht, Daniel and Speck, Robert and Wittum, Gabriel and Krause, Rolf},
issue = {2},
journal = {Computing and Visualization in Science},
pages = {99--108},
title = {{Numerical simulation of skin transport using Parareal}},
url = {http://dx.doi.org/10.1007/s00791-015-0246-y},
doi = {10.1007/s00791-015-0246-y},
volume = {17},
year = {2015},
}
@article{MinionEtAl2015,
abstract = {{The parallel full approximation scheme in space and time (PFASST) introduced by Emmett and Minion in
2012 is an iterative strategy for the temporal parallelization of ODEs and discretized PDEs.
As the name suggests, PFASST is similar in spirit to a space-time FAS multigrid method performed over multiple
time-steps in parallel.
However, since the original focus of PFASST has been on the performance of the method in terms of time
parallelism, the solution of any spatial system arising from the use of implicit or semi-implicit temporal
methods within PFASST have simply been assumed to be solved to some desired accuracy completely at each sub-step
and each iteration by some unspecified procedure.
It hence is natural to investigate how iterative solvers in the spatial dimensions can be interwoven with the
PFASST iterations and whether this strategy leads to a more efficient overall approach.
This paper presents an initial investigation on the relative performance of different strategies for coupling
PFASST iterations with multigrid methods for the implicit treatment of diffusion terms in PDEs.
In particular, we compare full accuracy multigrid solves at each sub-step with a small fixed number of multigrid
V-cycles.
This reduces the cost of each PFASST iteration at the possible expense of a corresponding increase in the number
of PFASST iterations needed for convergence.
Parallel efficiency of the resulting methods is explored through numerical examples.}},
author = {Minion, Michael L. and Speck, Robert and Bolten, Matthias and Emmett, Matthew and Ruprecht, Daniel},
journal = {{SIAM} Journal on Scientific Computing},
issue = {5},
pages = {S244--S263},
title = {{Interweaving {PFASST} and parallel multigrid}},
url = {http://dx.doi.org/10.1137/14097536X},
doi = {10.1137/14097536X},
volume = {37},
year = {2015}
}
@inproceedings{OngEtAl2015,
author = {Ong, Benjamin and Kwok, Felix and High, Scott},
booktitle = {Methods in Science and Engineering XXII},
publisher = {Spring--Verlag},
series = {Lecture Notes in Computational Science and Engineering},
title = {Pipeline Schwarz Waveform Relaxation},
year = {2015}}
@article{PerezEtAl2015,
abstract = {{Simulating the atomistic evolution of materials over long timescales is a longstanding challenge,
especially for complex systems where the distribution of barrier heights is very heterogeneous.
Such systems are difficult to investigate using conventional long-timescale techniques and the fact that they
tend to remain trapped in small regions of configuration space for extended periods of time strongly limits the
physical insights gained from short simulations.
We introduce a novel simulation technique, Parallel Trajectory Splicing (ParSplice), that aims at addressing
this problem through the timewise parallelization of long trajectories.
The computational efficiency of ParSplice stems from a speculation strategy whereby predictions of the future
evolution of the system are leveraged to increase the amount of work that can be concurrently performed at any
one time, hence improving the scalability of the method.
ParSplice is also able to accurately account for, and potentially reuse, a substantial fraction of the
computational work invested in the simulation.
We validate the method on a simple Ag surface system and demonstrate substantial increases in efficiency
compared to previous methods.
We then demonstrate the power of ParSplice through the study of topology changes in Ag42Cu13 core-shell
nanoparticles.}},
author = {Danny Perez and Ekin Dogus Cubuk and Amos Waterland and Efthimios Kaxiras and Arthur F. Voter },
doi = {10.1021/acs.jctc.5b00916},
journal = {Journal of Chemical Theory and Computation},
title = {Long-time dynamics through parallel trajectory splicing},
url = {http://dx.doi.org/10.1021/acs.jctc.5b00916},
year = {2015},
}
@article{Scheibe2015,
author = {Scheibe, Timothy D. and Murphy, Ellyn M. and Chen, Xingyuan and Rice, Amy K. and Carroll, Kenneth C. and Palmer, Bruce J. and Tartakovsky, Alexandre M. and Battiato, Ilenia and Wood, Brian D.},
journal = {Groundwater},
number = {1},
pages = {38--56},
title = {{An Analysis Platform for Multiscale Hydrogeologic Modeling with Emphasis on Hybrid Multiscale Methods}},
url = {http://dx.doi.org/10.1111/gwat.12179},
doi = {10.1111/gwat.12179},
volume = {53},
year = {2015}
}
@unpublished{SchreiberEtAl2015,
abstract = {{With steadily increasing parallelism for high-performance architectures, simulations
requiring a good strong scalability are prone to be limited in scalability with standard
spatial-decomposition strategies at a certain amount of parallel processors.
This can be a show-stopper if the simulation results have to be computed with wallclock time
restrictions or as fast as possible.
Here, the time-dimension is the only one left for parallelisation and we focus on Parareal as one
particular parallelisationin-time method.
We present a software approach for making Parareal parallelisation transparent for application
developers, hence allowing fast prototyping for Parareal.
Further, we introduce a decentralized Parareal which results in autonomous simulation instances
which only require communicating with the previous and next simulation instances.
This concept is evaluated by solving the rotational shallow water equations parallel-in-time:
We provide speedup benchmarks and an in-depth analysis of our results based on state-plots and a
performance model.
This allows us to show the applicability of the Parareal approach with the rotational shallow water
equations and also to evaluate the limitations of Parareal.}},
author = {Schreiber, Martin and Peddle, Adam and Haut, Terry and Wingate, Beth},
howpublished = {arXiv:1506.05157 [cs.DC]},
title = {A Decentralized Parallelization-in-Time Approach with Parareal},
year = {2015},
url = {http://arxiv.org/abs/1506.05157},
}
@article{Song2015,
author = {Song, Bo and Jiang, Yao-Lin},
journal = {International Journal of Computer Mathematics},
number = {2},
pages = {377--393},
title = {{A new parareal waveform relaxation algorithm for time-periodic problems}},
url = {http://dx.doi.org/10.1080/00207160.2014.891734},
doi = {10.1080/00207160.2014.891734},
volume = {92},
year = {2015}
}
@article{SpeckEtAl2015_BIT,
abstract = {{The spectral deferred correction (SDC) method is an iterative scheme for computing a higher-order
collocation solution to an ODE by performing a series of correction sweeps using a low-order timestepping method.
This paper examines a variation of SDC for the temporal integration of PDEs called multi-level spectral deferred
corrections (MLSDC), where sweeps are performed on a hierarchy of levels and an FAS correction term, as in
nonlinear multigrid methods, couples solutions on different levels.
Three different strategies to reduce the computational cost of correction sweeps on the coarser levels are
examined: reducing the degrees of freedom, reducing the order of the spatial discretization, and reducing the
accuracy when solving linear systems arising in implicit temporal integration.
Several numerical examples demonstrate the effect of multi-level coarsening on the convergence and cost of SDC
integration.
In particular, MLSDC can provide significant savings in compute time compared to SDC for a three-dimensional
problem.}},
author = {Speck, Robert and Ruprecht, Daniel and Emmett, Matthew and Minion, Michael L. and Bolten, Matthias and Krause, Rolf},
issue = {3},
journal = {{BIT} Numerical Mathematics},
pages = {843--867},
title = {{A multi-level spectral deferred correction method}},
url = {http://dx.doi.org/10.1007/s10543-014-0517-x},
doi = {10.1007/s10543-014-0517-x},
year = {2015},
volume = {55},
}
@incollection{SteinerEtAl2015,
abstract = {{The paper presents first a linear stability analysis for the time-parallel Parareal method, using an
IMEX Euler as coarse and a Runge-Kutta-3 method as fine propagator, confirming that dominant imaginary
eigenvalues negatively affect Parareal's convergence.
This suggests that when Parareal is applied to the nonlinear Navier-Stokes equations, problems for small
viscosities could arise.
Numerical results for a driven cavity benchmark are presented, confirming that Parareal's convergence can indeed
deteriorate as viscosity decreases and the flow becomes increasingly dominated by convection.
The effect is found to strongly depend on the spatial resolution.}},
author = {Steiner, J. and Ruprecht, Daniel and Speck, Robert and Krause, Rolf},
booktitle = {Numerical Mathematics and Advanced Applications - {ENUMATH} 2013},
editor = {Abdulle, Assyr and Deparis, Simone and Kressner, Daniel and Nobile, Fabio and Picasso, Marco},
pages = {195--202},
publisher = {Springer International Publishing},
series = {{Lecture Notes in Computational Science and Engineering}},
title = {{Convergence of {P}arareal for the {N}avier-{S}tokes equations depending on the {R}eynolds number}},
url = {http://dx.doi.org/10.1007/978-3-319-10705-9_19},
doi = {10.1007/978-3-319-10705-9_19},
volume = {103},
year = {2015}
}
@Inbook{Ulbrich2015,
author= {Ulbrich, Stefan},
editor= {Carraro, Thomas and Geiger, Michael and K{\"o}rkel, Stefan and Rannacher, Rolf},
title= {{Preconditioners Based on ``Parareal'' Time-Domain Decomposition for Time-Dependent PDE-Constrained Optimization}},
bookTitle= {{Multiple Shooting and Time Domain Decomposition Methods: MuS-TDD, Heidelberg, May 6-8, 2013}},
year= {2015},
publisher= {Springer International Publishing},
address= {Cham},
pages= {203--232},
doi= {10.1007/978-3-319-23321-5_8},
url= {http://dx.doi.org/10.1007/978-3-319-23321-5_8}
}
@article{Wang2015,
abstract = {{Parareal algorithm is a very powerful parallel computation method and has received much
interest from many researchers over the past few years.
The aim of this paper is to investigate the performance of parareal algorithm implemented with
IMEX Runge-Kutta (RK) methods.
A stability criterion of the parareal algorithm coupled with IMEX RK methods is established and the
advantage (in the sense of stability) of implementing with this kind of RK methods is numerically
investigated.
Finally, numerical examples are given to illustrate the efficiency and performance of different
parareal methods.}},
author = {Wang, Zhiyong and Wu, Shu-Lin},
journal = {Mathematical Problems in Engineering},
title = {Parareal Algorithms Implemented with {IMEX} Runge-Kutta Methods},
url = {http://dx.doi.org/10.1155/2015/395340},
doi = {10.1155/2015/395340},
volume = {2015},
year = {2015},
}
@article{Wu2015,
author = {Wu, Shu-Lin and Zhou, Tao},
journal = {SIAM Journal on Scientific Computing},
number = {2},
pages = {A970--A992},
title = {Convergence Analysis for Three Parareal Solvers},
url = {http://dx.doi.org/10.1137/140970756},
doi = {10.1137/140970756},
volume = {37},
year = {2015}
}
@article{Wu2015b,
author = {Wu, Shu-Lin},
doi = {10.1007/s10915-015-0100-x},
journal = {Journal of Scientific Computing},
pages = {1--25},
title = {Convergence Analysis of the Parareal-Euler Algorithm for Systems of ODEs with Complex Eigenvalues},
url = {http://dx.doi.org/10.1007/s10915-015-0100-x},
year = {2015},
}
%
% 2016
%
@article{AlhubailEtAl2016,
abstract = {{This article investigates the swept rule of space-time domain decomposition, an idea to break the latency barrier via communicating less often when explicitly solving time-dependent PDEs. The swept rule decomposes space and time among computing nodes in ways that exploit the domains of influence and the domain of dependency, making it possible to communicate once per many timesteps without redundant computation. The article presents simple theoretical analysis to the performance of the swept rule which then was shown to be accurate by conducting numerical experiments.}},
author = {Maitham Alhubail and Qiqi Wang},
doi = {10.1016/j.jcp.2015.11.026},
journal = {Journal of Computational Physics},
pages = {110--121},
title = {The swept rule for breaking the latency barrier in time advancing {PDEs}},
url = {http://dx.doi.org/10.1016/j.jcp.2015.11.026},
volume = {307},
year = {2016},
}
@article{Astorino2016,
abstract ={{In this work, we propose a new numerical procedure for the simulation of time-dependent problems based on the coupling between the finite element method (FEM) and the lattice Boltzmann method. The procedure exploits the Parareal paradigm to efficiently couple the two numerical methods, allowing independent grid size and time-step size. The motivations behind this approach are wide-ranging. In particular, one technique may be more efficient or physically more appropriate or less memory consuming than the other depending on the target of the simulation and/or on the sub-region of the computational domain. Furthermore, the coupling with FEM may circumvent some difficulties inherent to lattice Boltzmann discretization, for some domains with complex boundaries, or for some kind of boundary conditions. The theoretical and numerical framework is presented for the time-dependent heat equation in order to describe and validate numerically the methodology in a simple situation.}},
author = {Astorino, Matteo and Chouly, Franz and Quarteroni, Alfio},
journal = {Applied Mathematics Research eXpress},
title = {A Time-Parallel Framework for Coupling Finite Element and Lattice Boltzmann Methods},
url = {http://dx.doi.org/10.1093/amrx/abv009},
doi = {10.1093/amrx/abv009},
volume = {2016},
number = {1},
pages = {24--67},
year = {2016},
}
@phdthesis{Beck2016,
abstract = {{This work investigates the potential of an in-time parallelization of atmospheric chemical kinetics. Its numerical calculation is one time-consuming step within the numerical prediction of the air quality. The widely used parallelization strategies only allow a limited potential level of parallelism. A higher level of parallelism within the codes will be necessary to enable benefits from future exa-scale computing architectures. In air quality prediction codes, chemical kinetics is typically considered to react in isolated boxes over short splitting intervals. This allows their trivial parallelization in space, which however is limited by the number of grid entities. This work pursues a parallelization beyond this trivial potential and investigates a parallelization across time using the so called ``parareal algorithm''. The latter is an iterative prediction-correction scheme, whose efficiency strongly depends on the choice of the predictor. For that purpose, different options are being investigate and compared: Time-stepping schemes with fixed step size, adaptive time-stepping schemes and repro-models, functional representations, that map a given state to a later state in time. Only the choice of repromodels leads to a speed-up through parallelism, compared to the sequential reference for the scenarios considered here.}},
author = {Beck, Teresa},
title = {In-Time Parallelization Of Atmospheric Chemical Kinetics},
school = {Ruprecht-Karls-Universit\"{a}t Heidelberg},
url = {http://archiv.ub.uni-heidelberg.de/volltextserver/20092/1/TBeck_Phd_a.pdf},
year = {2016},
}
@unpublished{CarlbergEtAl2016,
abstract = {{This work proposes a data-driven method for enabling the efficient, stable time-parallel numerical solution of
systems of ordinary differential equations (ODEs). The method assumes that low-dimensional bases that accurately capture
the time evolution of the dynamical-system state are available; these bases can be computed from snapshot data by proper
orthogonal decomposition (POD) in the case of parameterized ODEs, for example. The method adopts the parareal framework
for time parallelism, which is defined by an initialization method, a coarse propagator that advances solutions on a coarse
time grid, and a fine propagator that operates on an underlying fine time grid. Rather than employing usual approaches for
initialization and coarse propagation (e.g., a typical time integrator applied with a large time step), we propose novel datadriven
techniques that leverage the available time-evolution bases. The coarse propagator is defined by a forecast (proposed in
Ref. [11]) applied locally within each coarse time interval, which comprises the following steps: (1) apply the fine propagator
for a small number of time steps, (2) approximate the state over the entire coarse time interval using gappy POD with the local
time-evolution bases, and (3) select the approximation at the end of the time interval as the propagated state. We also propose
both local-forecast initialization (i.e., the local-forecast coarse propagator applied sequentially) and global-forecast initialization
(i.e., the local-forecast coarse propagator applied over the entire time interval with global time-evolution bases). The method
is particularly well suited for POD-based reduced-order models (ROMs). In this case, spatial parallelism quickly saturates, as
the ROM dynamical system is low dimensional; thus, time parallelism is needed to enable lower wall times. Further, the timeevolution
bases can be extracted from readily available data, i.e., the right singular vectors arising during POD computation.
In addition to performing analyses related to the method’s accuracy, speedup, and stability, we also numerically demonstrate
the method’s performance. Here, numerical experiments on ROMs for a nonlinear convection–reaction problem demonstrate
the method’s ability to realize near-ideal speedups; global-forecast initialization with a local-forecast coarse propagator leads
to the best performance}},
author = {Carlberg, Kevin and Brencher, Lukas and Haasdonk, Bernard and Barth, Andreas},
title = {Data-driven time parallelism via forecasting},
howpublished = {arXiv:1610.09049v1 [cs.NA]},
url = {https://arxiv.org/pdf/1610.09049.pdf},
year = {2016},
}
@article{ChaudryEtAl2016,
abstract = {{We consider numerical methods for initial value problems that employ a two-stage approach consisting of solution on a relatively coarse discretization followed by solution on a relatively fine discretization. Examples include adaptive error control, parallel-in-time solution schemes, and efficient solution of adjoint problems for computing a posteriori error estimates. We describe a general formulation of two-stage computations and then perform a general a posteriori error analysis based on computable residuals and solution of an adjoint problem. The analysis accommodates various variations in the two-stage computation and in the formulation of the adjoint problems. We apply the analysis to computing “dual-weighted” a posteriori error estimates, developing novel algorithms for efficient solution that take into account cancellation of error, and to the Parareal algorithm. We test the various results using several numerical examples.}},
author = {Jehanzeb Hameed Chaudhry and Don Estep and Simon Tavener and Varis Carey and Jeff Sandelin},
title = {A Posteriori Error Analysis of Two-Stage Computation Methods with Application to Efficient Discretization and the Parareal Algorithm},
journal = {SIAM Journal on Numerical Analysis},
volume = {54},
number = {5},
pages = {2974--3002},
year = {2016},
doi = {10.1137/16M1079014},
url = {http://dx.doi.org/10.1137/16M1079014},
}
@article{DeVuyst2016,
author = {De Vuyst, Florian},
title = {Efficient solvers for time-dependent problems: a review of {IMEX}, {LATIN}, {PARAEXP} and {PARAREAL} algorithms for heat-type problems with potential use of approximate exponential integrators and reduced-order models},
journal = {Advanced Modeling and Simulation in Engineering Sciences},
pages = {3--8},
url = {http://dx.doi.org/10.1186/s40323-016-0063-y},
doi = {10.1186/s40323-016-0063-y},
year = {2016}
}
@article{EghbalEtAl2016,
abstract = {{The parareal algorithm is used to obtain temporal parallelization added to the parallelism obtained from the conventional spatial domain decomposition techniques for hydrodynamic problems. Parareal solution becomes unstable at high Reynolds numbers where the non-linear convection term in the Navier-Stokes equations becomes much larger than the diffusion term. A new framework that allows using parareal for unsteady high Reynolds number hydrodynamic problems is proposed where parareal coarse and fine time integration operators are incorporated with coarse and fine spatial grids respectively and \{RANS\} or \{DES\} turbulence models are employed with a blended filter that can be tuned for the stability of the method. This framework is composed of three solution stages where parareal serves as a transitional stage that bridges a coarse grid solution to a fine grid one. While in lower Reynolds number problems parareal solution can serve as a final solution, in higher Reynolds number problems with high degree of non-linearity parareal provides a shorter path to the final solution. Anticipating a parareal stage in a transitional sense allows a looser convergence requirement which leads to high speedup gains in that stage. On the other hand improved initial values at the beginning of the last stage yields a shorter final fine stage solution. A windowing technique is employed in this methodology to further control the parareal instabilities by keeping the parareal corrections smaller while still being able to cover an arbitrary simulation time with given computational resources. Application of this methodology has been illustrated with a fully turbulent vortex shedding from a cylinder and a flow from the Grand Passage tidal zone in the Bay of Fundy. It is concluded that a tuned turbulence model may sufficiently stabilize the parareal methodology for many practical problems such that it becomes applicable in the initialization process if not accurate enough as a final solution. \{MPI\} and OpenMP programming paradigms are used for temporal parallelism introduced by parareal and data parallelism obtained via spatial domain decomposition methods respectively. Also all computational tasks are accelerated using \{CUDA\} compatible GPGPUs.}},
author = {Araz Eghbal and Andrew G. Gerber and Eric Aubanel},
doi = {10.1016/j.jocs.2016.12.006},
journal = "Journal of Computational Science ",
pages = {57--76},
title = {Acceleration of Unsteady Hydrodynamic Simulations Using the Parareal Algorithm},
url = {http://dx.doi.org/10.1016/j.jocs.2016.12.006},
volume = {19},
year = {2016},
}
@techreport{FalgoutEtAl2016,
abstract = {{With steadily growing computational resources available, scientists must develop effective ways to utilize the increased resources. High performance, highly parallel software has become a standard. However until recent years parallelism has focused primarily on the spatial domain. When solving a space-time partial differential equation (PDE), this leads to a sequential bottleneck in the temporal dimension, particularly when taking a large number of time steps. The XBraid parallel-in-time library was developed as a practical way to add temporal parallelism to existing sequential codes with only minor modi cations. In this work, a rezoning-type moving mesh is applied to a diffusion problem and formulated in a parallel-in-time framework. Tests and scaling studies are run using XBraid and demonstrate excellent results for the simple model problem considered herein.}},
author = {Falgout, R.~D. and Manteuffel, T.~A. and Southworth, B. and Schroder, J. B.},
institution = {Lawrence Livermore National Laboratory},
doi = {10.2172/1239230},
title = {Parallel-In-Time For Moving Meshes},
url = {http://www.osti.gov/scitech/servlets/purl/1239230},
year={2016},
}
@inproceedings{GahvariEtAl2016,
abstract = {{The traditional way to numerically solve time-dependent problems is to sequentially march through time, solving for one time step and then the next. The parallelism in this approach is limited to the spatial dimension, which is quickly exhausted, causing the gain from using more processors to solve a problem to diminish. One approach to overcome this barrier is to use methods that are parallel in time. These methods have the potential to achieve dramatically better performance compared to time-stepping approaches, but achieving this performance requires carefully choosing the amount of parallelism devoted to space versus the amount devoted to time. Here, we present
a performance model that, for a multigrid-in-time solver, makes the decision on when to switch to parallel-in-time and on how much parallelism to devote to space vs. time. In our experiments, the model selects the best parallel configuration in most of our test cases and a configuration close to the best one in all other cases}},
author = {Gahvari, Hormozd and Dobrev, Veselin A. and Falgout, Rob D. and Kolev, Tzanio V. and Schroder, Jacob B. and Schulz, Martin and {Meier Yang}, Ulrike},
title = {A Performance Model for Allocating the Parallelism in a Multigrid-in-Time Solver},
booktitle = {7th International Workshop on Performance Modeling, Benchmarking and Simulation of High Performance Computer Systems},
doi = {10.1109/PMBS.2016.8},
url = {http://dx.doi.org/10.1109/PMBS.2016.8},
year = {2016}
}
@InProceedings{GanderEtAl2016,
author={Gander, Martin J. and Halpern, Laurence and Ryan, Juliet and Tran, Thuy Thi Bich},
editor={Dickopf, Thomas and Gander, Martin J. and Halpern, Laurence and Krause, Rolf and Pavarino, Luca F.},
title={{A Direct Solver for Time Parallelization}},
booktitle={Domain Decomposition Methods in Science and Engineering XXII},
year={2016},
publisher={Springer International Publishing},
pages={491--499},
url={http://dx.doi.org/10.1007/978-3-319-18827-0_50},
doi={10.1007/978-3-319-18827-0_50},
}
@article{GurralaEtAl2016,
abstract = {{Recent advancements in high-performance parallel computing platforms and parallel algorithms have significantly enhanced the opportunities for real-time power system protection and control. This paper investigates application of Parareal in time algorithm for fast dynamic simulations. Parareal algorithm belongs to the class of temporal decomposition methods which divide the time interval into sub-intervals and solve them concurrently. Time-parallel algorithms face the difficulty of providing correct initial conditions for all the sub-intervals which impact the convergence rates. Parareal overcomes this difficulty by using an approximate trajectory. It has become popular in recent years for long transient simulations (e.g., molecular dynamics, fusion, reacting flows). This paper presents an approach for reliable implementation of Parareal with detailed models of power systems including saturation. Windowing approach is proposed for improving the convergence. Parareal is compared with the Newton-based time-parallel method. Effectiveness of the algorithm is analyzed by parallel emulation using extensive case studies on 10-generator 39-bus system and 327-generator 2383-bus system for various disturbances. Parareal with simulation windows of 1 s have shown convergence in 1 to 3 iterations for majority of the simulated cases, irrespective of the size of the system and nature of the disturbance. All the cases tested have converged with the proposed implementation.}},
author={G. {Gurrala} and A. {Dimitrovski} and S. {Pannala} and S. {Simunovic} and M. {Starke}},
journal={IEEE Transactions on Power Systems},
title={{Parareal in Time for Fast Power System Dynamic Simulations}},
year={2016},
volume={31},
number={3},
pages={1820--1830},
url={http://dx.doi.org/10.1109/TPWRS.2015.2434833},
doi={10.1109/TPWRS.2015.2434833},
}
@unpublished{Guetat2016,
abstract = {{In this paper, we present a new parallel algorithm for time dependent problems based on coupling parareal with non-overlapping domain decomposition method in order to increase parallelism in time and in space. For this we focus on the iterative methods of parallization in space to solve the interface problem like Neumann-Neumann method. In the new algorithm, the coarse temporel propagator is defined on the global domain and the Neumann-Neumann method is chosen as a fine propagator with a few iterations. We present the rigorous convergence analysis of the new coupled algorithm on bounded time interval. Numerical experiments illustrate the performance of this new algorithm and confirm our analysis.}},
author = {Guetat, Rim},
howpublished = {hal-01312528},
url = {https://hal.archives-ouvertes.fr/hal-01312528/},
title = {Coupling Parareal with Non-Overlapping Domain Decomposition Method},
year = {2016}
}
@article{Haut2016,
abstract ={The manuscript presents a technique for efficiently solving the classical wave equation, the shallow water equations, and, more generally, equations of the form $\partial u /\partial t = \mathcal {L}u$, where $\mathcal {L}$ is a skew-Hermitian differential operator. The idea is to explicitly construct an approximation to the time-evolution operator $\exp (\tau \mathcal {L})$ for a relatively large time-step $\tau $. Recently developed techniques for approximating oscillatory scalar functions by rational functions, and accelerated algorithms for computing functions of discretized differential operators are exploited. Principal advantages of the proposed method include: stability even for large time-steps, the possibility to parallelize in time over many characteristic wavelengths and large speed-ups over existing methods in situations where simulation over long times are required. Numerical examples involving the 2D rotating shallow water equations and the 2D wave equation in an inhomogenous medium are presented, and the method is compared to the 4th order Runge–Kutta (RK4) method and to the use of Chebyshev polynomials. The new method achieved high accuracy over long-time intervals, and with speeds that are orders of magnitude faster than both RK4 and the use of Chebyshev polynomials.},
author = {Haut, T.~S. and Babb, T. and Martinsson, P.~G. and Wingate, B.~A.},
doi = {10.1093/imanum/drv021},
journal = {IMA Journal of Numerical Analysis},
number = {2},
pages = {688--716},
title = {A high-order time-parallel scheme for solving wave propagation problems via the direct construction of an approximate time-evolution operator},
URL = {http://dx.doi.org/10.1093/imanum/drv021},
volume = {36},
year = {2016},
}
@article{LapinEtAl2016,
abstract={{The article deals with the optimal control problem with the parabolic equation as state problem. There are point-wise constraints on the state and control functions. The objective functional involves the observation given in the domain at each moment. The conditions for convergence Udzawa's type iterative method are given. The parareal method to inverse preconditioner is given. The results of calculations are presented.}},
author={A Lapin and A Romanenko},
journal={IOP Conference Series: Materials Science and Engineering},
number={1},
pages={012059},
title={Udzawa-type iterative method with parareal preconditioner for a parabolic optimal control problem},
url={http://dx.doi.org/10.1088/1757-899X/158/1/012059},
doi={10.1088/1757-899X/158/1/012059},
volume={158},
year={2016},
}
@inproceedings{Lecouvez2016,
abstract = {{This paper presents a fully multilevel approach to parallel in time solution of transient power system simulations. The method employs a multigrid reduction algorithm in time parallelized using the MPI distributed memory programming model. The method is demonstrated on a simple Single Machine Infinite Bus differential-algebraic equation model problem, for which speedup is obtained for as few as 8 processing cores on a problem with 10,000 time steps. Speedup of a factor of 13 is observed for a 100,000 step version of this simple problem. Based on these results, we expect significantly better speedup on larger problems where more work is available to each processor allowing greater amortization of the parallel communication.}},
author = {M. {Lecouvez} and R.~D. {Falgout} and C.~S. {Woodward} and P. {Top}},
booktitle = {2016 IEEE Power and Energy Society General Meeting (PESGM)},
title = {A parallel multigrid reduction in time method for power systems},
year = {2016},
pages = {1--5},
doi = {10.1109/PESGM.2016.7741520},
url = {https://dx.doi.org/10.1109/PESGM.2016.7741520}
}
@article{Lederman2016,
author = {Lederman, C. and Martin, R. and Cambier, J.-L.},
title = {Time-parallel solutions to differential equations via functional optimization},
journal = {Computational and Applied Mathematics},
year = {2016},
pages = {1--25},
abstract={{We describe an approach to solving a generic time-dependent differential equation (DE) that recasts the problem as a functional optimization one. The techniques employed to solve for the functional minimum, which we relate to the Sobolev Gradient method, allow for large-scale parallelization in time, and therefore potential faster ``wall-clock'' time computing on machines with significant parallel computing capacity. We are able to come up with numerous different discretizations and approximations for our optimization-derived equations, each of which either puts an existing approach, the Parareal method, in an optimization context, or provides a new time-parallel (TP) scheme with potentially faster convergence to the DE solution. We describe how the approach is particularly effective for solving multiscale DEs and present TP schemes that incorporate two different solution scales. Sample results are provided for three differential equations, solved with TP schemes, and we discuss how the choice of TP scheme can have an orders of magnitude effect on the accuracy or convergence rate.}},
doi = {10.1007/s40314-016-0319-7},
url = {http://dx.doi.org/10.1007/s40314-016-0319-7}
}
@inproceedings{LeffellEtAl2016,
abstract = {{}},
author = {Leffell, Joshua I. and Sitaraman, Jayanarayanan and Lakshminarayan, Vinod K. and Wissink, Andrew M.},
booktitle = {54th AIAA Aerospace Sciences Meeting},
title = {Towards Efficient Parallel-in-Time Simulation of Periodic Flows},
doi = {10.2514/6.2016-0066},
url = {http://dx.doi.org/10.2514/6.2016-0066},
publisher = {American Institute of Aeronautics and Astronautics},
year = {2016},
}
@inproceedings{MatsuokaEtAl2016,
abstract = {{Slowdown and inevitable end in exponential scaling of processor performance, the end of the so-called "Moore's Law" is predicted to occur around 2025--2030 timeframe. Because CMOS semiconductor voltage is also approaching its limits, this means that logic transistor power will become constant, and as a result, the system FLOPS will cease to improve, resulting in serious consequences for IT in general, especially supercomputing. Existing attempts to overcome the end of Moore's law are rather limited in their future outlook or applicability. We claim that data-oriented parameters, such as bandwidth and capacity, or BYTES, are the new parameters that will allow continued performance gains for periods even after computing performance or FLOPS ceases to improve, due to continued advances in storage device technologies and optics, and manufacturing technologies including 3-D packaging. Such transition from FLOPS to BYTES will lead to disruptive changes in the overall systems from applications, algorithms, software to architecture, as to what parameter to optimize for, in order to achieve continued performance growth over time. We are launching a new set of research efforts to investigate and devise new technologies to enable such disruptive changes from FLOPS to BYTES in the Post-Moore era, focusing on HPC, where there is extreme sensitivity to performance, and expect the results to disseminate to the rest of IT.}},
author = {Matsuoka, Satoshi and Amano, Hideharu and Nakajima, Kengo and Inoue, Koji and Kudoh, Tomohiro and Maruyama, Naoya and Taura, Kenjiro and Iwashita, Takeshi and Katagiri, Takahiro and Hanawa, Toshihiro and Endo, Toshio},
title = {From FLOPS to BYTES: Disruptive Change in High-performance Computing Towards the Post-moore Era},
booktitle = {Proceedings of the ACM International Conference on Computing Frontiers},
series = {CF '16},
year = {2016},
location = {Como, Italy},
pages = {274--281},
numpages = {8},
url = {http://dx.doi.org/10.1145/2903150.2906830},
doi = {10.1145/2903150.2906830},
publisher = {ACM},
address = {New York, NY, USA},
}
@inproceedings{MerkelEtAl2016,
abstract = {{Recently, ParaExp was proposed for the time integration of hyperbolic problems. It splits the time interval of interest into sub-intervals and computes the solution on each sub-interval in parallel. The overall solution is decomposed into a particular solution defined on each sub-interval with zero initial conditions and a homogeneous solution propagated by the matrix exponential applied to the initial conditions. The efficiency of the method results from fast approximations of this matrix exponential using tools from linear algebra. This paper deals with the application of ParaExp to electromagnetic wave problems in time-domain. Numerical tests are carried out for an electric circuit and an electromagnetic wave problem discretized by the Finite Integration Technique.}},
author = {Merkel, Melina and Niyonzima, Innocent and Schöps, Sebastian},
booktitle = {Proceedings of 2016 URSI International Symposium on Electromagnetic Theory (EMTS)},
editor = {Sihvola, Ari},
note = {arXiv:1607.00368 [math.NA]},
publisher = {IEEE},
title = {An Application of ParaExp to Electromagnetic Wave Problems},
url = {https://doi.org/10.1109/URSI-EMTS.2016.7571330},
doi = {10.1109/URSI-EMTS.2016.7571330},
year = {2016}
}
@article{NeumuellerGander2016,
abstract = {{We present and analyze a new space-time parallel multigrid method for parabolic equations.
The method is based on arbitrarily high order discontinuous Galerkin discretizations in time, and a finite
element discretization in space.
The key ingredient of the new algorithm is a block Jacobi smoother.
We present a detailed convergence analysis when the algorithm is applied to the heat equation, and determine
asymptotically optimal smoothing parameters, a precise criterion for semi-coarsening in time or full coarsening,
and give an asymptotic two grid contraction factor estimate.
We then explain how to implement the new multigrid algorithm in parallel, and show with numerical experiments
its excellent strong and weak scalability properties.}},
author = {Martin J. Gander and Martin Neum\"uller},
title = {Analysis of a New Space-Time Parallel Multigrid Algorithm for Parabolic Problems},
journal = {SIAM Journal on Scientific Computing},
volume = {38},
number = {4},
pages = {A2173--A2208},
year = {2016},
doi = {10.1137/15M1046605},
url = {http://dx.doi.org/10.1137/15M1046605},
}
@inproceedings{NielsenHesthaven2016,
author = {Nielsen, Allan S. and Hesthaven, Jan S.},
title = {Fault Tolerance in the Parareal Method},
booktitle = {Proceedings of the ACM Workshop on Fault-Tolerance for HPC at Extreme Scale},
series = {FTXS '16},
year = {2016},
isbn = {978-1-4503-4349-7},
location = {Kyoto, Japan},
pages = {1--8},
numpages = {8},
url = {http://dx.doi.org/10.1145/2909428.2909431},
doi = {10.1145/2909428.2909431},
acmid = {2909431},
publisher = {ACM},
address = {New York, NY, USA},
abstract = {{Parallel-in-time integration is an often advocated approach for extracting parallelism in the solution of PDEs beyond what is possible using spacial domain decomposition tech- niques. Due to the comparatively low parallel efficiency of parallel-in-time integration techniques, they are primar- ily of interest as an extension for classical approaches at parallelism. As such, potential applications are expected to scale across several hundreds, or possibly thousands of nodes, making algorithmic resilience towards hardware in- duced errors highly relevant. In this work we develop a scheduling scheme for the parareal algorithm that is resilient to node-loss. The fault-tolerant scheme is based on a popu- lar approach introduced by E. Aubanel in [1], modified with a set of MPI interface extensions for implementing recov- ery strategies available in the ULFM framework. In ad- dition, we demonstrate how the parareal algorithm may be made resilient towards Silent-Data-Corruption (SDC) errors by viewing it as a point-iterative method, locally monitor- ing the residual between consecutive iterations so to discard potentially corrupt iterations.}}
}
@article{OngEtAl2016,
abstract = {{Revisionist integral deferred correction methods are a family of parallel-in-time methods to solve systems of initial values problems. The approach is able to bootstrap lower-order time integrators to provide high-order approximations in approximately the same wall-clock time, hence providing a multiplicative increase in the number of compute cores utilized. Here we provide a library that automatically produces a parallel-in-time solution of a system of initial value problems given user-supplied code for the right-hand side of the system and a sequential code for a first-order timestep. The user-supplied timestep routine may be explicit or implicit and may make use of any auxiliary libraries that take care of the solution of any nonlinear algebraic systems that may arise or the numerical linear algebra required.}},
author = {Ong, Benjamin W. and Haynes, Ronald D. and Ladd, Kyle},
articleno = {8},
doi = {10.1145/2964377},
title = {Algorithm 965: {RIDC} Methods: A Family of Parallel Time Integrators},
journal = {ACM Trans. Math. Softw.},
number = {1},
numpages = {13},
pages = {8:1--8:13},
url = {http://dx.doi.org/10.1145/2964377},
volume = {43},
year = {2016},
}
@Inproceedings{RuprechtEtAl2016,
abstract = {{For the time-parallel Parareal method, there exists both numerical and analytical proof that it converges very well
for diffusive problems like the heat equation. Many applications, however, do not lead to simple homogeneous
diffusive problems but feature strongly inhomogeneous and possibly anisotropic coefficients. In the talk, we will
present results from a numerical study of how non-constant coefficients in a diffusion problem influence the convergence
behaviour of Parareal. Further, the effect of different parameters like e.g. temporal and spatial resolution
and geometry is explored.}},
author = {Ruprecht, Daniel and Speck, Robert and Krause, Rolf},
booktitle = {Domain Decomposition Methods in Science and Engineering {XXII}},
doi = {10.1007/978-3-319-18827-0_37},
editor = {Dickopf, Thomas and Gander, J. Martin and Halpern, Laurence and Krause, Rolf and Pavarino, F. Luca},
pages = {371--378},
publisher = {Springer International Publishing},
url = {http://dx.doi.org/10.1007/978-3-319-18827-0_37},
title = {Parareal for Diffusion Problems with Space- and Time-Dependent Coefficients},
year = {2016},
}
@inproceedings{SekineEtAl2016,
abstract={Long computation time is required for transient stability analysis of power systems because it can be expressed as combination of differential and algebraic equations. In order to finish the calculation within a practical amount of time, it is an effective approach that applying Parareal method as one of parallel computing technique to transient stability analysis. In the Parareal method, the accuracy of the result is gradually updated through iterative procedures in combination with rough estimation of entire waveform and detailed calculation for each decomposed time window. Based on the Parareal method, the authors have developed a new stability assessment method by using chaos theory. If an operating point is in unstable region, the trajectory has the chaotic property, “sensitive dependence on initial conditions”. Therefore, it is possible to assess the stability by detecting the convergence characteristics of the estimated waveform at each iterative procedure by the Parareal method. The effectiveness of the proposed method was tested by using IEEJ WEST10 system model.},
author={T. Sekine and T. Tsuji and T. Oyama and F. Magoulès and K. Uchida},
booktitle={2016 IEEE Innovative Smart Grid Technologies - Asia (ISGT-Asia)},
doi={10.1109/ISGT-Asia.2016.7796552},
pages={1177--1182},
title={Speedup of parallel computing by parareal method in transient stability analysis of Japanese power system},
url={http://dx.doi.org/10.1109/ISGT-Asia.2016.7796552},
year={2016},
}
@article{Wu2016,
title = {A second-order parareal algorithm for fractional {PDEs}},
journal = {Journal of Computational Physics},
volume = {307},
pages = {280--290},
year = {2016},
url = {http://dx.doi.org/10.1016/j.jcp.2015.12.007},
doi = {10.1016/j.jcp.2015.12.007},
author = {Shu-Lin Wu},
}
@Article{Wu2016_JSC,
author = {Wu, Shu-Lin},
doi = {10.1007/s10915-015-0100-x},
journal = {Journal of Scientific Computing},
number = {2},
pages = {644--668},
title = {Convergence Analysis of the Parareal-Euler Algorithm for Systems of ODEs with Complex Eigenvalues},
url = {http://dx.doi.org/10.1007/s10915-015-0100-x},
volume = {67},
year = {2016},
}
@article{Wu2016_JCAM,
abstract = {{Abstract Parareal is an iterative algorithm and is characterized by two propagators G and F , which are respectively associated with large step size Δ T and small step size Δ t , where Δ T = J Δ t and J ≥ 2 is an integer. For symmetric positive definite (SPD) system u ′ ( t ) + A u ( t ) = g ( t ) arising from semi-discretizing time-dependent PDEs, if we fix the G -propagator to the Backward-Euler method and choose for F some L -stable time-integrator it can be proven that the convergence factors of the corresponding parareal algorithms satisfy ρ ≈ 1 3 , ∀ J ≥ 2 and ∀ σ ( A ) ⊂ [ 0 , + ∞ ) , where σ ( A ) is the spectrum of the matrix A . However, this result does not hold when time-integrators that lack L -stability, such as the Trapezoidal rule and the 4th-order Gauss \{RK\} method, are chosen as the F -propagator. The parareal algorithms using these two methods for the F -propagator are denoted by Parareal-TR and Parareal-Gauss4. In this paper, we propose a strategy to let these two parareal algorithms possess such a uniform convergence property. The idea is to choose an L -stable propagator F ˜ and on each coarse time-interval [ T n , T n + 1 ] we perform first two steps of F ˜ , then followed by J − 2 steps of F . Precisely, for the Trapezoidal rule we select the 2nd-order \{SDIRK\} method as the F ˜ -propagator, and for the 4th-order Gauss \{RK\} method we select the 4th-order Lobatto III-C method as the F ˜ -propagator. Numerical results are given to support our theoretical conclusions.}},
author = {Shu-Lin Wu},
doi = {10.1016/j.cam.2016.05.036},
journal = {Journal of Computational and Applied Mathematics},
pages = {391--407},
title = {Towards essential improvement for the Parareal-TR and Parareal-Gauss4 algorithms},
url = {http://dx.doi.org/10.1016/j.cam.2016.05.036},
volume = {308},
year = {2016},
}
@article{WuZhou2016_JCP,
author = {Shu-Lin Wu and Tao Zhou},
doi = {10.1016/j.jcp.2016.10.046},
journal = {Journal of Computational Physics},
pages = {210--226},
title = {Fast parareal iterations for fractional diffusion equations},
url = {http://dx.doi.org/10.1016/j.jcp.2016.10.046},
volume = {329},
year = {2016},
}
@article {ZhangEtAl2016,
author = {Zhang, Liying and Zhou, Weien and Ji, Lihai},
title = {Parareal algorithms applied to stochastic differential equations with conserved quantities},
journal = {Journal of Computational Mathematics},
volume = {37},
year = {2019},
number = {1},
pages = {48--60},
doi = {10.4208/jcm.1708-m2017-0089},
url = {https://doi.org/10.4208/jcm.1708-m2017-0089},
}
%
% 2017
%
@unpublished{ArielEtAl2017,
abstract = {{A weighted version of the parareal method for parallel-in-time computation of time dependent problems is presented. Linear stability analysis for a scalar weighing strategy shows that the new scheme may enjoy favorable stability properties with marginal reduction in accuracy at worse. More complicated matrix-valued weights are applied in numerical examples. The weights are optimized using information from past iterations, providing a systematic framework for using the parareal iterations as an approach to multiscale coupling. The advantage of the method is demonstrated using numerical examples, including some well-studied nonlinear Hamiltonian systems.}},
author = {Ariel, Gil and Nguyen, Hieu and Tsai, Richard},
title = {$\theta$-parareal schemes},
howpublished = {arXiv:1704.06882 [math.NA]},
url = {https://arxiv.org/abs/1704.06882},
year = {2017},
}
@article{BadiaEtAl2017,
abstract = {{In this work, we propose two-level space-time domain decomposition preconditioners for parabolic problems discretized using finite elements. They are motivated as an extension to space-time of balancing domain decomposition by constraints preconditioners. The key ingredients to be defined are the subassembled space and operator, the coarse degrees of freedom (DOFs) in which we want to enforce continuity among subdomains at the preconditioner level, and the transfer operator from the subassembled to the original finite element space. With regard to the subassembled operator, a perturbation of the time derivative is needed to end up with a well-posed preconditioner. The set of coarse DOFs includes the time average (at the space-time subdomain) of classical space constraints plus new constraints between consecutive subdomains in time. Numerical experiments show that the proposed schemes are weakly scalable in time, i.e., we can efficiently exploit increasing computational resources to solve more time steps in the same total elapsed time. Further, the scheme is also weakly space-time scalable, since it leads to asymptotically constant iterations when solving larger problems both in space and time. Excellent wall clock time weak scalability is achieved for space-time parallel solvers on some thousands of cores.}},
author = {Santiago Badia and Marc Olm},
title = {Space-Time Balancing Domain Decomposition},
journal = {SIAM Journal on Scientific Computing},
volume = {39},
number = {2},
pages = {C194--C213},
year = {2017},
url = {https://doi.org/10.1137/16M1074266},
doi = {10.1137/16M1074266}
}
@article{BelliveauHaber2017,
abstract = {{We have developed a new algorithm for three-dimensional time-domain electromagnetic (EM) modelling, taking full account of induced polarization (IP) and the coupling between EM and IP effects. The algorithm can be used to model grounded source IP surveys that show EM induction effects as well as airborne time-domain electromagnetic surveys that exhibit IP effects. IP effects are most often approximated as static or modelled in the frequency domain, using frequency dependent electrical conductivity. It is difficult to translate the frequency dependent conductivity approach directly to the time domain in a computationally efficient manner. We take an alternative approach in which we model IP relaxations in time using the stretched exponential function. We incorporate this IP model into a direct time-stepping discretization of the quasi-static time-domain Maxwell equations. We show that modelling of IP effects with this stretched exponential approach is asymptotically equivalent to the commonly used Cole-Cole model of IP transformed to the time-domain. We have implemented our algorithm using efficient numerical methods that allow it to tackle large scale problems and are amenable to use in inversion. In particular we have developed a parallel time-stepping technique that allows us to compute transient electric fields at multiple time-steps simultaneously. We demonstrate the behaviour of the stretched exponential model of IP decay as well as the efficiency of our algorithm by applying it to synthetic numerical examples that simulate a grounded source IP survey with significant EM effects and a concentric-loop airborne EM sounding over a chargeable body.}},
author = {Patrick Belliveau and Eldad Haber},
title = {Coupled simulation of electromagnetic induction and {IP} effects using stretched exponential relaxation},
journal = {Geophysics},
pages = {1-–61},
year = {2017},
doi = {10.1190/geo2017-0494.1},
url = {https://doi.org/10.1190/geo2017-0494.1},
}
@article{BoltenEtAl2017,
abstract = {{For the numerical solution of time-dependent partial differential equations, time-parallel methods have recently been shown to provide a promising way to extend prevailing strong-scaling limits of numerical codes. One of the most complex methods in this field is the “Parallel Full Approximation Scheme in Space and Time” (PFASST). PFASST already shows promising results for many use cases and benchmarks. However, a solid and reliable mathematical foundation is still missing. We show that, under certain assumptions, the PFASST algorithm can be conveniently and rigorously described as a multigrid-in-time method. Following this equivalence, first steps towards a comprehensive analysis of PFASST using blockwise local Fourier analysis are taken. The theoretical results are applied to examples of diffusive and advective type.}},
author = {Bolten, Matthias and Moser, Dieter and Speck, Robert},
title = {A multigrid perspective on the parallel full approximation scheme in space and time},
journal = {Numerical Linear Algebra with Applications},
volume = {24},
number = {6},
pages = {e2110},
doi = {10.1002/nla.2110},
url = {https://dx.doi.org/10.1002/nla.2110},
year = {2017}
}
@article{DobrevEtAl2017,
abstract = {{In this paper we develop a two-grid convergence theory for the parallel-in-time scheme known as multigrid reduction in time (MGRIT), as it is implemented in the open-source package [XBraid: Parallel Multigrid in Time, http://llnl.gov/casc/xbraid]. MGRIT is a scalable and multilevel approach to parallel-in-time simulations that nonintrusively uses existing time-stepping schemes, and in a specific two-level setting it is equivalent to the widely known parareal algorithm. The goal of this paper is twofold. First, we present a two-level MGRIT convergence analysis for linear problems where the spatial discretization matrix can be diagonalized, and then apply this analysis to our two basic model problems, the heat equation and the advection equation. One important assumption is that the coarse and fine time-grid propagators can be diagaonalized by the same set of eigenvectors, which is often the case when the same spatial discretization operator is used on the coarse and fine time grids. In many cases, the MGRIT algorithm is guaranteed to converge, and we demonstrate numerically that the theoretically predicted convergence rates are sharp in practice for our model problems. Second, we explore how the convergence of MGRIT compares to the stability of the chosen time-stepping scheme. In particular, we demonstrate that a stable time-stepping scheme does not necessarily imply convergence of MGRIT, although MGRIT with FCF-relaxation always converges for the diffusion dominated problems considered here.}},
author = {V.~A. Dobrev and Tz. Kolev and N.~A. Petersson and J.~B. Schroder},
title = {Two-Level Convergence Theory for Multigrid Reduction in Time (MGRIT)},
journal = {SIAM Journal on Scientific Computing},
volume = {39},
number = {5},
pages = {S501--S527},
year = {2017},
doi = {10.1137/16M1074096},
url = {https://doi.org/10.1137/16M1074096},
}
@article{FalgoutEtAl2017,
abstract = {{The need for parallelism in the time dimension is being driven by changes in computer architectures, where performance increases are now provided through greater concurrency, not faster clock speeds. This creates a bottleneck for sequential time marching schemes because they lack parallelism in the time dimension. Multigrid reduction in time (MGRIT) is an iterative procedure that allows for temporal parallelism by utilizing multigrid reduction techniques and a multilevel hierarchy of coarse time grids. MGRIT has been shown to be effective for linear problems, with speedups of up to 50 times. The goal of this work is the efficient solution of nonlinear problems with MGRIT, where efficiency is defined as achieving similar performance when compared to an equivalent linear problem. The benchmark nonlinear problem is the $p$-Laplacian, where p=4 corresponds to a well-known nonlinear diffusion equation and $p=2$ corresponds to the standard linear diffusion operator, our benchmark linear problem. The key difficulty encountered is that the nonlinear time-step solver becomes progressively more expensive on coarser time levels as the time-step size increases. To overcome such difficulties, multigrid research has historically targeted an accumulated body of experience regarding how to choose an appropriate solver for a specific problem type. To that end, this paper develops a library of MGRIT optimizations and modifications, most important an alternate initial guess for the nonlinear time-step solver and delayed spatial coarsening, that will allow many nonlinear parabolic problems to be solved with parallel scaling behavior comparable to the corresponding linear problem.}},
author = {R.~D. Falgout and T.~A. Manteuffel and B. O'Neill and J.~B. Schroder},
title = {Multigrid Reduction in Time for Nonlinear Parabolic Problems: A Case Study},
journal = {SIAM Journal on Scientific Computing},
volume = {39},
number = {5},
pages = {S298--S322},
year = {2017},
doi = {10.1137/16M1082330},
url = {https://doi.org/10.1137/16M1082330},
}
@article{FalgoutEtAl2017b,
abstract = {We consider the comparison of multigrid methods for parabolic partial differential equations that allow space--time concurrency. With current trends in computer architectures leading towards systems with more, but not faster, processors, space--time concurrency is crucial for speeding up time-integration simulations. In contrast, traditional time-integration techniques impose serious limitations on parallel performance due to the sequential nature of the time-stepping approach, allowing spatial concurrency only. This paper considers the three basic options of multigrid algorithms on space--time grids that allow parallelism in space and time: coarsening in space and time, semicoarsening in the spatial dimensions, and semicoarsening in the temporal dimension. We develop parallel software and performance models to study the three methods at scales of up to 16K cores and introduce an extension of one of them for handling multistep time integration. We then discuss advantages and disadvantages of the different approaches and their benefit compared to traditional space-parallel algorithms with sequential time stepping on modern architectures.},
author = {Falgout, R.~D. and Friedhoff, S. and Kolev, Tz.~V. and MacLachlan, S. P. and Schroder, J.~B. and Vandewalle, S.},
title = {Multigrid methods with space--time concurrency},
journal = {Computing and Visualization in Science},
year = {2017},
volume = {18},
number = {4},
pages = {123--143},
doi = {10.1007/s00791-017-0283-9},
url = {https://doi.org/10.1007/s00791-017-0283-9}
}
@unpublished{GanderEtAl2017,
author = {Martin J. Gander and Stefan G{\"u}ttel and Madalina Petcu},
title = {A nonlinear {ParaExp} algorithm},
howpublished = {MIMS EPrint: 2017.17},
url = {http://eprints.ma.man.ac.uk/2550/01/covered/MIMS_ep2017_17.pdf},
year = {2017}
}
@inproceedings{GanderHalpern2017,
abstract = {The direct time parallelization method based on diagonalization is only applicable to linear problems. We propose here a new method based on diagonalization which permits the direct parallelization in time of a Newton iteration that works simultaneously over several time steps. We first explain the method for a scalar model problem, and then give a formulation for a nonlinear partial differential equation based on tensorization. We illustrate the methods with numerical experiments.},
author = {Gander, Martin J. and Halpern, Laurence},
editor = {Lee, Chang-Ock and Cai, Xiao-Chuan and Keyes, David E. and Kim, Hyea Hyun and Klawonn, Axel and Park, Eun-Jae and Widlund, Olof B.},
title = {Time Parallelization for Nonlinear Problems Based on Diagonalization},
booktitle = {Domain Decomposition Methods in Science and Engineering {XXIII}},
year = {2017},
publisher = {Springer International Publishing},
pages = {163--170},
doi = {10.1007/978-3-319-52389-7_15},
url = {https://doi.org/10.1007/978-3-319-52389-7_15}
}
@article{GasparRodrigo2017,
abstract = {In this work, we propose an efficient and robust multigrid method for solving the time-fractional heat equation. Due to the nonlocal property of fractional differential operators, numerical methods usually generate systems of equations for which the coefficient matrix is dense. Therefore, the design of efficient solvers for the numerical simulation of these problems is a difficult task. We develop a parallel-in-time multigrid algorithm based on the waveform relaxation approach, whose application to time-fractional problems seems very natural due to the fact that the fractional derivative at each spatial point depends on the values of the function at this point at all earlier times. Exploiting the Toeplitz-like structure of the coefficient matrix, the proposed multigrid waveform relaxation method has a computational cost of $O(NM\log(M))$ operations, where $M$ is the number of time steps and $N$ is the number of spatial grid points. A semialgebraic mode analysis is also developed to theoretically confirm the good results obtained. Several numerical experiments, including examples with nonsmooth solutions and a nonlinear problem with applications in porous media, are presented.},
author = {Francisco J. Gaspar and Carmen Rodrigo},
title = {Multigrid Waveform Relaxation for the Time-Fractional Heat Equation},
journal = {SIAM Journal on Scientific Computing},
volume = {39},
number = {4},
pages = {A1201--A1224},
year = {2017},
doi = {10.1137/16M1090193},
URL = {https://doi.org/10.1137/16M1090193},
}
@inproceedings{HanEtAl2017,
abstract = {{Traditionally, the time integration algorithms for multibody dynamics are in sequential. The predictions of previous time steps are necessary to get the solutions at current time step. This time-marching character impedes the application of parallel processor implementation. In this paper, the idea of computing a number of time steps concurrently is applied to flexible multi-body dynamics, which makes parallel time-integration possible. In the present method, the solution at the current time step is computed before accurate values at previous time step are available. This method is suitable for small-scale parallel analysis of flexible multibody systems.}},
author = {Shilei Han and Olivier A. Bauchau},
booktitle = {13th International Conference on Multibody Systems, Nonlinear Dynamics, and Control},
title = {Parallel Time-Integration of Flexible Multibody Dynamics Based on Newton-Waveform Method},
volume = {6},
url = {https://dx.doi.org/10.1115/DETC2017-68232},
doi = {10.1115/DETC2017-68232},
year = {2017},
}
@phdthesis{Howse2017,
author = {Howse, Alexander James Maxwell},
title = {Nonlinear Preconditioning Methods for Optimization and Parallel-In-Time Methods for 1D Scalar Hyperbolic Partial Differential Equations},
year = {2017},
publisher = {UWSpace},
url = {http://hdl.handle.net/10012/12559}
}
@unpublished{HuEtAl2017,
abstract = {{This work deals with the efficient numerical solution of the time-fractional heat equation discretized on non-uniform temporal meshes. Non-uniform grids are essential to capture the singularities of “typical” solutions of time-fractional problems. We propose an efficient parallel-in-time multigrid method based on the waveform relaxation technique, which accounts for the nonlocal character of the fractional differential operator. To maintain an optimal complexity, which can be obtained for the case of uniform grids, we approximate the coefficient matrix corresponding to the temporal discretization by its hierarchical matrix (H-matrix) representation. In particular, the proposed method has a computational cost of O(kNM log(M)), where M is the number of time steps, N is the number of spatial grid points, and k is a parameter which controls the accuracy of the H-matrix approximation. The efficiency and the good convergence of the algorithm, which can be theoretically justified by a semi-algebraic mode analysis, are demonstrated through numerical experiments in both one- and two-dimensional spaces.}},
author = {Xiaozhe Hu and Carmen Rodrigo and Francisco J. Gaspar},
title = {Using hierarchical matrices in the solution of the time-fractional heat equation by multigrid waveform relaxation},
howpublished = {arXiv:1706.07632v1 [math.NA] },
url = {https://arxiv.org/pdf/1706.07632.pdf},
year = {2017},
}
@unpublished{JanssonEtAl2017,
author = {Johan Jansson and Johan Hoffman},
title = {Direct FEM parallel-in-time computation of turbulent flow},
howpublished.= {KTH Preprint},
year = {2017},
url = {http://www.csc.kth.se/%7ejjan/publications/pit_preprint_2017-08-09.pdf},
}
@article{KooijEtAl2017,
abstract = {{A parallel time integration method for nonlinear partial differential equations is proposed. It is based on a new implementation of the Paraexp method for linear partial differential equations (PDEs) employing a block Krylov subspace method. For nonlinear \{PDEs\} the algorithm is based on our Paraexp implementation within a waveform relaxation. The initial value problem is solved iteratively on a complete time interval. Nonlinear terms are treated as source terms, provided by the solution from the previous iteration. At each iteration, the problem is decoupled into independent subproblems by the principle of superposition. The decoupled subproblems are solved fast by exponential integration, based on a block Krylov method. The new time integration is demonstrated for the one-dimensional advection–diffusion equation and the viscous Burgers equation. Numerical experiments confirm excellent parallel scaling for the linear advection–diffusion problem, and good scaling in case the nonlinear Burgers equation is simulated.}},
author = {G.L. Kooij and M.A. Botchev and B.J. Geurts},
doi = {10.1016/j.cam.2016.09.036},
journal = {Journal of Computational and Applied Mathematics},
note = {Selected Papers from NUMDIFF-14},
pages = {229--246},
title = {A block Krylov subspace implementation of the time-parallel Paraexp method and its extension for nonlinear partial differential equations},
url = {http://dx.doi.org/10.1016/j.cam.2016.09.036},
volume = {316},
year = {2017},
}
@article{KreienbuehlEtAl2017,
abstract = {{This article demonstrates the applicability of the parallel-in-time method Parareal to the numerical solution of the Einstein gravity equations for the spherical collapse of a massless scalar field. To account for the shrinking of the spatial domain in time, a tailored load balancing scheme is proposed and compared to load balancing based on number of time steps alone. The performance of Parareal is studied for both the sub-critical and black hole case; our experiments show that Parareal generates substantial speedup and, in the super-critical regime, can reproduce Choptuik's black hole mass scaling law.}},
author = {Kreienbuehl, Andreas and Benedusi, Pietro and Ruprecht, Daniel and Krause, Rolf},
issue = {1},
journal = {Communications in Applied Mathematics and Computational Science},
pages = {109--128},
title = {Time-parallel gravitational collapse simulation},
url = {http://dx.doi.org/10.2140/camcos.2017.12.109},
doi = {10.2140/camcos.2017.12.109},
volume = {12},
year = {2017},
}
@unpublished{MasthayEtAl2017,
abstract = {{We present a full implementation of the parareal algorithm—an integration technique to solve differential equations in parallel— in the Julia programming language for a fully general, first-order, initial-value problem. Our implementation accepts both coarse and fine integrators as functional arguments. We use Euler’s method and another Runge-Kutta integration technique as the integrators in our experiments. We also present a simulation of the algorithm for purposes of pedagogy.}},
author = {Tyler M. Masthay and Saverio Perugini},
title = {Parareal Algorithm Implementation and Simulation in Julia},
howpublished = {arXiv:1706.08569v1 [cs.MS]},
url = {https://arxiv.org/pdf/1706.08569.pdf},
year = {2017},
}
@article{MerkelEtAl2017,
abstract = {Abstract Recently, ParaExp was proposed for the time integration of linear hyperbolic problems. It splits the time interval of interest into subintervals and computes the solution on each subinterval in parallel. The overall solution is decomposed into a particular solution defined on each subinterval with zero initial conditions and a homogeneous solution propagated by the matrix exponential applied to the initial conditions. The efficiency of the method depends on fast approximations of this matrix exponential based on recent results from numerical linear algebra. This paper deals with the application of ParaExp in combination with Leapfrog to electromagnetic wave problems in time domain. Numerical tests are carried out for a simple toy problem and a realistic spiral inductor model discretized by the Finite Integration Technique.},
author = {Merkel, Melina and Niyonzima, Innocent and Schöps, Sebastian},
title = {ParaExp Using Leapfrog as Integrator for High-Frequency Electromagnetic Simulations},
journal = {Radio Science},
volume = {52},
number = {12},
pages = {1558--1569},
doi = {10.1002/2017RS006357},
url = {https://dx.doi.org/10.1002/2017RS006357},
year = {2017}
}
@article{Pazner2017700,
abstract = {{Abstract In this paper, we develop new techniques for solving the large, coupled linear systems that arise from fully implicit Runge–Kutta methods. This method makes use of the iterative preconditioned \{GMRES\} algorithm for solving the linear systems, which has seen success for fluid flow problems and discontinuous Galerkin discretizations. By transforming the resulting linear system of equations, one can obtain a method which is much less computationally expensive than the untransformed formulation, and which compares competitively with other time-integration schemes, such as diagonally implicit Runge–Kutta (DIRK) methods. We develop and test several ILU-based preconditioners effective for these large systems. We additionally employ a parallel-in-time strategy to compute the Runge–Kutta stages simultaneously. Numerical experiments are performed on the Navier–Stokes equations using Euler vortex and 2D and 3D \{NACA\} airfoil test cases in serial and in parallel settings. The fully implicit Radau \{IIA\} Runge–Kutta methods compare favorably with equal-order \{DIRK\} methods in terms of accuracy, number of \{GMRES\} iterations, number of matrix–vector multiplications, and wall-clock time, for a wide range of time steps.}},
author = {Will Pazner and Per-Olof Persson},
doi = {10.1016/j.jcp.2017.01.050},
journal = {Journal of Computational Physics},
pages = {700--717},
title = {{Stage-parallel fully implicit Runge–Kutta solvers for discontinuous Galerkin fluid simulations}},
url = {https://doi.org/10.1016/j.jcp.2017.01.050},
volume = {335},
year = {2017},
}
@unpublished{PeddleEtAl2017,
abstract = {{A variant of the Parareal method for highly oscillatory systems of PDEs was proposed by [21]. In that work they proved superlinear convergence of the method in the limit of infinite time scale separation. Their coarse solver features a coordinate transformation and a fast-wave averaging method inspired by analysis of multiple scales PDEs and is integrated using an HMM-type method. However, for many physical applications the timescale separation is finite, not infinite. In this paper we prove convergence for finite timescale separaration by extending the error bound on the coarse propagator to this case. We show that convergence requires the solution of an optimization problem that involves the averaging window interval, the time step, and the parameters in the problem. We also propose a method for choosing the averaging window relative to the time step based as a function of the finite frequencies inherent in the problem.}},
author = {Adam Peddle and Terry Haut and Beth Wingate},
title = {Parareal Convergence for Oscillatory {PDE}s with Finite Time-scale Separation},
howpublished = {arXiv:1705.09565v1 [math.NA]},
url = {https://arxiv.org/pdf/1705.09565.pdf},
year = {2017},
}
@article{PerezEtAl2017,
abstract = {{Molecular dynamics (MD) is one of the most widely used techniques in computational materials science. By providing fully resolved trajectories, it allows for a natural description of static, thermodynamic, and kinetic properties. A major hurdle that has hampered the use of MD is the fact that the timescales that can be directly simulated are very limited, even when using massively parallel computers. In this study, we compare two time-parallelization approaches, parallel replica dynamics (ParRep) and parallel trajectory splicing (ParSplice), that were specifically designed to address this issue for rare event systems by leveraging parallel computing resources. Using simulations of the relaxation of small disordered platinum nanoparticles, a comparative performance analysis of the two methods is presented. The results show that ParSplice can significantly outperform ParRep in the common case where the trajectory remains trapped for a long time within a region of configuration space but makes rapid structural transitions within this region.}},
author={Perez, Danny and Huang, Rao and Voter, Arthur F.},
title={Long-time molecular dynamics simulations on massively parallel platforms: A comparison of parallel replica dynamics and parallel trajectory splicing},
doi={10.1557/jmr.2017.456},
journal={Journal of Materials Research},
url = {https://dx.doi.org/10.1557/jmr.2017.456},
year={2017},
pages={1-–10}
}
@Inbook{Ruprecht2017_lncs,
abstract={{For the parallel-in-time integration method Parareal, pipelining can be used to hide some of the cost of the serial correction step and improve its efficiency. The paper introduces a basic OpenMP implementation of pipelined Parareal and compares it to a standard MPI-based variant. Both versions yield almost identical runtimes, but, depending on the compiler, the OpenMP variant consumes about 7{\%} less energy and has a significantly smaller memory footprint. However, its higher implementation complexity might make it difficult to use in legacy codes and in combination with spatial parallelisation.}},
author={Ruprecht, Daniel},
booktitle={Euro-Par 2017: Parallel Processing: 23rd International Conference on Parallel and Distributed Computing, Santiago de Compostela, Spain, August 28 -- September 1, 2017, Proceedings},
doi={10.1007/978-3-319-64203-1_48},
editor={Rivera, Francisco F. and Pena, Tom{\'a}s F. and Cabaleiro, Jos{\'e} C.},
pages={669--681},
publisher={Springer International Publishing},
url={https://doi.org/10.1007/978-3-319-64203-1_48},
title={Shared Memory Pipelined Parareal},
year={2017},
}
@inproceedings{SchroderEtAl2017,
title={Parallel-in-Time Solution of Power Systems with Scheduled Events},
author={Schroder, Jacob B and Falgout, Robert D and Woodward, Carol S and Top, Philip and Lecouvez, Matthieu},
booktitle={2018 IEEE Power \& Energy Society General Meeting (PESGM)},
pages={1--5},
year={2018},
organization={IEEE}
}
@article{SpeckRuprecht2017,
abstract = {{Abstract We introduce and analyze different strategies for the parallel-in-time integration method PFASST to recover from hard faults and subsequent data loss. Since PFASST stores solutions at multiple time steps on different processors, information from adjacent steps can be used to recover after a processor has failed. PFASST’s multi-level hierarchy allows to use the coarse level for correcting the reconstructed solution, which can help to minimize overhead. A theoretical model is devised linking overhead to the number of additional PFASST iterations required for convergence after a fault. The potential efficiency of different strategies is assessed in terms of required additional iterations for examples of diffusive and advective type.}},
author = {Robert Speck and Daniel Ruprecht},
doi = {10.1016/j.parco.2016.12.001},
journal = {Parallel Computing},
pages = {20--37},
title = {Toward fault-tolerant parallel-in-time integration with {PFASST} },
url = "http://dx.doi.org/10.1016/j.parco.2016.12.001",
volume = {62},
year = {2017},
}
@inproceedings{WangPeng2017,
author = {S. Wang and Z. Peng},
booktitle = {2017 International Conference on Electromagnetics in Advanced Applications (ICEAA)},
title = {Space-time parallel computation for time-domain Maxwell's equations},
year = {2017},
volume = {},
number = {},
pages = {1680--1683},
abstract = {This work addresses a growing need for the parallel-in-time simulation capability in electromagnetics (EM) applications. Currently time-dependent EM solvers are typically parallel only in space. The sequential-in-time nature of these solvers can achieve good parallel scaling when the number of spatial mesh points per core is large. But the parallel efficiency quickly deteriorates and even saturates if spatial parallelism has been fully exploited. We proposed a new time domain EM solver to harvest parallelism in both spatial and temporal dimension. The spatial parallelism is achieved by discontinuous Galerkin formulation, and the temporal parallelism is enabled by Krylov subspace method based exponential integrator. This work results in a highly scalable parallel time domain solver which can amend the scalability issue for traditional ones. The convergence and parallel performance are validated through numerical experiments.},
doi = {10.1109/ICEAA.2017.8065615},
url = {http://ieeexplore.ieee.org/document/8065615/},
month={Sept},
}
@article {Wu2017,
author = {Wu, Shu-Lin},
url = {http://dx.doi.org/10.1002/mma.4273},
doi = {10.1002/mma.4273},
journal = {Mathematical Methods in the Applied Sciences},
url = {http://dx.doi.org/10.1002/mma.4273},
title = {Three rapidly convergent parareal solvers with application to time-dependent PDEs with fractional Laplacian},
year = {2017},
}
@article{Wu2017b,
author = {Shu-Lin Wu},
doi = {10.1016/j.amc.2017.02.012},
journal = {Applied Mathematics and Computation},
title = {An efficient parareal algorithm for a class of time-dependent problems with fractional Laplacian},
pages = {329--341},
url = {http://dx.doi.org/10.1016/j.amc.2017.02.012},
volume = {307},
year = {2017},
}
@article{WuEtAl2017,
author = {Shu-Lin Wu and Ting-Zhu Huang},
title = {A fast second-order parareal solver for fractional optimal control problems},
journal = {Journal of Vibration and Control},
volume = {0},
number = {0},
pages = {1077546317705557},
year = {2017},
doi = {10.1177/1077546317705557},
URL = {http://dx.doi.org/10.1177/1077546317705557},
}
%
% 2018
%
@article{BadiaEtAl2018,
abstract = {{Abstract In this work, we propose a parallel-in-time solver for linear and nonlinear ordinary differential equations. The approach is based on an efficient multilevel solver of the Schur complement related to a multilevel time partition. For linear problems, the scheme leads to a fast direct method. Next, two different strategies for solving nonlinear ODEs are proposed. First, we consider a Newton method over the global nonlinear ODE, using the multilevel Schur complement solver at every nonlinear iteration. Second, we state the global nonlinear problem in terms of the nonlinear Schur complement (at an arbitrary level), and perform nonlinear iterations over it. Numerical experiments show that the proposed schemes are weakly scalable, i.e., we can efficiently exploit increasing computational resources to solve for more time steps the same problem.}},
author = {Santiago Badia and Marc Olm},
title = {Nonlinear parallel-in-time Schur complement solvers for ordinary differential equations},
journal = {Journal of Computational and Applied Mathematics},
volume = {344},
pages = {794--806},
year = {2018},
url = {https://doi.org/10.1016/j.cam.2017.09.033},
doi = {10.1016/j.cam.2017.09.033}
}
@inproceedings{BenedusiEtAl2016,
abstract = {{We present a parallel and efficient multilevel solution method for the nonlinear systems arising from the discretization of Navier–Stokes (N-S) equations with finite differences. In particular we study the incompressible, unsteady N-S equations with periodic boundary condition in time. A sequential time integration limits the parallelism of the solver to the spatial variables and can therefore be an obstacle to parallel scalability. Time periodicity allows for a space-time discretization, which adds time as an additional direction for parallelism and thus can improve parallel scalability. To achieve fast convergence, we used a space-time multigrid algorithm with a SCGS smoothing procedure (symmetrical coupled Gauss–Seidel, a.k.a. box smoothing). This technique, proposed by Vanka (J Comput Phys 65:138–156, 1986), for the steady viscous incompressible Navier–Stokes equations is extended to the unsteady case and its properties are studied using local Fourier analysis. We used numerical experiments to analyze the scalability and the convergence of the solver, focusing on the case of a pulsatile flow.}},
title={{A Parallel Multigrid Solver for Time--periodic Incompressible Navier--Stokes Equations in 3D}},
author={Benedusi, P. and Hupp, D. and Arbenz, P. and Krause, R.},
booktitle={Numerical Mathematics and Advanced Applications ENUMATH 2015},
pages={265--273},
year={2016},
organization={Springer},
doi = {10.1007/978-3-319-39929-4_26},
url = {https://doi.org/10.1007/978-3-319-39929-4_26}
}
@article{BlumersEtAl2019,
abstract = {{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.}},
title = {Supervised parallel-in-time algorithm for long-time Lagrangian simulations of stochastic dynamics: Application to hydrodynamics},
journal = {Journal of Computational Physics},
volume = {393},
pages = {214 - 228},
year = {2019},
url = {https://doi.org/10.1016/j.jcp.2019.05.016},
doi = {10.1016/j.jcp.2019.05.016},
author = {Ansel L. Blumers and Zhen Li and George Em Karniadakis},
}
@article{BoltenEtAl2018,
abstract = {For time-dependent partial differential equations, parallel-in-time integration using the “parallel full approximation scheme in space and time” (PFASST) is a promising way to accelerate existing space-parallel approaches beyond their scaling limits. Inspired by the classical Parareal method and multigrid ideas, PFASST allows to integrate multiple time steps simultaneously using a space–time hierarchy of spectral deferred correction sweeps. While many use cases and benchmarks exist, a solid and reliable mathematical foundation is still missing. Very recently, however, PFASST for linear problems has been identified as a multigrid method. In this paper, we will use this multigrid formulation and, in particular, PFASST's iteration matrix to show that, in the nonstiff and stiff limit, PFASST indeed is a convergent iterative method. We will provide upper bounds for the spectral radius of the iteration matrix and investigate how PFASST performs for increasing numbers of parallel time steps. Finally, we will demonstrate that the results obtained here indeed relate to actual PFASST runs.},
author = {Bolten, Matthias and Moser, Dieter and Speck, Robert},
title = {Asymptotic convergence of the parallel full approximation scheme in space and time for linear problems},
journal = {Numerical Linear Algebra with Applications},
volume = {25},
number = {6},
pages = {e2208},
doi = {10.1002/nla.2208},
url = {https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.2208},
year = {2018}
}
@article{BorregalesEtAl2018,
abstract = {{In this work, we study the parallel-in-time iterative solution of coupled flow and geomechanics in porous media, modelled by a two-field formulation of Biot’s equations. In particular, we propose a new version of the fixed-stress splitting method, which has been widely used as solution method of these problems. This new approach forgets about the sequential nature of the temporal variable and considers the time direction as a further direction for parallelization. The method is partially parallel-in-time. We present a rigorous convergence analysis of the method and numerical experiments to demonstrate the robust behaviour of the algorithm.}},
author = {{Manuel Borregales and Kundan Kumar and Florin Adrian Radu and Carmen Rodrigo and Francisco Jos{\'e} Gaspar}},
title = {{A partially parallel-in-time fixed-stress splitting method for Biot’s consolidation model}},
journal = {Computers \& Mathematics with Applications},
year = {2018},
doi = {10.1016/j.camwa.2018.09.005},
url = {https://doi.org/10.1016/j.camwa.2018.09.005},
}
@article{Bu2018,
abstract = {{In this paper, we introduce a practical strategy to select an adaptive time step size suitable for the parareal algorithm designed to parallelize a numerical scheme for solving stiff initial value problems. For the adaptive time step size, a technique to detect stiffness of a given system is first considered since the step size will be chosen according to the extent of stiffness. Finally, the stiffness detection technique is applied to an initial prediction step of the parareal algorithm, and select an adaptive step size to each time interval according to the stiffness. Several numerical experiments demonstrate the efficiency of the proposed method.}},
author = {Sunyoung Bu},
doi = {10.1515/math-2018-0022},
journal = {Open Mathematics},
issue = {1},
pages = {210--218},
title = {Time parallelization scheme with an adaptive time step size for solving stiff initial value problems},
url = {https://doi.org/10.1515/math-2018-0022},
volume = {16},
year = {2018},
}
@unpublished{DamoreEtAl2018,
abstract = {{We present the mathematical framework of a Domain Decomposition (DD) aproach based on Parallel-in-Time methods (PinT-based approach) for solving the 4D-Var Data Assimilation (DA) model. The main outcome of the proposed DD PinT-based approach is: 1. DA acts as coarse/predictor for the local PDE-based forecasting model, increasing the accuracy of the local solution. 2. The fine and coarse solvers can be used in parallel, increasing the efficiency of the algorithm.3. Data locality is preserved and data movement is reduced, increasing the software scalability. We provide the mathematical framework including convergence analysis and error propagation.}},
author = {D'Amore, Luisa and Cacciapuoti, Rosalba},
title = {DD-DA PinT-based model: A Domain Decomposition approach in space and time, based on Parareal, for solving the 4D-Var Data Assimilation model},
howpublished = {arXiv:1807.07107 [math.NA]},
url = {https://arxiv.org/abs/1807.07107},
year = {2018},
}
@inproceedings{DuanEtAl2018,
abstract={The performance of parareal-in-time algorithms is determined on the number of sequential, coarse step iterations. A common tradeoff in designing an efficient parareal-in-time algorithm is between accuracy of the coarse solver and the number of iterations. Traditional parareal implementation for the power system simulation can also have difficulties handling complex power systems. In this paper, we propose a Krylov subspace enhanced parareal algorithm to reduce the number of coarse iterations. The proposed approach is demonstrated on a single-machine-infinite-bus system and the IEEE 10-machine 39-bus system. Noticeable decrease of number of iterations is observed in both cases.},
author={N. {Duan} and S. {Simunovic} and A. {Dimitrovski} and K. {Sun}},
booktitle={2018 IEEE Power Energy Society General Meeting (PESGM)},
title={Improving the Convergence Rate of Parareal-in-time Power System Simulation using the {K}rylov Subspace},
year={2018},
pages={1--5},
doi={10.1109/PESGM.2018.8586354},
url = {https://dx.doi.org/10.1109/PESGM.2018.8586354}
}
@article{DyjaEtal2018,
abstract = {{We present an adaptive methodology for the solution of (linear and) nonlinear time dependent problems that is especially tailored for massively parallel computations. The basic concept is to solve for large blocks of space-time unknowns instead of marching sequentially in time. The methodology is a combination of a computationally efficient implementation of a parallel-in-space-time finite element solver coupled with a posteriori space-time error estimates and a parallel mesh generator. While we focus on spatial adaptivity in this work, the methodology enables simultaneous adaptivity in both space and time domains. We explore this basic concept in the context of a variety of time steppers including $\Theta$-schemes and backward difference formulas. We specifically illustrate this framework with applications involving time dependent linear, quasi-linear, and semilinear diffusion equations. We focus on investigating how the coupled space-time refinement indicators for this class of problems affect spatial adaptivity. Finally, we show good scaling behavior up to 150,000 processors on the NCSA Blue Waters machine. This conceptually simple methodology enables scaling on next generation multicore machines by simultaneously solving for a large number of timesteps, and reducing computational overhead by locally refining spatial blocks that can track localized features. This methodology also opens up the possibility of efficiently incorporating adjoint equations for error estimators and inverse design problems, since blocks of space-time are simultaneously solved and stored in memory.}},
author = {Robert Dyja and Baskar Ganapathysubramanian and Kristoffer G. van der Zee},
doi = {10.1137/16M108985X},
journal = {SIAM Journal on Scientific Computing},
number = {3},
pages = {C283--C304},
title = {Parallel-In-Space-Time, Adaptive Finite Element Framework for Nonlinear Parabolic Equations},
url = {https://doi.org/10.1137/16M108985X},
volume = {40},
year = {2018},
}
@unpublished{FalgoutEtAl2018,
abstract = {{The advent of exascale computing resources will leave many users with access to more computational resources than they can simultaneously use, i.e., billions of cores. This is especially true for time-dependent simulations that limit parallelism to the spatial domain. Multigrid Reduction in Time (MGRIT), a non-intrusive parallel-in-time solver, adds parallelism across the time steps to existing time dependent codes, allowing users to utilize a larger portion of the available computational resources and achieve a faster time to solution. In this paper, MGRIT is enhanced with Richardson extrapolation in a cost efficient way to produce a non-intrusive parallel-in-time method with improved accuracy. Overall, this leads to a large improvement in the accuracy per computational cost of the MGRIT algorithm.}},
author = {R.~D. Falgout and T.~A. Manteuffel and B. O'Neill and J.~B. Schroder},
title = {Multigrid Reduction in Time with Richardson Extrapolation},
url = {http://www.math.unm.edu/~schroder/docs/FaMaOnSc2018.pdf},
year = {2018},
}
@article{FischerEtAl2018,
abstract = {{Parallel in time methods for solving initial value problems are a means
to increase the parallelism of numerical simulations. Hybrid parareal
schemes interleaving the parallel in time iteration with an iterative solution
of the individual time steps are among the most efficient methods
for general nonlinear problems. Despite the hiding of communication time
behind computation, communication has in certain situations a significant
impact on the total runtime. Here we present strict, yet no sharp, error
bounds for hybrid parareal methods with inexact communication due to
lossy data compression, and derive theoretical estimates of the impact
of compression on parallel efficiency of the algorithms. These and some
computational experiments suggest that compression is a viable method
to make hybrid parareal schemes robust with respect to low bandwidth
setups.}},
author = {Fischer, L. and G\"otschel, S. and Weiser, M.},
journal = {Computing and Visualization in Science},
title = {Lossy data compression reduces communication time in hybrid time-parallel integrators},
doi = {10.1007/s00791-018-0293-2},
url = {https://doi.org/10.1007/s00791-018-0293-2},
volume = {19},
number = {1},
pages = {19--30},
year = {2018}
}
@article{FrancoEtAl2018,
abstract = {{In this work, a space-time multigrid method which uses standard coarsening in both temporal and spatial domains and combines the use of different smoothers is proposed for the solution of the heat equation in one and two space dimensions. In particular, an adaptive smoothing strategy, based on the degree of anisotropy of the discrete operator on each grid-level, is the basis of the proposed multigrid algorithm. Local Fourier analysis is used for the selection of the crucial parameter defining such an adaptive smoothing approach. Central differences are used to discretize the spatial derivatives and both implicit Euler and Crank–Nicolson schemes are considered for approximating the time derivative. For the solution of the second-order scheme, we apply a double discretization approach within the space-time multigrid method. The good performance of the method is illustrated through several numerical experiments.}},
author = {Sebasti\~{a}o Romero Franco and Francisco Jos\'{e} Gaspar and Marcio Augusto Villela Pinto and Carmen Rodrigo},
doi = {10.1016/j.amc.2017.08.043},
journal = {Applied Mathematics and Computation},
number = {Supplement C},
pages = {25--34},
title = {Multigrid method based on a space-time approach with standard coarsening for parabolic problems},
url = {https://doi.org/10.1016/j.amc.2017.08.043},
volume = {317},
year = {2018},
}
@article{FrancoEtAl2018a,
abstract = {{In this work, a multigrid waveform relaxation method is proposed for solving a collocated finite difference discretization of the linear Biot’s model. This gives rise to the first space–time multigrid solver for poroelasticity equations in the literature. The waveform relaxation iteration is based on a point-wise Vanka smoother that couples the pressure variable at a grid-point with the displacements around it. A semi-algebraic mode analysis is proposed to theoretically analyze the convergence of the multigrid waveform relaxation algorithm. This analysis is novel since it combines the semi-algebraic analysis, suitable for parabolic problems, with the non-standard analysis for overlapping smoothers. The practical utility of the method is illustrated through several numerical experiments in one and two dimensions.}},
author = {Sebasti\~{a}o Romero Franco and Carmen Rodrigo and Francisco Jos\'{e} Gaspar and Marcio Augusto Villela Pinto},
doi = {10.1007/s40314-018-0603-9},
journal = {Computational and Applied Mathematics},
pages = {1--16},
title = {A multigrid waveform relaxation method for solving the poroelasticity equations},
url = {https://doi.org/10.1007/s40314-018-0603-9},
year = {2018},
}
@unpublished{FriedhoffEtAl2018b,
abstract = {{We consider the usage of parallel-in-time algorithms of the Parareal and multigrid-reduction-in-time (MGRIT) methodologies for the parallel-in-time solution of the eddy current problem. Via application of these methods to a two-dimensional model problem for a coaxial cable model, we show that a significant speedup can be achieved in comparison to sequential time stepping.}},
author = {Friedhoff, Stephanie and Hahne, Jens and Kulchytska-Ruchka, Iryna and Schöps, Sebastian},
title = {Exploring Parallel-in-Time Approaches for Eddy Current Problems},
howpublished = {arXiv:1810.13263 [math.NA]},
url = {https://arxiv.org/abs/1810.13263},
year = {2018},
}
@article{FuWang2018,
abstract = {We develop a fast parareal finite difference method for space-time fractional partial differential equation. The method properly handles the heavy tail behavior in the numerical discretization, while retaining the numerical advantages of conventional parareal algorithm. At each time step, we explore the structure of the stiffness matrix to develop a matrix-free preconditioned fast Krylov subspace iterative solver for the finite difference method without resorting to any lossy compression. Consequently, the method has significantly reduced computational complexity and memory requirement. Numerical experiments show the strong potential of the method.},
author = {Fu, Hongfei and Wang, Hong},
title = {A Preconditioned Fast Parareal Finite Difference Method for Space-Time Fractional Partial Differential Equation},
journal = {Journal of Scientific Computing},
year = {2018},
doi = {10.1007/s10915-018-0835-2},
url = {https://doi.org/10.1007/s10915-018-0835-2},
}
@unpublished{GanderEtAl2018b,
abstract = {{The Parareal algorithm, which is related to multiple shooting, was introduced for solving evolution problems in a time-parallel manner. The algorithm was then extended to solve time-periodic problems. We are interested here in time-periodic systems which are forced with quickly-switching discontinuous inputs. Such situations occur, e.g., in power engineering when electric devices are excited with a pulse-width-modulated signal. In order to solve those problems numerically we consider a recently introduced modified Parareal method with reduced coarse dynamics. Its main idea is to use a low-frequency smooth input for the coarse problem, which can be obtained, e.g., from Fourier analysis. Based on this approach, we present and analyze a new Parareal algorithm for time-periodic problems with highly-oscillatory discontinuous sources. We illustrate the performance of the method via its application to the simulation of an induction machine.}},
author = {Gander, Martin J. and Kulchytska-Ruchka, Iryna and Schöps, Sebastian},
title = {A New Parareal Algorithm for Time-Periodic Problems with Discontinuous Inputs},
howpublished = {arXiv:1810.12372 [math.NA]},
url = {https://arxiv.org/abs/1810.12372},
year = {2018},
}
@article{GanderEtAl2018_cvs,
abstract = {{The parareal algorithm is by construction a two level method, and there are several ways to interpret the parareal algorithm to obtain multilevel versions. We first review the three main interpretations of the parareal algorithm as a two-level method, a direct one, one based on geometric multigrid and one based on algebraic multigrid. The algebraic multigrid interpretation leads to the MGRIT algorithm, when using instead of only an F-smoother, a so called FCF -smoother. We show that this can be interpreted at the level of the parareal algorithm as generous overlap in time. This allows us to generalize the method to even larger overlap, corresponding in MGRIT to F(CF)ν -smoothing, ν >=1 , and we prove two new convergence results for such algorithms in the fully non-linear setting: convergence in a finite number of steps, becoming smaller when ν increases, and a general superlinear convergence estimate for this generalized version of MGRIT. We illustrate our results with numerical experiments, both for linear and non-linear systems of ordinary and partial differential equations. Our results show that overlap only sometimes leads to faster algorithms.}},
author = {Gander, Martin J. and Kwok, Felix and Zhang, Hui},
title = {Multigrid interpretations of the parareal algorithm leading to an overlapping variant and MGRIT},
journal = {Computing and Visualization in Science},
doi = {10.1007/s00791-018-0297-y},
url = {https://doi.org/10.1007/s00791-018-0297-y},
year = {2018},
}
@article{GoddenWathen2018,
abstract = {{McDonald, Pestana, and Wathen [SIAM J. Sci. Comput., 40 (2018), pp. A1012–A1033] present a method for preconditioning time-dependent PDEs via an approximation by a nearby time-periodic problem, that is, they employ circulant-related matrices as preconditioners for the non-symmetric block Toeplitz matrices which arise from an all-at-once formulation. They suggest that such an approach might be efficiently implemented in parallel. In this short article, we present parallel numerical results for their preconditioner which exhibit strong scaling. We also extend their preconditioner via a Neumann series approach which also allows for efficient parallel execution. Results are shown for both parabolic and hyperbolic PDEs. Our simple implementation (in C++ and MPI) is available at the Git repository PARALAAOMPI.}},
publisher = {Verlag der Österreichischen Akademie der Wissenschaften},
pages = {135-150},
title = {A note on parallel preconditioning for all-at-once evolutionary PDEs},
author = {Anthony Goddard and Andy Wathen},
editor = {Ronny Ramlau, Lothar Reichel (Hg.)},
url = {https://dx.doi.org/10.1553/etna_vol51s135},
doi = {10.1553/etna_vol51s135},
address = {Wien},
}
@inproceedings{GoetschelMinion2018,
abstract = {{In gradient-based methods for parabolic optimal control problems, it is necessary to solve both the state equation and a backward-in-time adjoint equation in each iteration of the optimization method. In order to facilitate fully parallel gradient-type and nonlinear conjugate gradient methods for the solution of such optimal control problems, we discuss the application of the parallel-in-time method PFASST to adjoint gradient computation. In addition to enabling time parallelism, PFASST provides high flexibility for handling nonlinear equations, as well as potential extra computational savings from reusing previous solutions in the optimization loop. The approach is demonstrated here for a model reaction-diffusion optimal control problem.}},
author = {G\"otschel, Sebastian and Minion, Michael L.},
editor = {Petter E. Bj{\o}rstad and Susanne C. Brenner and Lawrence Halpern and Hyea Hyun Kim and Ralf Kornhuber and Talal Rahman and Olof B. Widlund},
title = {Parallel-in-Time for Parabolic Optimal Control Problems Using {PFASST}},
booktitle = {Domain Decomposition Methods in Science and Engineering {XXIV}},
year = {2018},
publisher = {Springer International Publishing},
pages = {363--371},
doi = {10.1007/978-3-319-93873-8_34},
url = {https://doi.org/10.1007/978-3-319-93873-8_34}
}
@article{GuentherEtAl2018,
abstract = {{In this paper, an adjoint solver for the multigrid in time software library XBraid is presented. XBraid provides a non-intrusive approach for simulating unsteady dynamics on multiple processors while parallelizing not only in space but also in the time domain. It applies an iterative multigrid reduction in time algorithm to existing spatially parallel classical time propagators and computes the unsteady solution parallel in time. Techniques from Automatic Differentiation are used to develop a consistent discrete adjoint solver which provides sensitivity information of output quantities with respect to design parameter changes. The adjoint code runs backwards through the primal XBraid actions and accumulates gradient information parallel in time. It is highly non-intrusive as existing adjoint time propagators can easily be integrated through the adjoint interface. The adjoint code is validated on advection-dominated flow with periodic upstream boundary condition. It provides similar strong scaling results as the primal XBraid solver and offers great potential for speeding up the overall computational costs for sensitivity analysis using multiple processors}},
author = {G\"unther, S. and Gauger, N. R. and Schroder, J. B.},
doi = {10.1007/s00791-018-0300-7},
journal = {Computing and Visualization in Science},
title = {A Non-Intrusive Parallel-in-Time Adjoint Solver with the {XBraid} Library},
url = {https://doi.org/10.1007/s00791-018-0300-7},
year = {2018}
}
@article{HessenthalerEtAl2018,
abstract = {{This paper presents some recent advances for parallel‐in‐time methods applied to linear elasticity. With recent computer architecture changes leading to stagnant clock speeds, but ever increasing numbers of cores, future speedups will be available through increased concurrency. Thus, sequential algorithms, such as time stepping, will suffer a bottleneck. This paper explores multigrid reduction in time (MGRIT) for an important application area, linear elasticity. Previously, efforts at parallel‐in‐time for elasticity have experienced difficulties, for example, the beating phenomenon. As a result, practical parallel‐in‐time algorithms for this application area currently do not exist. This paper proposes some solutions made possible by MGRIT (e.g., slow temporal coarsening and FCF‐relaxation) and, more importantly, a different formulation of the problem that is more amenable to parallel‐in‐time methods. Using a recently developed convergence theory for MGRIT and Parareal, we show that the changed formulation of the problem avoids the instability issues and allows the reduction of the error using two temporal grids. We then extend our approach to the multilevel case, where we demonstrate how slow temporal coarsening improves convergence. The paper ends with supporting numerical results showing a practical algorithm enjoying speedup benefits over the sequential algorithm.}},
author = {Hessenthaler, A. and Nordsletten, D. and Röhrle, O. and Schroder, J. B. and Falgout, R. D.},
doi = {10.1002/nla.2155},
journal = {Numerical Linear Algebra with Applications},
number = {3},
pages = {e2155},
url = {https://dx.doi.org/10.1002/nla.2155},
title = {Convergence of the multigrid reduction in time algorithm for the linear elasticity equations},
volume = {25},
year = {2018},
}
@unpublished{HessenthalerEtAl2018b,
abstract = {{This paper presents a multilevel convergence framework for multigrid-reduction-in-time (MGRIT) as a generalization of previous two-grid estimates. The framework provides a priori upper bounds on the convergence of MGRIT V- and F-cycles with different relaxation schemes by deriving the respective residual and error propagation operators. The residual and error operators are functions of the time stepping operator, analyzed directly and bounded in norm, both numerically and analytically. We present various upper bounds of different computational cost and varying sharpness. These upper bounds are complemented by proposing analytic formulae for the approximate convergence factor of V-cycle algorithms that take the number of fine grid time points, the temporal coarsening factors, and the eigenvalues of the time stepping operator as parameters. The paper concludes with supporting numerical investigations of parabolic and hyperbolic model problems. We assess the sharpness of the bounds and the quality of the approximate convergence factors. Observations from these numerical investigations demonstrate the value of the proposed multilevel convergence framework for the design of a convergent MGRIT algorithm. We further highlight that observations in the literature are captured by the theory, including that two-level Parareal and multilevel MGRIT with F-relaxation do not yield scalable algorithms, that iteration counts increase with increasing numbers of levels, and the benefit of a stronger relaxation scheme. The theory also proves in a two-level setting, and confirms for multilevel, that L-stable Runge-Kutta schemes are more amendable to parallel-in-time integration with MGRIT than A-stable Runge-Kutta schemes.}},
author = {Andreas Hessenthaler and Ben S. Southworth and David Nordsletten and Oliver Röhrle and Robert D. Falgout and Jacob B. Schroder},
title = {Multilevel convergence analysis of multigrid-reduction-in-time},
howpublished = {arXiv:1812.11508 [math.NA]},
url = {https://arxiv.org/abs/1812.11508},
year = {2018},
}
@unpublished{HongEtAl2018,
abstract = {{A parareal algorithm based on an exponential θ-scheme is proposed for the stochastic Schr\"odinger equation with weak damping and additive noise. It proceeds as a two-level temporal parallelizable integrator with the exponential θ-scheme as the propagator on the coarse grid. The proposed algorithm in the linear case increases the convergence order from one to k for θ∈[0,1]∖{12}. In particular, the convergence order increases to 2k when θ=12 due to the symmetry of the algorithm. Furthermore, the algorithm is proved to be suitable for longtime simulation based on the analysis of the invariant distributions for the exponential θ-scheme. The convergence condition for longtime simulation is also established for the proposed algorithm in the nonlinear case, which indicates the superiority of implicit schemes. Numerical experiments are dedicated to illustrate the best choice of the iteration number k, as well as the convergence order of the algorithm for different choices of θ.}},
author = {Jialin Hong and Xu Wang and Liying Zhang},
title = {Parareal exponential $\theta$-scheme for longtime simulation of stochastic Schrödinger equations with weak damping},
howpublished = {arXiv:1803.09188 [math.NA]},
url = {https://arxiv.org/abs/1803.09188v1},
year = {2018},
}
@inbook{HwangMunster2018,
abstract = {{A gradient-based approach to multidisciplinary design optimization enables efficient scalability to large numbers of design variables. However, the need for derivatives imposes a difficult requirement when integrating ordinary differential equations in models. To simplify this, we propose the use of the general linear methods framework, which unifies all Runge–Kutta and linear multistep methods. This approach enables rapid implementation of integration methods without the need to differentiate each individual method, even in a gradient-based optimization context. We also develop a new parallel time integration algorithm that enables vectorization across time steps. We present a set of benchmarking results using a stiff ODE, a non-stiff nonlinear ODE, and an orbital dynamics ODE, and compare integration methods. In a modular gradient-based multidisciplinary design optimization context, we find that the new parallel time integration algorithm with high-order implicit methods, especially Gauss–Legendre collocation, is the best choice for a broad range of problems.}},
author = {Hwang, John T. and Munster, Drayton},
booktitle = {2018 AIAA/ASCE/AHS/ASC Structures, Structural Dynamics, and Materials Conference},
doi = {doi:10.2514/6.2018-1646},
publisher = {American Institute of Aeronautics and Astronautics},
title = {Solution of ordinary differential equations in gradient-based multidisciplinary design optimization},
url = {https://doi.org/10.2514/6.2018-1646},
year = {2018},
}
@Article{IizukaEtAl2018,
abstract = {{Gander and Petcu (ESAIM Proc 25:114–129, 2008) reported that, theoretically, the convergence of the parareal method iteration for hyperbolic PDEs is strongly influenced by the phase (frequency) accuracy of the coarse solver calculation. However, no numerical study has clearly shown this. Therefore, through numerical tests, we investigate the influence of the phase accuracy of the coarse solver calculation on the convergence of the parareal method iteration for hyperbolic PDEs. First, we consider a simple harmonic motion and a multi-DOF mass-spring system (MDMSS) as examples of hyperbolic PDEs using the modified Newmark- β method (Mizuta et al. in J JSCE 268:15–21, 1977), which can provide the exact phase of the time integration of a simple harmonic motion. Based on the results of the numerical tests, we show that the convergence of the parareal method iteration for hyperbolic PDEs is approximately independent of the parameters of parallel-in-time integration (PinT) and instead is dependent primarily on the phase accuracy of the coarse solver calculation. In addition, we show that reducing the number of bases in the reduced basis method (RBM) (Chen et al., in: Rozza (ed) Reduced order methods for modeling and computational reduction, MS and a modeling, simulation and applications, vol 9, Springer, Berlin, pp 187–214, 2014) causes the saturation of a decrease in an error during the parareal iteration for the MDMSS using the mode analysis method. The RBM is expected to make available accurate phase calculation in the coarse solver by maintaining the time step width as same as that of the fine solver. Second, we investigate whether the same saturation appears for the linear advection–diffusion equation when we use the RBM. We use the time evolution basis method in the RBM for the linear advection–diffusion equation. As a result, we show that reducing the number of bases causes the saturation of the decrease in the error in the linear advection–diffusion equation. Based on the results of the present study, an increase in the phase accuracy of the coarse solver calculation is strongly required for better convergence of the parareal method iteration for hyperbolic PDEs. Moreover, the saturation of the decrease in the error during the parareal method iteration should be overcome when using the RBM.}},
author = {Iizuka, Mikio and Ono, Kenji},
title = {Influence of the phase accuracy of the coarse solver calculation on the convergence of the parareal method iteration for hyperbolic PDEs},
journal = {Computing and Visualization in Science},
year = {2018},
doi = {10.1007/s00791-018-0299-9},
url = {https://doi.org/10.1007/s00791-018-0299-9},
}
@article{KooijEtAl2018,
abstract ={{We present an exponential time integration method for the incompressible Navier--Stokes equation. An essential step in our procedure is the treatment of the pressure by applying a divergence-free projection to the momentum equation. The differential-algebraic equation for the discrete velocity and pressure is then reduced to a conventional ordinary differential equation that can be solved with the proposed exponential integrator. A promising feature of exponential time integration is its potential time parallelism within the Paraexp algorithm. We demonstrate that our approach leads to parallel speedup assuming negligible parallel communication.}},
author = {Gijs L. Kooij and Mike A. Botchev and Bernard J. Geurts},
title = {An Exponential Time Integrator for the Incompressible Navier--Stokes Equation},
journal = {SIAM Journal on Scientific Computing},
volume = {40},
number = {3},
pages = {B684--B705},
year = {2018},
doi = {10.1137/17M1121950},
URL = {https://doi.org/10.1137/17M1121950},
}
@article{LedermanBilyeu2018,
abstract = {{A temporal multiscale hybridization method is presented that carefully couples coarse scale gyrokinetic models with exact charged particle solution trajectories (that is, with full phase information) in a magnetic field. The approach is based on the careful approximation of a sum, generally employed for time-parallel (TP) computing applications. While the hybridization method presented is highly parallelizable, a computational efficiency gain is seen from considering serial computations only. A complete numerical method is only presented for the aforementioned charged particle application, however, the general approach depicted likely has relevance to a wide swath of challenging multiscale/multiphysics problems. Additionally, the approach has obvious relevance to TP computing applications (such as variable selection on which to perform TP calculations and fine scale sampling strategies).}},
author = {Carl Lederman and David Bilyeu},
doi = {10.4236/jamp.2018.63046 },
journal = {Journal of Applied Mathematics and Physics},
pages = {498--519},
title = {An Approximate Time-Parallel Method for the Fast and Accurate Computation of Particle Trajectories in a Magnetic Field},
url = {https://doi.org/10.4236/jamp.2018.63046},
volume = {6},
year = {2018},
}
@article{LiangLin2018,
abstract = {{Cloth simulations, widely used in computer animation and apparel design, can be computationally expensive for real-time applications. Some parallelization techniques have been proposed for visual simulation of cloth using CPU or GPU clusters and often rely on parallelization using spatial domain decomposition techniques that have a large communication overhead. In this paper, we propose a novel time-domain parallelization technique that makes use of the two-level mesh representation to resolve the time-dependency issue and develop a practical algorithm to smooth the state transition from the corresponding coarse to fine meshes. A load estimation and a load balancing technique used in online partitioning are also proposed to maximize the performance acceleration. Our method achieves a nearly linear performance scaling on manycore clusters and outperforms spatial-domain parallelization on a diverse set of benchmarks.}},
author = {Liang, Junbang and Lin, Ming C.},
title = {Time-Domain Parallelization for Accelerating Cloth Simulation},
journal = {Computer Graphics Forum},
volume = {37},
number = {8},
pages = {21--34},
doi = {10.1111/cgf.13509},
url = {https://dx.doi.org/10.1111/cgf.13509},
year = {2018}
}
@Article{LunetEtAl2018,
abstract = {Direct Numerical Simulation of turbulent flows is a computationally demanding problem that requires efficient parallel algorithms. We investigate the applicability of the time-parallel Parareal algorithm to an instructional case study related to the simulation of the decay of homogeneous isotropic turbulence in three dimensions. We combine a Parareal variant based on explicit time integrators and spatial coarsening with the space-parallel Hybrid Navier--Stokes solver. We analyse the performance of this space--time parallel solver with respect to speedup and quality of the solution. The results are compared with reference data obtained with a classical explicit integration, using an error analysis which relies on the energetic content of the solution. We show that a single Parareal iteration is able to reproduce with high fidelity the main statistical quantities characterizing the turbulent flow field.},
author = {Lunet, Thibaut and Bodart, Julien and Gratton, Serge and Vasseur, Xavier},
title = {Time-parallel simulation of the decay of homogeneous turbulence using Parareal with spatial coarsening},
journal = {Computing and Visualization in Science},
doi = {10.1007/s00791-018-0295-0},
url = {https://doi.org/10.1007/s00791-018-0295-0},
volume = {19},
number = {1},
pages = {31--44},
year = {2018},
}
@unpublished{MadayMula2018,
abstract = {{In this paper, we consider the problem of accelerating the numerical simulation of time dependent problems by time domain decomposition. The available algorithms enabling such decompositions present severe efficiency limitations and are an obstacle for the solution of large scale and high dimensional problems. Our main contribution is the significant improvement of the parallel efficiency of the parareal in time method, an iterative predictor-corrector algorithm. This is achieved by first reformulating the algorithm in a rigorous infinite dimensional functional space setting. We then formulate implementable versions where time dependent subproblems are solved at increasing accuracy across the parareal iterations (in opposition to the classical version where the subproblems are solved at a fixed high accuracy). Aside from the important improvement in parallel efficiency and as a natural by product, the new approach provides a rigourous online stopping criterion with a posteriori error estimators and the numerical cost to achieve a certain final accuracy is designed to be near-minimal. We illustrate the gain in efficiency of the new approach on simple numerical experiments. In addition to this, we discuss the potential benefits of reusing information from previous parareal iterations to enhance efficiency even more.}},
author = {Yvon Maday and Olga Mula},
title = {A Scalable Adaptive Parareal Algorithm With Online Stopping Criterion},
howpublished = {hal-01781257, version 1},
url = {https://hal.archives-ouvertes.fr/hal-01781257/},
year = {2018},
}
@Article{MagoulesEtAl2018,
abstract = {{Spatial domain decomposition methods have been largely investigated in the last decades, while time domain decomposition seems to be contrary to intuition and so is not as popular as the former. However, many attractive methods have been proposed, especially the parareal algorithm, which showed both theoretical and experimental efficiency in the context of parallel computing. In this paper, we present an original model of asynchronous variant based on the parareal scheme, applied to the European option pricing problem. Some numerical experiments are given to illustrate the convergence performance and computational efficiency of such a method.}},
author = {Magoul{\`e}s, Fr{\'e}d{\'e}ric and Gbikpi-Benissan, Guillaume and Zou, Qinmeng},
title = {Asynchronous Iterations of Parareal Algorithm for Option Pricing Models},
journal = {Mathematics},
volume = {6},
year = {2018},
number = {4},
url = {https://doi.org/10.3390/math6040045},
doi = {10.3390/math6040045}
}
@inbook{Morton2018,
author = {Morton, Scott A. },
booktitle = {2018 AIAA Aerospace Sciences Meeting},
doi = {doi:10.2514/6.2018-1046},
title = {An Implicit BDF2 Time-Parallel Algorithm for Solving Convection Diffusion Equations},
url = {https://doi.org/10.2514/6.2018-1046},
year = {2018},
}
@article{MaRuSo2018,
author = {Manteuffel, T. and Ruge, J. and Southworth, B.},
title = {Nonsymmetric Algebraic Multigrid Based on Local Approximate Ideal Restriction},
journal = {SIAM Journal on Scientific Computing},
volume = {40},
number = {6},
pages = {A4105--A4130},
year = {2018},
}
@article{MeleEtAl2018,
abstract = {{We address the development of a modular implementation of the MGRIT (MultiGrid-In-Time) algorithm to solve linear and nonlinear systems that arise from the discretization of evolutionary models with a parallel-in-time approach in the context of the PETSc (the Portable, Extensible Toolkit for Scientific computing) library. Our aim is to give the opportunity of predicting the performance gain achievable when using the MGRIT approach instead of the Time Stepping integrator (TS). To this end, we analyze the performance parameters of the algorithm that provide a-priori the best number of processing elements and grid levels to use to address the scaling of MGRIT, regarded as a parallel iterative algorithm proceeding along the time dimension.}},
author = {Mele, Valeria and Constantinescu, Emil M. and Carracciuolo, Luisa and D'Amore, Luisa},
title = {{A PETSc parallel-in-time solver based on MGRIT algorithm}},
journal = {Concurrency and Computation: Practice and Experience},
volume = {0},
number = {0},
pages = {e4928},
doi = {10.1002/cpe.4928},
url = {https://dx.doi.org/10.1002/cpe.4928},
}
@article{MiaoEtAl2018,
abstract = {{This paper presents and analyzes a parareal-in-time scheme for the incompressible non-isothermal Navier–Stokes equations with Boussinesq approximation. Standard finite element method is adopted for the spatial discretization.The proposed algorithm is proved to be unconditional stability. The convergence factor of iteration error for the velocity and temperature is given at time-continuous case. It theoretically demonstrates the superlinearly convergence of the parareal iteration combined with finite element method for incompressible non-isothermal flows. Finally, several numerical experiments that confirm feasibility and applicability of the algorithm perform well as expected.}},
author = {Zhen Miao and Yao-Lin Jiang and Yun-Bo Yang},
title = {Convergence analysis of a parareal-in-time algorithm for the incompressible non-isothermal flows},
journal = {International Journal of Computer Mathematics},
volume = {0},
number = {0},
pages = {1--18},
year = {2018},
doi = {10.1080/00207160.2018.1498484},
url = {https://doi.org/10.1080/00207160.2018.1498484},
}
@article{NielsenEtAl2018,
abstract = {{In the strong scaling limit, the performance of conventional spatial domain decomposition techniques for the parallel solution of PDEs saturates. When sub-domains become small, halo-communication and other overhead come to dominate. A potential path beyond this scaling limit is to introduce domain-decomposition in time, with one such popular approach being the Parareal algorithm which has received a lot of attention due to its generality and potential scalability. Low efficiency, particularly on convection dominated problems, has however limited the adoption of the method. In this paper we demonstrate trough large-scale numerical experiments that it is possible not only to obtain time-parallel speedup on the non-linear shallow water wave equation, but also that we may obtain parallel acceleration beyond what is possible using conventional spatial domain-decomposition techniques alone. Two factors were essential in achieving this. First, for Parareal to converge on the hyperbolic problem we used an approximate Riemann solver as the preconditioner. This preconditioner introduces only dissipative errors with respect to the 3rd order accurate WENO-RK discretization used to solve the PDE system. The preconditoner is comparatively expensive and convergence is slow unless time-subdomains are short. We therefore introduce a new scheduler that we denote Communication Aware Adaptive Parareal (CAAP). CAAP increases obtainable speed-up by minimizing the time-subdomain length without making communication of time-subdomains too costly whilst also adaptively overlapping consecutive cycles of Parareal so to mitigate the impact of a relatively expensive coarse operator.}},
author = {Allan S. Nielsen and Gilles Brunner and Jan S. Hesthaven},
title = {Communication-aware adaptive parareal with application to a nonlinear hyperbolic system of partial differential equations},
journal = {Journal of Computational Physics},
doi = {10.1016/j.jcp.2018.04.056},
url = {https://doi.org/10.1016/j.jcp.2018.04.056},
year = {2018},
}
@article{OngMandal2018,
author={Ong, Benjamin W. and Mandal, Bankim C.},
title={{Pipeline implementations of Neumann--Neumann and Dirichlet--Neumann waveform relaxation methods}},
journal={Numerical Algorithms},
year={2018},
month={May},
day={01},
volume={78},
number={1},
pages={1--20},
abstract={This paper is concerned with the reformulation of Neumann--Neumann waveform relaxation (NNWR) methods and Dirichlet--Neumann waveform relaxation (DNWR) methods, a family of parallel space-time approaches to solving time-dependent PDEs. By changing the order of the operations, pipeline-parallel computation of the waveform iterates are possible, without changing the solution of each waveform iterate. The parallel efficiency of the pipeline implementation is analyzed, as well as the change in the communication pattern. Numerical studies are presented to show the effectiveness of the pipeline NNWR and DNWR algorithms.},
doi={10.1007/s11075-017-0364-3},
url={https://doi.org/10.1007/s11075-017-0364-3}
}
@article{PagesEtAl2018,
abstract = {{With parallelism in mind we investigate the parareal method for American contracts, both theoretically and numerically. Least-square Monte Carlo (LSMC) and parareal time decomposition with two or more levels are used, leading to an efficient parallel implementation which scales linearly with the number of processors and is appropriate to any multiprocessor-memory architecture in its multilevel version. We prove $L^2$ superlinear convergence for an LSMC backward in time computation of American contracts, when the conditional expectations are known, i.e., before Monte Carlo discretization. The argument provides also a tool to analyze the multilevel parareal algorithm; in all cases the computing time is increased only by a constant factor, compared to the sequential algorithm on the finest grid, and speedup is guaranteed when the number of processors is larger than that constant. A numerical implementation confirms the theoretical error estimates.}},
author = {Pagès, G. and Pironneau, O. and Sall, G.},
title = {The Parareal Algorithm for American Options},
journal = {SIAM Journal on Financial Mathematics},
volume = {9},
number = {3},
pages = {966--993},
year = {2018},
doi = {10.1137/17M1138832},
url = {https://doi.org/10.1137/17M1138832},
}
@article{Ruprecht2018,
abstract = {{The paper derives and analyses the (semi-)discrete dispersion relation of the Parareal parallel-in-time integration method. It investigates Parareal's wave propagation characteristics with the aim to better understand what causes the well documented stability problems for hyperbolic equations. The analysis shows that the instability is caused by convergence of the amplification factor to the exact value from above for medium to high wave numbers. Phase errors in the coarse propagator are identified as the culprit, which suggests that specifically tailored coarse level methods could provide a remedy.}},
author = {Ruprecht, D.},
title = {Wave propagation characteristics of Parareal},
journal = {Computing and Visualization in Science},
url = {https://doi.org/10.1007/s00791-018-0296-z},
doi = {10.1007/s00791-018-0296-z},
volume = {19},
number = {1},
pages = {1--17},
year = {2018},
}
@Article{SchmittEtAl2018,
author = {Schmitt, A. and Schreiber, M. and Peixoto, P. and Sch{\"a}fer, M.},
title = {A numerical study of a semi-Lagrangian Parareal method applied to the viscous Burgers equation},
journal = {Computing and Visualization in Science},
abstract = {This work focuses on the Parareal parallel-in-time method and its application to the viscous Burgers equation. A crucial component of Parareal is the coarse time stepping scheme, which strongly impacts the convergence of the parallel-in-time method. Three choices of coarse time stepping schemes are investigated in this work: explicit Runge--Kutta, implicit--explicit Runge--Kutta, and implicit Runge--Kutta with semi-Lagrangian advection. Manufactured solutions are used to conduct studies, which provide insight into the viability of each considered time stepping method for the coarse time step of Parareal. One of our main findings is the advantageous convergence behavior of the semi-Lagrangian scheme for advective flows.},
doi = {10.1007/s00791-018-0294-1},
url = {https://doi.org/10.1007/s00791-018-0294-1},
volume = {19},
number = {1},
pages = {45--57},
year = {2018},
}
@unpublished{SamaeyEtAl2018,
abstract = {{We present the application of a micro/macro parareal algorithm for a 1-D energy balance climate model with discontinuous and non-monotone coefficients and forcing terms. The micro/macro parareal method uses a coarse propagator, based on a (macroscopic) 0-D approximation of the underlying (microscopic) 1-D model. We compare the performance of the method using different versions of the macro model, as well as different numerical schemes for the micro propagator, namely an explicit Euler method with constant stepsize and an adaptive library routine. We study convergence of the method and the theoretical gain in computational time in a realization on parallel processors. We show that, in this example and for all settings, the micro/macro parareal method converges in fewer iterations than the number of used parareal subintervals, and that a theoretical gain in performance of up to 10 is possible.}},
author = {Giovanni Samaey and Thomas Slawig},
title = {A micro/macro parallel-in-time (parareal) algorithm applied to a climate model with discontinuous non-monotone coefficients and oscillatory forcing},
howpublished = {arXiv:1806.04442 [math.NA]},
url = {https://arxiv.org/abs/1806.04442},
year = {2018},
}
@article{SchoepsEtAl2018,
abstract = {{In this paper, the usage of the Parareal method is proposed for the time-parallel solution of the eddy current problem. The method is adapted to the particular challenges of the problem that are related to the differential algebraic character due to non-conducting regions. It is shown how the necessary modification can be automatically incorporated by using a suitable time-stepping method. This paper closes with the first demonstration of a simulation of a realistic four-pole induction machine model using Parareal.}},
author = {Schöps, Sebastian and Niyonzima, Innocent and Clemens, Markus},
journal = {IEEE Transactions on Magnetics},
title = {Parallel-In-Time Simulation of Eddy Current Problems Using Parareal},
year = {2018},
volume = {54},
number = {3},
pages = {1--4},
doi = {10.1109/TMAG.2017.2763090},
url = {https://dx.doi.org/10.1109/TMAG.2017.2763090}
}
@article{SchreiberEtAl2018,
abstract = {{This paper presents, discusses and analyses a massively parallel-in-time solver for linear oscillatory partial differential equations, which is a key numerical component for evolving weather, ocean, climate and seismic models. The time parallelization in this solver allows us to significantly exceed the computing resources used by parallelization-in-space methods and results in a correspondingly significantly reduced wall-clock time. One of the major difficulties of achieving Exascale performance for weather prediction is that the strong scaling limit – the parallel performance for a fixed problem size with an increasing number of processors – saturates. A main avenue to circumvent this problem is to introduce new numerical techniques that take advantage of time parallelism. In this paper, we use a time-parallel approximation that retains the frequency information of oscillatory problems. This approximation is based on (a) reformulating the original problem into a large set of independent terms and (b) solving each of these terms independently of each other which can now be accomplished on a large number of high-performance computing resources. Our results are conducted on up to 3586 cores for problem sizes with the parallelization-in-space scalability limited already on a single node. We gain significant reductions in the time-to-solution of 118.3× for spectral methods and 1503.0× for finite-difference methods with the parallelization-in-time approach. A developed and calibrated performance model gives the scalability limitations a priori for this new approach and allows us to extrapolate the performance of the method towards large-scale systems. This work has the potential to contribute as a basic building block of parallelization-in-time approaches, with possible major implications in applied areas modelling oscillatory dominated problems.}},
author = {Martin Schreiber and Pedro S Peixoto and Terry Haut and Beth Wingate},
title ={Beyond spatial scalability limitations with a massively parallel method for linear oscillatory problems},
journal = {The International Journal of High Performance Computing Applications},
volume = {32},
number = {6},
pages = {913--933},
year = {2018},
doi = {10.1177/1094342016687625},
url = {https://doi.org/10.1177/1094342016687625},
}
@article{SchreiberLoft2018,
abstract = {{With the stagnation of processor core performance, further reductions in the time to solution for geophysical fluid problems are becoming increasingly difficult with standard time integrators. Parallel‐in‐time exposes and exploits additional parallelism in the time dimension, which is inherently sequential in traditional methods. The rational approximation of exponential integrators (REXI) method allows taking arbitrarily long time steps based on a sum over a number of decoupled complex PDEs that can be solved independently massively parallel. Hence, REXI is assumed to be well suited for modern massively parallel super computers, which are currently trending. To date, the study and development of the REXI approach have been limited to linearized problems on the periodic two‐dimensional plane. This work extends the REXI time stepping method to the linear shallow‐water equations on the rotating sphere, thus moving the method one step closer to solving fully nonlinear fluid problems of geophysical interest on the sphere. The rotating sphere poses particular challenges for finding an efficient solver due to the zonal dependence of the Coriolis term. Here, we present an efficient REXI solver based on spherical harmonics, showing the results of a geostrophic balance test, a comparison with alternative time stepping methods, an analysis of dispersion relations indicating superior properties of REXI, and finally, a performance comparison on the Cheyenne supercomputer. Our results indicate that REXI not only can take larger time steps but also can be used to gain higher accuracy and significantly reduced time to solution compared with currently existing time stepping methods.}},
title={A parallel time integrator for solving the linearized shallow water equations on the rotating sphere},
author={Schreiber, M. and Loft, R.},
journal={Numerical Linear Algebra with Applications},
year={2018},
doi={10.1002/nla.2220},
url={https://doi.org/10.1002/nla.2220}
}
@article{Speck2018,
abstract = {{In this paper we present two strategies to enable "parallelization across the method" for spectral deferred corrections (SDC). Using standard low-order time-stepping methods in an iterative fashion, SDC can be seen as preconditioned Picard iteration for the collocation problem. Typically, a serial Gauss-Seidel-like preconditioner is used, computing updates for each collocation node one by one. The goal of this paper is to show how this process can be parallelized, so that all collocation nodes are updated simultaneously. The first strategy aims at finding parallel preconditioners for the Picard iteration and we test three choices using four different test problems. For the second strategy we diagonalize the quadrature matrix of the collocation problem directly. In order to integrate non-linear problems we employ simplified and inexact Newton methods. Here, we estimate the speed of convergence depending on the time-step size and verify our results using a non-linear diffusion problem.}},
author = {Speck, Robert},
title = {Parallelizing spectral deferred corrections across the method},
doi = {10.1007/s00791-018-0298-x},
journal = {Computing and Visualization in Science},
url = {https://doi.org/10.1007/s00791-018-0298-x},
year = {2018}
}
@article{Subber2018,
abstract = {{In this paper, we adapt a parallel time integration scheme to track the trajectories of noisy non-linear dynamical systems. Specifically, we formulate a parallel algorithm to generate the sample path of nonlinear oscillator defined by stochastic differential equations (SDEs) using the so-called parareal method for ordinary differential equations (ODEs). The presence of Wiener process in \{SDEs\} causes difficulties in the direct application of any numerical integration techniques of \{ODEs\} including the parareal algorithm. The parallel implementation of the algorithm involves two \{SDEs\} solvers, namely a fine-level scheme to integrate the system in parallel and a coarse-level scheme to generate and correct the required initial conditions to start the fine-level integrators. For the numerical illustration, a randomly excited Duffing oscillator is investigated in order to study the performance of the stochastic parallel algorithm with respect to a range of system parameters. The distributed implementation of the algorithm exploits Massage Passing Interface (MPI).}},
author = {Waad Subber and Abhijit Sarkar},
title = {A Parallel Time Integrator for Noisy Nonlinear Oscillatory Systems},
journal = {Journal of Computational Physics},
year = {2018},
doi = {10.1016/j.jcp.2018.01.019},
url = {https://doi.org/10.1016/j.jcp.2018.01.019},
}
@article{Wu2018,
abstract = {{In this paper, we present an idea toward parallel coarse grid correction (CGC) for the parareal algorithm. It is well known that such a CGC procedure is often the bottleneck of speedup of the parareal algorithm. For an ODE system with initial-value condition $u(0)=u_0$ the idea can be explained as follows. First, we apply the $\mathcal{G}$-propagator to the same ODE system but with a special condition $u(0)=\alpha u(T)$, where $\alpha\in\mathbb{R}$ is a crux parameter. Second, in each iteration of the parareal algorithm the CGC procedure will be carried out by the so-called diagonalization technique established recently. The parameter $\alpha$ controls both the roundoff error arising from such a diagonalization technique and the convergence rate of the resulting parareal algorithm. We show that there exists some threshold $\alpha^*$ such that the parareal algorithm with diagonalization-based CGC possesses the same convergence rate as that of the parareal algorithm with classical CGC if $|\alpha|\leq \alpha^*$. With $|\alpha|=\alpha^*$, we show that the condition number associated with the diagonalization technique is a moderate quantity of order $\mathcal{O}(1)$ (and therefore the roundoff error is small) and is independent of the length of the time interval. Numerical results are given to support our findings.}},
author = {Wu, S.},
title = {Toward Parallel Coarse Grid Correction for the Parareal Algorithm},
journal = {SIAM Journal on Scientific Computing},
volume = {40},
number = {3},
pages = {A1446--A1472},
year = {2018},
doi = {10.1137/17M1141102},
url = {https://doi.org/10.1137/17M1141102},
}
@article{WuZhou2018_JCP,
abstract = {It is challenge work to design parareal algorithms for time-fractional differential equations due to the historical effect of the fractional operator. A direct extension of the classical parareal methed to such equations will lead to unbalance computational time in each process. In this work, we present an efficient parareal iteration scheme to overcome this issue, by adopting two recently developed local time-integrators for time fractional operators. In both approaches, one introduces auxiliary variables to localized the fractional operator. To this end, we propose a new strategy to perform the coarse grid correction so that the auxiliary variables and the solution variable are corrected separately in a mixed pattern. It is shown that the proposed parareal algorithm admits robust rate of convergence. Numerical examples are presented to support our conclusions.},
author = {Shu-Lin Wu and Tao Zhou},
title = {Parareal algorithms with local time-integrators for time fractional differential equations},
journal = {Journal of Computational Physics},
volume = {358},
pages = {135--149},
year = {2018},
url = {https://doi.org/10.1016/j.jcp.2017.12.029},
doi = {10.1016/j.jcp.2017.12.029},
}
@inproceedings{YallaEnquist2018,
abstract = {{The parareal algorithm allows for efficient parallel in time computation of dynamical systems. We present a novel coarse scale solver to be used in the parareal framework. The coarse scale solver can be defined through interpolation or as the output of a neural network, and accounts for slow scale motion in the system. Through a parareal scheme, we pair this coarse solver with a fine scale solver that corrects for fast scale motion. By doing so we are able to achieve the accuracy of the fine solver at the efficiency of the coarse solver. Successful tests for smaller but challenging problems are presented, which cover both highly oscillatory solutions and problems with strong forces localized in time. The results suggest significant speed up can be gained for multiscale problems when using a parareal scheme with this new coarse solver as opposed to the traditional parareal setup.}},
author = {Yalla, Gopal R. and Engquist, Bjorn},
articleno = {9},
booktitle = {Proceedings of the High Performance Computing Symposium},
pages = {9:1--9:12},
publisher = {Society for Computer Simulation International},
series = {HPC '18},
url = {http://dl.acm.org/citation.cfm?id=3213069.3213078},
title = {Parallel in Time Algorithms for Multiscale Dynamical Systems Using Interpolation and Neural Networks},
year = {2018},
}
@unpublished{YueEtAl2018,
abstract = {{The paper investigates a non-intrusive parallel time integration with multigrid for space-fractional diffusion equations in two spatial dimensions. We firstly obtain a fully discrete scheme via using the linear finite element method to discretize spatial and temporal derivatives to propagate solutions. Next, we present a non-intrusive time-parallelization and its two-level convergence analysis, where we algorithmically and theoretically generalize the MGRIT to time-dependent fine time-grid propagators. Finally, numerical illustrations show that the obtained numerical scheme possesses the saturation error order, theoretical results of the two-level variant deliver good predictions, and significant speedups can be achieved when compared to parareal and the sequential time-stepping approach.}},
author = {Yue, X.~Q. and Shu, S. and Xu, X.~W. and Bu, W.~P. and Pan, K.~J.},
title = {Parallel-in-Time with Fully Finite Element Multigrid for 2-D Space-fractional Diffusion Equations},
howpublished = {arXiv:1805.06688 [math.NA]},
url = {https://arxiv.org/abs/1805.06688v1},
year = {2018},
}
@article{ZhuWeng2018,
abstract = {{This paper investigates a novel parallel technique based on the spectral deferred correction (SDC) method and a compensation step for solving first-order evolution problems, and we call it para-SDC method for convenience. The standard SDC method is used in parallel with a rough initial guess and a Picard integral equation with high precision initial condition is acted as a compensator. The goal of this paper is to show how these processes can be parallelized and how to improve the efficiency. During the SDC step an implicit or semi-implicit method can be used for stiff problems which is always time-consuming, therefore that’s why we do this procedure in parallel. Due to a better initial condition of parallel intervals after the SDC step, the goal of compensation step is to get a better approximation and also avoid of solving an implicit problem again. During the compensation step an explicit Picard scheme is taken based on the numerical integration with polynomial interpolation on Gauss Radau II nodes, which is almost no time consumption, obviously, that’s why we do this procedure in serial. The convergency analysis and the parallel efficiency of our method are also discussed. Several numerical experiments and an application for simulation Allen–Cahn equation are presented to show the accuracy, stability, convergence order and efficiency features of para-SDC method.}},
author = {Zhu, Shuai and Weng, Shilie},
year = {2018},
pages = {1--28},
title = {A parallel spectral deferred correction method for first-order evolution problems},
journal = {BIT Numerical Mathematics},
doi = {10.1007/s10543-018-0702-4},
url = {https://doi.org/10.1007/s10543-018-0702-4}
}
%
% 2019
%
@unpublished{AgbohEtAl2019,
abstract = {{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.}},
author = {Wisdom C. Agboh and Daniel Ruprecht and Mehmet R. Dogar},
title = {Combining Coarse and Fine Physics for Manipulation using Parallel-in-Time Integration},
howpublished = {arXiv:1903.08470 [cs.RO]},
url = {https://arxiv.org/abs/1903.08470},
year = {2019},
}
@unpublished{BastEtAl2019,
abstract = {{This paper focuses on efficient steady-state computations of induction machines. In particular, the periodic Parareal algorithm with initial-value coarse problem (PP-IC) is considered for acceleration of classical time-stepping simulations via non-intrusive parallelization in time domain, i.e., existing implementations can be reused. Superiority of this parallel-in-time method is in its direct applicability to time-periodic problems, compared to, e.g, the standard Parareal method, which only solves an initial-value problem, starting from a prescribed initial value. PP-IC is exploited here to obtain the steady state of several operating points of an induction motor, developed by Robert Bosch GmbH. Numerical experiments show that acceleration up to several dozens of times can be obtained, depending on availability of parallel processing units. Comparison of PP-IC with existing time-periodic explicit error correction method highlights better robustness and efficiency of the considered time-parallel approach.}},
author = {Bast, Denys and Kulchytska-Ruchka, Iryna and Schöps, Sebastian and Rain, Oliver},
title = {Accelerated Steady-State Torque Computation for Induction Machines using Parallel-In-Time Algorithms},
howpublished = {arXiv:1902.08277 [cs.CE]},
url = {https://arxiv.org/abs/1902.08277},
year = {2019},
}
@unpublished{BrehierWang2019,
abstract = {{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.}},
author = {Charles-Edouard Bréhier and Xu Wang},
title = {On parareal algorithms for semilinear parabolic Stochastic PDEs},
howpublished = {arXiv:1902.05370 [math.NA]},
url = {https://arxiv.org/abs/1902.05370},
year = {2019},
}
@unpublished{ClarkeEtAl2019,
abstract = {{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. Speed ups beyond those possible from spatial parallelization 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 parallelization 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.}},
author = {Andrew T. Clarke and Christopher J. Davies and Daniel Ruprecht and Steven M. Tobias},
title = {Parallel-in-time integration of Kinematic Dynamos},
howpublished = {arXiv:1902.00387 [physics.comp-ph]},
url = {https://arxiv.org/abs/1902.00387},
year = {2019},
}
@unpublished{DeSterckEtAl2019,
abstract = {{Parallel-in-time algorithms have been successfully employed for reducing time-to-solution of a variety of partial differential equations, especially for diffusive (parabolic-type) equations. A major failing of parallel-in-time approaches to date, however, is that most methods show instabilities or poor convergence for hyperbolic problems. This paper focuses on the analysis of the convergence behavior of multigrid methods for the parallel-in-time solution of hyperbolic problems. Three analysis tools are considered that differ, in particular, in the treatment of the time dimension: (1) space-time local Fourier analysis, using a Fourier ansatz in space and time, (2) semi-algebraic mode analysis, coupling standard local Fourier analysis approaches in space with algebraic computation in time, and (3) a two-level reduction analysis, considering error propagation only on the coarse time grid. In this paper, we show how insights from reduction analysis can be used to improve feasibility of the semi-algebraic mode analysis, resulting in a tool that offers the best features of both analysis techniques. Following validating numerical results, we investigate what insights the combined analysis framework can offer for two model hyperbolic problems, the linear advection equation in one space dimension and linear elasticity in two space dimensions.}},
author = {Hans De Sterck and Stephanie Friedhoff and Alexander J. M. Howse and Scott P. MacLachlan},
title = {Convergence analysis for parallel-in-time solution of hyperbolic systems},
howpublished = {arXiv:1903.08928 [math.NA]},
url = {https://arxiv.org/abs/1903.08928},
year = {2019},
}
@article{DohrEtAl2019,
abstract = {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.},
author = {Stefan Dohr and Jan Zapletal and Günther Of and Michal Merta and Michal Kravčenko},
title = {A parallel space–time boundary element method for the heat equation},
journal = {Computers \& Mathematics with Applications},
year = {2019},
doi = {https://doi.org/10.1016/j.camwa.2018.12.031},
url = {http://www.sciencedirect.com/science/article/pii/S0898122118307296},
}
@unpublished{FriedhoffSouthworth2019,
abstract = {{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.}},
author = {Stephanie Friedhoff and Ben S. Southworth},
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},
}
@unpublished{FriedhoffEtAl2019,
abstract = {{Parallel-in-time methods have shown success for reducing the simulation time of many time-dependent problems. Here, we consider applying the multigrid-reduction-in-time (MGRIT) algorithm to a voltage-driven eddy current model problem.}},
author = {Friedhoff, Stephanie and Hahne, Jens and Schöps, Sebastian},
title = {Multigrid-reduction-in-time for Eddy Current Problems},
howpublished = {arXiv:1905.06879 [math.NA]},
url = {https://arxiv.org/abs/1905.06879},
year = {2019},
}
@article{GanderEtAl2019,
abstract = {{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.}},
author = {Gander, M. and Halpern, L. and Rannou, J. and Ryan, J.},
title = {A Direct Time Parallel Solver by Diagonalization for the Wave Equation},
journal = {SIAM Journal on Scientific Computing},
volume = {41},
number = {1},
pages = {A220--A245},
year = {2019},
doi = {10.1137/17M1148347},
url = {https://doi.org/10.1137/17M1148347},
}
@article{GanderEtAl2019b,
abstract = {{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.}},
author = {Gander, M. and Jiang, Y. and Song, B.},
title = {A Superlinear Convergence Estimate for the Parareal Schwarz Waveform Relaxation Algorithm},
journal = {SIAM Journal on Scientific Computing},
volume = {41},
number = {2},
pages = {A1148--A1169},
year = {2019},
doi = {10.1137/18M1177226},
url = {https://doi.org/10.1137/18M1177226},
}
@article{GanderEtAl2019c,
abstract = {{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.}},
author = {Gander, Martin J. and Kulchytska-Ruchka, Iryna and Niyonzima, Innocent and Schöps, Sebastian},
title = {A New Parareal Algorithm for Problems with Discontinuous Sources},
journal = {SIAM Journal on Scientific Computing},
volume = {41},
number = {2},
pages = {B375--B395},
year = {2019},
doi = {10.1137/18M1175653},
url = {https://doi.org/10.1137/18M1175653},
}
@unpublished{GoetschelMinion2019,
abstract = {{To solve optimization problems with parabolic PDE constraints, often methods working on the reduced objective functional are used. They are computationally expensive due to the necessity of solving both the state equation and a backward-in-time adjoint equation to evaluate the reduced gradient in each iteration of the optimization method. In this study, we investigate the use of the parallel-in-time method PFASST in the setting of PDE constrained optimization. In order to develop an efficient fully time-parallel algorithm we discuss different options for applying PFASST to adjoint gradient computation, including the possibility of doing PFASST iterations on both the state and adjoint equations simultaneously. We also explore the additional gains in efficiency from reusing information from previous optimization iterations when solving each equation. Numerical results for both a linear and a non-linear reaction-diffusion optimal control problem demonstrate the parallel speedup and efficiency of different approaches.}},
author = {Sebastian Götschel and Michael L. Minion},
institution = {Lawrence Berkeley National Laboratory},
title = {{An Efficient Parallel-in-Time Method for Optimization with Parabolic PDEs}},
howpublished = {arXiv:1901.06850 [math.OC]},
url = {https://arxiv.org/abs/1901.06850},
year = {2019},
}
@article{HedinLelievre2019,
abstract = {{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.}},
author = {Florent Hédin and Tony Lelièvre},
title = {gen.parRep: A first implementation of the Generalized Parallel Replica dynamics for the long time simulation of metastable biochemical systems},
journal = {Computer Physics Communications},
year = {2019},
url = {https://doi.org/10.1016/j.cpc.2019.01.005},
doi = {10.1016/j.cpc.2019.01.005},
}
@article{HowseEtAl2019,
abstract = {{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.}},
author = {Howse, A. and Sterck, H. and Falgout, R. and MacLachlan, S. and Schroder, J.},
title = {Parallel-In-Time Multigrid with Adaptive Spatial Coarsening for The Linear Advection and Inviscid Burgers Equations},
journal = {SIAM Journal on Scientific Computing},
volume = {41},
number = {1},
pages = {A538--A565},
year = {2019},
doi = {10.1137/17M1144982},
url = {https://dx.doi.org/10.1137/17M1144982}
}
@unpublished{KrzysikEtAl2019,
abstract = {{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.}},
author = {Oliver A. Krzysik and Hans De Sterck and Scott P. MacLachlan and Stephanie Friedhoff},
title = {On selecting coarse-grid operators for Parareal and MGRIT applied to linear advection},
howpublished = {arXiv:1902.07757 [math.NA]},
url = {https://arxiv.org/abs/1902.07757},
year = {2019},
}
@article{KwokOng2019,
abstract = {{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.}},
author = {Kwok, F. and Ong, B.},
title = {Schwarz Waveform Relaxation with Adaptive Pipelining},
journal = {SIAM Journal on Scientific Computing},
volume = {41},
number = {1},
pages = {A339--A364},
year = {2019},
doi = {10.1137/17M115311X},
url = {https://doi.org/10.1137/17M115311X},
}
@article{LiEtAl2019,
abstract = {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.},
author = {Shishun Li and Rongliang Chen and Xinping Shao},
title = {Parallel two-level space–time hybrid Schwarz method for solving linear parabolic equations},
journal = {Applied Numerical Mathematics},
volume = {139},
pages = {120--135},
year = {2019},
doi = {10.1016/j.apnum.2019.01.016},
url = {https://doi.org/10.1016/j.apnum.2019.01.016},
}
@article{LiEtAl2019b,
abstract = {{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.}},
author = {Li, Shishun and Shao, Xinping and Cai, Xiao-Chuan},
title = {Highly parallel space-time domain decomposition methods for parabolic problems},
journal = {CCF Transactions on High Performance Computing},
year = {2019},
doi = {10.1007/s42514-019-00003-x},
url = {https://doi.org/10.1007/s42514-019-00003-x}
}
@inproceedings{MeleEtAl2019,
abstract = {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.},
author = {Mele, Valeria and Romano, Diego and Constantinescu, Emil M. and Carracciuolo, Luisa and D'Amore, Luisa},
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.},
title = {Performance Evaluation for a PETSc Parallel-in-Time Solver Based on the MGRIT Algorithm},
booktitle = {Euro-Par 2018: Parallel Processing Workshops},
year = {2019},
publisher = {Springer International Publishing},
pages = {716--728},
doi = {10.1002/cpe.4928},
url = {https://doi.org/10.1002/cpe.4928}
}
@article{NeumuellerSmears2019,
abstract = {{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.}},
author = {Neum{\"u}ller, M. and Smears, I.},
title = {Time-Parallel Iterative Solvers for Parabolic Evolution Equations},
journal = {SIAM Journal on Scientific Computing},
volume = {41},
number = {1},
pages = {C28--C51},
year = {2019},
doi = {10.1137/18M1172466},
url = {https://doi.org/10.1137/18M1172466},
}
@unpublished{NguyenTsai2019,
title={A stable parareal-like method for the second order wave equation},
abstract={{ 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 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 by Lions et. al. 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 energy residual of the fine and coarse propagated solutions. An example of Marmousi model is provided to demonstrate the performance of the proposed method.}},
author={Hieu Nguyen and Richard Tsai},
howpublished = {arXiv:1905.00473 [math.NA]},
url={https://arxiv.org/abs/1905.00473},
year={2019}
}
@article{SamaddarEtAl2019,
abstract = {{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.}},
author = {D. Samaddar and D.P. Coster and X. Bonnin and L.A. Berry and W.R. Elwasif and D.B. Batchelor},
journal = {Computer Physics Communications},
title = {Application of the parareal algorithm to simulations of {ELM}s in {ITER} plasma},
volume = {235},
pages = {246--257},
year = {2019},
doi = {10.1016/j.cpc.2018.08.007},
url = {https://doi.org/10.1016/j.cpc.2018.08.007},
}
@article{SchreiberLoft2019,
abstract = {{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.}},
title={Exponential Integrators with Parallel-in-Time Rational Approximations for Shallow-Water Equations on the Rotating Sphere},
author={Schreiber, M. and Schaeffer, N. and Loft, R.},
journal={Parallel Computing},
year={2019},
doi = {10.1016/j.parco.2019.01.005},
url = {https://dx.doi.org/10.1016/j.parco.2019.01.005}
}
@article{Southworth2019,
abstract = {{Parareal and multigrid reduction in time (MGRiT) are two of the most popular parallel-in-time methods. The basic idea is to treat time integration in a parallel context by using a multigrid method in time. If $\Phi$ is the (fine-grid) time-stepping scheme of interest, such as any Runge--Kutta scheme, then let $\Psi$ denote a “coarse-grid" time-stepping scheme chosen to approximate $k$ steps of $\Phi$, where $k\geq 1$. In particular, $\Psi$ defines the coarse-grid correction, and evaluating $\Psi$ should be (significantly) cheaper than evaluating $\Phi^k$. Parareal is a two-level method with a fixed relaxation scheme, and MGRiT is a generalization to the multilevel setting, with the additional option of a modified, stronger relaxation scheme. A number of papers have studied the convergence of Parareal and MGRiT. However, general conditions on the convergence of Parareal or MGRiT that answer the following simple questions have yet to be developed: (i) For a given $\Phi$ and $k$, what is the best $\Psi$? (ii) Can Parareal/MGRiT converge for my problem? This work derives necessary and sufficient conditions for the convergence of Parareal and MGRiT applied to linear problems, along with tight two-level convergence bounds, under minimal additional assumptions on $\Phi$ and $\Psi$. Results all rest on the introduction of a temporal approximation property (TAP) that indicates how $\Phi^k$ must approximate the action of $\Psi$ on different vectors. Loosely, for unitarily diagonalizable operators, the TAP indicates that the fine-grid and coarse-grid time integration schemes must integrate geometrically smooth spatial components similarly, and less so for geometrically high frequency. In the (nonunitarily) diagonalizable setting, the conditioning of each eigenvector, ${v}_i$, must also be reflected in how well $\Psi{v}_i \sim\Phi^k{v}_i$. In general, worst-case convergence bounds are exactly given by $\min \varphi < 1$ such that an inequality along the lines of $\|(\Psi-\Phi^k){v}\| \leq\varphi \|(I - \Psi){v}\|$ holds for all ${v}$. Such inequalities are formalized as different realizations of the TAP in section 2 and form the basis for convergence of MGRiT and Parareal applied to linear problems.}},
author = {Ben S. Southworth},
doi = {https://doi.org/10.1137/18M1226208},
journal = {SIAM J. Matrix Anal. Appl.},
number = {2},
pages = {564--608},
title = {Necessary {C}onditions and {T}ight {T}wo-level {C}onvergence {B}ounds for {P}arareal and {M}ultigrid {R}eduction in {T}ime},
volume = {40},
year = {2019}
}