The numerical least squares solution of large linear systems - a compromise between speed and accuracy

We propose and justify a numerical method called the Householder Unitary Transformation Scheme (HUTS) for the least squares solution of large linear systems in the form YCC^* = AC^*, where A ∈ Cm × n with rank(A) = h and C ∈ Ch × n, where m, n ∈ N are large and $n = h+s$, and where h = ∑ⱼ₌₁q hⱼ with hⱼ ∈ N and s ∈ N-1. Direct solution of the least squares equation requires finding the Moore-Penrose inverse of a large h × h matrix. The recently proposed Elementary Block Operations Scheme (EBOS) [20] calculates the Moore-Penrose inverses of a collection of q matrices of size hⱼ × hⱼ and then uses these matrices to construct the Moore-Penrose inverses of an associated collection of h × hⱼ matrices. The new HUTS calculates the Moore-Penrose inverses of an alternative collection of q matrices of size hⱼ × hⱼ and then uses a process of back substitution to find the desired solution. In each case, the total computation time is substantially less than the direct method. In general, the HUTS is faster, but the EBOS is more accurate. We will compare the performance of all three methods in a range of typical examples.