Lectures:  TR 1:30-2:45 pm
Location:  MRDC 2404

Instructor:  Edmond Chow
E-mail: 
Office Hours: Wednesdays 2:30-3:30 in KACB 1312

TA: Michael Sheppard
TA E-mail:  msheppard30@gatech.edu
TA Office Hours: Tuesdays 3-4 pm (Skiles 256) and Thursdays 11 am - noon (Clough 421)


Course Description

Introduction to the state-of-the-art iterative methods for solving linear and nonlinear systems of equations. This will be a very practical course, involving Matlab programming and a project.

Prerequisites

Numerical Linear Algebra (CSE/MATH 6643) or equivalent. (Note that Numerical Linear Algebra is a completely different course than Linear Algebra. The latter is an undergraduate math course, sometimes taught along with differential equations, while the former is a graduate level course.) The assignments will require Matlab programming (at least at the level of CS 1371).

Topics

  • Sparse matrices and review of direct methods
  • Basic iterative methods (splitting methods, Jacobi, Gauss-Seidel, SOR)
  • Chebyshev iterative method and matrix polynomials
  • Krylov subspace methods (conjugate gradient method, GMRES, etc.)
  • Projection method framework
  • Methods based on biorthogonalization
  • Iterative methods for linear least squares
  • Preconditioning
  • Multigrid methods
  • Domain decomposition
  • Nonlinear systems of equations (fixed point methods, Newton, Broyden, Newton-Krylov and other Newton variants for large problems)
  • Line search and global convergence
  • Contraction mapping and local convergence theory
  • Nonlinear least squares (Gauss-Newton, Levenberg-Marquardt)
  • Related ideas in optimization

Learning Objectives

Students will develop facility with iterative methods for the numerical solution of linear and nonlinear systems, and their analysis. The students will be able to:

  • Given a linear or nonlinear system, choose an appropriate numerical solution method based on the properties of the system
  • Evaulate a method for its convergence and computational cost, including parallel computing aspects
  • Diagnose convergence problems of iterative solution methods
  • Select or design a method or approach for preconditioning the solution of specific problems
  • Use Matlab or other numerical software for solving systems of equations

Grading

50% Assignments

40% Project (progress reports, in-class presentation, final report)

10% Class participation

Recommended Texts

  • Iterative Methods for Sparse Linear Systems, 2nd edition, by Yousef Saad, SIAM, 2003.
  • Numerical Methods for Unconstrained Optimization and Nonlinear Equations, by J. E. Dennis, Jr. and Robert B. Schabel, SIAM, 1996.
  • Matrix Computations, 4th edition, by Gene Golub and C. F. van Loan, Johns Hopkins, 2013.
You should already have the third book from your course in Numerical Linear Algebra. You can order the first two books from SIAM, here. You can get a 30 percent discount if you are a SIAM member. As a student, you can join SIAM for free, since Georgia Tech is an Academic Member. Check it out here! These two books are also available electronically from the Georgia Tech library.