Re: factorization of multivariate polynomials
- From: rusin@xxxxxxxxxxxxxxxxxxxxx (Dave Rusin)
- Date: 31 Oct 2006 18:43:13 GMT
In article <VjE1h.30776$t6.18666@xxxxxxxxxxxxxxxxxxxx>,
Jeremy Watts <stevie4545@xxxxxxxxxxx> wrote:
thank you both for the replies, what i dont understand about all this is, in
the case of univariate factorization, why arent the zeroes of the polynomial
simply found and then the factorization deduced from this? solving a
polynomial is pretty easy using say the companion matrix method
Sure -- if it's a polynomial with small integer coefficients and low degree.
But what if you want a factorization over some other field, e.g. F_p or
Q[sqrt(2)]? Or what if the degree is in the hundreds? (This will make it
complicated to consider all partitions of the roots looking for rational
factors). Or what if the coefficients are hundreds of digits? (This makes
it hard to compute the roots accurately.) All these kinds of events happen
regularly. Well, they happen to me, anyway, which maybe reflects the
kind of life I lead... .
Also you underestimate the difficulty in finding roots. A classic example
(due to Wilkinson I guess) is P(x) = \prod_{i=1}^{20} (X-i) . When
expanded into traditional polynomial form, the coefficients are a wee bit
too big to be stored accurately in floating point arithmetic. The small
variation in coefficients completely destroys the structure of the roots,
e.g. half of them are not even real. And it's not just because the
coefficients are big: increase the smallest coefficient (the 210 in
front of X^19) by some amount epsilon. For large enough epsilon you
might expect that you will eventually get a discriminant equal to zero
and the number of real roots will change. Well, the surprise is that the
equation discriminant( epsilon ) = 0 has about ten roots smaller
than 10^{-7}, which is to say that even tiny changes in this small
coefficient will repeatedly change even the number of real roots, to say
nothing of their location. And the problems can be really bad: within the
discriminant=0 variety there are subvarieties corresponding to polynomials
with high multiplicities of roots; this P is close to them too.
For instance the polynomial
(x- 0.99713149865455388824650436429131018139) *
(x- 2.30344584958190213110984938660366515107)^2*
(x- 5.78877037745816247611104621735810949576)^5*
(x-11.75636640100993094821856085082058574258)^7*
(x-18.68755591926662175273839684309617398506)^5
has coefficients that differ from those of P by no more than 1/3 of 1%.
I got this from a talk by Zhonggang Zeng:
http://www.ima.umn.edu/2006-2007/seminars/zeng/zeng.pdf
(By the way, that equation discrim=0 is itself a degree-20 polynomial with
integer coefficients and all roots real. But it has coefficients of 316
digits, and that's after dividing out the content of the polynomial
(the gcd of its coefficients). I think it's easier to prove the
polynomial is irreducible than to start computing its roots!)
dave
.
- Prev by Date: Re: factorization of multivariate polynomials
- Next by Date: Re: factorization of multivariate polynomials
- Previous by thread: Re: factorization of multivariate polynomials
- Index(es):
Relevant Pages
|
