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

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

• 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