Exact Results in Quantum Theory

Solving large systems of linear equations has numerous applications across many areas, from partial differential equations to numerical optimization and beyond. Krylov subspace methods such as conjugate gradient have long been the gold standard in this area, thanks to their ability to exploit clusters and outliers in the spectrum of the input matrix to achieve fast convergence. Yet, our recent results have shown that it is possible to improve upon Krylov methods by introducing randomness into the algorithmic procedure. In this talk, I will survey the advantages of randomized algorithms in solving large linear systems, including our new randomized variant of the linear solver originally proposed by Stefan Kaczmarz in 1937, showing that this algorithm exploits large outlying eigenvalues provably better than any Krylov subspace method.