Parallel Iterative Algorithms: From Sequential to Grid Computing

by Bahi; Jacques Mohcine

• ISBN13: 9781584888086
• ISBN10: 1584888083
• eBook ISBN(s): 9781040206898
• Format: Hardcover
• Copyright: 2007-11-28
• Publisher: Chapman & Hall/

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

List of Tables	p. ix
List of Figures	p. xi
Acknowledgments	p. xiii
Introduction	p. xv
Iterative Algorithms	p. 1
Basic theory	p. 1
Characteristic elements of a matrix	p. 1
Norms	p. 2
Sequential iterative algorithms	p. 5
A classical illustration example	p. 8
Iterative Algorithms and Applications to Numerical Problems	p. 11
Systems of linear equations	p. 11
Construction and convergence of linear iterative algorithms	p. 11
Speed of convergence of linear iterative algorithms	p. 13
Jacobi algorithm	p. 15
Gauss-Seidel algorithm	p. 17
Successive overrelaxation method	p. 19
Block versions of the previous algorithms	p. 20
Block tridiagonal matrices	p. 22
Minimization algorithms to solve linear systems	p. 24
Preconditioning	p. 33
Nonlinear equation systems	p. 39
Derivatives	p. 40
Newton method	p. 41
Convergence of the Newton method	p. 43
Exercises	p. 45
Parallel Architectures and Iterative Algorithms	p. 49
Historical context	p. 49
Parallel architectures	p. 51
Classifications of the architectures	p. 51
Trends of used configurations	p. 60
Classification of parallel iterative algorithms	p. 61
Synchronous iterations - synchronous communications (SISC)	p. 62
Synchronous iterations - asynchronous communications (SIAC)	p. 63
Asynchronous iterations - asynchronous communications (AIAC)	p. 64
What PIA on what architecture?	p. 68
Synchronous Iterations	p. 71
Parallel linear iterative algorithms for linear systems	p. 71
Block Jacobi and O'Leary and White multisplitting algorithms	p. 71
General multisplitting algorithms	p. 76
Nonlinear systems: parallel synchronous Newton-multisplitting algorithms	p. 79
Newton-Jacobi algorithms	p. 79
Newton-multisplitting algorithms	p. 80
Preconditioning	p. 82
Implementation	p. 82
Survey of synchronous algorithms with shared memory architecture	p. 84
Synchronous Jacobi algorithm	p. 85
Synchronous conjugate gradient algorithm	p. 88
Synchronous block Jacobi algorithm	p. 88
Synchronous multisplitting algorithm for solving linear systems	p. 91
Synchronous Newton-multisplitting algorithm	p. 101
Convergence detection	p. 104
Exercises	p. 107
Asynchronous Iterations	p. 111
Advantages of asynchronous algorithms	p. 112
Mathematical model and convergence results	p. 113
The mathematical model of asynchronous algorithms	p. 113
Some derived basic algorithms	p. 115
Convergence results of asynchronous algorithms	p. 116
Convergence situations	p. 118
The linear framework	p. 118
The nonlinear framework	p. 120
Parallel asynchronous multisplitting algorithms	p. 120
A general framework of asynchronous multisplitting methods	p. 121
Asynchronous multisplitting algorithms for linear problems	p. 124
Asynchronous multisplitting algorithms for nonlinear problems	p. 125
Coupling Newton and multisplitting algorithms	p. 129
Newton-multisplitting algorithms: multisplitting algorithms as inner algorithms in the Newton method	p. 129
Nonlinear multisplitting-Newton algorithms	p. 131
Implementation	p. 131
Some solutions to manage the communications using threads	p. 133
Asynchronous Jacobi algorithm	p. 135
Asynchronous block Jacobi algorithm	p. 135
Asynchronous multisplitting algorithm for solving linear systems	p. 138
Asynchronous Newton-multisplitting algorithm	p. 140
Asynchronous multisplitting-Newton algorithm	p. 142
Convergence detection	p. 145
Decentralized convergence detection algorithm	p. 145
Exercises	p. 169
Programming Environments and Experimental Results	p. 173
Implementation of AIAC algorithms with non-dedicated environments	p. 174
Comparison of the environments	p. 174
Two environments dedicated to asynchronous iterative algorithms	p. 176
JACE	p. 177
CRAC	p. 180
Ratio between computation time and communication time	p. 186
Experiments in the context of linear systems	p. 186
Context of experimentation	p. 186
Comparison of local and distant executions	p. 189
Impact of the computation amount	p. 191
Larger experiments	p. 192
Other experiments in the context of linear systems	p. 193
Experiments in the context of partial differential equations using a finite difference scheme	p. 196
Appendix	p. 201
Diagonal dominance. Irreducible matrices	p. 201
Z-matrices, M-matrices and H-matrices	p. 202
Perron-Frobenius theorem	p. 203
Sequences and sets	p. 203
References	p. 205
Index	p. 215
Table of Contents provided by Ingram. All Rights Reserved.