Parallel Iterative Algorithms from Sequential to Grid Computing

Contents
List of Tables ix
List of Figures xi
Acknowledgments xiii
Introduction xv
1 Iterative Algorithms 1
1.1 Basic theory . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Characteristic elements of a matrix . . . . . . . . . . . 1
1.1.2 Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Sequential iterative algorithms . . . . . . . . . . . . . . . . . 5
1.3 A classical illustration example . . . . . . . . . . . . . . . . . 8
2 Iterative Algorithms and Applications to Numerical Prob-
lems 11
2.1 Systems of linear equations . . . . . . . . . . . . . . . . . . . 11
2.1.1 Construction and convergence of linear iterative algo-
rithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.2 Speed of convergence of linear iterative algorithms . . 13
2.1.3 Jacobi algorithm . . . . . . . . . . . . . . . . . . . . . 15
2.1.4 Gauss-Seidel algorithm . . . . . . . . . . . . . . . . . . 17
2.1.5 Successive overrelaxation method . . . . . . . . . . . . 19
2.1.6 Block versions of the previous algorithms . . . . . . . 20
2.1.7 Block tridiagonal matrices . . . . . . . . . . . . . . . . 22
2.1.8 Minimization algorithms to solve linear systems . . . . 24
2.1.9 Preconditioning . . . . . . . . . . . . . . . . . . . . . . 33
2.2 Nonlinear equation systems . . . . . . . . . . . . . . . . . . . 39
2.2.1 Derivatives . . . . . . . . . . . . . . . . . . . . . . . . 40
2.2.2 Newton method . . . . . . . . . . . . . . . . . . . . . 41
2.2.3 Convergence of the Newton method . . . . . . . . . . 43
2.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3 Parallel Architectures and Iterative Algorithms 49
3.1 Historical context . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2 Parallel architectures . . . . . . . . . . . . . . . . . . . . . . 51
3.2.1 Classifications of the architectures . . . . . . . . . . . 51
3.3 Trends of used configurations . . . . . . . . . . . . . . . . . . 60
3.4 Classification of parallel iterative algorithms . . . . . . . . . 61
3.4.1 Synchronous iterations - synchronous communications
(SISC) . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.4.2 Synchronous iterations - asynchronous communications
(SIAC) . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.4.3 Asynchronous iterations - asynchronous communications
(AIAC) . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.4.4 What PIA on what architecture? . . . . . . . . . . . . 68
4 Synchronous Iterations 71
4.1 Parallel linear iterative algorithms for linear systems . . . . . 71
4.1.1 Block Jacobi and O’Leary and White multisplitting al-
gorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.1.2 General multisplitting algorithms . . . . . . . . . . . . 76
4.2 Nonlinear systems: parallel synchronous Newton-multisplitting
algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.2.1 Newton-Jacobi algorithms . . . . . . . . . . . . . . . . 79
4.2.2 Newton-multisplitting algorithms . . . . . . . . . . . . 80
4.3 Preconditioning . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.4 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.4.1 Survey of synchronous algorithms with shared memory
architecture . . . . . . . . . . . . . . . . . . . . . . . . 84
4.4.2 Synchronous Jacobi algorithm . . . . . . . . . . . . . . 85
4.4.3 Synchronous conjugate gradient algorithm . . . . . . . 88
4.4.4 Synchronous block Jacobi algorithm . . . . . . . . . . 88
4.4.5 Synchronous multisplitting algorithm for solving linear
systems . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.4.6 Synchronous Newton-multisplitting algorithm . . . . . 101
4.5 Convergence detection . . . . . . . . . . . . . . . . . . . . . . 104
4.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5 Asynchronous Iterations 111
5.1 Advantages of asynchronous algorithms . . . . . . . . . . . . 112
5.2 Mathematical model and convergence results . . . . . . . . . 113
5.2.1 The mathematical model of asynchronous algorithms . 113
5.2.2 Some derived basic algorithms . . . . . . . . . . . . . 115
5.2.3 Convergence results of asynchronous algorithms . . . . 116
5.3 Convergence situations . . . . . . . . . . . . . . . . . . . . . 118
5.3.1 The linear framework . . . . . . . . . . . . . . . . . . 118
5.3.2 The nonlinear framework . . . . . . . . . . . . . . . . 120
5.4 Parallel asynchronous multisplitting algorithms . . . . . . . . 120
5.4.1 A general framework of asynchronous multisplitting meth-
ods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.4.2 Asynchronous multisplitting algorithms for linear prob-
lems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.4.3 Asynchronous multisplitting algorithms for nonlinear
problems . . . . . . . . . . . . . . . . . . . . . . . . . 125
5.5 Coupling Newton and multisplitting algorithms . . . . . . . 129
5.5.1 Newton-multisplitting algorithms: multisplitting algo-
rithms as inner algorithms in the Newton method . . 129
5.5.2 Nonlinear multisplitting-Newton algorithms . . . . . . 131
5.6 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . 131
5.6.1 Some solutions to manage the communications using
threads . . . . . . . . . . . . . . . . . . . . . . . . . . 133
5.6.2 Asynchronous Jacobi algorithm . . . . . . . . . . . . . 135
5.6.3 Asynchronous block Jacobi algorithm . . . . . . . . . 135
5.6.4 Asynchronous multisplitting algorithm for solving linear
systems . . . . . . . . . . . . . . . . . . . . . . . . . . 138
5.6.5 Asynchronous Newton-multisplitting algorithm . . . . 140
5.6.6 Asynchronous multisplitting-Newton algorithm . . . . 142
5.7 Convergence detection . . . . . . . . . . . . . . . . . . . . . . 145
5.7.1 Decentralized convergence detection algorithm . . . . 145
5.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
6 Programming Environments and Experimental Results 173
6.1 Implementation of AIAC algorithms with non-dedicated envi-
ronments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
6.1.1 Comparison of the environments . . . . . . . . . . . . 174
6.2 Two environments dedicated to asynchronous iterative algo-
rithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
6.2.1 JACE . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
6.2.2 CRAC . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
6.3 Ratio between computation time and communication time . 186
6.4 Experiments in the context of linear systems . . . . . . . . . 186
6.4.1 Context of experimentation . . . . . . . . . . . . . . . 186
6.4.2 Comparison of local and distant executions . . . . . . 189
6.4.3 Impact of the computation amount . . . . . . . . . . . 191
6.4.4 Larger experiments . . . . . . . . . . . . . . . . . . . . 192
6.4.5 Other experiments in the context of linear systems . . 193
6.5 Experiments in the context of partial differential equations us-
ing a finite difference scheme . . . . . . . . . . . . . . . . . . 196
Appendix 201
A-1 Diagonal dominance. Irreducible matrices . . . . . . . . . . . 201
A-1.1 Z-matrices, M-matrices and H-matrices . . . . . . . . 202
A-1.2 Perron-Frobenius theorem . . . . . . . . . . . . . . . . 203
A-1.3 Sequences and sets . . . . . . . . . . . . . . . . . . . . 203
References 205

Another Grid Computing
Download