The G-algorithm was proposed by Bareiss  as a method for solving the weighted linear least squares problem. It is a square root free algorithm similar to the fast Givens method except that it triangularizes a rectangular matrix a column at a time instead of one element at a time. In this paper an error analysis of the G-algorithm is presented which shows that it is as stable as any of the standard orthogonal decomposition methods for solving least squares problems. The algorithm is shown to be a competitive method for sparse least squares problems. A pivoting strategy is given for heavily weighted problems similar to that in  for the Householder-Golub algorithm. The strategy is prohibitively expensive, but it is not necessary for most of the least squares problems that arise in practice.
All Science Journal Classification (ASJC) codes
- Computer Networks and Communications
- Computational Mathematics
- Applied Mathematics