 # ABS algorithm

This is a family of algorithms to solve a linear system of $LaTeX: m$ equations, $LaTeX: Ax = b$, with $LaTeX: n$ variables such that $LaTeX: n \ge m$. Its distinguishing property is that the k-th iterate, $LaTeX: x^k$, is a solution to the first $LaTeX: 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: $LaTeX: A_{(i,:)}$ is the i-th row of $LaTeX: A$.

1. Initialize: choose $LaTeX: x^0 \in \mathbb{R}^n$, $LaTeX: H^1 \in \mathbb{R}^{n \times n}$ so that is it nonsingular, set $LaTeX: i = 1$
2. Set search direction $LaTeX: d^i = H^i z$ for any $LaTeX: z$ that does not satisfy $LaTeX: z^T H^i A_{(i,:)} = 0$. Compute residuals: $LaTeX: r = Ax^i - b$.
3. Iterate: $LaTeX: x^{i+1} = x^i - s d^i$, where $LaTeX: s$ is the step size: $LaTeX: s = r_i / A_{(i,:)} d^i$.
4. Test for convergance (update residuals, if used in test): Is solution within tolerance? If so, stop; else, continue.
5. Update: $LaTeX: H^{i+1} = H^i - D^i$, where $LaTeX: D^i$ is a rank 1 update of the form $LaTeX: H^i A_{(i,:)} (H^i w)^T$ for $LaTeX: w$ such that $LaTeX: w^T H^i A_{(i,:)} = 1$.
6. Increment: let $LaTeX: i = i + 1$ and go to step 1.

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