CPSC 660: Computational Linear Algebra (Spring 08)

 

Instructor

Vivek Sarin, 309C HRBB, 458-2214, sarin@cs.tamu.edu

Lecture

TR, 12:45pm-2:00pm, ZACH 227A

Office Hours

TR, 11:30am-12:30pm

Prerequisites

CPSC 442 or MATH 417 or equivalent

Textbook

Numerical Linear Algebra by Lloyd N. Trefethen and David Bau, III

Reference

Matrix Computations by Gene H. Golub and Charles V. Loan

 

Description

This course will focus on algorithms for matrix computations; the following broad topics will be covered:

·         Matrix fundamentals

·         Solution of systems of equations

·         Orthogonalization and Least-Squares problems

·         Eigenvalue problems

·         Iterative methods for systems of equations

Computational techniques will be accompanied by error and stability analysis. Homework will consist of theoretical problems as well as programming exercises using MATLAB. You are expected to learn basic MATLAB during the early part of the course (this is not at all difficult).

Outline

·        Fundamentals: Vectors, Norms, Matrices

·        QR Factorization and Least Squares: Gram-Schmidt orthogonalization, Householder reflections and Givens rotations, QR factorization of a matrix, Least Squares problems

·        Conditioning and Stability: Conditioning of a problem, Floating point arithmetic, Stability of algorithms

·        Systems of Equations: Gaussian elimination, Pivoting, Stability of Gaussian elimination, Cholesky factorization,

·        Sparse linear systems: Factorization techniques for sparse matrices

·        Eigenvalues: Eigenvalue problems; Reduction to Hessenberg or tridiagonal form; Rayleigh quotient, power method, inverse iteration; QR method; Other algorithms (Jacobi, bisection, divide-and-conquer, SVD)

·         Iterative Methods: Stationary iterative methods (Jacobi, Gauss-Seidel, SOR); GMRES; Conjugate gradients method; Preconditioning for convergence; Other iterative methods

Homework

Homework assignments will be given once every couple of weeks. They will be posted in the Lecture Schedule section below. 

MATLAB

You are expected to learn basic MATLAB during the early part of the course. CS majors should use their accounts on department machines to access MATLAB. Non-CS majors with no access to MATLAB in their respective departments should contact the CS system administrators for accounts. MATLAB documentation can be found at the MathWorks web site.

Grading

The final grade will depend upon your performance on homework and three exams as follows:

Homework

25%

Exam 1

25%

Exam 2

25%

Exam 3

25%

Homework policy: 1 day late: -10%, 2 day late: -20%, 3 day late: -40%, 4 or more days late homeworks will not accepted

Exams: All exams are open-book/open-notes

Scholastic Dishonesty

University regulations (Section 42) define scholastic dishonesty to include acquiring answers from any unauthorized source, working with another person when not specifically permitted, observing the work of other students during any exam, providing answers when not specifically authorized to do so, informing any person of the contents of an exam prior to the exam, and failing to credit sources used. Disciplinary actions range from grade penalty to expulsion. 

Lecture Schedule (Tentative)

Handouts, homework assignments, solutions, etc., will be available here.

 

 

Tue

Thu

 

Tue

Thu

1/15

Fundamentals

Fundamentals

3/22

QR Factorization

QR Factorization

 

 

 

 

 

 

1/29

QR Factorization

QR Factorization

3/5

Conditioning and Stability

Conditioning and Stability

 

 

 

 

 

 

2/12

Floating Point Arithmetic

Floating Point Arithmetic

3/19

Linear Systems

Linear Systems

 

 

 

 

 

 

2/26

Linear Systems

Linear Systems

3/4

Sparse Linear Systems

Sparse Linear Systems

 

 

 

 

 

 

3/11

Spring

Break

3/18

Sparse Linear Systems

Sparse Linear Systems

 

 

 

 

 

 

3/25

Eigenvalues

Eigenvalues

4/1

Eigenvalues

Eigenvalues

 

 

 

 

 

 

4/8

Iterative Methods

Iterative Methods

4/15

Iterative Methods

Iterative Methods

 

 

 

 

 

 

4/22

Iterative Methods

Iterative Methods

4/29

No class

 

 

 

 

 

 

 

Final Exam: May 7, 8:00am-10:00am (Wed.)

 

Last updated by Vivek Sarin on November 16, 2007