I might be missing something big, but isn't chemical equation balancing just a system of linear Diophantine equations[1]? If it is, you should be able to solve it in O(n^3) time by converting to Smith normal form[2]. Unlike Hermite form, which the paper mentions, you don't need rational arithmetic or floating points.

[1]https://en.wikipedia.org/wiki/Diophantine_equation#System_of... [2]https://en.wikipedia.org/wiki/Smith_normal_form