Front Cover

Sparse Matrix Technology

Copyright Page

Table of Contents

Preface

Dedication

Introduction

Chapter 1. Fundamentals

1.1 Introduction

1.2 Storage of arrays, lists, stacks and queues

1.3 Storage of lists of integers

1.4 Representation and storage of graphs

1.5 Diagonal storage of band matrices

1.6 Envelope storage of symmetric matrices

1.7 Linked sparse storage schemes

1.8 The sparse row-wise format

1.9 Ordered and unordered representations

1.10 Sherman's compression

1.11 Storage of block-partitioned matrices

1.12 Symbolic processing and dynamic storage schemes

1.13 Merging sparse lists of integers

1.14 The multiple switch technique

1.15 Addition of sparse vectors with the help of an expanded real accumulator

1.16 Addition of sparse vectors with the help of an expanded integer array of pointers

1.17 Scalar product of two sparse vectors with the help of an array of pointers

Chapter 2. Linear Algebraic Equations

2.1 Introduction

2.2 Some definitions and properties

2.3 Elementary matrices and triangular matrices

2.4 Some properties of elementary matrices

2.5 Some properties of triangular matrices

2.6 Permutation matrices

2.7 Gauss elimination by columns

2.8 Gauss elimination by rows

2.9 Gauss–Jordan elimination

2.10 Relation between the elimination form of the inverse and the product form of the inverse

2.11 Cholesky factorization of a symmetric positive definite matrix

2.12 Practical implementation of Cholesky factorization

2.13 Forward and backward substitution

2.14 Cost considerations

2.15 Numerical examples

Chapter 3. Numerical Errors in Gausss Elimination

3.1 Introduction

3.2 Numerical errors in floating point operations

3.3 Numerical errors in sparse factorization

3.4 Numerical errors in sparse substitution

3.5 The control of numerical errors

3.6 Numerical stability and pivot selection

3.7 Monitoring or estimating element growth

3.8 Scaling

Chapter 4. Ordering for Gauss Elimination: Symmetric Matrices

4.1 Introduction: Statement of the problem

4.2 Basic notions of graph theory

4.3 Breadth-first search and adjacency level structures

4.4 Finding a pseudoperipheral vertex and a narrow level structure of a graph

4.5 Reducing the bandwidth of a symmetric matrix

4.6 Reducing the profile of a symmetric matrix

4.7 Graph-theoretical background of symmetric Gauss elimination

4.8 The minimum degree algorithm

4.9 Tree partitioning of a symmetric sparse matrix

4.10 Nested dissection

4.11 Properties of nested dissection orderings

4.12 Generalized nested dissection

4.13 One-way dissection for finite element problems

4.14 Orderings for the finite element method

4.15 Depth-first search of an undirected graph

4.16 Lexicographic search

4.17 Symmetric indefinite matrices

Chapter 5. Ordering for Gauss Elimination: General Matrices

5.1 Introduction: Statement of the problem

5.2 Graph theory for unsymmetric matrices

5.3 The strong components of a digraph

5.4 Depth-first search of a digraph

5.5 Breadth-first search of a digraph and directed adjacency level structures

5.6 Finding a maximal set of vertex disjoint paths in an acyclic digraph

5.7 Finding a transversal: the algorithm of Hall

5.8 Finding a transversal: the algorithm of Hopcroft and Karp

5.9 The algorithm of Sargent and Westerberg for finding the strong components of a digraph

5.10 The algorithm of Tarjan for finding the strong components of a digraph

5.11 Pivoting strategies for unsymmetric matrices

5.12 Other methods and available software

Chapter 6. Sparse Eigenanalysis

6.1 Introduction

6.2 The Rayleigh quotient

6.3 Bounds for eigenvalues

6.4 The bisection method for eigenvalue calculations

6.5 Reduction of a general matrix

6.6 Reduction of a symmetric band matrix to tridiagonal form

6.7 Eigenanalysis of tridiagonal and Hessenberg matrices

