Read more
Wetenschap is meer dan het object dat zij bestudeert. Wetenschap is ook de weg naar de ontdekking, en bovendien, wetenschap is ook het verhaaJ van de ontdekkingsreis. -Po Thielen Focus research, Nr 10-11, juli 1991. The numerical solution of a parabolic partial differential equation is usually calcu lated by using a time-stepping method. This precludes the efficient use of parallelism and vectorization, unless the problem to be solved at each time-level is very large. This monograph investigates the use of an algorithm that overcomes the limitations of the standard schemes by calculating the solution at many time-levels, or along a continuous time-window simultaneously. The algorithm is based on waveform relazation, a highly parallel technique for solving very large systems of ordinary differential equations, and multigrid, a very fast method for solving elliptic partial differential equations. The resulting multigrid waveform relazation method is applicable to both initial boundary value and time-periodic parabolic problems. We analyse in this book theoretical and practical aspects of the multigrid waveform relaxation algorithm. Its implementation on a distributed memory message-passing computer and its computational complexity (arithmetic complexity, communication complexity and potential for vectorization) are studied. The method has been im plemented and extensively tested on a hypercube multiprocessor with vector nodes. Results of numerical experiments are given, which illustrate a severalfold performance gain when compared to parallel implementations of a variety of standard initial bound ary value and time-periodic solvers.
List of contents
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.
