Fast randomized linear solver

We propose a randomized algorithm for solving a linear system $Ax = b$ with a highly numerically rank-deficient coefficient matrix $A$ with nearly consistent right-hand side possessing a small-norm solution. Our algorithm finds a small-norm solution with small residual in $O(N_r + nrlogn + r^3 )$ operations, where $r$ is the numerical rank of $A$ and $N_r$ is the cost of multiplying an $n\times r$ matrix to $A$. 

Joint work with Marcus Webb (Manchester). 

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please contact @email.