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.
- Section 7.1.4: void Diffusion_EF_CentralDifference(int N, double DN, double *uold, double *unew) function definition
- Section 7.1.4: void Diffusion_EB_CentralDifference(int N, double DN, double *uold, double *unew) function definition
- Section 7.2.1: int Diffusion_Jacobi(int N, double dx, double dt, double **A, double **q, double abstol) function definition
- Section 7.2.2: int Jacobi_P(int mynode, int numnodes, int N, double **A, double *x, double *b, double abstol) function definition
- Section 7.2.3: int Diffusion_GaussSeidel(int N, double dx, double dt, double **A, double **q, double abstol) function definition
- Section 7.2.3: void GaussSeidel(int N, double **A, double *x, double *b, int iterations) function definition
- Section 7.2.5: void SOR(double omega, int N, double **A, double *x, double *b, double abstol) function definition
Go to the file SCchapter7.h for function/class declarations
Go to the file SCchapter7.cpp for function/class definitionsIn 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 |