Numerical linear algebra and stochastic eigenanalysis: border interactions

The connection between numerical linear algebra and stochastic eigenanalysis (AKA random matrix theory) is simple but deep: the latter solves stochastically one of the cornerstone problems (in MATLAB language, "eig") of the former. Naturally, methods of numerical linear algebra have been used in practice for studying large random matrices, and random matrices have been used as "average case" tests for algorithms known to vastly out-perform in practice their worst-case bounds. The connections between these two fields are, however, deeper than that.

In one direction, applying numerical algorithms stochastically lead us to the discovery of matrix models for generalizations of classical random matrix ensembles. In turn, these ensembles have been used as exploratory tools which lead to connections with stochastic operators, the Brownian Carousel, and other interesting mathematical objects.

In the other direction, we have discovered that random matrices can be used to speed up and stabilize eigenvalue/singular value computations, to the point of stably reducing their complexity to that of (fast) matrix multiplication. Surprisingly, random matrices can also be used to minimize communication in the case of very large-scale matrix computations, both in the (single-processor) sequential case, when data is transported between various levels of the memory hierarchy, and in the (multi-processor) parallel case, when data is transported over a network. This application is particularly interesting in the current (super)computing context, which includes an exponential increase in the processor-memory gap and the end of Moore's Law.

I will try to sketch a picture of the current state of affairs at the border between these two fields, and particularly focus on a couple of results, one of which is the communication-minimizing algorithm mentioned above.