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

Basic Information
    The course will survey contemporary topics in numerical linear algebra, including iterative solution algorithms for sparse linear systems of equations, fast direct methods for sparse linear systems, numerical methods for solving eigenvalue problems, reduced-order models for parameter-dependent discrete partial differential equations, and (time permitting) approximate and probabilistic methods in linear algebra. Both theoretical and computational issues will be studied.

    It is expected that students have had some exposure at the graduate level to topics in Numerical Analysis / Scientific Computing, including matrix factorizations, discrete partial differential equations, singular value decompositions, or, with the permission of the instructor, be willing to learn such material as the course proceeds.
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
  • Fast Direct Methods for Sparse Matrices
    • Low-rank matrices
    • Fast algorithms for rank-structured matrices
    • Dissection algorithms
    • Hierarchical solvers
  • Computational Methods for Eigenvalue Problems
    • Classic method: QR algorithm
    • Lanczos and Arnoldi methods
    • The Krylov-Schur method
  • Reduced-order models for Parametrized Problems
    • The online-offline paradigm
    • Greedy sampling methods to construct reduced bases
    • Reduced-order models for Monte Carlo simulation
  • Approximate and Probabilistic Methods in Linear Algebra (time permitting)
    • Low-rank computations
    • Probabilistic methods
    • The CUR factorization
There will be no assigned text. Principal references for each of the topics are:
  • Iterative methods:
      Y. Saad, Iterative Methods for Sparse Linear Systems, Second Edition, SIAM Publications, Philadelphia, 2003.
  • Fast direct methods:
      P. G. Martinsson, Fast Direct Solvers for Elliptic PDEs, SIAM Publications, Philadelphia, 2020.
  • Eigenvalue methods:
      G. W. Stewart, Matrix Algorithms Volume II: Eigensystems, SIAM Publications, Philadelphia, 2001.
  • Reduced-order models:
      A. Quarteroni, A. Manzoni and F. Negri, Reduced Basis Methods for Partial Differential Equations, Springer, 2016.
Other useful references are:
  • 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.
  • J. S. Hesthaven, G. Rozza and B. Stamm, Certified Reduced Basis Methods for Parametrized Partial Differential Equations, Springer, 2015.
  • Y. Saad, Numerical Methods for Large Eigenvalue Problems, Manchester University Press, Manchester, 1992.
  • D. S. Watkins, The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods, SIAM Publications, Philadelphia, 2007.
The references by Saad are available at
Several of the books published by SIAM are available in electronic format, at no cost to SIAM members, through the SIAM web page, SIAM membership is free for UMD students who use the UMD VPN to connect.
Grades will be determined as follows:
  • 4-6 homework assignments: 40%
  • In-class midterm examination: 25%
  • Final exam or course project (decision to be made near the beginning of the term): 35%
The homework will consist of both analysis and computational testing. Computations can be done using any convenient programming tools.

Other Policy Matters

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 26, 2023]