Parallel and Distributed Computation: Numerical Methods

Dimitri P. Bertsekas and John N. Tsitsiklis

Click here to obtain a searchable electronic version of the book from Google Play.

The hardcover version can be purchased from Athena Scientific. The book (including the solutions manual) can be freely downloaded from MIT, or from Athena Scientific.

Click here for a survey containing followup research, and for a related subsequent paper.

For further discussions of asynchronous algorithms in specialized contexts based on material from this book, see the books Nonlinear Programming, 3rd edition, Athena Scientific, 2016; Convex Optimization Algorithms, Athena Scientific, 2015; and Abstract Dynamic Programming, 2nd edition, Athena Scientific, 2018;

The book is a comprehensive and theoretically sound treatment of parallel and distributed numerical methods. It focuses on algorithms that are naturally suited for massive parallelization, and it explores the fundamental convergence, rate of convergence, communication, and synchronization issues associated with such algorithms.

Reviews :

"This major contribution to the literature belongs on the bookshelf of every scientist with an interest in computational science, directly beside Knuth's three volumes and Numerical Recipes..."
Anna Nagurney, University of Massachusetts, in the International Journal of Supercomputer Applications

"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."
W. F. Smyth, in Computing Reviews

"This book marks an important landmark in the theory of distributed systems and I highly recommend it to students and practicing engineers in the fields of operations research and computer science, as well as to mathematicians interested in numerical methods."
Lorne G. Mason, in IEEE Communications Magazine

Parallel and Distributed Computation: Numerical Methods

Table of Contents:

  1. Introduction

    1. Parallel and distributed architectures
      1. The need for parallel and distributed computation
      2. Parallel computing systems and their classification
    2. Models, complexity measures, and some simple algorithms
      1. Models
      2. Complexity measures
      3. Examples: Vector, and matrix computations
      4. Parallelization of iterative methods
    3. Communication aspects of parallel and distributed systems
      1. Communication links
      2. Data link control
      3. Routing
      4. Network topologies
      5. Concurrency and communication tradeoffs
      6. Examples of matrix-vector calculations
    4. Synchronization issues in parallel and distributed algorithms
      1. Synchronous algorithms
      2. Asynchronous algorithms and the reduction of the synchronization penalty


    PART I: SYNCHRONOUS ALGORITHMS


  2. Algorithms for Systems of Linear Equations and Matrix Inversion

    1. Parallel algorithms for linear systems with special structure
      1. Triangular matrices and back substitution
      2. Tridiagonal sytems and odd-even reduction
    2. Parallel direct methods for general linear equations
      1. Gaussian elimination
      2. Triangularization using Givens rotations
    3. A fast direct matrix inversion algorithm
    4. Classical iterative methods for systems of linear equations
    5. Parallel implementation of classical iterative methods
      1. An example: Poisson's equation
      2. Multigrid methods
    6. Convergence analysis of classical iterative methods
      1. Background on maximum norms and nonnegative matrices
      2. Convergence analysis using maximum norms
      3. Convergence analysis using a quadratic cost function
      4. The Poisson equation revisited
    7. The conjugate gradient method
      1. Description of the algorithm
      2. Speed of convergence
      3. Preconditioned conjugate gradient method
      4. Parallel implementation
    8. Computation of the invariant distribution of a Markov chain
    9. Fast iterative matrix inversion

  3. Iterative Methods for Nonlinear Problems

    1. Contraction mappings
      1. General results
      2. Contractions over Cartesian product sets
      3. Some useful contraction mappings
    2. Unconstrained optimization
      1. The main algorithms
      2. Convergence analysis using the descent approach
      3. The case of a convex cost function
      4. Nonlinear algorithms
    3. Constrained convex optimization
      1. Optimality conditions and the projection theorem
      2. The gradient projection algorithm
      3. Scaled gradient projection algorithms
      4. The case of a product constraint set: parallel implementations
      5. Nonlinear agorithms
    4. Parallelization and decomposition of optimization problems
      1. Quadratic programming
      2. Separable stritly convex programming
      3. The proximal minimization algorithm
      4. Augmented Lagrangian methods
    5. Algorithms for variational inequalities
      1. Examples of variational inequality problems
      2. Preliminaries
      3. The projection algorithm
      4. Linearized algorithms
      5. The Cartesian product case: Parallel implementations
      6. Nonlinear algorithms
      7. Decomposition methods for variational inequalities

  4. Shortest Paths and Dynamic Programming

    1. The shortest path problem
      1. The Bellman-Ford algorithm
      2. Other parallel shortest path methods
    2. Markov chains with transition costs
    3. Markovian decision problems
      1. Discounted problems
      2. Undiscounted problems - Stochastic shortest paths
      3. Parallel implementation of the Dynamic Programming iteration

  5. Network Flow Problems

    1. The linear network flow problem and its dual
    2. The relaxation method
      1. Application to the shortest path problem
      2. Multiple node relaxation method
    3. The epsilon-relaxation method
      1. The auction algorithm for the assignment problem
      2. Parallel versions of the epsilon-relaxation and the auction algorithms
    4. Complexity analysis of the epsilon-relaxation method and its scaled version
      1. The scaled version of the algorithm
      2. Application to the assignment problem
    5. Network flow problems with strictly convex cost
      1. The relaxation method
      2. Convergence analysis
      3. The problem without arc flow bounds
      4. An example: Constrained matrix problems
      5. Parallel implementations of the relaxation method
    6. Nonlinear multicommodity flow problems - Routing applications


    PART II: ASYNCHRONOUS ALGORITHMS


  6. Totally Asynchronous Iterative Methods

    1. The totally asynchronous algorithmic model
    2. A general convergence theorem
    3. Applications to problems involving maximum norm contraction mappings
      1. Solution of linear systems of equations
      2. Unconstrained optimization
      3. Constrained optimization and variational inequalities
      4. Dynamic programming
      5. Convergence rate comparison of synchronous and asynchronous algorithms
    4. Applications to monotone mappings and the shortest path problem
    5. Linear network flow problems
    6. Nonlinear network flow problems
    7. Asynchronous relaxation for ordinary differential equations and two--point boundary value problems
      1. The asynchronous relaxation algorithm
      2. Two-point boundary value problems
      3. The discrete time case

  7. Partially Asynchronous Iterative Methods

    1. The partially asynchronous algorithmic model
    2. Algorithms for fixed points of nonexpansive mappings
      1. A convergence result
      2. Weakly diagonally dominant systems of linear equations
      3. Strictly convex network flow problems
    3. Algorithms for agreement and for Markov chain problems
      1. The agreement algorithm
      2. An asynchronous algorithm for the invariant distribution of a Markov chain
    4. Load balancing in a computer network
    5. Gradient-like optimization algorithms
      1. The algorithm and its convergence
      2. The role of the various parameters
      3. Block - iterative algorithms
      4. Gradient projection algorithms
    6. Distributed asynchronous routing in data networks
      1. Problem definition
      2. The algorihm and its convergence
      3. Discussion
    7. A model in which several processors may update the same variables
    8. Stochastic gradient algorithms
      1. Description of the algorithm and assumptions
      2. A convergence result
      3. Discussion and extensions

  8. Organizing an Asynchronous Network of Processors for Distributed Computation

    1. Detecting termination of a distributed algorithm
    2. Snapshots
    3. Resource scheduling
    4. Synchronization using rollback: asynchronous simulation
    5. Maintaining communication with a center

  9. APPENDIXES

    1. Appendix A: Linear algebra and analysis
    2. Appendix B: Graph theory
    3. Appendix C: Optimization and duality theory
    4. Appendix D: Probability theory and Markov chains