ABS ALGORITHM

ABS algorithm - This is a family of algorithms to solve a linear system of m equations, Ax=b, with n variables such that n >= m. Its distinguishing property is that the k-th iterate, x^k, is a solution to the first k equations. While algorithms in this class date back to 1934, the family was recognized and formally developed by J. Abaffy, C.G. Broyden and E. Spedicato, so the algorithm family name bears their initials. The ABS algorithm is given by the following. Notation: A_i is the i-th row of A.

1. Initialize: choose x⁰ in Rⁿ, H¹ in R^n×n and nonsingular; set i=1.
2. Set search direction dⁱ = Hⁱz for any z that does not satisfy z'HⁱA_i=0. Compute residuals : r = Axⁱ-b.
3. Iterate: xⁱ⁺¹ = xⁱ - s dⁱ, where s is the step size : s = r_i / A_i dⁱ.
4. Test for convergance (update residuals, if used in test): Is solution within tolerance ? If so, stop; else, continue.
5. Update Hⁱ⁺¹ = Hⁱ - Dⁱ, where Dⁱ is a rank 1 update of the form HⁱA_iwHⁱ' for w such that wHⁱA_i = 1.
6. Increment i and go to step 1.

The ABS algorithm extends to nonlinear equations and to linear diophantine equations .