Solving linear systems of equations with randomization, augmentation and aggregation (Q454828)

The paper concentrates on computing an approximation to the basis of the null space of a given rectangular (possibly rank deficient and/or ill-conditioned) matrix. Classical algorithms for solving such problems are usually based on a singular value decomposition, the LU or QR factorization. However, these techniques do not preserve a possible sparse structure of the matrix during the computation. Thus, algorithms are derived that are able to do so. They are based on randomization of different types (e.g. randomized preconditioning), augmentation and aggregation. These algorithms are then extended to solve nonhomogeneous systems of linear equations with a nonsingular and possibly ill-conditioned matrix. A theoretical analysis is included. Several numerical experiments illustrate behaviour of the algorithms.