Solving linear systems of equations with randomization, augmentation and aggregation

• Published in: Linear algebra and its applications 2012-12, Vol.437 (12), p.2851-2876
• Main Authors: Pan, Victor Y., Qian, Guoliang
• Format: Article
• Language: English
• Subjects: Aggregation; Algebra; Augmentation; Exact sciences and technology; Linear and multilinear algebra, matrix theory; Linear systems of equations; Mathematics; Numerical rank; Randomization; Rank; Sciences and techniques of general use
• ISSN: 0024-3795; 1873-1856
• DOI: 10.1016/j.laa.2012.07.002

Seeking a basis for the null space of a rectangular and possibly rank deficient and ill conditioned matrix we apply randomization, augmentation, and aggregation to reduce our task to computations with well conditioned matrices of full rank. Our algorithms avoid pivoting and orthogonalization, preserve matrix structure and sparseness, and in the case of an ill conditioned input perform only a small part of the computations with high accuracy. We extend the algorithms to the solution of nonhomogeneous nonsingular ill conditioned linear systems of equations whose matrices have small numerical nullities. Our estimates and experiments show dramatic progress versus the customary matrix algorithms where the input matrices are rank deficient or ill conditioned. Our study can be of independent technical interest: we extend the known results on conditioning of random matrices to randomized preconditioning, estimate the condition numbers of randomly augmented matrices, and link augmentation to aggregation as well as homogeneous to nonhomogeneous linear systems of equations.