Khachiyan’s algorithm for linear inequalities: optimization and implementation

An optimized version of Khachiyan’s algorithm is developed here, and an APL implementation of it is provided. The operation count for $M$ linear constraints on $N$ variables is brought from the $O\left ( {{N^4}{M^2}} \right )$ of the original algorithm to $O\left ( {{N^4}M ln N} \right )$ with a smaller coefficient. There is no significant change of the storage requirement, which remains at $O\left ( {NM} \right )$ locations.