We have already discussed how to solve tridiagonal linear systems of equations using direct solvers (the Thomas algorithm) in chapter 6 and some iterative solvers (Jacobi, Gauss-Seidel, SOR and multigrid) in chapter 7. We have also discussed solutions of nonlinear and linear systems and have introduced the conjugate gradient method in chapter 4. In the current chapter we revisit this subject and present general algorithms for the direct and iterative solution of large linear systems. We start with the classical Gaussian elimination (which is a fast solver!) and then proceed with more sophisticated solvers and preconditioners for symmetric and non-symmetric systems.
In parallel computing, we introduce the broadcasting command MPI_Bcast, and demonstrate its usefulness in the context of Gaussian elimination. In addition, we reiterate the use of MPI_Send, MPI_Recv, MPI_Allgather, and MPI_Allreduce through example implementations of algorithms presented in this chapter.
- Section 9.1.2: void GaussElimination(SCMatrix &A, SCVector &b, int pivotflag) function definition
- Section 9.3.1: void Hessenberg(SCMatrix &A) function definition
- Section 9.5.1: void ModifiedArnoldi(int m, const SCMatrix &A, SCMatrix &H, SCMatrix &V) function definition
- Section 9.5.3: void GMRES(int m, const SCMatrix &A, const SCVector &b, SCVector &x) function definition
Go to the file SCchapter9.h for function/class declarations
Go to the file SCchapter9.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 9.1.4: MPI - Program demonstrating parallel Gaussian elimination | chapter9c0P.cpp |
Section 9.1.6: Program demonstrating cyclic reduction for triadiagonal systems | chapter9c1.cpp |
Section 9.1.6: MPI - Program demonstrating parallel cyclic reduction for triadiagonal systems | chapter9c2P.cpp |
Section 9.4.4: MPI - Program demonstrating the parallel preconditioned conjugate gradient method (PCGM) | chapter9c3P.cpp |