Universality in numerical computations with random data

作者：Deift Percy A^*; Menon Govind; Olver Sheehan; Trogdon Thomas

来源：Proceedings of the National Academy of Sciences, 2014, 111(42): 14973-14978.

DOI：10.1073/pnas.1413446111

• random matrix theory
• decision times
• numerical analysis

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.

• 出版日期2014-10-21