In this lecture algorithms are investigated for solving eigenvalue problems with large sparse matrices. Some of these eigensolvers have been developed only in the last few years. They will be analyzed in theory and practice (by means of MATLAB exercises).

Lecture notes will be provided to the participants. They are available from this web site as well.

• Introduction
• What makes eigenvalues interesting?
• Example 1: The vibrating string
• Numerical methods for solving 1-dimensional problems
• Example 2: The heat equation
• Example 3: The wave equation
• The 2D Laplace eigenvalue problem
• Cavity resonances in particle accelerators
• Spectral clustering
• Other Sources of Eigenvalue Problems
• Bibliography
• Basics
• Notation
• Statement of the problem
• Similarity transformations
• Schur decomposition
• The real Schur decomposition
• Hermitian matrices
• Cholesky factorization
• The singular value decomposition (SVD)
• Projections
• Angles between vectors and subspaces
• Bibliography
• The QR Algorithm
• The basic QR algorithm
• The Hessenberg QR algorithm
• The Householder reduction to Hessenberg form
• Improving the convergence of the QR algorithm
• The double shift QR algorithm
• The symmetric tridiagonal QR algorithm
• Summary
• Bibliography
• LAPACK and the BLAS
• LAPACK
• BLAS
• Blocking
• LAPACK solvers for the symmetric eigenproblems
• Generalized Symmetric Definite Eigenproblems (GSEP)
• An example of a LAPACK routines
• Bibliography
• Cuppen's Divide and Conquer Algorithm
• The divide and conquer idea
• Partitioning the tridiagonal matrix
• Solving the small systems
• Deflation
• The eigenvalue problem for $D + \rho \mathbf {vv}^T$
• Solving the secular equation
• A first algorithm
• The algorithm of Gu and Eisenstat
• Bibliography
• Vector iteration (power method)
• Simple vector iteration
• Convergence analysis
• A numerical example
• The symmetric case
• Inverse vector iteration
• Computing higher eigenvalues
• Rayleigh quotient iteration
• Bibliography
• Simultaneous vector or subspace iterations
• Basic subspace iteration
• Convergence of basic subspace iteration
• Accelerating subspace iteration
• Relation of the simultaneous vector iteration with the QR algorithm
• Addendum
• Bibliography
• Krylov subspaces
• Introduction
• Definition and basic properties
• Polynomial representation of Krylov subspaces
• Error bounds of Saad
• Bibliography
• Arnoldi and Lanczos algorithms
• An orthonormal basis for the Krylov space $\mathcal {K}^j (\mathbf {x})$
• Arnoldi algorithm with explicit restarts
• The Lanczos basis
• The Lanczos process as an iterative method
• An error analysis of the unmodified Lanczos algorithm
• Partial reorthogonalization
• Block Lanczos
• External selective reorthogonalization
• Bibliography
• Restarting Arnoldi and Lanczos algorithms
• The $m$-step Arnoldi iteration
• Implicit restart
• Convergence criterion
• The generalized eigenvalue problem
• A numerical example
• Another numerical example
• The Lanczos algorithm with thick restarts
• Krylov-Schur algorithm
• The rational Krylov space method
• Bibliography
• The Jacobi-Davidson Method
• The Davidson algorithm
• The Jacobi orthogonal component correction
• The generalized Hermitian eigenvalue problem
• A numerical example
• The Jacobi--Davidson algorithm for interior eigenvalues
• Harmonic Ritz values and vectors
• Refined Ritz vectors
• The generalized Schur decomposition
• JDQZ: Computing a partial QZ decomposition
• Jacobi-Davidson for nonlinear eigenvalue problems
• Bibliography
• Rayleigh quotient minimization
• The method of steepest descent
• The conjugate gradient algorithm
• Locally optimal PCG (LOPCG)
• The block Rayleigh quotient minimization algorithm (BRQMIN)
• The locally-optimal block preconditioned conjugate gradient method (LOBPCG)
• A numerical example
• Bibliography

1. Z. Bai,  J. Demmel,  J. Dongarra,  A. Ruhe, and H. van der Vorst: Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide.   SIAM,  Philadelphia,  2000.
2. Y. Saad: Numerical Methods for Large Eigenvalue Problems, 2nd revised edition. SIAM,  Philadelphia,  2011.
3. G. H. Golub and Ch. van Loan: Matrix Computations, 3rd edition Johns Hopkins University Press, Baltimore 1996.
4. B. N. Parlett: The Symmetric Eigenvalue Problem. Prentice Hall, Englewood Cliffs, NJ, 1980. (Republished by SIAM, Philadelphia, 1998.)

Comments to arbenz@inf.ethz.ch