Parallel Multigrid Waveform Relaxation for Parabolic Problems

Frontmatter

Chapter 1. Introduction

Abstract

We emphasize the increasing importance of parallel supercomputers for the solution of large-scale scientific and engineering problems. A sequential bottleneck which limits the obtainable parallelism and performance when simulating time-dependent processes with standard time-marching schemes is identified. Some of the approaches that have been suggested in the literature for eliminating or alleviating this fundamental problem are reviewed. Finally, we present an overview of the book.

Stefan Vandewalle

Chapter 2. Waveform Relaxation Methods

Abstract

We survey standard waveform relaxation results, mainly for future reference. The method is introduced and its use for solving ordinary differential equations is illustrated. The convergence theorems based on a contraction mapping argument are recalled and some alternative proofs are presented. A detailed analysis for linear constant coefficient ordinary differential equations is given. Finally, we enumerate techniques which have been proposed for accelerating the computational process.

Stefan Vandewalle

Chapter 3. Waveform Relaxation Methods for Initial Boundary Value Problems

Abstract

We comment on the use of waveform relaxation techniques for solving parabolic initial boundary value problems. It is illustrated that the Jacobi, Gauss-Seidel and SOR methods do not lead to satisfactory, rapidly convergent algorithms. A linear multigrid acceleration is presented, and illustrated by a numerical example. An analysis of the continuous-time and discrete-time variants is given. The method is extended to nonlinear problems and related to a multigrid method on a space-time grid.

Stefan Vandewalle

Chapter 4. Waveform Relaxation for Solving Time-Periodic Problems

Abstract

We extend the applicability of waveform relaxation and discuss its use for solving time-periodic non-autonomous ordinary and partial differential equations. The convergence characteristics of both the continuous-time and the discrete-time time-periodic iteration are analysed. It is shown that the convergence of the method is intimately related to the convergence of the corresponding initial value waveform relaxation method. The multigrid acceleration is discussed. Finally, an algorithm based on a modified shooting method is given for solving autonomous periodic problems.

Stefan Vandewalle

Chapter 5. A Short Introduction to Parallel Computers and Parallel Computing

Abstract

This chapter provides a short elementary introduction to parallel computers and parallel computing, and is a prerequisite for a good understanding of the following chapters. We present some architectural multiprocessor characteristics with the emphasis on distributed memory multicomputers. We discuss the hypercube topology in particular, and we illustrate its connectivity by recalling a number of well-known properties. A particular multicomputer with hypercube topology, the Intel iPSC/2, which will be used for the experiments in later chapters, is discussed in some more detail. Finally, a number of important performance parameters, such as speedup and parallel efficiency, are defined.

Stefan Vandewalle

Chapter 6. Parallel Implementation of Standard Parabolic Marching Schemes

Abstract

We analyse the parallel characteristics of several time-stepping schemes for linear parabolic partial differential equations. We discuss the classical explicit methods (forward Euler, Heun and DuFort-Frankel), three standard implicit methods (the first and second order backward differentiation formulae, and the Crank-Nicolson rule), the line hopscotch technique and the ADI formula of McKee and Mitchell. Three numerical kernels are identified and studied in particular: the explicit update step, the solution of a linear system by means of the multigrid method, and the solution of tridiagonal systems of equations by means of substructured Gaussian elimination. It is shown that numerical efficiency must usually be traded off against parallel efficiency.

Stefan Vandewalle

Chapter 7. Computational Complexity of Multigrid Waveform Relaxation

Abstract

We detail the arithmetic complexity of the multigrid waveform relaxation method. It is shown that the complexity is comparable to that of the best sequential solvers in the case of initial boundary value problems. It is better by a factor of 2.5 in the case of time-periodic problems. The communication complexity of a parallel implementation based on a spatial grid partitioning approach is analysed and compared to that of a similar implementation of standard initial value and time-periodic solvers. Finally, we discuss the vectorization of the waveform relaxation method.

Stefan Vandewalle

Chapter 8. Case Studies

Abstract

We present a number of non-trivial, linear and nonlinear examples of initial boundary value and time-periodic parabolic partial differential equations. Each problem is solved with the appropriate variant of the multigrid waveform relaxation method as well as with “the best” standard parabolic solver. The differences in performance are explained and the theoretical results obtained in the previous chapters are illustrated. It is shown that the waveform relaxation methods are competitive on sequential processors, and that they outperform the standard techniques on parallel machines. In particular we illustrate that on a 16-processor vector hypercube waveform relaxation can be faster than any of the standard approaches by a factor of ten up to forty.

Stefan Vandewalle

Chapter 9. Concluding Remarks and Suggestions for Future Research

Abstract

We started this book with the observation that time-marching methods for solving parabolic problems are inherently sequential. The computation proceeds from time-level to time-level, and the parallelism is limited to the parallelism inherent in the solvers applied in each time-step. It was further illustrated that standard solvers trade off numerical quality against parallel efficiency. Consequently, no time-stepping method proved to be really satisfactory for use on large-scale parallel processors.

Stefan Vandewalle

Backmatter