General Information

Intended audience

Recommended Reading

• Golub, Gene, ``Matrix computations".
• Briggs, William, ``A multigrid tutorial".
• Atkinson, Kendall, ``An Introduction to Numerical Analysis''.
• Other books about finite difference methods, finite element methods, integral equation methods, numerical ODE and numerical PDE.
• Selected research papers.

Course Outline

1. Basic Linear Algebra
   Overview/review of basic concepts in Numerical Linear algebra: vector and matrix norms, eigenvalues, stability and condition numbers, and direct vs. iterative methods.
2. Formulations : Applications involving Numerical Linear Algebra
   A brief introduction to each of the following topics will be presented with an emphasis on the type and character of the Numerical Linear Algebra problem each presents.
   • Finite Difference Methods
     Finite difference approximations. Two-point boundary value problems for ODE. Advection equations and the method of lines. The heat equation and semi-implicit methods. Linear convergence/stability analysis.
   • Finite Element Methods
     Variational formulations for two-point boundary value problems. Construction of elements and basic convergence analysis.
   • Integral Equation Methods
     Green's function, layer and volume potentials. Numerical solution of two-point boundary value ODE problems and two dimensional Poisson Equations. Integral equation method for the Heat equation.
   • Spectral Methods
     Fourier analysis and orthogonal polynomials. Numerical solution techniques for ODE two-point boundary value problems using Fourier series or Chebyshev polynomials.
   • Particle Methods
     The N-body problem for molecular dynamics, cosmology, and vortex dynamics. Overview of fast algorithms.
   • Least Squares Problems
     Applications of least squares problems to curve fitting, statistical modeling and geodetic modeling. Normal equations methods. Methods using QR decomposition and SVD decomposition.
3. Algorithms : Methods in Numerical Linear Algebra
   Solution techniques for a variety of Numerical Linear Algebra problems will be discussed. Attention will be paid to when a particular technique is preferred, available software, and how to test and evaluate methods. Linear Algebra problems from above will be used as examples.
   • Direct Methods
     Gauss Elimination and LU decomposition, QR decomposition. Direct methods for inverting certain sparse and dense matrices including symmetric positive definite matrices and Cholesky factorization, and banded matrices.
   • Iterative Methods for Linear Systems
     Basic iterative methods including Jacobi's method, Gauss-Seidel, and SOR. Multigrid method for one and two dimensional Poisson's equation. Krylov subspace based methods including Conjugate Gradient (CG) and GMRES.
   • Fast Matrix Vector Product/Fast Summation techniques
     The FFT and fast convolutions. Particle Mesh based methods including particle mesh (PM), precorrected FFT (pFFT), particle-particle particle-mesh (P3M), and particle mesh Ewald (PME). Multipole Expansion based methods including the Tree code and the fast multipole methods (FMM).
   • Eigenvalues and Single Value Decomposition
     Elementary concepts and a discussion of available numerical routines. Applications of Single Value Decomposition, including solution of rank deficient least squares problems, data/image compression.
4. Monte-Carlo Methods
   Pseudo random number generators, including the mapping methods, Box-Muller method, and rejection methods. Monte Carlo integration and variance reduction, simulation techniques for Markov Chains. Accurate time stepping methods for stochastic differential equations.

Programming