Scientific Computing
Course Home Page
Spring, 2003

Questions or comments

If you have questions, please check the FAQ, then contact me (see the contact information above). I welcome comments on the lecture notes from anyone, enrolled or not.

Communication

To help people communicate with each other, there is a class bboard. Please check this regularly since I will also post announcements there. If you have questions or problems with the homework or notes, please post them rather than emailing them to me. This way everyone can see them. I will not use the Computer Science Department maintained class mailing list.

Assignments

See the assignments page.

Course Description

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.

Outline

• 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).

Lecture notes

These lecture notes are supposed to become a book soon . I welcome comments, positive or (especially) negative, from students and web surfers. I am editing the notes so the posted versions may change. I will always date the posted version so you can see when yours is superseeded. If you have a Windows or Linux box, you can download a Postscript reader or an Acrobat reader

• Sources of error, in Postscript or pdf format. Last update: January 26.
• Getting started
• Dynamics, in Postscript or pdf format. Last update: April 21
• Monte Carlo (incomplete) in Postscript or pdf format. Last update: AMay 9