Solving Linear Systems in $\tilde{O}(mn\log \frac{\kappa }{\epsilon })$ Bit Operations

Jonathan A. Kelner

We give a deterministic algorithm that solves a nonsingular linear system $Ax=b$, where $A\in {\mathbb{R}}^{n\times n}$ has $m$ nonzero entries and condition number $\kappa$, to any relati…