CSW3210

Scientific Computation - CS3210, Spring 2013

Roon: TBA

Instructor:Joseph Traub
Office Address: 456 CSB
Office Hours: Tuesday 2:30 - 3:00 pm, Thursday 3:30 - 4:00 pm and by appointment
Email: traub@cs.columbia.edu

TAs: TBA

Class Info:

Required Text: Numerical Methods, Third Edition, Faires and Burden. I suggest you buy the 3^rd edition used.
Detailed information about homeworks, solution sets, handouts, grades etc. will be posted in Courseworks.

Grading

• 30% homework
• 30% midterm,
• 40% final
• 10% extra credit homework

You are responsible for the material covered in: lectures, readings and homeworks.

TOPICS

1. Continuous Problems
   Many problems in physics, chemistry, biology, engineering vision graphics, animations, weather predictions, etc. have continuous mathematical models
   Example: Ecosystems.
   Continuous problems usually have to be solved numerically
2. The most important law in computing:
   Moore's law
   Why Moore's law is ending for current technology and what can be done about it.
3. The world's fastest computers
4. Scaling laws
5. Brief review of calculus results we'll need.
6. Solutions of nonlinear equation
   Bisection algorithm
   Pros/Cons
   Newton iteration
   Error formula
   Pros/Cons
   Termination criteria
   Applications of Newton
   Square root
   Reciprocal
   Secant algorithm
   Fibonacci sequence
   Pros/Cons
7. Polynomial interpolation
8. Spline interpolation
9. Linear recurrences with constant coefficients
10. Uncertainty, Undecidability
11. Nonlinear recurrences
    Logistic equation
    Chaos
    Strange attractors
    Limits to weather prediction
    Butterfly effect
    Fractals
12. Univariate integration
    Why such an important problem
    Trapezoid module
    Simpson module
    Composite algorithm
13. High dimensional integration
    Curse of dimensionality
    Randomization
    Monte Carlo algorithm
    Pros/Cons
14. Dynamical systems
    Linear ordinary differential equations (ODE)
    Nonlinear ODE
    Separation of variables
    Numerical solution
    Euler algorithm
    Error of Euler
    Pros/Cons
    Higher order Taylor
    Runge-Kutta
15. Condition of problem
    Wilkinson polynomial
16. Implications of finite precision algorithm
17. Stability of algorithm
18. Backward error analysis