6.8 Direct and inverse iteration

6.9 Subspaces and invariant subspaces

6.10 Simultaneous iteration

6.11 Lanczos algorithm

6.12 Lanczos algorithm in practice

6.13 Block Lanczos and band Lanczos algorithms

6.14 Trace minimization

6.15 Eigenanalysis of hermitian matrices

6.16 Unsymmetric eigenproblems

Chapter 7. Sparse Matrix Algebra

7.1 Introduction

7.2 Transposition of a sparse matrix

7.3 Algorithm for the transposition of a general sparse matrix

7.4 Ordering a sparse representation

7.5 Permutation of rows or columns of a sparse matrix: First procedure

7.6 Permutation of rows or columns of a sparse matrix: Second procedure

7.7 Ordering of the upper representation of a sparse symmetric matrix

7.8 Addition of sparse matrices

7.9 Example of addition of two sparse matrices

7.10 Algorithm for the symbolic addition of two sparse matrices with N rows and M columns

7.11 Algorithm for the numerical addition of two sparse matrices with N rows

7.12 Product of a general sparse matrix by a column vector

7.13 Algorithm for the product of a general sparse matrix by a full column vector

7.14 Product of a row vector by a general sparse matrix

7.15 Example of product of a full row vector by a general sparse matrix

7.16 Algorithm for the product of a full row vector by a general sparse matrix

7.17 Product of a symmetric sparse matrix by a column vector

7.18 Algorithms for the product of a symmetric sparse matrix by a full column vector

7.19 Multiplication of sparse matrices

7.20 Example of product of two matrices which are stored by rows

7.21 Algorithm for the symbolic multiplication of two sparse matrices given in row-wise format

7.22 Algorithm for the numerial multiplication of two sparse matrices given in row-wise format

7.23 Triangular factorization of a sparse symmetric matrix given in row-wise format

7.24 Numerical triangular factorization of a sparse symmetric matrix given in row-wise format

7.25 Algorithm for the symbolic triangular factorization of a symmetric sparse matrix A

7.26 Algorithm for the numerical triangular factorization of a symmetric positive definite sparse matrix A

7.27 Example of forward and backward substitution

7.28 Algorithm for the solution of the system UтDUx = b

Chapter 8. Connectivity and Nodal Assembly

8.1 Introduction

8.2 Boundary conditions for scalar problems

8.3 Boundary conditions for vector problems

8.4 Example of a connectivity matrix

8.5 Example of a nodal assembly matrix

8.6 Algorithm for the symbolic assembly of a symmetric nodal assembly matrix

8.7 Algorithm for the numerical assembly of an element matrix and vector into the nodal assembly matrix A and right-hand vector b: Symmetric case

8.8 Algorithm for the numerical assembly of an element matrix and vector into the nodal assembly matrix A and right-hand vector b: General case

Chapter 9. General Purpose Algorithms

9.1 Introduction

9.2 Multiplication of the inverse of a lower triangular matrix by a general matrix

9.3 Algorithm for the symbolic multiplication of the inverse of a lower triangular matrix U-т by a general matrix B

9.4 Algorithm for the numerical multiplication of the inverse of a lower triangular matrix U-т by a general matrix B

9.5 Algorithm for the multiplication of the inverse of an upper triangular unit diagonal matrix U by a full vector x

9.6 Algorithm for the multiplication of the transpose inverse of an upper triangular unit diagonal matrix U by a full vector

9.7 Solution of linear equations by the Gauss–Seidel iterative method

9.8 Algorithm for the iterative solution of linear equations by the Gauss–Seidel method

9.9 Checking the representation of a sparse matrix

9.10 Printing or displaying a sparse matrix

9.11 Algorithm for transforming a RR(C)U of a symmetric matrix into a RR(U)U of the same matrix

9.12 Algorithm for the pre-multiplieation of a sparse matrix A by a diagonal matrix D

9.13 Algorithm for copying a sparse matrix from IA, JA, AN to IB, JB, BN

References

Subject Index