Matrix Computations

Title......Page 3
Contents......Page 7
Preface......Page 11
Global References......Page 13
Other Books......Page 15
Useful URLs......Page 19
Common Notation......Page 21
1. Matrix Multiplication......Page 25
1.1 Basic Algorithms and Notation......Page 26
1.2 Structure and Efficiency......Page 38
1.3 Block Matrices and Algorithms......Page 46
1.4 Fast Matrix-Vector Products......Page 57
1.5 Vectorization and Locality......Page 67
1.6 Parallel Matrix Multiplication......Page 73
2. Matrix Analysis......Page 87
2.1 Basic Ideas from Linear Algebra......Page 88
2.2 Vector Norms......Page 92
2.3 Matrix Norms......Page 95
2.4 The Singular Value Decomposition......Page 100
2.5 Subspace Matrix......Page 105
2.6 The Sensitivity of Square Systems......Page 111
2.7 Finite Precision Matrix Computations......Page 117
3. General Linear Systems......Page 129
3.1 Triangular Systems......Page 130
3.2 The LU Factorization......Page 135
3.3 Roundoff Error in Gaussian Elimination......Page 146
3.4 Pivoting......Page 149
3.5 Improving and Estimating Accuracy......Page 161
3.6 Parallel LU......Page 168
4. Special Linear Systems......Page 177
4.1 Diagonal Dominance and Symmetry......Page 178
4.2 Positive Definite Systems......Page 183
4.3 Banded Systems......Page 200
4.4 Symmetric Indefinite Systems......Page 210
4.5 Block Tridiagonal Systems......Page 220
4.6 Vandermonde Systems......Page 227
4.7 Classical Methods for Toeplitz Systems......Page 232
4.8 Circulant and Discrete Poisson Systems......Page 243
5. Orthogonalization and Least Squares......Page 257
5.1 Householder and Givens Transformations......Page 258
5.2 The QR Factorization......Page 270
5.3 The Full-Rank Least Squares Problem......Page 284
5.4 Other Orthogonal Factorizations......Page 298
5.5 The Rank-Deficient Least Squares Problem......Page 312
5.6 Square and Underdetermined Systems......Page 322
6. Modified Least Squares Problems and Methods......Page 327
6.1 Weighting and Regularization......Page 328
6.2 Constrained Least Squares......Page 337
6.3 Total Least Squares......Page 344
6.4 Subspace Computations with the SVD......Page 351
6.5 Updating Matrix Factorizations......Page 358
7. Unsymmetric Eigenvalue Problems......Page 371
7.1 Properties and Decompositions......Page 372
7.2 Perturbation Theory......Page 381
7.3 Power Iterations......Page 389
7.4 The Hessenberg and Real Schur Forms......Page 400
7.5 The Practical QR Algorithm......Page 409
7.6 Invariant Subspace Computations......Page 418
7.7 The Generalized Eigenvalue Problem......Page 429
7.8 Hamiltonian and Product Eigenvalue Problems......Page 444
7.9 Pseudospectra......Page 450
8. Symmetric Eigenvalue Problems......Page 463
8.1 Properties and Decompositions......Page 464
8.2 Power Iterations......Page 474
8.3 The Symmetric QR Algorithm......Page 482
8.4 More Methods for Tridiagonal Problems......Page 491
8.5 Jacobi Methods......Page 500
8.6 Computing the SVD......Page 510
8.7 Generalized Eigenvalue Problems with Symmetry......Page 521
9. Functions of Matrices......Page 537
9.1 Eigenvalue Methods......Page 538
9.2 Approximation Methods......Page 546
9.3 The Matrix Exponential......Page 554
9.4 The Sign, Square Root, and Log of a Matrix......Page 560
10. Large Sparse Eigenvalue Problems......Page 569
10.1 The Symmetric Lanczos Process......Page 570
10.2 Lanczos, Quadrature, and Approximation......Page 580
10.3 Practical Lanczos Procedures......Page 586
10.4 Large Sparse SVD Frameworks......Page 595
10.5 Krylov Methods for Unsymmetric Problems......Page 603
10.6 Jacobi-Davidson and Related Methods......Page 613
11. Large Sparse Linear System Problems......Page 621
11.1 Direct Methods......Page 622
11.2 The Classical Iterations......Page 635
11.3 The Conjugate Gradient Method......Page 649
11.4 Other Krylov Methods......Page 663
11.5 Preconditioning......Page 674
11.6 The Multigrid Framework......Page 694
12.1 Linear Systems with Displacement Structure......Page 705
12.2 Structured-Rank Problems......Page 715
12.3 Kronecker Product Computations......Page 731
12.4 Tensor Unfoldings and Contractions......Page 743
12.5 Tensor Decompositions and Iterations......Page 755