1 High-Performance Computing

1.1 Trends in Computer Design

1.2 Traditional Computers and Their Limitations

1.3 Parallelism within a Single Processor

1.3.1 Multiple Functional Units

1.3.2 Pipelining

1.3.3 Overlapping

1.3.4 RISC

1.3.5 VLIW

1.3.6 Vector Instructions

1.3.7 Chaining

1.3.8 Memory-to-Memory and Register-to-Register Organizations

1.3.9 Register Set

1.3.10 Stripmining

1.3.11 Reconfigurable Vector Registers

1.3.12 Memory Organization

1.4 Data Organization

1.4.1 Main Memory

1.4.2 Cache

1.4.3 Local Memory

1.5 Memory Management

1.6 Parallelism through Multiple Pipes or Multiple Processors

1.7 Message Passing

1.8 Virtual Shared Memory

1.8.1 Routing

1.9 Interconnection Topology

1.9.1 Crossbar Switch

1.9.2 Timeshared Bus

1.9.3 Ring Connection

1.9.4 Mesh Connection

1.9.5 Hypercube

1.9.6 Multi-staged Network

1.10 Programming Techniques

1.11 Trends:Network-Based Computing

2 Overview of Current High-Performance Computers

2.1 Supercomputers

2.2 RISC-Based Processors

2.3 Parallel Processors

3 Implementation Details and Overhead

3.1 Parallel Decomposition and Data Dependency Graphs

3.2 Synchronization

3.3 Load Balancing

3.4 Recurrence

3.5 Indirect Addressing

3.6 Message Passing

3.6.1 Performance Prediction

3.6.2 Message-Passing Standards

3.6.3 Routing

4 Performance:Analysis,Modeling,and Measurements

4.1 Amdahl's Law

4.1.1 Simple Case of Amdahl's Law

4.1.2 General Form of Amdahl's Law

4.2 Vector Speed and Vector Length

4.3 Amdahl's Law—Parallel Processing

4.3.1 A Simple Model

4.3.2 Gustafson's Model

4.4 Examples of(r∞,n1/2)-values for Various Computers

4.4.1 CRAY J90 and CRAY T90 (One Processor)

4.4.2 General Observations

4.5 LINPACK Benchmark

4.5.1 Description of the Benchmark

4.5.2 Calls to the BLAS

4.5.3 Asymptotic Performance

5 Building Blocks in Linear Algebra

5.1 Basic Linear Algebra Subprograms

5.1.1 Level 1 BLAS

5.1.2 Level 2 BLAS

5.1.3 Level 3 BLAS

5.2 Levels of Parallelism

5.2.1 Vector Computers

5.2.2 Parallel Processors with Shared Memory

5.2.3 Parallel-Vector Computers

5.2.4 Clusters Computing

5.3 Basic Factorizations of Linear Algebra

5.3.1 Point Algorithm:Gaussian Elimination with Partial Piv-oting

5.3.2 Special Matrices

5.4 Blocked Algorithms:Matrix-Vector and Matrix-Matrix Versions

5.4.1 Right-Looking Algorithm

5.4.2 Left-Looking Algorithm

5.4.3 Crout Algorithm

5.4.4 Typical Performance of Blocked LU Decomposition

5.4.5 Blocked Symmetric Indefinite Factorization

5.4.6 Typical Performance of Blocked Symmetric Indefinite Fac-torization

5.5 Linear Least Squares

5.5.1 Householder Method

5.5.2 Blocked Householder Method

5.5.3 Typical Performance of the Blocked Householder Factor-ization

5.6 Organization of the Modules

5.6.1 Matrix-Vector Product

5.6.2 Matrix-Matrix Product

5.6.3 Typical Performance for Parallel Processing

5.6.4 Benefits

5.7 LAPACK

5.8 ScaLAPACK

5.8.1 The Basic Linear Algebra Communication Subprograms(BLACS)

5.8.2 PBLAS

5.8.3 ScaLAPACK Sample Code

6 Direct Solution of Sparse Linear Systems

6.1 Introduction to Direct Methods for Sparse Linear Systems

6.1.1 Four Approaches

6.1.2 Description of Sparse Data Structure

6.1.3 Manipulation of Sparse Data Structures

6.2 General Sparse Matrix Methods

6.2.1 Fill-in and Sparsity Ordering

6.2.2 Indirect Addressing—Its Effect and How to Avoid It

6.2.3 Comparison with Dense Codes

6.2.4 Other Approaches

