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 Newton’s method suitable for very large problems. In many cases we will use iterative methods to solve approximately the linear systems arising in Newton-type methods, and we analyze the properties of these methods, conditions for convergence, and rate of convergence. We will also consider several methods that avoid the (in general) expensive computation of Jacobians such as secant methods (like Broyden’s method) and Newton-Krylov methods.

 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 (SIAM), 2001

 

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 by 5pm, Thursday, February 7. Solutions, matlab script
  2. Homework 2 is due by 5pm, Tuesday, April 1. The homework can be done in groups of up to three. Groups need not be fixed.
  3. Homework 3 is due by 5pm, Tuesday, April 22. The homework can be done in groups of up to three. Groups need not be fixed.
  4. Homework 4 is due by 5pm, Friday, May 2. The homework can be done in groups of up to three. Groups need not be fixed. You can find the required software (jdqr.m) on Blackboard.

Quizzes will only be given on request J

Course Policies

Class Projects (link will be added shortly)