Parallel iterative algorithms. From sequential to grid computing. (English) Zbl 1153.65004

Bahi, Jacques Mohcine; Contassot-Vivier, Sylvain; Couturier, Raphaël

Chapman & Hall/CRC Numerical Analysis and Scientific Computing. Boca Raton, FL: Chapman & Hall/CRC (ISBN 978-1-58488-808-6/hbk; 978-1-58488-809-3/ebook). xviii, 217 p. (2008).

This book is on the theory and implementation of multisplitting methods for the solution of large linear systems on clusters and systems of clusters (i.e., grids) of computers. It contains on its 217 pages the chapters iterative algorithms, iterative algorithms and applications to numerical problems, parallel architectures and iterative algorithms, synchronous iterations, asynchronous iterations, programming environments and experimental results, and an appendix (on matrix properties and on sequences and convergence). The first two chapters remind the reader of the classical books by R.S. Varga [Matrix iterative analysis. 2nd revised and expanded ed. Berlin: Springer (2000; Zbl 0998.65505)] and W.C. Rheinboldt and J.M. Ortega [Iterative solution of nonlinear equations in several variables. New York-London: Academic Press (1970; Zbl 0241.65046)] (showing also material on nonlinear systems by detailing the Newton method), or O. Axelsson [Iterative solution methods. Cambridge: Cambridge University Press (1994; Zbl 0795.65014)]. These two chapters and their exercises feature a classical math style. Whereas the conjugate gradient method is considered yet, regretfully its bicgstab variant already is missing. Later, in Section 5.6, one gets a hint why, since there follows the explanation that, essentially, only the parallel versions of block-Jacobi iterations (i.e., multisplitting methods) are suitable in the asynchronous mode of grids.
With Chapter 3, the book switches to an informatics style of presentation which is characterized by much words, figures on computer and processor constellations, and by useful pseudo-code algorithms. Here, the reader gets much fresh information on modern computer developments and the organisation of computations on systems of computer clusters. A considerable amount of trendy abbreviations appears several of which are not included into the index, and some are not explained at all or at the place of their first appearance.
Chapters 4 and 5 feature a wealth of pseudo-code algorithms which should facilitate the implementation. In the latter chapter, Section 5.7 with its 25 pages on convergence detection for asynchronous iterations running on grids is, surely, the culmination of the book containing as well a validity proof of a theoretical version of convergence detection as a practical version where a spanning tree for the grid becomes important. However, when touching the convergence detection first time in Section 4.5, I wonder that the authors confine themselves to consider the distance between the old and new iteration vector (called by them “residual”) as the single measure of convergence. Did they never hear of or experience themselves complete stalling of iterations in situations where theoretically convergence is guaranteed? Chapter 6 is decisive for the whole book with its report on a specific French nation-wide grid and details of experiments on the solution of systems of sparse equations in some ten millions of unknowns. But this report appears to have been a separate (French) report which has not been integrated fully into the book. Say, in Section 3.4, or, especially in 3.4.4, a reference to the outcome of this final chapter would have been mandatory when arguing in favour of asynchronous algorithms. In the references, it is a pleasure to see fresh sources until 2007 included - and regretable that all the 3 German titles cited are written with several misprints. On the whole, an interesting and (inspite of our criticism) useful book on an up-to-date topic.

Reviewer: Gisbert Stoyan (Budapest)

MSC:

65-02	Research exposition (monographs, survey articles) pertaining to numerical analysis
65F10	Iterative numerical methods for linear systems
65H10	Numerical computation of solutions to systems of equations

Keywords:

iterative solution; systems of linear equations; systems of nonlinear equations; block-Jacobi; multisplitting algorithms; convergence; parallel computation; multisplitting methods; numerical examples; textbook

Citations:

Zbl 0998.65505; Zbl 0241.65046; Zbl 0795.65014

Software:

MPI; SparseMatrix; SuperLU-DIST; na10