
Advanced Numerical Linear Algebra  AMSC/CMSC 763, Fall 2023

Basic Information



Overview

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,
reducedorder models for parameterdependent 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
 Lowrank matrices
 Fast algorithms for rankstructured matrices
 Dissection algorithms
 Hierarchical solvers
 Computational Methods for Eigenvalue Problems
 Classic method: QR algorithm
 Lanczos and Arnoldi methods
 The KrylovSchur method
 Reducedorder models for Parametrized Problems
 The onlineoffline paradigm
 Greedy sampling methods to construct reduced bases
 Reducedorder models for Monte Carlo simulation
 Approximate and Probabilistic Methods in Linear Algebra
(time permitting)
 Lowrank computations
 Probabilistic methods
 The CUR factorization


References

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.

Reducedorder 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
http://wwwusers.cs.umn.edu/~saad/books.html.
Several of the books published by SIAM are available in electronic format,
at no cost to SIAM members, through the SIAM web page,
https://siam.org/.
SIAM membership is free for UMD students who use the UMD VPN to connect.


Grading

Grades will be determined as follows:
 46 homework assignments: 40%
 Inclass 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.

 
