CS 421 -Spring ’24

CSCI-UA.421 Numerical Computing

2024 Spring Syllabus and Schedule

Section Info: 11:00 AM – 12:15 PM Tu Th
251 Mercer St (Warren Weaver) Room 101 Loc: Washington Square

Course Description

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. Variety of examples from animation techniques used in games and CG will be given.

Pre-requisites:CS 102 (intro to computer science II) and Math 140 (linear algebra) or my permission. 

Office Hours: Wednesdays, 11.30-12.30 in-person

Please send me an email for appointment if this time is not good for you.

You are highly encouraged to visit the instructor during office hours without notice. Prepare for office hours by coming up with focused and targeted questions. In case there is a line of students waiting, the instructor will limit the meeting to a maximum of 5 minutes per student. You are also encouraged to meet with tutors. The schedule of the tutors will be uploaded on Brightspace and I will be sending emails about the schedule, separately.

Textbook:

PLEASE CHECK BRIGHTSPACE FOR THE SECOND EDITION OF PROF. OVERTON’S BOOK WITH NOTES 

Assignments

The assignments will be sent out via the Brightspace and the course website.

HW Submission: You will be asked to send your assignments via Brightspace. While you send your files (source codes, zip files, etc.), please use appropriate file names. For every 24 hours that an assignment is late, we will apply a 10% penalty on the grade, up to a maximum penalty of 30%. After 72 hours, we will no longer accept the assignment.

Grading

Please note that this grading policy is subject to change at any time without notice. If a change occurs, a new version will be uploaded on NYU Brightspace.

 Final grades for the course will be determined using the following weights:

    • MT – 24%
    • Final – 30%
    • Quizzes – 6%
    • Homework – 40%

The missed quizzes will not be made up.

Missing an exam: There will be no make-up exams. The only exception to this rule is for students who have a valid medical emergency. These students need to talk to the instructor as soon as possible.

The grade of Incomplete is reserved for students who, for legitimate and documented reason, miss the final exam. The grade of Incomplete will not be given to student who started falling behind in class. Those students can withdraw from the class.

Software

Required Software

    • MATLAB
      • https://www.mathworks.com/products/matlab.html
      • https://www.nyu.edu/life/information-technology/computing-support/software/software/matlab.html
      • https://guides.nyu.edu/matlab
      • There are many books on Matlab, e.g. :
Date Class Materials Covered Notes
01/23 #1 Intro and motivation, IEEE floating point representation Book of Overton: Chapter 1-4
01/25 #2 Rounding, absolute and relative rounding errors Book of Overton: Chapter 5
01/30 #3 Two loop programs, correctly rounded floating point operations, exceptions  Book of Overton: Chapter 6-7

Ch. 10
02/01 #4 Floating point microprocessor and programming language support for the standard, cancellation, approximating a derivative by a difference quotient Book of Overton: Chapter 8,9,11
02/06 #5 Conditioning of problems, intro to stability of algorithms Book of Overton: Chapter 12-13
02/08 #6 More on stability of algorithms Book of Overton: Chapter 13-14

Quiz 1
02/13 #7 Linear algebra review: linear independence of vectors, conditions for square matrix to be nonsingular, matrix rank. Vector and matrix norms, computing the matrix ∞ norm. Brief intro to polynomial interpolation via Vandermonde matrices. Book of Ascher & Greif starts here
02/15 #8 Polynomial interpolation via Vandermonde matrices. Matlab’s \ (backslash). Solving linear systems of equations: back substitution, Gaussian elimination without pivoting, equivalence to LU factorization (decomposition)  
02/20 #9 More details on the LU factorization, Gauss elimination with partial pivoting (GEPP) and the PA=LU factorization   
02/22 #10 Continuation of GEPP and its equivalence to PA=LU, demo that on random matrices  
02/27 #11 GEPP is stable, rare worst case instability of GEPP, banded matrices, Matlab’s sparse matrices Quiz 2
02/29 #12 GEPP stability continues

Cholesky factorization of positive definite matrices.

  
03/05 #13 Errors, residuals, condition numbers and stability for solving Ax=b 

Review of practice midterm

  
03/07 #14 Midterm  
03/12 #15 Review

Least squares: the normal equations and solution by Cholesky factorization, orthogonal vectors and matrices

  
03/14 #16 Least squares: solution via QR factorization using Householder reflections  Quiz 3
03/19   SPRING BREAK  
03/21   SPRING BREAK  
03/26 #17 Eigenvalues  
03/28 #18 Eigenvalues and SVD  
04/02 #19 The power method, inverse power method and Rayleigh quotient method for computing an eigenvalue of a real matrix  
04/04 #20 The power method cont. 

PAGE RANK example

  
04/09 #21 The [orthogonalized] block power method for computing several eigenvalues of a real matrix

Householder reduction of a matrix to Hessenberg or tridiagonal form, extensions for SVD

  
04/11 #22  Lagrange formula for polynomial interpolation, cubic splines   
04/16 #23 Bisection method and Newton’s method for solving a nonlinear equation, quadratic convergence of Newton’s method   
04/18 #24 Newton’s method for solving a system of nonlinear equations, boundary value problems for ordinary differential equations  Quiz 4
04/23 #25 Convex optimization, gradient descent method, backtracking line search, strong convexity  
04/25 #26 Complexity of gradient descent, Newton’s method for convex optimization,   
04/30 #27  Nonconvex optimization for deep learning: stochastic gradient method  
05/02 #28 Discussion of practice final