Solving Linear Systems of Equations with Randomization

Seeking a basis for the null space of a rectangular and possibly rank deficient and ill condi-tioned matrix A we combine scaled randomized augmentation with aggregation to reduce our task to computations with well conditioned matrices of full rank. Our algorithms avoid piv-oting and orthogonalization and preserve matrix structure and sparseness. In the case of ill conditioned inputs we perform a small part of our computations with high accuracy by applying iterative refinement, but overall we still dramatically accelerate the customary algorithms for rank deficient or ill conditioned linear systems with general and Toeplitz matrices, according to both our formal estimates and experiments. Our study can be of independent technical interest, e.g., we extend the Smoothed Analysis of conditioning of random matrices in [42] to precon-ditioning by means of randomized augmentation and link augmentation and aggregation. Our progress has been extended to various other fundamental matrix computations