"Bernstein fast gcd notes" - читать интересную книгу автора

From: [email protected] (David Lieberman)
Subject: Re: Roots of higher order polynomials
Date: 08 Jun 1999 10:40:53 -0400
Newsgroups: sci.math.research
Keywords: efficiency of Euclid's algorithm for g.c.d.

In article <[email protected]>,
Greg Kuperberg wrote:
>In article <030619990902577004%[email protected]>,
>G. A. Edgar wrote:
>>Wouldn't the Euclidean algorithm (to find the greatest common
>>divisor of two polynomials) be easier than evaluating
>>a large determinant [of the resultant matrix]?
>I think that if you are free to use a special sparse matrix method to
>compute the determinant, the two algorithms are almost equivalent.


The euclidean algorithm is far more efficient than the computation of
the resultant determinant. For one thing you only need two rows of
storage rather than n+m and for another when you subtract a multiple
of one polynomial from the other you are simultaneously reducing many
rows of the resultant matrix.

The determinant computation is O((n+m)^3), while euclid is O(n^2) (in
fact one has improvements on euclid due to Aho Hopcroft and Ullman

which make it O(n^(1 + epsilon)) i.e. it is O(n log^k(n)) for some k
if I remember correctly.

Moreover, euclid gives more information at the end...ie it identifies
the gcd rather than simply saying whether a nontrivial gcd exists.

More precisely, euclid gives different information at the end... this
is particularly noticeable when the ring of coefficients is not a
field e.g. when one is dealing with multivariate polynomials.

The resultant determinant is still defined and is computed using only
operations in the coefficient ring, and is quite useful at least in
theory, for doing elimination. It is quite costly to compute. The
euclidean algorithm does not compute this resultant and in fact
requires one to work in the ring of fractions. In the case of a
domain, euclid plus bookkeeping allows one to compute the
resultant. (See Cox, Little and O'Shea). What is known about the most
efficient way to evaluate the resultant in general?
==============================================================================

From: [email protected] (D. J. Bernstein)
Subject: Re: Roots of higher order polynomials
Date: 8 Jun 1999 18:42:30 GMT
Newsgroups: sci.math.research

12