Feasibility study of the parareal algorithm 
Allan Svejstrup Nielsen

Abstract  A general introduction to the topic of timedomain parallelism with motivation is given in Chapter 1. The ’parareal’ algorithm itself along with pseudocode for a simple implementation and all the basic properties are presented in chapter 2. Chapter 3 contains a comprehensive review of the research literature available as well as current stateoftheart implementations of parareal. Investigations on the convergence rate of the algorithm applied to various types of differential equations using various numerical schemes as operators in the algorithm is presented in Chapter 4, followed by an investigation in Chapter 5 on optimal coarse propagator parameter choice when considering the distribution of parallel work. In this context a heuristic for the optimal choice of coarse propagator accuracy is proposed. In Chapter 6 the parareal algorithm is applied to a nonlinear free surface water wave model. The convergence rate is analysed in a Matlab implementations of the algorithm, simulating the parallelism for a range of different wave types. As will be shown, the nonlinearity of the wave and the water depth influence the parallel efficiency that can be obtained using the parareal algorithm. In Chapter 7 a large scale implementation of parareal is tested using a fully distributed task scheduling model to distribute the work that is to be computed concurrently on GPUs. The GPU implementation constitute a novel contribution to the literature on parareal. The findings in the report are summarized with a discussion on the feasibility and future outlook of the parareal algorithm for the parallel solution of initial value problems. 
Type  Master's thesis [Academic thesis] 
Year  2012 
Publisher  Technical University of Denmark, DTU Informatics, Email: reception@imm.dtu.dk 
Address  Asmussens Alle, Building 305, DK2800 Kgs. Lyngby, Denmark 
Series  IMMM.Sc.2012134 
Note  DTU supervisor: Allan P. Engsig Karup, apek@imm.dtu.dk, DTU Informatics 
Electronic version(s)  [pdf] 
Publication link  http://www.imm.dtu.dk/English.aspx 
BibTeX data  [bibtex] 
IMM Group(s)  Scientific Computing 