Contents

• List of Contributors
• How to Use This Book
• How to Cite This Book
• Acknowledgments
• Contents
• List of Symbols and Acronyms
  • Symbols
  • Acronyms
• List of Direct Algorithms
• List of Figures
• List of Tables
• Introduction
  • Why Eigenvalue Templates?
  • Intended Readership
  • Using the Decision Tree to Choose a Template
  • What Is a Template?
  • Organization of the Book
• A Brief Tour of Eigenproblems
  • Introduction
    • Numerical Stability and Conditioning
  • Hermitian Eigenproblems
      J. Demmel
    • Eigenvalues and Eigenvectors
    • Invariant Subspaces
    • Equivalences (Similarities)
    • Eigendecompositions
    • Conditioning
    • Specifying an Eigenproblem
    • Related Eigenproblems
    • Example
  • Generalized Hermitian Eigenproblems
      J. Demmel
    • Eigenvalues and Eigenvectors
    • Eigenspaces
    • Equivalences (Congruences)
    • Eigendecompositions
    • Conditioning
    • Specifying an Eigenproblem
    • Related Eigenproblems
    • Example
  • Singular Value Decomposition
     J. Demmel
    • Singular Values and Singular Vectors
    • Singular Subspaces
    • Equivalences
    • Decompositions
    • Conditioning
    • Specifying a Singular Value Problem
    • Related Singular Value Problems
    • Example
  • Non-Hermitian Eigenproblems
     J. Demmel
    • Eigenvalues and Eigenvectors
    • Invariant Subspaces
    • Equivalences (Similarities)
    • Eigendecompositions
    • Conditioning
    • Specifying an Eigenproblem
    • Related Eigenproblems
    • Example
  • Generalized Non-Hermitian Eigenproblems
      J. Demmel
    • Eigenvalues and Eigenvectors
    • Deflating Subspaces
    • Equivalences
    • Eigendecompositions
    • Conditioning
    • Specifying an Eigenproblem
    • Related Eigenproblems
    • Example
    • Singular Case
  • More Generalized Eigenproblems
  • Nonlinear Eigenproblems
      J. Demmel
• An Introduction to Iterative Projection Methods
  • Introduction
  • Basic Ideas
    Y. Saad
  • Spectral Transformations
      R. Lehoucq and D. Sorensen
• Hermitian Eigenvalue Problems
  • Introduction
  • Direct Methods
  • Single- and Multiple-Vector Iterations
      M. Gu
    • Power Method
    • Inverse Iteration
    • Rayleigh Quotient Iteration
    • Subspace Iteration
    • Software Availability
  • Lanczos Method
      A. Ruhe
    • Algorithm
    • Convergence Properties
    • Spectral Transformation
    • Reorthogonalization
    • Software Availability
    • Numerical Examples
  • Implicitly Restarted Lanczos Method
      R. Lehoucq and D. Sorensen
    • Implicit Restart
    • Shift Selection
    • Lanczos Method in GEMV Form
    • Convergence Properties
    • Computational Costs and Tradeoffs
    • Deflation and Stopping Rules
    • Orthogonal Deflating Transformation
    • Implementation of Locking and Purging
    • Software Availability
  • Band Lanczos Method
      R. Freund
    • The Need for Deflation
    • Basic Properties
    • Algorithm
    • Variants
  • Jacobi-Davidson Methods
      G. Sleijpen and H. van der Vorst
    • Basic Theory
    • Basic Algorithm
    • Restart and Deflation
    • Computing Interior Eigenvalues
    • Software Availability
    • Numerical Example
  • Stability and Accuracy Assessments
      Z. Bai and R. Li
• Generalized Hermitian Eigenvalue Problems
  • Introduction
  • Transformation to Standard Problem
  • Direct Methods
  • Single- and Multiple-Vector Iterations
         M. Gu
  • Lanczos Methods
      A. Ruhe
  • Jacobi-Davidson Methods
     G. Sleijpen and H. van der Vorst
  • Stability and Accuracy Assessments
      Z. Bai and R. Li
    • Positive Definite $B$
    • Some Combination of $A$ and $B$ is Positive Definite
• Singular Value Decomposition
  • Introduction
  • Direct Methods
  • Iterative Algorithms
      J. Demmel
    • What Operations Can One Afford to Perform?
    • Which Singular Values and Vectors Are Desired?
    • Golub-Kahan-Lanczos Method
    • Software Availability
    • Numerical Example
  • Related Problems
      J. Demmel
