Implicit Nullspace Iterative Methods for Constrained Least Squares Problems

Abstract

A class of iterative algorithms is proposed for solving equality constrained least squares problems, generalizing an order-reducing algorithm first analyzed by Barlow, Nichols, and Plemmons (algorithm BNP). The new algorithms, called implicit null space methods, are based on the classical nullspace method, except that the basis for the nullspace of the constraint matrix is not explicitly formed. The implicit basis acts as a preconditioner for a set of normal equations in factored form. Implicit nullspace methods allow great flexibility in the choice of preconditioner, and can be used to solve certain problems for which algorithm BNP is not well suited. In addition, they offer the opportunity for parallel implementation on substructured problems. Some numerical results based on both structural engineering applications and Stokes flow are included.