SPACE-TIME CONTINUOUS ANALYSIS OF WAVE-FORM RELAXATION FOR THE HEAT-EQUATION

Waveform relaxation algorithms for partial differential equations (PDE s) are traditionally obtained by discretizing the PDE in space and the n splitting the discrete operator using matrix splittings. For the sem idiscrete heat equation one can show linear convergence on unbounded t ime intervals and superlinear convergence on bounded time intervals by this approach. However, the bounds depend in general on the mesh para meter and convergence rates deteriorate as one refines the mesh. Motiv ated by the original development of waveform relaxation in circuit sim ulation, where the circuits are split in the physical domain into subc ircuits, we split the PDE by using overlapping domain decomposition. W e prove linear convergence of the algorithm in the continuous case on an infinite time interval, at a rate depending on the size of the over lap. This result remains valid after discretization in space and the c onvergence rates are robust with respect to mesh refinement. The algor ithm is in the class of waveform relaxation algorithms based on overla pping multisplittings. Our analysis quantifies the empirical observati on by Jeltsch and Pohl [SIAM J. Sci. Comput., 16 (1995), pp. 40-49] th at the convergence rate of a multisplitting algorithm depends on the o verlap. Numerical results are presented which support the convergence theory.