A quadratic-cost backward-error solver for general real systems

We give an explicit randomized algorithm, in an exact-real arithmetic model in
which every input entry may be read, for $Ax = b$ with
$A \in \mathbb{R}^{n \times n}$, $\|A\|_2 = 1$, $b \ne 0$ and
$0 < \varepsilon < 1/2$. Its deterministic worst-case operation count is
$O(n^2\varepsilon^{-3})$, with indexed table reads and writes charged one
operation each; with probability greater than $0.997$ its nonzero output
satisfies $\|Ax - b\|_2/\|x\|_2 \le 5\varepsilon/8$. Thus such a solver exists
with $q = 3$. The algorithm rounds $A$ once to a
nearby scaled integer matrix. A weighted-pattern multiplication scheme supports
repeated products with this matrix and its transpose more cheaply than dense
products. A rectangular augmented system supplies an exact kernel, and a
fixed-length randomly started polynomial filter finds an approximate kernel
vector. A clamping step converts it to the required backward-error guarantee
without perturbing $b$. The logarithm in the iteration count is canceled by the
preprocessed product cost, not removed from convergence itself.