It is known that pivoting-free Gaussian elimination is numerically unsafe
but can run significantly faster than
GEPP. We prove and confirm
experimentally that randomized preconditioning combined with iterative
refinement can to some extent replace pivoting in numerical Gaussian
elimination. The resulting algorithms compute solution more rapidly than
GEPP and still with high accuracy.
In the case of Toeplitz, Hankel, and
other structured inputs we yield acceleration from cubic to nearly
linear arithmetic time. Our auxiliary estimates for the condition number of
the product of fixed and random
matrices can be of independent interest.