Numerical Methods for Large Eigenvalue Problems

✍ Scribed by Yousef Saad

• Publisher: SIAM
• Year: 2011
• Tongue: English
• Leaves: 285
• Series: Classics in Applied Mathematics 66
• Edition: 2nd.
• Category: Library

✦ Synopsis

This revised edition discusses numerical methods for computing eigenvalues and eigenvectors of large sparse matrices. It provides an in-depth view of the numerical methods that are applicable for solving matrix eigenvalue problems that arise in various engineering and scientific applications. Each chapter was updated by shortening or deleting outdated topics, adding topics of more recent interest, and adapting the Notes and References section. Significant changes have been made to Chapters 6 through 8, which describe algorithms and their implementations and now include topics such as the implicit restart techniques, the Jacobi-Davidson method, and automatic multilevel substructuring. Audience: This book is intended for researchers in applied mathematics and scientific computing as well as for practitioners interested in understanding the theory of numerical methods used for eigenvalue problems. It also can be used as a supplemental text for an advanced graduate-level course on these methods. Contents: Chapter One: Background in Matrix Theory and Linear Algebra; Chapter Two: Sparse Matrices; Chapter Three: Perturbation Theory and Error Analysis; Chapter Four: The Tools of Spectral Approximation; Chapter Five: Subspace Iteration; Chapter Six: Krylov Subspace Methods; Chapter Seven: Filtering and Restarting Techniques; Chapter Eight: Preconditioning Techniques; Chapter Nine: Non-Standard Eigenvalue Problems; Chapter Ten: Origins of Matrix Eigenvalue Problems

✦ Table of Contents

BookmarkTitle:......Page 7
BookmarkTitle:......Page 9
Matrices......Page 11
Square Matrices and Eigenvalues......Page 12
Matrices with Special Srtuctures......Page 14
Special Matrices......Page 15
Vector Inner Products and Norms......Page 16
Matrix Norms......Page 18
Subspaces......Page 19
Orthogonal Vectors and Subspaces......Page 21
Canonical Forms of Matrices......Page 22
The Jordan Canonical Form......Page 24
The Schur Canonical Form......Page 28
Normal Matrices......Page 31
Hermitian Matrices......Page 33
Nonnegative Matrices......Page 35
Introduction......Page 39
Storage Schemes......Page 40
Basic Sparse Matrix Operations......Page 44
Sparse Direct Solution Methods......Page 45
Random Walk Problem......Page 46
Chemical Reactions......Page 48
SPARSKIT......Page 50
Sparse Matrices in Matlab......Page 53
Projectors and their Properties......Page 57
Orthogonal Projectors......Page 58
Oblique Projectors......Page 60
Resolvent and Spectral Projector......Page 61
Relations with the Jordan form......Page 63
Linear Perturbations of A......Page 65
General Error Bounds......Page 69
The Hermitian Case......Page 71
The Kahan-Parlett-Jiang Theorem......Page 76
Conditioning of Eigenvalues......Page 80
Conditioning of Eigenvectors......Page 82
Conditioning of Invariant Subspaces......Page 85
Localization Theorems......Page 87
Pseudo-eigenvalues......Page 89
The Power Method......Page 95
Inverse Iteration......Page 98
Deflation Techniques......Page 100
Wielandt Deflation with One Vector......Page 101
Optimality in Wieldant's Deflation......Page 102
Deflation with Several Vectors.......Page 104
Partial Schur Decomposition.......Page 105
General Projection Methods......Page 106
Orthogonal Projection Methods......Page 107
The Hermitian Case......Page 110
Oblique Projection Methods......Page 116
Real Chebyshev Polynomials......Page 118
Complex Chebyshev Polynomials......Page 119
Simple Subspace Iteration......Page 125
Subspace Iteration with Projection......Page 128
Locking......Page 131
Preconditioning......Page 133
Krylov Subspaces......Page 135
The Basic Algorithm......Page 138
Practical Implementations......Page 141
Incorporation of Implicit Deflation......Page 144
The Hermitian Lanczos Algorithm......Page 146
The Algorithm......Page 147
Non-Hermitian Lanczos Algorithm......Page 148
The Algorithm......Page 149
Practical Implementations......Page 153
Block Krylov Methods......Page 155
Distance between Km and an Eigenvector......Page 157
Convergence of the Eigenvalues......Page 159
Convergence of the Eigenvectors......Page 160
Convergence of the Arnoldi Process......Page 161
Polynomial Filtering......Page 173
Explicitly Restarted Arnoldi's Method......Page 175
Implicitly Restarted Arnoldi's Method......Page 176
Chebyshev Iteration......Page 179
Convergence Properties.......Page 183
Computing an Optimal Ellipse......Page 184
Chebyshev Subspace Iteration......Page 187
Deflation......Page 188
The Least Squares Polynomial......Page 189
Use of Chebyshev Bases......Page 191
The Gram Matrix......Page 192
Computing the Best Polynomial......Page 194
Least Squares Arnoldi Algorithms......Page 198
Shift-and-invert Preconditioning......Page 203
General Concepts......Page 204
Dealing with Complex Arithmetic......Page 205
Shift-and-Invert Arnoldi......Page 207
Polynomial Preconditioning......Page 210
Davidson's Method......Page 213
Olsen's Method......Page 216
Connection with Newton's Method......Page 217
The Jacobi-Davidson Approach......Page 218
The CMS -- AMLS connection......Page 219
AMLS and the Correction Equation......Page 222
Spectral Schur Complements......Page 223
The Projection Viewpoint......Page 225
Introduction......Page 229
General Results......Page 230
Reduction to Standard Form......Page 235
Deflation......Page 236
Shift-and-Invert......Page 237
Projection Methods......Page 238
The Hermitian Definite Case......Page 239
Quadratic Problems......Page 241
From Quadratic to Generalized Problems......Page 242
Introduction......Page 245
Mechanical Vibrations......Page 246
Electrical Networks.......Page 251
Quantum descriptions of matter......Page 252
The Hartree approximation......Page 254
The Hartree-Fock approximation......Page 256
Density Functional Theory......Page 258
Pseudopotentials......Page 260
Stability of Dynamical Systems......Page 261
Bifurcation Analysis......Page 262
Chemical Reactions......Page 263
Macro-economics......Page 264
Markov Chain Models......Page 265
References......Page 267
Index......Page 269