Numerical Linear Algebra
Learning Objective:At the end of the course, you should: understand the algorithms underlying matrix computations software for dense matrices, be able to implement basic versions of these algorithms, understand the difference between iterative methods for linear systems and direct methods, be able to implement iterative methods for large scale problems, appreciate the variety of applications of matrix computations. Students will:
a) become knowledgeable about major kernels and algorithms underlying matrix computations for dense and sparse matrices including linear systems of equation, symmetric eigenvalue problems, and the singular-value decomposition
b)be able to implement basic versions of these kernels and algorithms
c) learn the difference between direct and iterative methods for linear systems
d)gain expertise in the design of iterative methods and preconditioning techniques for large-scale sparse linear systems
e)be able to implement eigenvalue and singular-value problem solvers.
Description:This course is an in-depth study of numerical linear algebra and the matrix computations that arise in solving linear systems, least squares problems, and eigenvalue problems for dense and sparse matrices. It will cover many of the fundamental algorithms such as the LU decomposition, the Cholesky decomposition, the conjugate gradient method, and the GMRES method. The course is designed for those who wish to use matrix computations in their own research and especially those in applied engineering and science.
Topics Covered:Dense Matrix Computation: Direct linear system solvers; LU and Cholesky factorization schemes, Norms and condition numbers, Pivoting strategies, scaling, and iterative refinement. Least squares problems; Orthogonal projections, Orthogonal factorization schemes--Givens, Householder, and Gram-Schmidt, Singular-value decomposition. The symmetric eigenvalue problem; Eigenvalues and eigenvectors, Power method and inverse iteration, Reduction to the tridiagonal form, Extraction of eigenpairs. Iterative methods for sparse linear systems: Discretization of partial differential equations, Sparse matrices, Basic iterative linear system solvers, Projection methods, Krylov subspace methods, Schemes for normal equations, Preconditioning techniques.
Prerequisites:A bachelor degree in computer science or an equivalent field. Students not in the Computer Science master's program should seek department permission to register.
This class is an in-depth graduate lecture class. You (the student) should have taken a mathematical course on linear algebra that covers vector spaces as well as a numerical analysis course that covers computer implementations of numerical algorithms.
Applied / Theory:40 / 60
Web Content:Syllabus, schedule, readings, references, homework assignments, and message board. Piazza to support course
Homework:Frequent quizzes and homeworks.
Exams:One midterm and a final exam.
Textbooks:Official textbook information is now listed in the Schedule of Classes. NOTE: Textbook information is subject to be changed at any time at the discretion of the faculty member. If you have questions or concerns please contact the academic department.
Tentative--Matrix Computations. Gene H. Golub and Charles van Loan. 4th Edition, Johns Hopkins University Press. Numerical Linear Algebra. Lloyd N. Trefethen and David Bau. ISBN: 9781421407944 SIAM.