MAT 321 - Numerical Analysis and Scientific Computing - Spring 2023

Instructor: Marc Aurèle Gilles

AI: Qinxin Yan

Course Description:

I like David Bindel's description of his numerical analysis class: "Scientists, engineers, mathematicians, and computer scientists use models to describe everything from the ringing of bells to the evolution of animal populations to the relationships between web pages. We turn to computers to help us analyze all but the simplest such models; but how can an inherently discrete device such as a computer solve continuous problems quickly and reliably? This is the fundamental question we address in (...)" MAT321.

More concretely, we cover the fundamental algorithms of computational mathematics: matrix decompositions, eigenvalue iterations, iterative linear algebra, optimization, interpolation, numerical quadrature, and more. We analyze the stability and accuracy of these algorithms and explore their applications to image processing, data science, and the numerical solution of differential equations. Along the way, we cover the majority of the top 10 algorithms of the 20th century.

In lectures, we cover the derivation and theory of algorithms, often illustrated by numerical experiments. The precepts are mostly reserved for programming-focused tasks. In problem sets, we discuss applications and derive and implement other interesting algorithms. This year, by popular demand, the class was in Python.

Problem sets:

• Finite difference methods, structured matrix-vector products, image alignment [hw2.ipynb]
• Matrix equations, displacement rank, deblurring images [hw3.ipynb]
• Eigenvalue problems, Bartels-Stewart, Poisson's equation [hw4.ipynb]
• The FFT, Chebyshev polynomials, preconditioning Krylov methods, ADI [hw5.ipynb]

Precepts:

• Matrix norms [precept3.ipynb]
• QR decomposition [precept4.ipynb]
• LU decomposition [precept5.ipynb]
• Midterm practice problems [precept6.ipynb]
• Reduction to Hessenberg [precept7.ipynb]
• Eigenvalue iterations [precept8.ipynb]
• Krylov subspace methods [precept9.ipynb]
• Interpolation [precept10.ipynb]
• Numerical quadrature [precept11.ipynb]

Lecture topics:

• Lecture 1: Introduction, root-finding, bisection
• Lecture 2: Newton's method, secant method, fixed point iterations
• Lecture 3: Floating point arithmetic
• Lecture 4: Intro to numerical linear algebra: complexity, matrices, vectors
• Lecture 5: Matrix norms, singular values
• Lecture 6: The singular value decomposition, the eigenvalue decomposition
• Lecture 7: The QR decomposition, Gram-Schmidt
• Lecture 8: QR by Householder reflection
• Lecture 9: Least-squares problem, ill-conditioning, and regularization
• Lecture 10: The LU decomposition, pivoting
• Lecture 11: The Cholesky decomposition, exploiting matrix structure
• Lecture 12: More structured linear systems
• Lecture 13: Intro to eigenvalue problems
• Lecture 14: Power iterations
• Lecture 15: Subspace iterations, the QR algorithm
• Lecture 16: Shifted QR, the Arnoldi iteration
• Lecture 17: Iterative linear algebra, Krylov subspace methods
• Lecture 18: The conjugate-gradient method
• Lecture 19: Polynomial interpolation
• Lecture 20: Numerical quadrature
• Lecture 21: Approximation theory
• Lecture 22: Initial value problems, Euler's method
• Lecture 23: Runge-Kutta and implicit schemes
• Lecture 24: Recap, the top 10 algorithms

Textbooks used:

• Numerical linear algebra by Lloyd N. Trefethen and David Bau
• An introduction to numerical analysis by Endre Süli and David F. Mayers