CS475/CM375 - Fall 2011 Computational Linear Algebra
Instructor: Pascal Poupart
Office: DC2514
Email: ppoupart [at] cs [dot] uwaterloo [dot] ca
Website:
http://www.student.cs.uwaterloo.ca/~cs475
Newsgroup: uw.cs.cs475
Office Hours: Wednesday 10-11:30 am (DC2514)
Lectures: Tuesday & Thursday 10-11:20 am (DWE3519)
TA: Ricardo Salmon (rsalmon
[at]
cs [dot] uwaterloo [dot] ca)
Objectives
Numerical linear algebra is a basic part of many problems in scientific
computation. This course provides an overview of algorithms and
numerical linear
algebra techniques to solve common problems that arise in many areas
such as image processing, search engines, natural language processing,
computational finance, aircraft design and artificial intelligence. The
course is structured around four
major topics:
- solving special linear systems,
- least squares problems,
- eigenvalue problems, and
- 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.
Prerequisite:
It is assumed that each student has completed an introductory course in
numerical computation (i.e., AMATH341, CM271, CS371 or CS370).
Course
Organization:
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 20, due Oct 6
- A2: out Oct 6, due Oct 25
- A3: out Oct 25, due Nov 15
- A4: out Nov 15, due Dec 1
On the due date
of an assignment, the work done to date should be submitted at the
beginning of class; further material may be submitted for half credit
within 24 hours. Assignments submitted more than 24 hours late
will not be marked.
There will be a midterm on Nov 3 and a final exam scheduled by the
registrar.
Grading Scheme
- Assignments (4): 40% (10% each)
- Midterm: 10%
- Final Exam: 50%
In order to pass the course, students
must have a pass on the exam component. Thus you must obtain a
mark of 30 (out of 60) on the total of the midterm and final exam to
pass the course. Otherwise, your final grade will be your exam mark.
Textbook
Numerical Linear Algebra
L.N. Trefethen and D. Bau III
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
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
Academic Integrity:
In order to
maintain a culture of academic integrity, members of the University of
Waterloo community are expected to promote honesty, trust, fairness,
respect and responsibility. [Check www.uwaterloo.ca/academicintegrity/
for more information.]
Grievance: A student who believes that a decision affecting some
aspect of his/her university life has been unfair or unreasonable may
have grounds for initiating a grievance. Read Policy 70, Student
Petitions and Grievances, Section 4, www.adm.uwaterloo.ca/infosec/Policies/policy70.htm.
When
in doubt please be certain to contact the department’s
administrative assistant who will provide further assistance.
Discipline: A student is expected to know what constitutes
academic integrity [check www.uwaterloo.ca/academicintegrity/]
to
avoid committing an academic offence, and to take responsibility for
his/her actions. A student who is unsure whether an action constitutes
an offence, or who needs help in learning how to avoid offences (e.g.,
plagiarism, cheating) or about “rules” for group work/collaboration
should seek guidance from the course instructor, academic advisor, or
the undergraduate Associate Dean. For information on categories of
offences and types of penalties, students should refer to Policy 71,
Student Discipline, www.adm.uwaterloo.ca/infosec/Policies/policy71.htm.
For
typical penalties check Guidelines for the Assessment of Penalties,
www.adm.uwaterloo.ca/infosec/guidelines/penaltyguidelines.htm.
Appeals: A decision made or
penalty imposed under Policy 70 (Student Petitions and Grievances)
(other than a petition) or Policy 71 (Student Discipline) may be
appealed if there is a
ground. A student who believes he/she has a ground for an appeal should
refer to Policy 72 (Student Appeals) www.adm.uwaterloo.ca/infosec/Policies/policy72.htm.
Note for Students with Disabilities:
The Office for Persons with Disabilities (OPD), located in Needles
Hall, Room 1132, collaborates with all academic departments to arrange
appropriate accommodations for students with disabilities without
compromising the academic integrity of the curriculum. If you require
academic accommodations to lessen the impact of your disability, please
register with the OPD at the beginning of each academic term.