Suchen und Finden
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
16
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
Alle Preise verstehen sich inklusive der gesetzlichen MwSt.