We propose new techniques and algorithms for
approximation by low-rank matrices and by structured matrices,
numerical stabilization of Gaussian elimination with no pivoting,
and preconditioning and block diagonalization
of an ill conditioned matrix having a small positive numerical nullity
or rank. Our technical advances include
estimates for the condition numbers
of random Toeplitz matrices,
dual
Sherman--Morrison--Woodbury formula,
novel techniques of randomized preprocessing, a
proof of their preconditioning power, and
application
to preconditioning general and structured matrices.
Our extensive tests support the results of
our analysis and show effectiveness of
the proposed algorithms.