LSRN: A parallel iterative solver for strongly over- or underdetermined systems. (English) Zbl 1298.65053

Meng, Xiangrui; Saunders, Michael A.; Mahoney, Michael W.

SIAM J. Sci. Comput. 36, No. 2, 95-118 (2014).

The authors propose a random normal projection least squares solver for general linear least squares problems and their Tikhonov regularized versions. The method iteratively constructs a provably efficient preconditioner. It has a fully predictable run-time performance and scales well in parallel environments.

Reviewer: Constantin Popa (Constanţa)

MSC:

65F08	Preconditioners for iterative methods
65F10	Iterative numerical methods for linear systems
65F20	Numerical solutions to overdetermined systems, pseudoinverses
65F22	Ill-posedness and regularization problems in numerical linear algebra
65F35	Numerical computation of matrix norms, conditioning, scaling
65F50	Computational methods for sparse matrices
15B52	Random matrices (algebraic aspects)
65Y05	Parallel numerical computation

Keywords:

linear least squares; overdetermined system, underdetermined system, rank-deficient; minimum-length solution; sparse matrix; iterative method; preconditioning; Chebyshev semi-iterative method; Tikhonov regularization; ridge regression; parallel computing; random projection; random sampling; random matrix; randomized algorithm

Software:

Blendenpik; LAPACK; LSRN; Ziggurat