## Sparse Matrix Technology - electronic edition (Google eBook) |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

511 Pivoting strategies for unsymmetric matrices | 173 |

512 Other methods and available software | 175 |

Sparse Eigenanalysis | 177 |

62 The Rayleigh quotient | 180 |

63 Bounds for eigenvalues | 182 |

64 The bisection method for eigenvalue calculations | 184 |

65 Reduction of a general matrix | 185 |

66 Reduction of a symmetric band matrix to tridiag onal form | 188 |

22 | |

24 | |

26 | |

28 | |

29 | |

30 | |

32 | |

33 | |

35 | |

37 | |

23 Elementary matrices and triangular matrices | 40 |

24 Some properties of elementary matrices | 41 |

25 Some properties of triangular matrices | 42 |

26 Permutation matrices | 44 |

27 Gauss elimination by columns | 45 |

28 Gauss elimination by rows | 49 |

29 GaussJordan elimination | 50 |

210 Relation between the elimination form of the inverse and the product form of the inverse | 52 |

211 Cholesky factorization of a symmetric positive deﬁnite matrix | 53 |

212 Practical implementation of Cholesky factorization | 55 |

213 Forward and backward substitution | 56 |

214 Cost considerations | 57 |

215 Numerical examples | 59 |

Numerical Errors in Gauss Elimination | 63 |

32 Numerical errors in ﬂoating point operations | 65 |

33 Numerical errors in sparse factorization | 68 |

34 Numerical errors in sparse substitution | 73 |

35 The control of numerical errors | 77 |

36 Numerical stability and pivot selection | 78 |

37 Monitoring or estimating element growth | 82 |

38 Scaling | 83 |

Ordering for Gauss Elimination Symmetric Matrices | 85 |

42 Basic notions of graph theory | 87 |

43 Breadthﬁrst search and adjacency level structures | 93 |

44 Finding a pseudoperipheral vertex and a narrow level structure of a graph | 95 |

45 Reducing the bandwidth of a symmetric matrix | 96 |

46 Reducing the proﬁle of a symmetric matrix | 98 |

47 Graphtheoretical background of symmetric Gauss elimination | 101 |

48 The minimum degree algorithm | 104 |

49 Tree partitioning of a symmetric sparse matrix | 109 |

410 Nested dissection | 113 |

411 Properties of nested dissection orderings | 118 |

412 Generalized nested dissection | 121 |

413 Oneway dissection of ﬁnite element problems | 122 |

414 Orderings for the ﬁnite element method | 127 |

415 Depthﬁrst search of an undirected graph | 132 |

416 Lexicographic search | 136 |

417 Symmetric indeﬁnite matrices | 140 |

Ordering for Gauss Elimination General Matrices | 143 |

52 Graph theory for unsymmetric matrices | 146 |

53 The strong components of a digraph | 148 |

54 Depthﬁrst search of a digraph | 151 |

55 Breadthﬁrst search of a digraph and directed adjacency level structures | 155 |

56 Finding a maximal set of vertex disjoint paths in an acyclic digraph | 157 |

the algorithm of Hall | 158 |

the algorithm of Hopcroft and Karp | 161 |

59 The algorithm of Sargent and Westerberg for ﬁnding the strong components of a digraph | 167 |

510 The algorithm of Tarjan for ﬁnding the strong components of a digraph | 168 |

67 Eigenanalysis of tridiagonal and Hessenberg matrices | 189 |

69 Subspaces and invariant subspaces | 193 |

610 Simultaneous iteration | 195 |

611 Lanczos algorithm | 199 |

612 Lanczos algorithm in practice | 203 |

613 Block Lanczos and band Lanczos algorithms | 206 |

614 Trace minimization | 208 |

615 Eigenanalysis of hermitian matrices | 209 |

616 Unsymmetric eigenproblems | 210 |

Sparse Matrix Algebra | 211 |

72 Transposition of a sparse matrix | 213 |

73 Algorithm for the transposition of a general sparse matrix | 215 |

