Randomized Preprocessing versus Pivoting II ∗

It is known that without pivoting Gaussian elimination can run significantly faster, partic-ularly for matrices that have structure 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 a cubic arithmetic time bound for Gaussian elimination with pivoting decreases to a nearly linear time bound, and our tests show dramatic decrease of the CPU time as well