Revised Sept 30, 2015

Watch a video introduction to this course on YouTube.

CS 475 covers four major topics: solving special linear systems, least squares problems, eigenvalue problems, and singular value decomposition. The course introduces students to mathematical concepts and numerical methods used for solving mathematical problems and to the implementation of algorithms in a high-level programming language framework.

- CS major students. Usually taken in fourth year.

- Summer

- Pre-requisites: AMATH 242/CM 271/CS 371 or CS 370; Not open to General Mathematics students students
- Anti-req: CM/CS 372, 472

For official details, see the UW calendar.

- UNIX

- L.N. Trefethen, D. Bau III,
*Numerical Linear Algebra*, SIAM, 1997 - J. Demmel,
*Applied Numerical Linear Algebra*, SIAM, 1997 - H. Wendland,
*Numerical Linear Algebra: An Introduction*,Cambridge University Press, 2017

At the start of the course, students should be able to

- Write programs in MATLAB
- Apply techniques and concepts of numerical computation, such as accuracy, stability, efficiency, floating point arithmetic, LU factorization
- Recall basic data structures, algorithms, and computer organization
- Use basic linear algebra and calculus

At the end of the course, students should be able to

- Use matrix factorizations in solving numerical linear algebra problems
- Analyze the complexity of numerical linear algebra algorithms
- Apply the numerical techniques for solving application problems
- Implement numerical linear algebra algorithms using MATLAB
- Develop a set of numerical linear algebra routines for solving linear systems, least squares problems, eigenvalue problems, and singular value decomposition.

- Examples of special matrices: symmetric, positive definite, tridiagonal, band, general sparse matrices
- Direct methods: sparse Gaussian elimination, basic graph theory, ordering algorithms
- Iterative methods: Jacobi, Gauss-Seidel, SOR, conjugate gradient
- Convergence analysis and concepts of preconditioning
- Example application: Image denoising using total variation models

- Data fitting, parametric estimation, overdetermined systems, and least squares problems
- Orthogonal matrices and orthogonal projection
- Different approaches for solving least squares problems, such as normal equations, QR factorization, and singular value decomposition
- Compute QR factorization using Gram-Schmidt, Householder transform, and Givens rotation

- Basic concepts of eigenvalues and eigenvectors
- Compute eigenvalues and eigenvectors using power methods, inverse iteration, Rayleigh-quotient iteration, and QR algorithm
- Connection between QR algorithm and simultaneous iteration
- Complexity and reduction to Hessenberg or tridiagonal form
- Example applications: Google page ranking, image segmentation

- Basic concepts of singular values and singular vectors
- Compute SVD via eigenvalue decomposition
- Implementation using bidiagonalization
- Low rank approximation using SVD and its application

David R. Cheriton School of Computer Science

University of Waterloo

Waterloo, Ontario, Canada N2L 3G1

Tel: 519-888-4567 x33293

Fax: 519-885-1208

Contact | Feedback: cs-webmaster@cs.uwaterloo.ca | David R. Cheriton School of Computer Science | Faculty of Mathematics