Computer Science

ECS 230 Applied Numerical Linear Algebra

ECS 230 APPLIED NUMERICAL LINEAR ALGEBRA (4) I

Lecture: 3 hours

Discussion: 1 hour

Prerequisite: Course ECS 130 or Engineering Applied Science 209 or Mathematics 167

Grading: Letter; problem sets and projects (30%), midterm (30%), final (40%)

Catalog Description:

Numerical linear algebra (NLA) with emphasis on applications in engineered systems; matrix factorizations; perturbation and rounding error analyses of fundamental NLA algorithms. Offered in alternate years.

Goals:

To give students an in-depth introduction to the graduate-level numerical linear algebra (NLA) that lies at the heart of all modern computational science and engineering. Throughout the course there is an emphasis on the interplay between the underlying mathematical descriptions of algorithms and their implementation on specific computing machines with specific software. Students should gain from the course an ability to be an intelligent, discriminating user of current algorithms and software in NLA and related disciplines.

Expanded Course Description:

  1. Review of Finite Arithmetic
    1. Approximating real numbers — what can go wrong?
    2. The IEEE floating-point arithmetic standard
  2. Conditioning and Numerical Stability
    1. Perturbation theory and conditioning
    2. Numerical stability, backward stability
    3. Accuracy of computed solutions
  3. Introduction to Rounding Analysis
  4. Numerical Matrix Algebra
    1. Elementary complexity analysis
    2. Software details
    3. Memory management
    4. Structured matrices
  5. Solution of Linear Systems
    1. Elementary transformations
    2. Gaussian elimination
    3. Triangular matrix factorizations
    4. Scaling
    5. Perturbation theory and conditioning
    6. A posteriori bounds and iterative improvement
    7. LINPACK and LAPACK implementations
  6. Solution of Linear Least Squares Problems
    1. Perturbation theory for pseudoinverses and linear least squares problems
    2. Householder transformations
    3. QR factorization
    4. Other algorithms (normal equations, Gram-Schmidt, Givens transformations, SVD, etc.)
    5. LINPACK and LAPACK implementations
  7. Computing Eigenvalues and Eigenvectors
    1. Perturbation theory and conditioning
    2. Reduction to Hessenberg and tridiagonal form
    3. The QR algorithm
    4. EISPACK and LAPACK implementations
  8. Other QR-type Algorithms
    1. Golub-Reinsch SVD algorithm
    2. QZ algorithm for generalized eigenvalue problems
    3. VZ algorithm
  9. Computation of Functions of Matrices
    1. The matrix exponential
    2. The matrix logarithm
    3. Condition estimation for matrix functions
  10. Solution of Special Matrix Equations
    1. Lyapunov equations
    2. Sylvester equations
    3. Algebraic Riccati equations

Textbook:

A.J. Laub, Computational Matrix Analysis (not published), LaTeX notes

Instructors: Z. Bai

Prepared by: A.J. Laub (January 2002)

Overlap Statement:

This course does not have a significant overlap with any other course. It covers some of the same general topics as Math 229A, but does so at a more applied and software-related level.

Applications in computational science and engineering are emphasized throughout. This course is suitable for graduate students in any department in the College of Engineering or the Division of Mathematical and Physical Sciences.

8/05

border