6.3 Methods for Symmetric Matrices and Band Systems

6.3.1 The Clique Concept in Gaussian Elimination

6.3.2 Further Comments on Ordering Schemes

6.4 Frontal Methods

6.4.1 Frontal Methods—Link to Band Methods and Numerical Pivoting

6.4.2 Vector Performance

6.4.3 Parallel Implementation of Frontal Schemes

6.5 Multifrontal Methods

6.5.1 Performance on Vector Machines

6.5.2 Performance on RISC Machines

6.5.3 Performance on Parallel Machines

6.5.4 Exploitation of Structure

6.5.5 Unsymmetric Multifrontal Methods

6.6 Other Approaches for Exploitation of Parallelism

6.7 Software

6.8 Brief Summary

7 Krylov Subspaces:Projection

7.1 Notation

7.2 Basic Iteration Methods:Richardson Iteration,Power Method

7.3 Orthogonal Basis(Arnoldi,Lanczos)

8 Iterative Methods for Linear Systems

8.1 Krylov Subspace Solution Methods:Basic Principles

8.1.1 The Ritz-Galerkin Approach:FOM and CG

8.1.2 The Minimum Residual Approach:GMRES and MINRES

8.1.3 The Petrov-Galerkin Approach:Bi-CG and QMR

8.1.4 The Minimum Error Approach:SYMMLQ and GMERR

8.2 Iterative Methods in More Detail

8.2.1 The CG Method

8.2.2 Parallelism in the CG Method:General Aspects

8.2.3 Parallelism in the CG Method:Communication Overhead

8.2.4 MINRES

8.2.5 Least Squares CG

8.2.6 GMRES and GMRES(m)

8.2.7 GMRES with Variable Preconditioning

8.2.8 Bi-CG and QMR

8.2.9 CGS

8.2.10 Bi-CGSTAB

8.2.11 Bi-CGSTAB(e)and Variants

8.3 Other Issues

8.4 How to Test Iterative Methods

9 Preconditioning and Parallel Preconditioning

9.1 Preconditioning and Parallel Preconditioning

9.2 The Purpose of Preconditioning

9.3 Incomplete LU Decompositions

9.3.1 Efficient Implementations of ILU(0) Preconditioning

9.3.2 General Incomplete Decompositions

9.3.3 Variants of ILU Preconditioners

9.3.4 Some General Comments on ILU

9.4 Some Other Forms of Preconditioning

9.4.1 Sparse Approximate Inverse(SPAI)

9.4.2 Polynomial Preconditioning

9.4.3 Preconditioning by Blocks or Domains

9.4.4 Element by Element Preconditioners

9.5 Vector and Parallel Implementation of Preconditioners

9.5.1 Partial Vectorization

9.5.2 Reordering the Unknowns

9.5.3 Changing the Order of Computation

9.5.4 Some Other Vectorizable Preconditioners

9.5.5 Parallel Aspects of Reorderings

9.5.6 Experiences with Parallelism

10 Linear Eigenvalue Problems Ax=λx

10.1 Theoretical Background and Notation

10.2 Single-Vector Methods

10.3 The QR Algorithm

10.4 Subspace Projection Methods

10.5 The Arnoldi Factorization

10.6 Restarting the Arnoldi Process

10.6.1 Explicit Restarting

10.7 Implicit Restarting

10.8 Lanczos'Method

10.9 Harmonic Ritz Values and Vectors

10.10 Other Subspace Iteration Methods

10.11 Davidson's Method

10.12 The Jacobi-Davidson Iteration Method

10.12.1 JDQR

10.13 Eigenvalue Software:ARPACK,P_ARPACK

10.13.1 Reverse Communication Interface

10.13.2 Parallelizing ARPACK

10.13.3 Data Distribution of the Arnoldi Factorization

10.14 Message Passing

10.15 Parallel Performance

10.16 Availability

10.17 Summary

11 The Generalized Eigenproblem

11.1 Arnoldi/Lanczos with Shift-Invert

11.2 Alternatives to Arnoldi/Lanczos with Shift-Invert

11.3 The Jacobi-Davidson QZ Algorithm

11.4 The Jacobi-Davidson QZ Method:Restart and Deflation

11.5 Parallel Aspects

A Acquiring Mathematical Software

A.1 netlib

A.1.1 Mathematical Software

A.2 Mathematical Software Libraries

B Glossary

C Level 1,2,and 3 BLAS Quick Reference

D Operation Counts for Various BLAS and Decompositions

Bibliography

Index