# The Probability that a Slight Perturbation of a Numerical Analysis Problem is Difficult

Friday, April 20, 2007 - 10:30am - 11:20am

EE/CS 3-180

Peter Bürgisser (Universität Paderborn)

The running time of many iterative numerical algorithms is

dominated by the condition number of the input,

a quantity measuring the sensitivity of the solution with

regard to small perturbations of the input.

Examples are iterative methods of linear algebra,

interior-point methods of linear and convex optimization,

as well as homotopy methods for solving systems of polynomial

equations.

Spielman and Teng introduced in 2001 the seminal concept of

smoothed analysis, which

arguably blends the best of both worst-case and average-case

analysis of algorithms.

This led to a much better understanding of the success of the

simplex method in practice.

We present a general theorem providing smoothed analysis

estimates for conic condition numbers of problems

of numerical analysis. Our probability estimates depend only on

geometric invariants of the corresponding sets

of ill-posed inputs. Several applications to linear and

polynomial equation solving show that the estimates obtained

in this way are easy to derive and quite accurate. The main

theorem is based on a volume estimate of ε-tubular

neighborhoods around a real algebraic subvariety of a sphere,

intersected with a disk of radius σ. Besides

ε and σ, this bound depends only the dimension of the

sphere and on the degree of the defining equations.

This is joint work with Felipe Cucker and Martin Lotz.

dominated by the condition number of the input,

a quantity measuring the sensitivity of the solution with

regard to small perturbations of the input.

Examples are iterative methods of linear algebra,

interior-point methods of linear and convex optimization,

as well as homotopy methods for solving systems of polynomial

equations.

Spielman and Teng introduced in 2001 the seminal concept of

smoothed analysis, which

arguably blends the best of both worst-case and average-case

analysis of algorithms.

This led to a much better understanding of the success of the

simplex method in practice.

We present a general theorem providing smoothed analysis

estimates for conic condition numbers of problems

of numerical analysis. Our probability estimates depend only on

geometric invariants of the corresponding sets

of ill-posed inputs. Several applications to linear and

polynomial equation solving show that the estimates obtained

in this way are easy to derive and quite accurate. The main

theorem is based on a volume estimate of ε-tubular

neighborhoods around a real algebraic subvariety of a sphere,

intersected with a disk of radius σ. Besides

ε and σ, this bound depends only the dimension of the

sphere and on the degree of the defining equations.

This is joint work with Felipe Cucker and Martin Lotz.

MSC Code:

65F10

Keywords: