LSRN: A PARALLEL ITERATIVE SOLVER FOR STRONGLY OVER- OR UNDERDETERMINED SYSTEMS.

Area of Science:

• Numerical Analysis
• Scientific Computing
• Linear Algebra

Background:

• Solving large-scale linear least squares problems (Ax = b) is computationally intensive, especially for ill-conditioned or rank-deficient matrices.
• Existing methods may struggle with efficiency or scalability for very large or specific matrix structures (dense, sparse, or linear operators).

Purpose of the Study:

• Introduce LSRN, a novel parallel iterative least squares solver.
• Evaluate LSRN's performance and scalability on diverse and large-scale problems.

Main Methods:

• LSRN employs random normal projection for preconditioning, followed by iterative methods like LSQR or Chebyshev semi-iteration.
• The method handles dense, sparse matrices, and linear operators, benefiting from matrix structure for speedups.
• Preconditioning involves a singular value decomposition of a smaller projected matrix.

Main Results:

• LSRN achieves competitive results against established solvers (DGELSD, Blendenpik, SuiteSparseQR) on large dense and sparse problems.
• The number of iterations is predictable due to the well-conditioned preconditioned system.
• The Chebyshev method proves efficient for high-communication cluster environments.

Conclusions:

• LSRN offers an efficient and scalable parallel approach for large linear least squares problems.
• Its performance is robust across different matrix types and problem sizes.
• The solver demonstrates strong scalability on cloud infrastructure.