Date: Tue, 26 May 1998 08:26:28 -0500 (CDT) From: To: dickinso@math.upenn.edu Subject: Re: Maple and Symbolic Computations of Solutions to Polynomial Systems of Equations >Doing the problem mod p I don't think will help as I want solutions over >the reals and having a parameter will really foul things up (I think). I think you miss the point. I wrote > On various systems you can also work mod p, for several p, then lift to get > integral answers. This seems to be more efficient for hard problems. For example, I recently did some very tricky problems of this sort. I had about a dozen integral polynomials (in just as many variables) from which I wanted to eliminate all but one variable. This proved very difficult to do rationally, but could be done mod-p in about a minute or two. I performed the elimination modulo about 150 "small" primes (10 digits or so I think) to determine, for each p, a monic polynomial f_p in one variable which that last variable was to satisfy. (The polynomial was of degree 32 in each case). Now, for a "generic" prime p, that polynomial f_p should be the reduction, mod p, of the polynomial f I was really looking for -- the polynomial with _rational_ coefficients which my variable was to satisfy. To determine f, I first used the Chines Remainder Theorem to join all the f_p's into one monic, integral polynomial F with the property that for each p, F == f_p mod p. I still had to find the rational polynomail f with f == F mod (N=p1*p2*...*p150). There _are_ such polynomials f, and they are _not_ unique, but all possible such lifts differ from each other by multiples of N, and in particular at most one will have coefficients which are less than 1500 digits long. Moreoever, if there is such a one, it's easy to find. Well, that's why I tried 150 primes -- it turns out that the rational coefficients had numerators and denominators which were about 750 digits each, so it wasn't until N had at least 1500 digits (hence 150 primes) that an obvious solution appeared. All this is kind of irrelevant if you can't work mod-p either, but if that option is available to you, see what kind of turnaround you get modulo primes; if the results resemble what you expect rationally and are computed rapidly, then the rational solution can indeed be constructed readily (I even have Maple code around here somewhere to perform this rational reconstruction). dave