Exact solution of linear equations usingP-adic expansions

Summary A method is described for computing the exact rational solution to a regular systemAx=b of linear equations with integer coefficients. The method involves: (i) computing the inverse (modp) ofA for some primep; (ii) using successive refinements to compute an integer vector such that (modp ^m ) for a suitably large integerm; and (iii) deducing the rational solutionx from thep-adic approximation . For matricesA andb with entries of bounded size and dimensionsn×n andn×1, this method can be implemented in timeO(n ³(logn)²) which is better than methods previously used.This research was supported in part by the Natural Sciences and Engineering Research Council of Canada (Grant No. A 7171)