Scientific Computing

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.

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, basic numerical analysis I.
• Sources of error: roundoff, truncation error, statistical error, numerical instability, computer bug.
• Taylor series as convergent and asymptotic series.
• Asymptotic error expansions, their use in validation and error reduction.
• Computing derivatives by finite differences.
• Week 2: Basic numerical analysis II.
• High order difference approximations via Taylor series and Richardson extrapolation.
• Methods for integration on a uniform mesh: rectangle rule, trapezoid rule, midpoint rule, Simpson's rule.
• Local error, cancellation, and global error.
• Using Richardson error estimation to achieve a specified level of accuracy.
• Local low order polynomial interpolation.
• Week 3: Floating point arithmetic and problem condition number.
• Highlights of the IEEE standard for floating point arithmetic.
• The "answer*(1+machine epsilon)" model of roundoff error.
• Relative and absolute error.
• Amplification of relative error through cancellation.
• The general definition of condition number and it's implication for scientific computing.
• Week 4: Numerical Linear Algebra, I.
• 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
• Week 5: Numerical Linear Algebra, II.
• 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

• Introduction, in Postscript format or Acrobat format. Last update: January 18.
• C/C++ coding for scientific computing, in html format only. Last update: January 17.
• Computer arithmetic Postscript format or Acrobat format. Last update: January 23.
• Basic Numerical Analysis, part 1 Postscript format or Acrobat format. Last update: February 11.
• Numerical Linear Algebra theory Postscript format or Acrobat format. Last update: February 25.
• Numerical Linear Algebra factorization algorithms, as yet incomplete Postscript format or Acrobat format. Last update: February 25.
• Monte Carlo methods Postscript format or Acrobat format. Last update: April 11.