Our randomized preprocessing enables pivoting-free and orthogonalization-free solution of homogeneous linear systems of equations. In the case of Toeplitz inputs,
we decrease the solution time from quadratic to nearly linear, and our tests show dramatic decrease of the CPU time as well. We prove and confirm experimentally numerical stability of our randomized algorithms and extend our approach to solving nonsingular linear systems,
matrix eigen-solving, and root-finding for polynomial and secular equations. Some
by-products and extensions of our study can be of independent technical intersest, e.g., this applies to our extensions of
the Sherman-Morrison-Woodbury formula for matrix inversion and our estimates for the condition number of the fixed-times-random matrix product.