Details:
Title  An algorithm to solve integer linear systems exactly using numerical methods  Author(s)  Zhendong Wan  Type  Article in Journal  Abstract  In this paper, we present a new algorithm for the exact solutions of linear systems with integer coefficients using numerical methods. It terminates with the correct answer in wellconditioned cases or quickly aborts in illconditioned cases. Success of this algorithm on a linear equation requires that the linear system must be sufficiently wellconditioned for the numeric linear algebra method being used to compute a solution with sufficient accuracy. Our method is to find an initial approximate solution by using a numerical method, then amplify the approximate solution by a scalar, and adjust the amplified solution and corresponding residual to integers so that they can be computed without large integer arithmetic involved and can be stored exactly. Then we repeat these steps to refine the solution until sufficient accuracy is achieved, and finally reconstruct the rational solution. Our approximating, amplifying, and adjusting idea enables us to compute the solutions without involving high precision software floating point operations in the whole procedure or large integer arithmetic except at the final rational reconstruction step. We will expose the theoretical cost and show some experimental results.  Keywords  Linear systems, Numerical linear algebra methods, Rational solvers  ISSN  07477171 
URL 
http://www.sciencedirect.com/science/article/pii/S0747717105001653 
Language  English  Journal  Journal of Symbolic Computation  Volume  41  Number  6  Pages  621  632  Year  2006  Edition  0  Translation 
No  Refereed 
No 
