Randomized preprocessing versus pivoting

It is known that without pivoting Gaussian elimination can run significantly faster (particularly for matrices that have structures of Toeplitz or Hankel types), but becomes numerically unsafe. The known remedies take their toll, e.g., symmetrization squares the condition number of the input matrix. Can we fix the problem without such a punishment? Taking this challenge we combine randomized preconditioning techniques with iterative refinement and prove that this combination is expected to make pivoting-free Gaussian elimination numerically safe while keeping it fast. For matrices having structures of Toeplitz or Hankel types transition to Gaussian elimination with no pivoting decreases arithmetic time bound from cubic to nearly linear, and our tests show dramatic decrease of the CPU time as well.