Parallel Algorithms for Numerical Linear Algebra (eBook)

P. van Dooren, H. van der Vorst (Herausgeber)

eBook Download: PDF

2014 | 1. Auflage
338 Seiten
Elsevier Science (Verlag)
978-1-4832-9573-2 (ISBN)

Infos

This is the first in a new series of books presenting research results and developments concerning the theory and applications of parallel computers, including vector, pipeline, array, fifth/future generation computers, and neural computers.All aspects of high-speed computing fall within the scope of the series, e.g. algorithm design, applications, software engineering, networking, taxonomy, models and architectural trends, performance, peripheral devices.Papers in Volume One cover the main streams of parallel linear algebra: systolic array algorithms, message-passing systems, algorithms for parallel shared-memory systems, and the design of fast algorithms and implementations for vector supercomputers.

Inhalt

Front Cover 1
Parallel Algorithms for Numerical Linear Algebra 4
Copyright Page 5
Table of Contents 10
Preface 8
Part 1: Systolic array algorithms 12
Chapter 1. A quadratically convergent parallel Jacobi process for diagonally dominant matrices with distinct eigenvalues 14
1. Introduction 14
2. Parallel annihilators the first step
3. The effect of a complete sweep 20
4. Numerical examples 24
5. Conclusions 26
References 26
Chapter 2. A Jacobi-like algorithm for computing the generalized Schur form of a regular pencil 28
1. Introduction 28
2. Normal pencils 30
3. Description of the method 32
4. Global convergence 35
5. Ultimate convergence 38
6. Numerical tests 42
7. Conclusion 45
References 46
Chapter 3. Canonical correlations and generalized SVD: applications and new algorithms 48
1. Introduction 48
2. Applications 52
3. SVD of products of three matrices 54
4. New algorithms 57
5. Final remarks 62
Acknowledgements 62
References 62
Chapter 4. From Bareiss' algorithm to the stable computation of partial correlations 64
1. Introduction 64
2. The Generalized Bareiss algorithm 66
3. Cybenko's algorithm 76
4. The Hyperbolic Cholesky algorithm 78
5. Application to the computation of certain sample partial correlations 84
6. Computation of arbitrary partial correlations 90
7. Conclusions 100
Acknowledgement 101
References 101
Part 2: Message-passing systems 104
Chapter 5. A recursive doubling algorithm for solution of tridiagonal systems on hypercube multiprocessors 106
1. Introduction 106
2. The LU decomposition algorithm 108
3. Solution of tridiagonal systems using prefix algorithms 108
4. Parallel prefix algorithms on hypercube multiprocessors 111
5. Estimated speedup and efficiency 115
6. Experimental results and conclusions 116
References 119
Chapter 6. Least squares modifications with inverse factorizations: parallel implications 120
1. Introduction 120
2. Updating R–1 125
3. Downdating R–1 130
4. Summary and parallel implications 135
Acknowledgements 136
References 136
Chapter 7. Solution of sparse positive definite systems on a hypercube 140
1. Introduction 140
2. Solution of sparse symmetric positive definite systems 141
3. Parallel Cholesky factorization 144
4. Symbolic factorization 152
5. Sparse triangular solution 156
6. Ordering 160
7. Some experiments and concluding remarks 163
References 165
Chapter 8. Some aspects of parallel implementation of the finite-element method on message passing architectures 168
1. Introduction 168
2. The model problem and finite-element discretization 170
3. Overview of computations 172
4. Cost analysis 174
5. Numerical experiments 182
6. Conclusions 190
Appendix 191
References 197
Part 3: Algorithms for parallel shared-memory systems 200
Chapter 9. An overview of parallel algorithms for the singular value and symmetric eigenvalue problems 202
1. Introduction 202
2. Jacobi methods 204
3. Reduction to tridiagonal form and multisectioning 210
4. Performance of eigensolvers 213
5. Singular value decomposition 216
6. Performance of SVD algorithms 220
7. Conclusions 222
Acknowledgements 223
References 223
Chapter 10. Block reduction of matrices to condensed forms for eigenvalue computations 226
1. Introduction 226
2. The algorithm: reduction to tridiagonal form 227
3. Reduction to Hessenberg form 230
4. Reduction to bidiagonal form 230
5. Relationship to the WY-factorization 233
6. Pipelining reduction to condensed form with determination of eigenvalues 234
7. Operations counts and storage 237
8. Experimental results 237
References 238
Chapter 11. Multiprocessing a sparse matrix code on the Alliant FX/8 240
1. Introduction 240
2. Alliant FX/8 241
3. Multifrontal codes and elimination trees 242
4. Data management issues 243
5. Task spawning and granularity 245
6. Management of work queue and performance of code 246
7. Use of the SCHEDULE package 248
8. Conclusions 249
Acknowledgements 250
References 250
Chapter 12. Vector and parallel methods for the direct solution of Poisson's equation 252
1. Introduction 252
2. Parallel communication algorithms 254
3. The FFT 257
4. Tridiagonal solvers 260
5. Direct methods for solving Poisson's equation 267
References 273
Part 4: Design of fast algorithms and implementations for vector supercomputers 276
Chapter 13. Factoring with the quadratic sieve on large vector computers 278
1. Introduction 278
2. The multiple polynomial quadratic sieve 280
3. Implementation of the MPQS-algorithm on the CYBER 205 and the NEC SX-2 283
4. Results 284
5. Conclusions 286
Note added in proof 288
Acknowledgements 288
References 288
Chapter 14. Efficient vectorizable PDE solvers 290
1. Introduction 290
2. Families of difference and error formulas 291
3. The error-equation and its consequences 293
4. Linear solver and vectorization 297
5. The FIDISOL program package 302
6. Examples 305
7. Concluding remarks 307
Acknowledgements 307
References 308
Chapter 15. Vectorizable preconditioners for elliptic difference equations in three space dimensions 310
1. Introduction 310
2. Factorization of matrices partitioned in block tridiagonal form 311
3. Limit matrix analysis of preconditioning matrices 316
4. Plane block factorizations 325
5. Numerical results 327
6. Conclusions 330
Acknowledgement 331
References 331
Chapter 16. Solving 3D block bidiagonal linear systems on vector computers 334
1. A sketch of the problem 334
2. Vectorization techniques 335
3. Implementations of the hyperplane ordering for the CYBER 205 337
4. Preconditioned linear systems and Eisenstat's trick 339
5. Examples 341
References 341

Produkt-Details

• Erscheint lt. Verlag: 28.6.2014
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Netzwerke
• Themenwelt: Mathematik / Informatik ► Informatik ► Theorie / Studium
• Themenwelt: Informatik ► Weitere Themen ► Hardware
• Themenwelt: Mathematik / Informatik ► Mathematik ► Angewandte Mathematik
• ISBN-10: 1-4832-9573-7 / 1483295737
• ISBN-13: 978-1-4832-9573-2 / 9781483295732