Parallel Scientific Computing in C++ and MPI

Chapter 7 Overview



Book Chapter Introduction

In this chapter we present discretizations for mixed initial value/boundary value problems (IVP/BVP) as well as relaxation iterative solvers associated with such discretizations.  The analogy between iterative procedures and equations of evolution, especially of parabolic type (diffusion), was realized about two centuries ago, but a rigorous connection was not established until the mid 1950s.

In the following, we first consider various mixed discretizations, and subsequently we derive some of the most popular iterative solvers. Our emphasis will be on parallel computing: A good algorithm is not simply the one that converges faster but also the one that is parallelizable. The Jacobi algorithm is such an example; forgotten for years in favor of the Gauss-Seidel algorithm, which converges twice as fast for about the same computational work, it was re-discovered in the last two decades as it is trivially parallelizable,  and today is used mostly  as a preconditioner for multigrid methods.  The Gauss-Seidel algorithm, although faster on a serial computer, is not parallelizable unless a special multi-color algorithm is employed, as we explain in section 7.2.4.  Based on these two basic algorithms, we present the multigrid method that exploits their good convergence properties but in a smart adaptive way.

On the parallel computing side, we introduce three new commands: MPI_Gather, MPI_Allgather, and MPI_Scatter.  Both MPI_Gather and MPI_Allgather are used for gathering information from a collection of processes.  MPI_Scatter is used to scatter data from one process to a collection of processes.  In addition to providing syntax and usage information, we present the applicability of the gathering functions in the parallel implementation of the Jacobi method.

SCchapter7 Introduction and Chapter 7 Driver Programs

    Within the text, there are several places where the software suite is referenced.  In some cases the code is explicitly placed within the text, and at other times within the text we merely alert you that the software is available on this CD.  As you read through Chapter 7, you will find that the following function/classes were discussed.




   The declarations and definitions of these functions/classes can be found in the following files:

Go to the file SCchapter7.h for function/class declarations
Go to the file SCchapter7.cpp for function/class definitions
    In the case that an entire program (meaning that a main() function is provided) is presented in the text, we classify this as a driver program.  Unlike the functions/classes above, driver programs are complete C++ programs which can be compiled and executed.  As you read through the book, you will see that driver programs are often times created by using functions/classes which are in the SCchapter files.  We denote driver programs which are explicitly given in the text of the book in red.  In some chapters, we present very few driver programs explicitly in the text, however we provide some example driver programs which demonstrate how to use the functions/classes with in SCchapter files.  Such driver programs are denoted in black.

Section 7.2.1: Program to demonstrate the use of the Diffusion_Jacobi routine chapter7c0.cpp
Section 7.2.2: MPI - Program to demonstrate the use of the parallel Diffusion_Jacobi routine chapter7c1P.cpp
Section 7.2.2: MPI - Program to demonstrate the use of the parallel Jacobi_P routine chapter7c2P.cpp