MPCS 58001 Numerical Methods (Summer 2018)

Course Description

This is a practical programming course focused on the basic theory and efficient implementation of a broad sampling of common numerical methods. Each topic will be introduced conceptually followed by detailed exercises focused on both prototyping (using matlab) and programming the key foundational algorithms efficiently on modern (serial and multicore) architectures.

The ideal student in this course would have a strong interest in the use of computer modeling as predictive tool in a range of discplines -- for example risk management, optimized engineering design, safety analysis, etc. The numerical methods studied in this course underlie the modeling and simulation of a huge range of physical and social phenomena, and are being put to increasing use to an increasing extent in industrial applications. After successfully completing this course, a student should have the necessary foundation to quickly gain expertise in any application-specific area of computer modeling.

Course Contents

Lesson 1:
Part I: Properties of Linear Systems
Part II: Gaussian elimination with backsubstition: pivoting, stability, operation count, implementing in matlab, C, and Fortran.
Reading: Numerical Recipes Ch. 1, 2.0-2.1

Lesson 2:
Part I: Floating point representation, roundoff error, stability
Part II: Real world linear systems: introduction to first piece of model app -- 1d implicit heat equation.
Readings: Numerical Recipes Ch. 2.2-2.4

Lesson 3:
Part I: Efficient Implemention of implicit 1-D heat equation solvers, LU decomposition; move to 2-3d version
Part II: Eigenvalues/vectors: basic theory
Readings: Numerical Recipes Ch. 9; Strang ch. 6

Lesson 4:
Part I: Eigenvector factorization: A = S Λ S-1; powers of A
Part II: Computing largest Eigenvalue/eigenvector numerically: power iteration; examples

Lesson 5:
Part I: A = Q R; Gramm Schmidt; approaches to calculating eigenvalues numerically
Part II: Norm, condition number, stability

Lesson 6:
Part I: More on QR, rotation matrices, similarity transformations

Lesson 7:
Part I: Complex eigenvalues/eigenvectors
Part II: Method of Steepest Descent

Lesson 8:
Part I: Jacobi iteration, Gauss-Seidel, and SOR
Part II: Introduction to Krylov Solvers

Lesson 9:
Part I: Pre-conditioned Conjugate gradient method
Part II: Efficient coding of sparse matrix multiply

Lesson 10: Survey Topics
Discrete Fourier Transforms
Systems of ODEs
Proper Orthogonal Decomposition

Core Programming
MPCS 50103 Mathematics for Computer Science: Discrete Math

Highly recommended: a basic background in linear algebra and calculus.

This class is scheduled at a time that does not conflict with any other classes this quarter.