Advanced Numerical Linear Algebra - AMSC/CMSC 763, Fall 2019

Basic Information
 
Overview
  • The course will survey topics in numerical linear algebra, with emphasis on solution algorithms for sparse linear systems of equations and numerical methods for solving eigenvalue problems. Both theoretical and computational issues will be studied.
 
 
Outline of Topics Covered
  • Iterative Methods
    • Krylov subspace methods:
      the conjugate gradient, MINRES, GMRES methods and generalizations
    • Preconditioning methods: uses and derivation
    • Multigrid methods for partial differential equations
      Algebraic multigrid
    • Communication-avoiding methods
  • Computational Methods for Eigenvalue Problems
    • Lanczos and Arnoldi methods
    • The implicitly restarted Arnoldi method
    • Subspace iteration
    • The Jacobi-Davidson method
  • Approximate Methods in Linear Algebra
    • Low-rank computations
    • Probabilistic methods
    • Tensor methods
  • Linear Algebra and Machine Learning
    • Gradient descent and stochastic gradient descent methods
    • Principal component analysis
    • Functions of deep learning
    • Other topics TBD
 
Homework
 
References
There will be no assigned text. Much of the material can be found in the references listed below. These are largely affordable books and it will be useful to purchase one or two of them.
  • J. W. Demmel, Applied Numerical Linear Algebra, SIAM Publications, Philadelphia, 1997.
  • H. C. Elman, D. J. Silvester and A. J. Wathen, Fast Solvers and Finite Elements, Oxford University Press, Oxford, 2005.
  • G. H. Golub and C. Van Loan, Matrix Computations, Third Edition, Johns Hopkins University Press, 1996.
  • A. Greenbaum, Iterative Methods for Solving Linear Systems, SIAM Publications, Philadelphia, 1997.
  • Y. Saad, Iterative Methods for Sparse Linear Systems, Second Edition, SIAM Publications, Philadelphia, 2003.
  • Y. Saad, Numerical Methods for Large Eigenvalue Problems, Manchester University Press, Manchester, 1992.
    Available at http://www-users.cs.umn.edu/~saad/books.html.
  • G. Strang, Linear Algebra and Learning from Data, Wellesley-Cambridge Press, 2019.
  • G. W. Stewart, Matrix Algorithms Volume II: Eigensystems, SIAM Publications, Philadelphia, 2001.
  • D. S. Watkins, The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods, SIAM Publications, Philadelphia, 2007.
 
Grading
Grades will be determined as follows:
  • 4-6 homework assignments: 40%
  • In-class midterm examination: 25%
  • Course Project: 35%
The homework will consist of both analysis and computational testing. Computations can be done using any convenient programming tools although Matlab will be encouraged.

Plagiarism: You are welcome to discuss assignments in a general way among yourselves, but you may not use other students' written work or programs. Use of external references for your work should be cited. Clear similarities between your work and others will result in a grade reduction for all parties. Flagrant violations will be referred to appropriate university authorities.
 
[Last updated July 30, 2019]