74 Ordering a sparse representation | 216 |

First procedure | 217 |

Second procedure | 218 |

78 Addition of sparse matrices | 219 |

79 Example of addition of two sparse matrices | 220 |

710 Algorithm for the symbolic addition of two sparse matrices with N rows and M columns | 221 |

711 Algorithm for the numerical addition of two sparse matrices with N rows | 223 |

712 Product of a general sparse matrix by a column vector | 224 |

713 Algorithm for the product of a general sparse matrix by a full column vector | 225 |

714 Product of a row vector by a general sparse matrix | 226 |

716 Algorithm for the product of a full row vector by a general sparse matrix | 227 |

717 Product of a symmetric sparse matrix by a column vector | 228 |

718 Algorithm for the product of a symmetric sparse matrix by a full column vector | 229 |

719 Multiplication of sparse matrices | 230 |

720 Example of product of two matrices which are stored by rows | 231 |

721 Algorithm for the symbolic multiplication of two sparse matrices given in rowwise format | 233 |

722 Algorithm for the numerical multiplication of two sparse matrices given in rowwise format | 234 |

723 Triangular factorization of a sparse symmetric matrix given in rowwise format | 235 |

724 Numerical triangular factorization of a sparse symmetric matrix given in rowwise format | 238 |

725 Algorithm for the symbolic triangular factorization of a symmetric sparse matrix A | 240 |

726 Algorithm for the numerical triangular factorization of a symmetric positive deﬁnite sparse matrix A | 242 |

727 Example of forward and backward substitution | 245 |

728 Algorithm for the solution of the system UTDUx b | 246 |

Connectivity and Nodal Assembly | 249 |

82 Boundary conditions for scalar problems | 251 |

83 Boundary conditions for vector problems | 252 |

84 Example of a connectivity matrix | 256 |

85 Example of a nodal assembly matrix | 257 |

86 Algorithm for the symbolic assembly of a symmetric nodal assembly matrix | 259 |

Symmetric case | 261 |

General case | 264 |

General Purpose Algorithms | 267 |

92 Multiplication of the inverse of a lower triangular matrix by a general matrix | 268 |

93 Algorithm for the symbolic multiplication of the inverse of a lower triangular matrix U T by a general matrix B | 269 |

94 Algorithm for the numerical multiplication of the inverse of a lower triangular matrix U T by a general matrix B | 270 |

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

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

97 Solution of linear equations by the GaussSeidel iterative method | 274 |

98 Algorithm for the iterative solution of linear equations by the GaussSeidel method | 275 |

99 Checking the representation of a sparse matrix | 276 |

910 Printing and displaying a sparse matrix | 277 |

911 Algorithm for transforming a RRCU of a symmetric matrix into a RRUU of the same matrix | 278 |

912 Algorithm for the premultiplication of a sparse matrix A by a diagonal matrix D | 279 |

References | 281 |

295 | |

### Common terms and phrases

active submatrix adjacent array augmenting path band matrix block Chapter column indices computed connected consider corresponding deﬁned depth-ﬁrst search diagonal elements diﬀerent digraph discussed in Section Duﬀ edges eﬃcient eigenanalysis eigenproblem eigenvectors elementary matrices example ﬁll ﬁll-in ﬁnal ﬁnd ﬁnding ﬁnite element ﬁrst Fortran Gauss elimination given matrix graph of Fig graph theory integers inverse inverse iteration iteration labelling Lanczos algorithm level structure linear equations lower triangular method minimal multiple switch nested dissection number of nonzeros obtained oﬀ-diagonal nonzeros orthogonal partitioning performed permuted matrix pointers procedure proﬁle representation rooted row-wise format rows and columns shown in Fig solution solved sparse matrix sparse matrix technology sparsity stack starting vertex Step storage scheme stored strong component submatrix suﬃcient symbolic symmetric matrix symmetric positive deﬁnite tree arcs triangular factorization tridiagonal undirected graph unit diagonal unsymmetric upper triangular vertex vertices zeros