ABS algorithms for linear equations and applications to optimization

We first review some of the main results concerning the ABS class for linear systems, introduced in 1984 by Abaffy, Broyden and Spedicato. Then we describe a new algorithm in this class, which solves a general n by n nonsingular linear system in n(3)/3 + O(n(2)) multiplications without the assumption that the coefficient matrix be regular. The method can be viewed as a variation of the implicit LU algorithm of the ABS class, whose associated factorization contains a factor which is not triangular (but can be reduced to triangular form after suitable row permutations). We describe properties of the method, including in particular an efficient way of updating the Abaffian matrix after column interchanges. The algorithm has a natural application to the simplex algorithm for the LP problem in standard form, where it provides a faster technique for the pivoting operation than the methods based upon the standard LU factorization when the number m of equality constraints is greater than n > 2. We present some numerical results showing that the implicit LX algorithm can solve very accurately ill conditioned problems. Then we consider several methods for KT equations, some of them faster or cheaper in storage than classical methods. Finally, we give a unified formulation of feasible direction methods for linearly constrained optimization, including the LP problem, in terms of the parameters of the ABS class.