Course Home Page

Spring, 2006

goodman@cims.nyu.edu

(212)998-3326

Office hours: Wednesday, 10-12, after class, or by appointment. Office: 617

Teaching Assistant: Gennady Kasyan, kasyan@nyu.edu

Office hours: Tuesday, 4-5 or 7-8 or by appointment (send email at least 2 hours in advance) until midnight. Office: 607

Department of Mathematics

Department of Computer Science

Courant Institute of Mathematical Sciences

Class communications will be on the NYU Blackboard system. Always check the Message board there before starting an assignment. There often are corrections or hints. If you are registered, use your netid to login to he NYUHome site, then click on "academics" and then "Scientific Computing". Once there, click on "Communication", then "Discussion Board", the "Message board". Please email me with individual issues such as grading but post questions or comments on the message board. I will post announcements and corrections there.

This is a one semester graduate course covering the basics of practical scientific computing for mathematicians, computer scientists, physical scientists, and finance. Topics ranging from basic mathematical principles and algorithms of numerical analysis to practical issues ranging from software reliability to performance on modern computing hardware. The outline below contains details of contents.

The prerequisites are linear algebra, multivariate calculus, some computer literacy, and (for the Monte Carlo part) some exposure to elementary probability theory. Students are expected to program in C/C++ from the beginning. With considerable effort, a student could learn C/C++ while taking the course; see below for more on this. I write C/C++ to indicate that students may use C or C++. For the scientific computing software we build in this class, the distinction between C and C++ is monor. Students will also be expected from the beginning to use scientific visualization software. I highly recommend Matlab for this purpose. It is very easy to learn and use and gives high quality plots. A depricated alternative is Excel. Matlab for the PC is available to NYU students through the NYU Computer Store for $99. Matlab and C/C++ environments are also available on the SUN workstation network maintained by the Courant Institute. All students registered for the course are entitled to use this system.

The grade will be based on weekly homework assignments the majority of which involve computing. Students are encouraged to discuss and help each other with assignments with each other but must write software individually. I estimate that the course will require between 8 and 10 hours per week out of the classroom, depending on the student's background. Students will be expected to hand in printouts of the software together with some plots and possibly other output. Students must also include some comments on the results. All assignments must come to me as hard copy. I will not accept fax or email submissions. Assignments will be graded partly on the basis of the quality of the code, including the quality of the comments, clarity of the control structure, modularity, etc.

The text for the course is a series of lecture notes I am writing, which will be posted on this page as they become available.

- Week 1: Sources of error.
- Sources of error: roundoff, truncation error, incomplete convergence, statistical error, program bug.
- Computer floating point arithmetic and the IEEE standard.
- Error amplification through cancellation.
- Conditioning, condition number, and error amplification.
- Stable and unstable computational algorithms.
- Weeks 2 and 3: Basic numerical analysis.
- Taylor series as asymptotic expansions.
- Finite difference approximations to derivatives.
- Asymptotic error expansions and order of accuracy.
- Richardson extrapolation.
- Local low order polynomial interpolation.
- Methods for integration on a uniform mesh: rectangle rule, trapezoid rule, midpoint rule, Simpson's rule.
- Local error, error cancellation, and global error.
- Convergence study as a correctness check.
- Using Richardson error estimation to achieve a specified level of accuracy.
- Weeks 4 and 5: Numerical Linear Algebra.
- Review of linear algebra, vector and matrix norms.
- Condition number of a system of linear equations, condition number of a matrix.
- Condition number of the symmetric and nonsymmertic eigenvalue problem (done lightly).
- Improving condition number: scaling and balancing
- The LU factorization and it's use for systems of linear equations.
- Computing the factors by Gauss elimination.
- Pivoting.
- The Choleski factorization.
- Band matrices.
- Week 6: Discrete Fourier transform and applications.
- The algebraic definition of the DFT.
- The physical and graphical interpretation of the modes.
- Application to convolution and filtering.
- What the FFT algorithm achieves (but not the algorithm itself).
- Week 7: Nonlinear equations and optimization I, Newton's method.
- Graphical and analytical definition of Newton's method in one dimension.
- Newton's method in higher dimensions.
- Local quadratic convergence.
- The problem of local minima, but no solution.
- Week 8: Nonlinear optimization II, robust software.
- The problem of convergence from a poor starting guess.
- Line search.
- Modified Choleski factorization.
- Robust software for optimization.
- Week 9: Time stepping methods for dynamical systems (ODE's).
- The time stepping (marching) approach to dynamics.
- Forward and backward Euler.
- Determining the accuracy of time stepping methods, local truncation error.
- Midpoint and trapezoid rules.
- Four stage Runge Kutta, what it is and what it achieves.
- Adaptive time step selection based on local error estimation.
- Week 10: Principles of numerical software, performance and reliabilty
- Software tools: debuggers, memory leaks, performance tools.
- Understanding the hardware: prefetch, piplining, cache.
- Coding for performance.
- Week 11: Monte Carlo I, basics.
- Review of basic probability: random variables, probability densities, expectation, independence, etc. (very quick)
- What psuedo random number generators do and how they do it.
- Discrete events and coin tossing.
- Generating exponential and Gaussian (normal) random variables: Box Muller.
- Error bars and the central limit theorem.
- Week 12: Monte Carlo II, variance reduction (cheating).
- Philosophy of variance reduction: find different random variables with the same expectation.
- Control variates.
- Antithetic variates
- Importance sampling (very lightly).

- Sources of Error
- Local Analysis
- Linear Algebra Theory
- Differential Equations
- Approximating Functions
- Monte Carlo

- Assignment 1, due February 2
- Assignment 2, due February 9
- Assignment 3, due February 23
- Assignment 6, due April 27