Numerical Computing, CSCI-UA 421
Instructor: Michael L. Overton
Spring 2017
Class Meets: Tue, Thu 9:30 - 10:45 a.m., 60 Fifth Ave, Room C12 (before spring break) and Room C04 (after spring break)
Information
- Office: WWH 429
- Telephone: 998-3121
- Office Hours: Mon 5 p.m. - 6 p.m., Thu 11 a.m. - 12 noon, or try dropping by any time or send e-mail for an appointment
- Email: overton@cs.nyu.edu
Course Summary
Introduction to numerical computation: the need for floating-point arithmetic,
the IEEE floating-point standard.
Importance of numerical computing in a wide variety of scientific applications.
Fundamental types of numerical algorithms: direct methods
(e.g. for systems of linear equations), iterative methods
(e.g. for a nonlinear equation), and discretization methods
(e.g. for a differential equation). Conditioning and stability.
How can you tell if you can trust your answers? We will use the computer
a lot in class and you should become quite proficient with Matlab by the end
of the course. If you like math as well as programming, you should enjoy
this class!
Prerequisites
Computer Systems Organization (CSCI-UA 201), either Calculus I (MATH-UA 121) or both of Mathematics for Economics I and II (MATH-UA 211 and 212), and Linear Algebra (MATH-UA 140), or permission of instructor. Knowledge of Matlab in advance is not expected.
The Linear Algebra prerequisite is particularly important; if you are not sure if you have enough background, discuss this
with me. If you have already taken the math department's Numerical Analysis course, you may find there is a lot of overlap
in this course; if you are not sure if you should take the course anyway, please discuss this with me.
Requirements
- Attend class
- Read the chapters from the two text books that are listed in the "Lectures" summary below, and any other
assigned notes
- Do the homework (worth about 50% of the final grade)
- Write midterm exam and final exam (worth about 20% and 30%, respectively, of the final grade)
Lectures
- Tue Jan 24: introduction and overview, computer representation of numbers (my book, chap 1-3)
- Thu Jan 26: IEEE floating point representation, rounding (my book, chap 4-5)
- Tue Jan 31: Correctly rounded floating point operations, exceptions, etc (my book, chap 6-10)
- Thu Feb 2: Cancellation, condition of problems (my book, chap 11-12)
- Tue Feb 7: Stability of algorithms (my book, chap 13-14)
- Thu Feb 9: SNOW DAY
- Tue Feb 14: Linear algebra review (A&G, chap 4), polynomial interpolation via Vandermonde matrices (A&G, chap 4),
introduction to MATLAB. Skip sections on eigenvalues, singular values, SVD and differential equations for now.
- Thu Feb 16: Solving linear systems of equations (A&G, sec 5.1-5.2): back substitution, Gaussian elimination,
equivalence to LU decomposition, what happens if we don't use pivoting (row interchanges):
programs backsolve.m, gauss_el.m
- Tue Feb 21: Inverse and determinant from LU factorization, partial pivoting (row interchanges)
and the PA=LU factorization, worst case instability: program LUppUnstableExample.m (A&G, sec 5.3)
- Thu Feb 26: Efficient implementation of LU factorization,
LU for symmetric positive definite matrices and Cholesky factorization (A&G, sec 5.4-5.5)
- Tue Feb 28: Sparse matrices, especially tridiagonal matrices: programs symtridiag.m,
demo_symtridiag.m, demo_symtridiag_2.m
(A&G, sec 5.6)
- Thu Mar 2: Errors, residuals and condition numbers for solving Ax=b (A&G, sec 5.8): programs
resid_LUppUnstableExamplePerturbed.m,
resid_LUppUnstableExamplePerturbed_demo.m
- Tue Mar 7: Review. Floating Point Puzzles
- MIDTERM and SPRING BREAK
- Tue Mar 21: Review of Midterm Exam: midtermQ7.m, Eigenvalues
- Thu Mar 23: Eigenvalues (continued) and Singular Values
- Tue Mar 28: SVD, continued: rank, range and null spaces, pseudoinverse:
Least squares problems, normal equations (A&G, sec 6.1)
- Thu Mar 30: Least squares, continued: QR factorization (A&G, sec 6.2), SVD (A&G, sec 8.2, p.234--235),
Updated notes on Eigenvalues, Singular Values and QR.
- Tue Apr 4: Computing QR via Householder reflectors (A&G, sec 6.3, p.159--160); PageRank (A&G, sec 8.1,
pp. 220, 223-226)
- Thu Apr 6: Power Method (A&G, sec 8.1) and the Block Power Method (Subspace Iteration, A&G, sec 8.3, p. 239),
programs powermethod.m, blockpowermethod.m
- Tue Apr 11: Bisection and Newton methods (A&G, chap 3 except 3.3),
Notes on Quadratic Convergence of Newton's Method
- Thu Apr 13: Differential equations example in one space dimension (A&G, Example 4.17, p. 85-86),
differential equations example in two space dimensions (Poisson equation, discrete Laplacian)
(A&G, Example 7.1, pp. 168-172), construction of five-point discrete matrix using column-wise ordering
in Matlab and its sparsity structure, fill-in using Cholesky
- Tue Apr 18: Gradient descent method (A&G, section 7.4)
- Thu Apr 20: More on gradient descent (program: gradient_descent.m),
Conjugate gradient method (A&G, section 7.4,
my notes on Krylov Space Property of Conjugate Gradient Method)
- Tue Apr 25: Preconditioned CG, incomplete Cholesky (A&G, section 7.4);
Newton's method for nonlinear systems of equations (A&G, section 9.1);
program: nonlinear_bvp_newton.m
- Thu Apr 27: Gradient descent and Newton's method for optimization of nonlinear functions (A&G, section 9.2)
- Tue May 2: Inverse and Rayleigh quotient iteration for eigenvalues (A&G, p.227-228),
Householder reduction to tridiagonal and Hessenberg form and ``inefficient" QR iteration for eigenvalues
(A&G, p.236-240)
- Thu May 4: Review
Exams
- Thu Mar 9: Midterm exam. Covers: my book, A&G Chapters 4 and 5 except material on eigenvalues,
singular values, SVD, differential equations, and sec 5.7. No books or e-devices.
- Thu May 11, 8:00AM-9:50AM : Final exam. Room: Warren Weaver Hall, 251 Mercer St, Room 102.
No books or e-devices. Covers: A&G Sections 3.2, 3.4, 6.1, 6.2, 6.3 (except Gram-Schmidt),
7.1, 7.4, 8.1, 8.2, 8.3 (except p. 240-242), and 9.1,
as well as my notes on Eigenvalues, Singular Values and QR,
Quadratic Convergence of Newton's Method, and Krylov Space Property of Conjugate Gradient Method.
The emphasis will be on material covered in homeworks 5 through 8.
Homework
It is important that you do the homework yourself (not jointly with another
student), but when you get stuck, I encourage you to consult with
other students, or me, to get help when necessary. However, when you get help,
it's important to acknowledge it in writing in your homework submission. Passing off other people's
work as your own is called plagiarism and is not acceptable.
For more information, see the CS department's policy on integrity.
Homework is due at 5:00 pm on the given date.
Late homework will be penalized 20%.
Homework will not be accepted more than one week late,
except in special circumstances.
- Homework 1, assigned Jan 26, due Feb 2
- Homework 2, assigned Feb 2, due Feb 9; extended to Feb 14 ***AT 5 P.M.***
- Homework 3, assigned Feb 14, due Feb 21 ***AT 5 P.M.***
- Homework 4, assigned Feb 21, due Mar 7 ***AT 5 P.M.***
- Homework 5, assigned Thu Mar 23, due Friday Mar 31 ***AT 5 P.M.**
(see Notes on Eigenvalues and Singular Values)
- Homework 6, assigned Thu Mar 30, due Friday Apr 7 ***AT 5 P.M.**
(Data for hw6)
- Homework 7, assigned Thu Apr 7, due Tuesday Apr 18 ***AT 5 P.M.**
(Matrix M and cell array url for Google 500)
(Matrix A and cell array url for Purdue 77587)
- Homework 8, assigned Tue Apr 18, deadline extended to Thu May 4 ***AT 5 P.M.**
(WallOfWindows.jpg)
Required Text Books
- Numerical Computing with IEEE Floating Point Arithmetic, by the instructor, SIAM (all chapters)
- A First Course on Numerical Methods, by Uri Ascher and Chen Greif (chapters to be announced)
Required Software
Class Mailing List
The class mailing list email address is csci_ua_0421_001_sp17@cs.nyu.edu.
All registered students should automatically be members of the list.
This list will be used for important announcements.
You can also send questions or comments to this list yourself (contact me
if you have questions about when this is appropriate).
If you are not already a member but want to join, go to the
web page for the course list.
Don't Hesitate to Ask for Help
If you have questions, send me email, give me a call, or drop by my office.
Don't wait until it's too late!