Our randomized preprocessing of
a matrix by augmentation counters its
degeneracy using neither pivoting nor orthogonalization. This preprocessing
is error-free and flop-free, readily
preserves matrix structure and
sparseness, and is numerically safe
with a probability close to one. For
a sample application we dramatically accelerate the solution of a Toeplitz linear system of equations in terms
of both estimated arithmetic time and observed CPU time.