One possibility is a course targeted on parallel algorithms, and intended for students who already have some knowledge of a subset of the fields of numerical analysis, graph theory, and optimization algorithms. Another possibility is a general course on numerical methods with a strong bias towards parallelizable algorithms. The book lends itself for such a course because it develops economically a broad variety of self-contained basic material in considerable depth. Chapter 1 contains an exposition of some generic issues that arise in a broad variety of parallel algorithms and are best addressed without specific reference to any particular algorithm. In particular, we discuss the scheduling of a set of processors for the parallel execution of a prescribed algorithm, some basic issues relating to interprocessor communication and the effects of the communication penalty on the amount by which an algorithm can be speeded up.
Special attention is paid on a few interesting architectures such as mesh and hypercube.
We then consider issues of synchronization, and we contrast synchronous and asynchronous algorithms. In this chapter, we also introduce briefly relaxation methods of the Gauss-Seidel and Jacobi type and some of their associated issues of parallelization, communication, and synchronization that are recurring themes throughout the book. Chapter 2 deals with parallel algorithms for systems of linear equations and matrix inversion. It covers direct methods, for general systems as well as systems with special structure, iterative methods, including their convergence analysis, and the conjugate gradient method. Chapter 3 is devoted to iterative methods for nonlinear problems, such as finding fixed points of contraction mappings, unconstrained and constrained optimization, and variational inequalities.