Parallel Iterative Algorithms: From Sequential to Grid Computing

Series:
Chapman & Hall/CRC Numerical Analysis and Scientific Computing Series
Published:
November 28, 2007 by Chapman and Hall/CRC - 240 Pages
Author(s):
Jacques Mohcine Bahi, University of Franche-Comte, Belfort cedex, France; Sylvain Contassot-Vivier, University of Franche-Comte, Belfort cedex, France; Raphael Couturier, University of Franche-Comte, Belfort cedex, France

Purchasing Options

Hardback
$104.95
Add to cart
ISBN 9781584888086
Cat# C808X
 

Features

  • Shows how iterative algorithms can solve numerical problems and discusses their implementation on parallel and distributed computers
  • Reviews basic convergence results of iterative algorithms
  • Explores the advantages of asynchronism, such as reducing the effect of bottlenecks and the synchronization penalty
  • Analyzes numerous experiments in various computational contexts for linear and nonlinear numerical problems
  • Contains several exercises at the end of most chapters as well as an appendix of mathematical results at the end of the book

    • Summary

    Focusing on grid computing and asynchronism, Parallel Iterative Algorithms explores the theoretical and practical aspects of parallel numerical algorithms. Each chapter contains a theoretical discussion of the topic, an algorithmic section that fully details implementation examples and specific algorithms, and an evaluation of the advantages and drawbacks of the algorithms. Several exercises also appear at the end of most chapters.

    The first two chapters introduce the general features of sequential iterative algorithms and their applications to numerical problems. The book then describes different kinds of parallel systems and parallel iterative algorithms. It goes on to address both linear and nonlinear parallel synchronous and asynchronous iterative algorithms for numerical computation, with an emphasis on the multisplitting approach. The final chapter discusses the features required for efficient implementation of asynchronous iterative algorithms.

    Providing the theoretical and practical knowledge needed to design and implement efficient parallel iterative algorithms, this book illustrates how to apply these algorithms to solve linear and nonlinear numerical problems in parallel environments, including local, distant, homogeneous, and heterogeneous clusters.

    Table of Contents

    INTRODUCTION

    ITERATIVE ALGORITHMS
    Basic theory
    Sequential iterative algorithms
    A classical illustration example

    ITERATIVE ALGORITHMS AND APPLICATIONS TO NUMERICAL PROBLEMS
    Systems of linear equations
    Nonlinear equation systems
    Exercises

    PARALLEL ARCHITECTURES AND ITERATIVE ALGORITHMS
    Historical context
    Parallel architectures
    Trends of used configurations
    Classification of parallel iterative algorithms

    SYNCHRONOUS ITERATIONS
    Parallel linear iterative algorithms for linear systems
    Nonlinear systems: parallel synchronous Newton-multisplitting algorithms
    Preconditioning
    Implementation
    Convergence detection
    Exercises

    ASYNCHRONOUS ITERATIONS
    Advantages of asynchronous algorithms
    Mathematical model and convergence results
    Convergence situations
    Parallel asynchronous multisplitting algorithms
    Coupling Newton and multisplitting algorithms
    Implementation
    Convergence detection
    Exercises

    PROGRAMMING ENVIRONMENTS AND EXPERIMENTAL RESULTS
    Implementation of AIAC algorithms with nondedicated environments
    Two environments dedicated to asynchronous iterative algorithms
    Ratio between computation time and communication time
    Experiments in the context of linear systems
    Experiments in the context of partial differential equations using a finite difference scheme

    APPENDIX: DIAGONAL DOMINANCE AND IRREDUCIBLE MATRICES
    Z-matrices, M-matrices, and H-matrices
    Perron-Frobenius theorem
    Sequences and sets

    REFERENCES
    INDEX

    Editorial Reviews

    "In Parallel Iterative Algorithms: From Sequential to Grid Computing, Bahi, Contassot-Vivier, and Couturier bring mathematical formalism to the study of parallel iterative solution techniques, creating a book that will be useful to those with a strong maths background who are making the transition into parallel scientific computing. … a great fit as a part of a graduate-level course on scientific computing in the math department, or for those already in scientific computing seeking to understand the key mathematical foundations of the analysis of iterative techniques. … The authors execute their mission well, making sure that they treat the mathematical theory of each method in just enough detail to be complete. … The combination of the theory and the implementation is valuable, and I found it illuminating to revisit algorithms I only knew at an implementation level from the mathematical perspective and to understand the reasons behind behaviors I had always taken as given. … a nice addition to your HPC bookshelf in that it brings a strong focus on mathematical formalism, which is often lacking in more computing-oriented approaches to numerical methods. … the book is loaded with citations, and readers looking for a different point of view or for more in depth material on a particular point will find a wealth of pointers to the literature."
    —John West, HPCwire, February 2009

    "On the whole, an interesting and useful book on an up-to-date topic."

    – Gisbert Stoyan, in Zentralblatt Math, 2009

     

    Related Titles