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