Smoothed and Average Analysis of Some Condition Numbers

Condition numbers play a fundamental role in the analysis of both the numerical accuracy and the time complexity of numerical algorithms. For instance, a typical result in this research area would establish that, for a given algorithm and for all data dÎIRn, the number of arithmetic operations T(d) needed to execute the algorithm with inputdis bounded by an expression likeln(C(d))anb(orC(d))anb)whereC(d) is a condition number fordanda,b> 0.A drawback of a result of this kind is that the conditionC(d) ofd, unlike its sizen, is not known a priori. A way out to this situation, proposed among others by J. Demmel and S. Smale, eliminatesC(d) by trading worst-case analysis by probabilistic analysis. The idea is to show that, for a given distribution in the space IRnof data, one hasor yet thatE(lnaC(d) )£(lnn)d(orE(C(d)a£nd)for someg,d> 0. Here Prob denotes probability andEexpected value. Such inequalities would yield bounds for both Prob{T(d)³k} andE(T(d)).There is a substantial body of results on this line of research. The goal of this project is to add to that body by either improving some known results (for a given condition number and probability distribution) or by considering probability distributions not considered thus far.