Lectures:  TR 1:30-2:45 pm
Location:  Clough 423

Instructor:  Edmond Chow
E-mail: 
Office Hours: After class and by appointment

TA: Luke Erlandson
TA E-mail:  sudo@gatech.edu
TA Office Hours: Tuesdays 4:30-5:30 at KACB 1324; Fridays 3:45-4:45 at CODA S1377K


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
  • Related ideas for large-scale eigenvalue problems
  • Methods based on biorthogonalization (if there is time)
  • Iterative methods for linear least squares
  • Preconditioning
  • Multigrid methods
  • Domain decomposition (if there is time)
  • 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, e.g., stochastic gradient descent

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 and exercises.

40% Project (project options will be given in class).

10% Class participation.

Audit and Pass/Fail

Please inform the instructor and TA if you are taking the course for audit or pass/fail. If you wish to take the course for audit credit, you do not need to do a project, but you must attempt all the assignments and score at least 20% on each of them. If you wish to take the course as pass/fail, you need to score 50% or higher to pass the course. To accomplish this, you will likely need to make some attempt at the project.

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, by Gene Golub and C. F. van Loan. Any edition is fine.
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!