Solving Linear System with Randomized Augmentation

With a high probablilty our randomized augmentation of a matrix eliminates its rank defi-ciency and ill conditioning. Our techniques avoid various drawbacks of the customary algorithms based on pivoting and orthogonalization, e.g., we readily preserve matrix structure and sparse-ness. Furthermore our randomized augmentation is expected to precondition quite a general class of ill conditioned input matrices. As a result, we dramatically accelerate the solution of both singular and ill conditioned linear systems of equations in terms of the estimated arithmetic time and the observed CPU time. The progress has been extended to various other fundamental matrix computations