#### Two-Component Universality

Consider the solution of $Ax = b$ with the conjugate gradient method where $A$ and $b$ are random and $n$ is the dimension of the system. The algorithm is iterative and at iteration $k$ an approximate solution, $w_k$ is found. The residual is $r_k = b-Aw_k$. The algorithm is typically halted when the 2-norm of the residual falls below a specified tolerance: $$\|r_k\|_{\ell^2} < \epsilon.$$ The number of iterations required to reach this tolerance is a random variable called the halting time $T$ and we examine it with Monte Carlo simulations. In particular, after $N$ simulations, we normalize the data to mean zero and variance one (the two components) and look at what remains: the fluctuations. The fluctuations appear to be universal, independent of the distribution (within a class) of $A$ for $n$ sufficiently large.

Motivated by these computations we (with P. Deift and G. Menon) also proved the following limit theorem:

**Theorem:**Let $X$ be an $n \times m$ array of complex iid standard Gaussian random variables and define $A = XX^*$. If $m = n + \alpha$ where $\alpha = \lfloor \sqrt{ 4 c n} \rfloor$ then for all $t \in \mathbb R$ $$\lim_{n \rightarrow \infty} \mathbb P\left( \frac{\kappa - 4 n c^{-1}}{4 c^{-4/3} n^{2/3}} \leq t \right) = F_2(t), ~~~ \kappa = \frac{\lambda_{\max}}{\lambda_{\min}},$$ where $F_2(t)$ is the distribution function for the Tracy-Widom ($\beta = 2$) distribution.