ILL-POSEDNESS AND CONDITIONING

Adrian Lewis
Cornell

In the 1980's, Demmel proposed a striking paradigm relating the
conditioning of computational problems, their "distance to ill-posedness",
and the speed of numerical methods.  As an example of this paradigm, I
discuss some simple randomized methods for linear systems; an alternating
projection scheme illustrates a powerful local analogue.  I describe a
recent Sard-type theorem for semi-algebraic systems, and outline its
variational implications for matrix pseudospectra.