title: Universality in numerical computations with random data.
abstract: The authors present evidence for universality in numerical computations with random data. Given a (possibly stochastic) numerical algorithm with random input data, the time (or number of iterations) to convergence (within a given tolerance) is a random variable, called the halting time. Two-component universality is observed for the fluctuations of the halting time--i.e., the histogram for the halting times, centered by the sample average and scaled by the sample variance, collapses to a universal curve, independent of the input data distribution, as the dimension increases. Thus, up to two components--the sample average and the sample variance--the statistics for the halting time are universally prescribed. The case studies include six standard numerical algorithms as well as a model of neural computation and decision-making. A link to relevant software is provided for readers who would like to do computations of their own.
authors.affiliation: Courant Institute, New York University, New York, NY 10012; deift@cims.nyu.edu.
authors.forename: Percy A
authors.initials: PA
authors.lastname: Deift
authors.affiliation: Division of Applied Mathematics, Brown University, Providence, RI 02912; and.
authors.forename: Govind
authors.initials: G
authors.lastname: Menon
authors.affiliation: School of Mathematics and Statistics, The University of Sydney, Sydney, NSW 2006, Australia.
authors.forename: Sheehan
authors.initials: S
authors.lastname: Olver
authors.affiliation: Courant Institute, New York University, New York, NY 10012;
authors.forename: Thomas
authors.initials: T
authors.lastname: Trogdon
keywords: decision times; numerical analysis; random matrix theory