Numerical Algorithms and Complexity

Spring 2010

Days & Time: Tuesday and Thursday 4:10 - 5:25pm

Location: TBA

Instructor: A. Papageorgiou

Prerequisites

Calculus and linear algebra

Topics covered

Introduction to complexity
Polynomial evaluation
Matrix multiplication - Strassen's algorithm
Nonlinear equations
Adaptive and non-adaptive information
Basic concepts of information-based complexity
Integration of functions of a single variable
Multivariate integration - applications in finance
Monte Carlo
Quasi-Monte Carlo
Function approximation
Linear problems
Systems of linear equations - direct and iterative methods
Roundoff error, stability, condition
Discretization of partial differential equations - Poison equation
Nonlinear problems - complexity of eigenvalue approximation

Grading

Homework 30%
Extra credit HW 10%
Midterm 30%,
Final 40%,
Total 110%

Homework

There will be about 5 homeworks. In general, you may use any programming language, with the understanding that if your favorite choice of programming language is unusual you should discuss it with the instructor or the TA.

You may discuss the homework with other students but you must write it up individually in a way that demonstates your understanding of the material. If you use material from journal articles or any other sources you must cite them.

The homeworks and additional information can be found in the CourseWorks web page.