Lossy data compression reduces communication time in hybrid time-parallel integrators

Please always quote using this URN: urn:nbn:de:0297-zib-63961
  • 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.

Download full text files

Export metadata

Author:Lisa Fischer, Sebastian Götschel, Martin WeiserORCiD
Document Type:ZIB-Report
Tag:MPI; convergence; hybrid parareal; lossy compression; parallel-in-time integration
MSC-Classification:65-XX NUMERICAL ANALYSIS / 65Lxx Ordinary differential equations / 65L05 Initial value problems
65-XX NUMERICAL ANALYSIS / 65Lxx Ordinary differential equations / 65L60 Finite elements, Rayleigh-Ritz, Galerkin and collocation methods
65-XX NUMERICAL ANALYSIS / 65Mxx Partial differential equations, initial value and time-dependent initial- boundary value problems / 65M20 Method of lines
65-XX NUMERICAL ANALYSIS / 65Yxx Computer aspects of numerical algorithms / 65Y05 Parallel computation
68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Pxx Theory of data / 68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) [See also 94Axx]
Date of first Publication:2017/09/05
Series (Serial Number):ZIB-Report (17-25)
Published in:Comput. Vis. Sci. 19, 19-30, 2018, DOI 10.1007/s00791-018-0293-2