A Fast Direct Method for the Least Squares Solution of Slightly Overdetermined Sets of Linear Equations

Publisher Website
Google Scholar
Abstract
Noble (1969) has described a method for the solution of N+M linear equations in N unknowns, which is based on an initial partitioning of the matrix A, and which requires only the solution of square sets of equations. He assumed rank (A) = N. We describe here an efficient implementation of Noble's method, and show that it generalizes in a simple way to cover also rank deficient problems. In the common case that the equation is only slightly overdetermined (M ≪ N) the resulting algorithm is much faster than the standard methods based on M.G.S. or Householder reduction of A, or on the normal equations, and has a very similar operation count to the algorithm of Cline (1973). Slightly overdetermined systems arise from Galerkin methods for non-Hermitian partial differential equations. In these systems, rank (A) = N and advantage can be taken of the structure of the matrix A to yield a least squares solution in θ(N2) operations.

This publication has 0 references indexed in Scilit: