CS475/CM375 - Fall 2011 Computational Linear Algebra
Instructor: Pascal Poupart
Email: ppoupart [at] cs [dot] uwaterloo [dot] ca
Office Hours: Wednesday 10-11:30 am (DC2514)
Lectures: Tuesday & Thursday 10-11:20 am (DWE3519)
TA: Ricardo Salmon (rsalmon
cs [dot] uwaterloo [dot] ca)
Numerical linear algebra is a basic part of many problems in scientific
computation. This course provides an overview of algorithms and
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
- solving special linear systems,
- least squares problems,
- eigenvalue problems, and
- singular value decomposition.
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:
- Search engine.
It is assumed that each student has completed an introductory course in
numerical computation (i.e., AMATH341, CM271, CS371 or CS370).
material will be covered primarily in lectures.
You should also read the appropriate sections of the textbook for each
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
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.
- 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
There will be a midterm on Nov 3 and a final exam scheduled by the
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.
- Assignments (4): 40% (10% each)
- Midterm: 10%
- Final Exam: 50%
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
- Applied Numerical Linear Algebra
- Matrix Computations
G. Golub and C. Van Loan
- Iterative Methods for Sparse Linear Systems
QA188.S17, 2003. (Also available on-line; see below)
- Direct Methods for Sparse Matrices
Duff, Erisman, Reid
- Computer Solution of Large Sparse Positive Definite Systems
George and Liu
References Available On-line
Software and Data
This is a traditional repository for mathematical software. Lots of
Linear Algebra PACKage. It is a widely used linear algebra lirary which
contains highly efficient implementation of numerical linear algebra
for solving linear systems, least squares problems, eigenvalue
singular value decomposition.
Market contains a set of standard test matrices from fluid dynamics
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.
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/]
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.
typical penalties check Guidelines for the Assessment of Penalties,
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.