Parallel Multigrid Waveform Relaxation for Parabolic Problems

1 Introduction.- 1.1 Numerical simulation and parallel processing.- 1.2 The simulation of time-dependent processes.- 1.3 Outline.- 2 Waveform Relaxation Methods.- 2.1 Introduction.- 2.2 Waveform relaxation: basic ideas.- 2.3 A classification of waveform methods.- 2.4 General convergence results.- 2.5 Convergence analysis for linear systems.- 2.6 Waveform relaxation acceleration techniques.- 2.7 Some concluding remarks.- 3 Waveform Relaxation Methods for Initial Boundary Value Problems.- 3.1 Introduction and notations.- 3.2 Standard waveform relaxation.- 3.3 Linear multigrid acceleration.- 3.4 Convergence analysis.- 3.5 Experimental results.- 3.6 Nonlinear multigrid waveform relaxation.- 3.7 A multigrid method on a space-time grid.- 3.8 Concluding remarks.- 4 Waveform Relaxation for Solving Time-Periodic Problems.- 4.1 Introduction.- 4.2 Standard time-periodic PDE solvers.- 4.3 Time-periodic waveform relaxation.- 4.4 Analysis of the continuous-time iteration.- 4.5 Analysis of the discrete-time iteration.- 4.6 Multigrid acceleration.- 4.7 Autonomous time-periodic problems.- 5 A Short Introduction to Parallel Computers and Parallel Computing.- 5.1 Introduction.- 5.2 Classification of parallel computers.- 5.3 The hypercube topology.- 5.4 The Intel iPSC/2 hypercube multiprocessor.- 5.5 Parallel performance parameters.- 6 Parallel Implementation of Standard Parabolic Marching Schemes.- 6.1 Introduction.- 6.2 Problem class and discretization.- 6.3 Parallel implementation: preliminaries.- 6.4 The explicit update step.- 6.5 The multigrid solver.- 6.6 The tridiagonal systems solver.- 6.7 Timing results on the Intel hypercube.- 6.8 Numerical examples.- 6.9 Concluding remarks.- 7 Computational Complexity of Multigrid Waveform Relaxation.- 7.1 Introduction.- 7.2 Arithmetic complexity.- 7.3 Parallel implementation.- 7.4 Vectorization.- 7.5 Concluding remarks.- 8 Case Studies.- 8.1 Introduction.- 8.2 Programming considerations.- 8.3 Representation of the results.- 8.4 Linear initial boundary value problems.- 8.5 Nonlinear initial boundary value problems.- 8.6 Linear time-periodic problems.- 8.7 Example 7: a nonlinear periodic system.- 8.8 Further remarks, limits of applicability.- 9 Concluding Remarks and Suggestions for Future Research.- A Discretization and Stencils.