Randomized Preconditioning of Linear Systems of Equations

Effective preconditioners are known for some important but special classes of matrices. In contrast our properly scaled randomized additive preprocessing and augmentation are likely to precondition any n × n ill conditioned matrix A that has a small positive numerical nullity r n, that is lies near a well conditioned matrix A ̃ of rank n − r for a small positive integer r. Both our randomized additive preprocessing and augmentation are likely to accelerate by roughly the factor n/r the customary cubic time solution of a nonsingular linear system Ay = b of n equations with a coefficient matrix A from this class. We achieve a similar randomized acceleration of the customary algorithms in the case of sparse or structured (e.g., Toeplitz or multilevel Toeplitz) inputs. Furthermore in the important case where the input matrix has displacement structure of Toeplitz or Hankel type, we avoid randomization and relax the restriction on numerical nullity. Our tests show significant acceleration of the known algorithms also in terms of the CPU time involved. Our preprocessing facilitates some other fundamenta