Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Parallel and distributed computation: numerical methods
Bertsekas D., Tsitsiklis J., Prentice-Hall, Inc., Upper Saddle River, NJ, 1989. Type: Book (9789780136487005)
Date Reviewed: Apr 1 1990

This major work of exceptional scholarship summarizes more than three decades of research into general-purpose algorithms for solving systems of equations and optimization problems. Of course, as the title implies, the focus is on parallel and distributed implementations of these algorithms; but one of the great strengths of the book is that parallel and distributed algorithms are initially introduced in a general framework that allows them, for the most part, to be seen as natural outgrowths of corresponding serial algorithms, and that allows them to be discussed independent of any specific parallel architecture. The book contains a great deal of material not available elsewhere in book form, and a number of results that have not been published at all. It will be an important reference book for any mathematician, computer scientist, or engineer with more than a passing interest in parallel algorithms, processor networks, numerical methods, or optimization techniques.

The book contains eight chapters: a lengthy (108 pages) introduction followed by four chapters in Part 1 (“Synchronous Algorithms”) and three chapters in Part 2 (“Asynchronous Algorithms”). The introduction presents an analysis of major issues related to parallel and distributed algorithms and their implementations: scheduling of processors, communication among processors, synchronous and asynchronous algorithms, and specific parallel architectures. The authors introduce relaxation methods of the Jacobi and Gauss-Seidel types, which recur frequently throughout the book in various forms and implementations.

Chapter 2, “Algorithms for Systems of Linear Equations and Matrix Inversion,” surveys both direct and iterative methods and includes convergence analyses for the latter. The authors derive complexity bounds for implementation on general parallel systems. They also derive complexity bounds on specific architectures, taking the communication penalty into account.

The first three sections of chapter 3, “Iterative Methods for Nonlinear Problems,” are devoted to existence and convergence results for contraction mappings and for algorithms for constrained and unconstrained optimizations. Section 4 deals with the parallelization of optimization problems and their decomposition into dual problems. Section 5 discusses algorithms for the variational inequality problems and their parallelization.

Chapter 4, “Shortest Paths and Dynamic Programming,” gives a useful comparison of parallel algorithms for the single-destination and all-pairs shortest path problems on various architectures, followed by a discussion of Markovian decision problems, in particular stochastic shortest paths. Chapter 5, “Network Flow Problems,” is the final chapter devoted to synchronous algorithms. It deals primarily with relaxation methods applied to both linear and nonlinear flow problems. In particular, the &egr;-relaxation method is studied in considerable detail.

Chapter 6, “Totally Asynchronous Iterative Algorithms,” introduces the totally asynchronous algorithmic model and proves a general convergence theorem. The authors then apply the model to contraction mappings, the shortest path problem, linear and nonlinear flow problems, and two-point boundary value problems.

In chapter 7, “Partially Asynchronous Iterative Methods,” the authors describe the partially asynchronous algorithmic model and then apply it to a variety of numerical problems. Chapter 8, “Organizing an Asynchronous Network of Processors for Distributed Computation,” covers algorithms for termination detection, deadlock avoidance, resource scheduling, synchronization using rollback, and maintaining communication with a central processor.

These chapters are supplemented by four appendices, which present fundamental results in linear algebra and analysis, graph theory, duality theory, probability theory, and Markov chains.

In a preface, the authors propose the use of their book as a text for two different courses: a course in parallel algorithms for students with some background in numerical methods or optimization algorithms, and a course in numerical methods with an emphasis on parallel algorithms. The book is more suited to the former than to the latter, primarily because the material on parallelism (concentrated in chapters 1 and 8) is presented in a more consistent, clear, and linear fashion. On the other hand, the book contains plenty of material to support a second course in numerical methods, which would include an introduction to parallel and distributed computation.

While the book obviously does not include everything published on parallel and distributed numerical algorithms, the references provide excellent coverage of important research of the last three decades. Almost every section contains instructive and challenging problems which form an integral part of, or cast light on, the main development. The use of figures to illustrate ideas and examples, and even to assist in establishing results, is a pervasive and particularly effective feature of the text. The material has been proofread exceptionally well: I was able to locate only a few minor typos in more than 700 pages. The only significant mathematical error I was able to find was also small: on page 74 no account is taken of the fact that the column storage method requires multinode accumulation of n (rather than k ) terms, but this oversight does not affect the general conclusion of the section.

The book’s defects are minor but should be mentioned. A glossary of notation would have been a significant asset and might have encouraged the authors to take a more comprehensive view of the symbolism adopted throughout the text. For instance, d represents (among other things) dimension and degree, and on page 65 it represents both; the arc set of a digraph is initially A , but then later for a time becomes A. It is difficult in a book of such breadth to standardize the notation or to invent enough mnemonic symbols to represent the quantities which need to be represented, but this aspect is certainly open to improvement in a future edition. More generally, while the exposition is generally clear, there is also evidence that it emerges out of the hurly-burly of either research or the classroom. Terms or symbols are defined, then later redefined as though they were quite new (for example, on page 333, the symbols | N | and | A | are defined, although they have been frequently used before), and fundamental ideas or results are usually carefully explained, but some are dismissed in a few lines (for example, the three shortest path algorithms covered on pages 303–304). In this sense, the book is somewhat uneven.

But these are cavils. This is a superb book. I learned a great deal from it and enjoyed doing so. I am sure that many other students and researchers will enjoy learning from it as well.

Reviewer:  W. F. Smyth Review #: CR113315
Bookmark and Share
 
Numerical Algorithms And Problems (F.2.1 )
 
 
Distributed Systems (D.4.7 ... )
 
 
Parallel Processors (C.1.2 ... )
 
 
Parallelism And Concurrency (F.1.2 ... )
 
 
General (G.0 )
 
Would you recommend this review?
yes
no
Other reviews under "Numerical Algorithms And Problems": Date
On the computational complexity of ordinary differential equations
Ko K. (ed) Information and Control 58(1-3): 157-194, 1984. Type: Article
Jun 1 1985
The computational complexity of simultaneous diophantine approximation problems
Lagarias J. SIAM Journal on Computing 14(1): 196-209, 1985. Type: Article
Jan 1 1986
A fast, reliable algorithm for calculating Padé-Hermite forms
Cabay S., Labahn G.  Symbolic and algebraic computation (, Portland, OR, Jul 17-19, 1989)1001989. Type: Proceedings
Nov 1 1991
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy