Communication
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.
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 (to be revised)
- 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
Assignments
Final exam