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

Abstract

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 \in {\mathbb C}^{m \times n}$ with $\mbox{rank}(A) = h$ and $C \in {\mathbb C}^{h \times n}$, where $m, n \in {\mathbb N}$ are large and $n = h+s$, and where $h = \sum_{j=1}^q h_j$ with $h_j \in {\mathbb N}$ and $s \in {\mathbb N}-1$. Direct solution of the least squares equation requires finding the Moore-Penrose inverse of a large $h \times 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_j \times h_j$ and then uses these matrices to construct the Moore-Penrose inverses of an associated collection of $h \times h_j$ matrices. The new HUTS calculates the Moore-Penrose inverses of an alternative collection of $q$ matrices of size $h_j \times h_j$ 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.