An algorithm to solve integer linear systems exactly using numerical methods (Q2457353)

A new algorithm for the exact solution of linear systems with integer coefficients is presented using numerical methods. For sufficiently well-conditioned coefficient matrices, it terminates with the correct rational answer, while for ill-conditioned cases it quickly aborts. The idea of the algorithm is to first calculate an approximate numerical solution as starting point, then iteratively refine the solution by amplifying the approximate solution by a scalar and adjusting it and the corresponding residuals to integers (so that they can be stored exactly). This is done until sufficient accuracy is achieved to uniquely determine the rational solution. As the algorithm does not employ floating point operations at all and large integer arithmetic only in the very last step, it is very efficient. A comparison with Dixon lifting shows a huge advantage of this solver method over Dixon lifting. As another example, the \((1,1)\) entry of the inverse of a special sparse integer matrix A is calculated with a speed-up of several magnitudes compared to previous methods.