Condition: the geometry of numerical algorithms

Numerical data rarely is given exact, but usually comes with errors due to noise, measurement errors or errors caused by prior calculations. Consequently, algorithms which take such data as input can't produce correct answers.

In this course we will learn about the concept of condition numbers and how it helps to understand how much the solution of a computational problem is changed, if the input data is perturbed. We will also discuss how condition numbers are related to the complexity of numerical algorithms. The concepts of average and smoothed analysis will be introduced.

We will consider the condition numbers of the following problems: linear equation solving, polynomial equation solving and computing tensor decompositions. If time permits, we will also cover condition numbers of problems in linear programming.

References

• Condition: the geometry of numerical algorithms by Bürgisser and Cucker (Springer, 2013)
• The condition number of join decompositions by Breiding and Vannieuwenhoven (SIAM J. Matrix Anal. and Appl., 39(1), 287–309)

Date and time info
Tuesday, 09:00 - 10:00

Keywords
Condition numbers, complexity of numerical algorithms, loss of precision, average analysis, smoothed analysis

Prerequisites
Participants should have a good understanding of linear algebra and a basic knowledge about probability theory and differential geometry. Expertise in linear programming, algebraic geometry or multilinear algebra is helpful but not required.

Audience
MSc students, PhD students, Postdocs

Language
English