Order-reducing conjugate gradients versus block AOR for constrained least-squares problems

AbstractWe compare the convergence properties of two iterative algorithms for solving equality-constrained least-squares problems. The first algorithm, due to Barlow, Nichols, and Plemmons, applies a variation of the conjugate-gradient algorithm to a symmetric positive definite system which is smaller than the original problem. The second, block accelerated overrelaxation, is a two-parameter generalization of block SOR. Barlow, Nichols, and Plemmons have proven that their order-reducing conjugate-gradient algorithm converges faster than block SOR. We extend their result to show that the algorithm is also superior to block AOR. Numerical experiments on some structural engineering problems support the analysis