• Non-Hermitian Eigenvalue Problems
  • Introduction
  • Balancing Matrices
      T. Chen and J. Demmel
    • Direct Balancing
    • Krylov Balancing Algorithms
    • Accuracy of Eigenvalues Computed after Balancing
  • Direct Methods
  • Single- and Multiple-Vector Iterations
      M. Gu
    • Power Method
    • Inverse Iteration
    • Subspace Iteration
    • Software Availability
  • Arnoldi Method
      Y. Saad
    • Basic Algorithm
    • Variants
    • Explicit Restarts
    • Deflation
  • Implicitly Restarted Arnoldi Method
      R. Lehoucq and D. Sorensen
    • Arnoldi Procedure in GEMV Form
    • Implicit Restart
    • Convergence Properties
    • Numerical Stability
    • Computational Costs and Tradeoffs
    • Deflation and Stopping Rules
    • Orthogonal Deflating Transformation
    • Eigenvector Computation with Spectral Transformation
    • Software Availability
  • Block Arnoldi Method
      R. Lehoucq and K. Maschhoff
    • Block Arnoldi Reductions
    • Practical Algorithm
    • Software Availability
    • Notes and References
  • Lanczos Method
      Z. Bai and D. Day
    • Algorithm
    • Convergence Properties
    • Software Availability
    • Notes and References
  • Block Lanczos Methods
      Z. Bai and D. Day
    • Basic Algorithm
    • An Adaptively Blocked Lanczos Method
    • Software Availability
    • Notes and References
  • Band Lanczos Method
      R. Freund
    • Deflation
    • Basic Properties
    • Algorithm
    • Application to Reduced-Order Modeling
    • Variants
  • Lanczos Method for Complex Symmetric Eigenproblems
      R. Freund
    • Properties of Complex Symmetric Matrices
    • Properties of the Algorithm
    • Algorithm
    • Solving the Reduced Eigenvalue Problems
    • Software Availability
    • Notes and References
  • Jacobi-Davidson Methods
      G. Sleijpen and H. van der Vorst
    • Generalization of Hermitian Case
    • Schur Form and Restart
    • Computing Interior Eigenvalues
    • Software Availability
    • Numerical Example
  • Stability and Accuracy Assessments
      Z. Bai and R. Li
• Generalized Non-Hermitian Eigenvalue Problems
  • Introduction
  • Direct Methods
  • Transformation to Standard Problems
  • Jacobi-Davidson Method
     G. Sleijpen and H. van der Vorst
    • Basic Theory
    • Deflation and Restart
    • Algorithm
    • Software Availability
    • Numerical Example
  • Rational Krylov Subspace Method
     A. Ruhe
  • Symmetric Indefinite Lanczos Method
     Z. Bai, T. Ericsson, and T. Kowalski
    • Some Properties of Symmetric Indefinite Matrix Pairs
    • Algorithm
    • Stopping Criteria and Accuracy Assessment
    • Singular $B$
    • Software Availability
    • Numerical Examples
    • Notes and References
  • Singular Matrix Pencils
      B. Kågström
    • Regular Versus Singular Problems
    • Kronecker Canonical Form
    • Generic and Nongeneric Kronecker Structures
    • Ill-Conditioning
    • Generalized Schur-Staircase Form
    • GUPTRI Algorithm
    • Software Availability
    • More on GUPTRI and Numerical Examples
    • Notes and References
  • Stability and Accuracy Assessments
      Z. Bai and R. Li
• Nonlinear Eigenvalue Problems
  • Introduction
  • Quadratic Eigenvalue Problems
    Z. Bai, G. Sleijpen, and H. van der Vorst
    • Introduction
    • Transformation to Linear Form
    • Spectral Transformations for QEP
    • Numerical Methods for Solving Linearized Problems
    • Jacobi-Davidson Method
    • Notes and References
  • Higher Order Polynomial Eigenvalue Problems
  • Nonlinear Eigenvalue Problems with Orthogonality Constraints
      R. Lippert and A. Edelman
    • Introduction
    • MATLAB Templates
    • Sample Problems and Their Differentials
    • Numerical Examples
    • Modifying the Templates
    • Geometric Technicalities
• Common Issues
  • Sparse Matrix Storage Formats
      J. Dongarra
    • Compressed Row Storage
    • Compressed Column Storage
    • Block Compressed Row Storage
    • Compressed Diagonal Storage
    • Jagged Diagonal Storage
    • Skyline Storage
  • Matrix-Vector and Matrix-Matrix Multiplications
      J. Dongarra, P. Koev, and X. Li
    • BLAS
    • Sparse BLAS
    • Fast Matrix-Vector Multiplication for Structured Matrices
  • A Brief Survey of Direct Linear Solvers
      J. Demmel, P. Koev, and X. Li
    • Direct Solvers for Dense Matrices
    • Direct Solvers for Band Matrices
    • Direct Solvers for Sparse Matrices
    • Direct Solvers for Structured Matrices
  • A Brief Survey of Iterative Linear Solvers
      H. van der Vorst
  • Parallelism
      J. Dongarra and X. Li
• Preconditioning Techniques
  • Introduction
  • Inexact Methods
      K. Meerbergen and R. Morgan
    • Matrix Transformations
    • Inexact Matrix Transformations
    • Arnoldi Method with Inexact Cayley Transform
    • Davidson Method
    • Jacobi-Davidson Method with Cayley Transform
    • Preconditioned Lanczos Method
    • Inexact Rational Krylov Method
    • Inexact Shift-and-Invert
  • Preconditioned Eigensolvers
      A. Knyazev
    • Introduction
    • General Framework of Preconditioning
    • Preconditioned Shifted Power Method
    • Preconditioned Steepest Ascent/Descent Methods
    • Preconditioned Lanczos Methods
    • Davidson Method
    • Methods with Preconditioned Inner Iterations
    • Preconditioned Conjugate Gradient Methods
    • Preconditioned Simultaneous Iterations
    • Software Availability
• Bibliography
• Index
• About this document ...