|
|
MATH 5486 / CS 5486
Numerical Analysis and
Software II
|
Numerical
Analysis and Software II
Large
Sparse Eigenvalue Problems and Nonlinear Systems
Many of the methods discussed in part II are
closely related to the Krylov methods discussed in part I of this course.
However, part II can be taken independently of part I.
Eigenvalue problems play a fundamental role in the analysis of systems,
and that makes eigenvalue solvers important tools in the understanding of those
systems. Eigenvalue problems arise in computing the vibrational modes of large
engineering structures as well as those of complex molecules, in assessing the
(in)stability of processes in engineering and physics, for example for tokamak
design, and for computing the ground state of materials and reaction or
excitation energies. Eigenvalue problems also play an important role in the analysis
of iterative methods. In many of these applications we encounter very large
eigenvalue problems; however, we do not need all the eigenvalues and
eigenvectors, only a subset. This subset can be small (1 eigenpair) or quite
large (1000 eigenpairs), but it is much smaller than the full set of
eigenpairs. In this course we will introduce and discuss the most successful
methods for large eigenvalue problems, analyze their theoretical properties
(including convergence issues), and evaluate methods for various applications.
Some of the algorithms/methods we will discuss are the (bi)Lanczos and
Arnoldi methods and their implicitly restarted versions (that are implemented
in the popular ARPACK package), Davidson’s method and the recent developed
Jacobi-Davidson method, and more generally shift-invert and approximate
shift-invert methods.
Large nonlinear systems arise in the solution of nonlinear differential
and integral equations, the computation of steady states of dynamical systems,
parameter estimation, large optimization problems, and many other problems. We
look at several variants of
Instructor:
- Eric de Sturler (click to check what I do the rest of my time)
- Office: 544 McBryde
- Phone: 231-5279
- Email: sturler-at-vt-dot-edu
- Office hours: Monday 2.30-4.30pm or by appointment (send email)
Textbooks:
1. Solving Nonlinear Equations with Newton’s Method, C.T. Kelley, Society for Industrial and Applied Mathematics (SIAM), 2003
2. Matrix
Algorithms Volume II: Eigensystems, G.W. Stewart, Society for Industrial and Applied Mathematics (
The lecture notes will cover significant additional material:
Lecture Notes for Iterative Methos (part I)
Lecture Notes for Nonlinear Systems (part IIa)
Lecture Notes for Eigenvalue Problems (part IIb)
Other useful books on eigenvalue problems are:
· Matrix Perturbation Theory, G.W. Stewart and Ji-Guang Sun, Academic Press, 1990,
· The Symmetrix Eigenvalue Problem, B.N. Parlett, SIAM 1997 (original Prentice-Hall 1980),
· Templates for the Solution of Algebraic Eigenvalue Problems - A Practical Guide, Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, H. van der Vorst Eds., SIAM 2000,
· The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods, David S. Watkins, SIAM, 2007,
· Matrix Analysis, R.A. Horn and C.R. Johnson, Cambridge University Press, 1985,
· Topics in Matrix Analysis, R.A. Horn and C.R. Johnson, Cambridge University Press, 1991.
Other useful books on nonlinear systems of equations are:
- Numerical Methods for Unconstrained Optimization and Nonlinear Equations, J.E. Dennis, Jr. and R.B. Schnabel, SIAM, 1996 (originally Prentice-Hall 1983)
Homework:
1. Homework 1 is due February 22 in class. Answers will be posted on the scholar site (in due course).
Quizzes will only be given on request J
Class Projects (link will be added shortly)