A Direct Solver for Time Parallelization

摘要

Using the time direction in evolution problems for parallelization is an active field of research. Most of these methods are iterative, see for example the parareal algorithm analyzed in, a variant that became known under the name PFASST, and waveform relaxation methods based on domain decomposition, see also for a method called RIDC. Direct time parallel solvers are much more rare, see for example. We present here a mathematical analysis of a different direct time parallel solver, proposed in. We consider as our model partial differential equation (PDE) the heat equation on a rectangular domain Ω, ?u/?t-Δu=f in Ω×(0,T), u = g on ?Ω, and u(-,0) = u_0 in Ω. (1) Using a Backward Euler discretization on the time mesh 0 = t_0 ＜ t_1 ＜ t_2 ＜ ... ＜ t_N = T, k_n = t_n - t_(n-1), and a finite difference approximation Δ_h of Δ over a rectangular grid of size J = J_1J_2, we obtain the discrete problem 1/k_n(u~n)-u~(n-1)-Δ_hu~n=f~n. (2) Let I_t be the N × N identity matrix associated with the time domain and I_x be the J × J identity matrix associated with the spatial domain. Setting u := (u~1,..., u~N), f := (f~1 + 1/k_1u_0, f~2,...,f~N) and using the Kronecker symbol, (2) becomes (B directX I_x-I_t directX Δ_h)u =f, B:=(1/k_1-1/k_2 0 ...-1/k_N 1/k_2...1/k_N 0)(3).