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

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: