ISSN:
0945-3245
Keywords:
(MR 1980) AMS(MOS)
;
65F05, 15A06, 10M10, 10A30
;
CR: 5.14
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
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 $$\bar x$$ such that $$A\bar x \equiv b$$ (modp m ) for a suitably large integerm; and (iii) deducing the rational solutionx from thep-adic approximation $$\bar x$$ . For matricesA andb with entries of bounded size and dimensionsn×n andn×1, this method can be implemented in timeO(n 3(logn)2) which is better than methods previously used.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01459082
Permalink
