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 <s> The PARAEXP algorithm <s> This paper is dedicated to the proposition that, in order to take full advantage for real-time computations of highly parallel computers as can be expected to be available in the near future, much of numerical analysis will have to be recast in a more “parallel” form. By this is meant that serial algorithms ought to be replaced by algorithms which consist of several subtasks which can be computed without knowledge of the results of the other subtasks. As an example, a method is proposed for “parallelizing” the numerical integration of an ordinary differential equation, which process, by all standard methods, is entirely serial. <s> BIB001 </s> 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 <s> The PARAEXP algorithm <s> A novel parallel algorithm for the integration of linear initial-value problems is proposed. This algorithm is based on the simple observation that homogeneous problems can typically be integrated much faster than inhomogeneous problems. An overlapping time-domain decomposition is utilized to obtain decoupled inhomogeneous and homogeneous subproblems, and a near-optimal Krylov method is used for the fast exponential integration of the homogeneous subproblems. We present an error analysis and discuss the parallel scaling of our algorithm. The efficiency of this approach is demonstrated with numerical examples. <s> BIB002
Numerical methods allowing parallelization in the time direction have been thought since a long time (see Nievergelt BIB001 in 1964) and have known great developments particularly in the last decade because of today's growing HPC platforms. Among time-parallel solvers, the PARAEXP algorithm introduced by Gander and Güttel BIB002 in 2013 is dedicated to linear ordinary differential problems, that is problems in the form especially when f (t) is varying fastly in time. Problem (4) has a solution written in integral form thanks to the variation-of-constant formula: If we want to take advantage of (5) for deriving a numerical computational method, in particular we need a high-order quadrature formula of the integral term. If the f (t) are fast varying source terms, quadrature may become irrelevant from the accuracy point of view. Gander and Güttel rather propose to split the problem over p sub-domains in time and use a superposition principle based on independent problems set onto different time domains: 3. For each j = 1, ..., p, solve the homogeneous probleṁ (with the notation v 0 (T 0 ) := u 0 ). It is clear that by a superposition principle, on can synthesize a solution u of (4) by the summation formula The PARAEXP algorithm is dedicated to parallel computing architectures, otherwise of course there is no benefit to execute it sequentially on one processor. It is remarkable to notice that good implementations of PARAEXP do not require any communication until the solution synthesis step, so the theoretical optimal efficiency is 1 before synthesis. Of course there is an issue of load balancing between processors because for a uniform time domain partitioning, some processors (especially the first one) are doing more work than others. The algorithm is graphically summarized in Fig. 1 . Another key of performance is the fast computation of the matrix exponentials. The solution of the homogeneous problem   and thus has to be evaluated many times (at any time t in fact). There are many approaches to compute accurate approximate matrix exponentials as commented in BIB002 . A way is to  looking for a best approximation into the truncated series expansion. We will come back on this issue when reduced order models (ROM) will be introduced below.