Numerical algorithms



  • 2018 Spring/Summer (Jan - May)

Course outline. This course will be an introduction to the analysis of numerical algorithms such as linear equation solving, linear programming and (if time permits) polynomial system solving. I expect to cover the following topics.

1. The notion of the condition number of a numerical problem. Solution concepts for understanding condition numbers (average case, smoothed analysis).

2. Simple example of condition numbers, e.g., matrix vertex multiplication, and the pitfalls of floating point arithmetic.

3. Condition numbers and the complexity of iterative methods such as steepest descent

4. Condition numbers and linear programming

Prerequisites. Linear algebra, analysis (notions of convergence, norms, Hölder’s inequality etc.), probability and some background in undergraduate multivariable calculus.

References. The main reference for the course will be the recent book Condition: The Geometry of Numerical Algorithms by Peter Bürgiser and Felipe Cucker.