CS475/CM375 - Fall 2010  Computational Linear Algebra

Objectives

1. solving special linear systems,
2. least squares problems,
   
3. eigenvalue problems, and
   
4. singular value decomposition.

Outline

The topics we will cover include:

• Solving Linear Systems:
  
• LU factorization, Cholesky factorization.
  
• Special matrices: tridiagonal, band, general sparse matrices.
  
• Iterative methods, conjugate gradient, convergence.
• Least Squares Problems:
  
• Pseudo inverse.
  
• QR factorization.
  
• Householder transform,
  
• Givens rotation.
• Eigenvalue Problems:
  
• Eigenvalues and eigenvectors.
  
• Characteristic polynomials.
  
• Schur form.
  
• Power iteration, inverse iteration.
  
• QR method.
  
• Jacobi, divide-and-conquer.
• Singular Value Decomposition:
  
• Bidiagonalization.
  
• Search engine.

The course material will be covered primarily in lectures. You should also read the appropriate sections of the textbook for each lecture.

There will be four assignments given in the course.  Each assignment will have a theoretical part and a programming part in Matlab. Assignments must be done individually (i.e., no teamwork).  The approximate out and due dates are:

• A1: out Sept 21, due Oct 12
  
• A2: out Oct 12, due Nov 2
  
• A3: out Nov 2, due Nov 18
  
• A4: out Nov 18, due Dec 2
  

There will be a midterm on Nov 9 and a final exam scheduled by the registrar.

Grading Scheme

• Assignments (4): 40% (10% each)
• Midterm: 10%
  
• Final Exam: 50%

Textbook

Material on Reserve in the library

These reference texts contain the algorithms discussed in class. References to these texts will be made from time to time.

• Numerical Linear Algebra (textbook)
  L.N. Trefethen and D. Bau III
  QA184.T74, 1997
• Applied Numerical Linear Algebra
  J. Demmel
  QA184.D455, 1997
• Matrix Computations
  G. Golub and C. Van Loan
  QA188.G65x, 1989.
• Iterative Methods for Sparse Linear Systems
  Y. Saad
  QA188.S17, 2003. (Also available on-line; see below)
• Direct Methods for Sparse Matrices
  Duff, Erisman, Reid
  QA188.D84
• Computer Solution of Large Sparse Positive Definite Systems
  George and Liu
  QA188.G46

References Available On-line

• Youcef Saad's Home Page
  Notably, this has the full first edition of his book Iterative methods for sparse linear systems (Revised 1st edition, 2000) available for reference on-line.
• Jonathon Shewchuck's Papers page
  This is home of the highly recommended paper "An Introduction to the Conjugate Gradient Method Without the Agonizing Pain".
• Templates for the Solution of linear Systems
  This 1994 book contains all of the basic algorithms for iterative solution in a fairly easy to read form.
• Mathworld at the Wolfram site has lots of good basic mathematical information.
• "Improving the memory-system performance of sparse-matrix vector multiplication" is an interesting article that gives you a taste of just how focused on creating fast code some people can get.

Software and Data

• Netlib
  This is a traditional repository for mathematical software. Lots of stuff.
• LAPACK
  Linear Algebra PACKage. It is a widely used linear algebra lirary which contains highly efficient implementation of numerical linear algebra methods for solving linear systems, least squares problems, eigenvalue problems, and singular value decomposition.
• Matrix Market contains a set of standard test matrices from fluid dynamics and from engineering.

Policies