CS 475 | SCS | UW

Revised Sept 30, 2015

CS 475: Computational Linear Algebra

Watch a video introduction to this course on YouTube.

General description

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.

Logistics

Audience

  • CS major students. Usually taken in fourth year.

Normally available

  • Summer

Related courses

  • 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.

Software/hardware used

  • UNIX

Typical reference(s)

  • 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

Required preparation

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

Learning objectives

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.

Typical syllabus

Solving special linear systems (15 hours)

  • 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

Least squares problems (8 hours)

  • 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

Eigenvalue problems (7 hours)

  • 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

Singular value decomposition (6 hours)

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