Vorst / Dooren Parallel Algorithms for Numerical Linear Algebra

1. Auflage 2014
ISBN: 978-1-4832-9573-2
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band Volume 1, 338 Seiten, Web PDF

Reihe: Advances in Parallel Computing

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.

Autoren/Hrsg.

Vorst, H. van der

Dooren, P. van

Inhaltsverzeichnis

1;Front Cover;1
2;Parallel Algorithms for Numerical Linear Algebra;4
3;Copyright Page;5
4;Table of Contents;10
5;Preface;8
6;Part 1: Systolic array algorithms;12
6.1;Chapter 1. A quadratically convergent parallel Jacobi process for diagonally dominant matrices with distinct eigenvalues;14
6.1.1;1. Introduction;14
6.1.2;2. Parallel annihilators; the first step;16
6.1.3;3. The effect of a complete sweep;20
6.1.4;4. Numerical examples;24
6.1.5;5. Conclusions;26
6.1.6;References;26
6.2;Chapter 2. A Jacobi-like algorithm for computing the generalized Schur form of a regular pencil;28
6.2.1;1. Introduction;28
6.2.2;2. Normal pencils;30
6.2.3;3. Description of the method;32
6.2.4;4. Global convergence;35
6.2.5;5. Ultimate convergence;38
6.2.6;6. Numerical tests;42
6.2.7;7. Conclusion;45
6.2.8;References;46
6.3;Chapter 3. Canonical correlations and generalized SVD: applications and new algorithms;48
6.3.1;1. Introduction;48
6.3.2;2. Applications;52
6.3.3;3. SVD of products of three matrices;54
6.3.4;4. New algorithms;57
6.3.5;5. Final remarks;62
6.3.6;Acknowledgements;62
6.3.7;References;62
6.4;Chapter 4. From Bareiss' algorithm to the stable computation of partial correlations;64
6.4.1;1. Introduction;64
6.4.2;2. The Generalized Bareiss algorithm;66
6.4.3;3. Cybenko's algorithm;76
6.4.4;4. The Hyperbolic Cholesky algorithm;78
6.4.5;5. Application to the computation of certain sample partial correlations;84
6.4.6;6. Computation of arbitrary partial correlations;90
6.4.7;7. Conclusions;100
6.4.8;Acknowledgement;101
6.4.9;References;101
7;Part 2: Message-passing systems;104
7.1;Chapter 5. A recursive doubling algorithm for solution of tridiagonal systems on hypercube multiprocessors;106
7.1.1;1. Introduction;106
7.1.2;2. The LU decomposition algorithm;108
7.1.3;3. Solution of tridiagonal systems using prefix algorithms;108
7.1.4;4. Parallel prefix algorithms on hypercube multiprocessors;111
7.1.5;5. Estimated speedup and efficiency;115
7.1.6;6. Experimental results and conclusions;116
7.1.7;References;119
7.2;Chapter 6. Least squares modifications with inverse factorizations: parallel implications;120
7.2.1;1. Introduction;120
7.2.2;2. Updating R–1;125
7.2.3;3. Downdating R–1;130
7.2.4;4. Summary and parallel implications;135
7.2.5;Acknowledgements;136
7.2.6;References;136
7.3;Chapter 7. Solution of sparse positive definite systems on a hypercube;140
7.3.1;1. Introduction;140
7.3.2;2. Solution of sparse symmetric positive definite systems;141
7.3.3;3. Parallel Cholesky factorization;144
7.3.4;4. Symbolic factorization;152
7.3.5;5. Sparse triangular solution;156
7.3.6;6. Ordering;160
7.3.7;7. Some experiments and concluding remarks;163
7.3.8;References;165
7.4;Chapter 8. Some aspects of parallel implementation of the finite-element method on message passing architectures;168
7.4.1;1. Introduction;168
7.4.2;2. The model problem and finite-element discretization;170
7.4.3;3. Overview of computations;172
7.4.4;4. Cost analysis;174
7.4.5;5. Numerical experiments;182
7.4.6;6. Conclusions;190
7.4.7;Appendix;191
7.4.8;References;197
8;Part 3: Algorithms for parallel shared-memory systems;200
8.1;Chapter 9. An overview of parallel algorithms for the singular value and symmetric eigenvalue problems;202
8.1.1;1. Introduction;202
8.1.2;2. Jacobi methods;204
8.1.3;3. Reduction to tridiagonal form and multisectioning;210
8.1.4;4. Performance of eigensolvers;213
8.1.5;5. Singular value decomposition;216
8.1.6;6. Performance of SVD algorithms;220
8.1.7;7. Conclusions;222
8.1.8;Acknowledgements;223
8.1.9;References;223
8.2;Chapter 10. Block reduction of matrices to condensed forms for eigenvalue computations;226
8.2.1;1. Introduction;226
8.2.2;2. The algorithm: reduction to tridiagonal form;227
8.2.3;3. Reduction to Hessenberg form;230
8.2.4;4. Reduction to bidiagonal form;230
8.2.5;5. Relationship to the WY-factorization;233
8.2.6;6. Pipelining reduction to condensed form with determination of eigenvalues;234
8.2.7;7. Operations counts and storage;237
8.2.8;8. Experimental results;237
8.2.9;References;238
8.3;Chapter 11. Multiprocessing a sparse matrix code on the Alliant FX/8;240
8.3.1;1. Introduction;240
8.3.2;2. Alliant FX/8;241
8.3.3;3. Multifrontal codes and elimination trees;242
8.3.4;4. Data management issues;243
8.3.5;5. Task spawning and granularity;245
8.3.6;6. Management of work queue and performance of code;246
8.3.7;7. Use of the SCHEDULE package;248
8.3.8;8. Conclusions;249
8.3.9;Acknowledgements;250
8.3.10;References;250
8.4;Chapter 12. Vector and parallel methods for the direct solution of Poisson's equation;252
8.4.1;1. Introduction;252
8.4.2;2. Parallel communication algorithms;254
8.4.3;3. The FFT;257
8.4.4;4. Tridiagonal solvers;260
8.4.5;5. Direct methods for solving Poisson's equation;267
8.4.6;References;273
9;Part 4: Design of fast algorithms and implementations for vector supercomputers;276
9.1;Chapter 13. Factoring with the quadratic sieve on large vector computers;278
9.1.1;1. Introduction;278
9.1.2;2. The multiple polynomial quadratic sieve;280
9.1.3;3. Implementation of the MPQS-algorithm on the CYBER 205 and the NEC SX-2;283
9.1.4;4. Results;284
9.1.5;5. Conclusions;286
9.1.6;Note added in proof;288
9.1.7;Acknowledgements;288
9.1.8;References;288
9.2;Chapter 14. Efficient vectorizable PDE solvers;290
9.2.1;1. Introduction;290
9.2.2;2. Families of difference and error formulas;291
9.2.3;3. The error-equation and its consequences;293
9.2.4;4. Linear solver and vectorization;297
9.2.5;5. The FIDISOL program package;302
9.2.6;6. Examples;305
9.2.7;7. Concluding remarks;307
9.2.8;Acknowledgements;307
9.2.9;References;308
9.3;Chapter 15. Vectorizable preconditioners for elliptic difference equations in three space dimensions;310
9.3.1;1. Introduction;310
9.3.2;2. Factorization of matrices partitioned in block tridiagonal form;311
9.3.3;3. Limit matrix analysis of preconditioning matrices;316
9.3.4;4. Plane block factorizations;325
9.3.5;5. Numerical results;327
9.3.6;6. Conclusions;330
9.3.7;Acknowledgement;331
9.3.8;References;331
9.4;Chapter 16. Solving 3D block bidiagonal linear systems on vector computers;334
9.4.1;1. A sketch of the problem;334
9.4.2;2. Vectorization techniques;335
9.4.3;3. Implementations of the hyperplane ordering for the CYBER 205;337
9.4.4;4. Preconditioned linear systems and Eisenstat's trick;339
9.4.5;5. Examples;341
9.4.6;References;341