Computationally efficient methods for solving linear systems that result in a non-square matrix (smaller than 20 x 20 matrices)

Question

For linear systems that result in an Ax = B problem where the matrices are non-square and smaller than 20 x 20 in size, what are the preferred methods that are less costly to compute? Would a direct method such as single variable decomposition, or an iterative one such as Gauss-Seidel or Jacobi's method be more efficient (or some kind of direct/iterative hybrid).

Answer 1

Let's assume that your system is overdetermined, i.e., $A \in \mathbb R^{n\times m}$ with $n>m$. For $n=m$ you can just use a direct solver ($20 \times 20$ is by no means large). For $n<m$ there is without any other assumptions on $A$ no guarantee that you can find a unique $x$ such that $Ax = b$.

The standard way to solve / approximate the overdetermined system would be Least Squares with solution $$ x_{LS} = \big(A^TA\big)^{-1} A^T b. $$