Geometric Methods in the Probabilistic Analysis of Condition Numbers

• Applicant: Dr. Martin Lotz
• Subject Area: Mathematics
• Term: from 2008 to 2011
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 76347084

The running time of many iterative algorithms in numerical analysis and optimisation is dominated by the condition number of the input. The study of the probability distribution of condition numbers for random inputs thus leads to a probabilistic analysis of the running time of such algorithms. In many cases, the condition number of an input is proportional to the inverse distance of the given input to a set of ill-posed inputs. In these situations, results about the probability distribution of condition numbers for random inputs can be obtained from studying the geometry of the set of ill-posed inputs. The goal of this project is to explore the scope and limitations of this geometric approach, with a particular emphasis on developing methods for dealing with different input distributions, with structured condition numbers, and with condition numbers arising in the context of optimisation theory. Ultimately, the proposed research project is expected to contribute to a better understanding of the performance of numerical and optimisation algorithms as observed in practice.

• DFG Programme: Research Fellowships
• International Connection: China (Hong Kong), United Kingdom
• Hosts: Professor Dr. Peter Bürgisser; Professor Dr. Felipe Cucker; Dr. Raphael Hauser