Randomized preprocessing of homogeneous linear systems of equations (Q968998)

A method for solving a homogeneous system of linear equations is given. The proposed method does not require pivoting or orthogonalization. Numerical stability of the method is proved. It is shown that in the case of Toeplitz inputs, the estimated solution time decreases from quadratic to nearly linear, and tests show also a dramatic decrease in CPU time. Extensions of the proposed method to the solution of a non-singular linear system inversion, generalized inverses of general and structured matrices, Newton's iteration etc., are also given. The authors point out some of the by-products and extensions of the proposed method to matrix inversion, estimates for the condition numbers of randomized matrix products, and preprocessing by augmentation.