Re: euclidean algorithm over Q[i]


Jeremy Watts wrote:
"Chip Eastham" <hardmath@xxxxxxxxx> wrote in message
news:1166245043.467094.262880@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

G. A. Edgar wrote:
In article <62tgh.6569$Dr3.1078@xxxxxxxxxxxxxxxxxxxx>, Jeremy Watts
<stevie4545@xxxxxxxxxxx> wrote:

how does the euclidean algorithm proceed for numbers in Q[i] ? my
knowledge
of abstract algebra's basic to say the least so i hope i am using the
correct term. i mean for complex numbers with rational real & complex
parts
ie. of form a/b + c/d i a,b,c,d in Z

i'm sure i have seen this somewhere but cant find reference to it
anywhere.

thanks



Q[i] is a field, so greatest common divisors are easy.
Any nonzero element divides any other nonzero element.

Z[i], the Gaussian integers, may be what you remember seeing.

--
G. A. Edgar
http://www.math.ohio-state.edu/~edgar/

And if the OP is interested in the Gaussian integers Z[i],
it is helpful to bear in mind that a Euclidean domain is
possessed of a norm. The "remainder" term is to have
norm less than the divisor in each application of the
division algorithm. Of course Z[i] is not an ordered ring,
so its important to pick the remainder to have minimum
norm as its defining characteristic.

The norm of z = a + bi is a^2 + b^2 in Z[i].

More discussion here:

yes of course, thank you both. the reason i'm asking this is because i've
written a pretty simplistic algorithm in java that carries out polynomial
GCD, just using polynomial long division and the euclidean algorithm.

i've been comparing the output with what 'wims' gives
http://wims.unice.fr/wims/wims.cgi?session=XKF67EF2A7.1&+lang=en&+module=too
l%2Farithmetic%2Fbezout.en

and they agree, apart from the final value for the gcd. which i assume
'wims' is getting somehow by avoiding intermediate 'coefficient swell'. i
have read that if you use 'pseudo division' rather than standard long
division you can get around this problem when working in the rationals

Are you using the Euclidean algorithm to compute
GCD's of univariate polynomials over Q[i]?

The statement that "they agree, apart from the final
value for the gcd" is a bit unsettling! I would assume
normalization to monic polynomials resolves any
ambiguity, and you are asking if there is strategic
advantage to using 'pseudo division' to avoid large
sized intermediate results.

I assume that Gauss's content lemma goes through
in Z[i] and that one can choose instead to compute
the GCD in polynomials with (Gaussian) integer
coefficients. Another ingredient that comes to mind
is the possibility of evaluating the polynomials at
some points in Z[i] and using the GCD of resulting
Gaussian integers to interpolate a "candidate"
polynomial GCD, something known as a "heuristic
GCD algorithm" as cited here:

http://www-fourier.ujf-grenoble.fr/~parisse/publi/gcdheu.pdf

regards, chip

.

Relevant Pages

  • Re: GCD of multivariate polynomials
    ... is necessary to simplify ratios of polynomials to simplest form. ... of GCD will come out faster. ... > What does work is a more generalized Euclidean gcd algorithm (divide ...
    (sci.math.symbolic)
  • Re: A GCD question
    ... it's not much more difficult to find the GCD if two polynomials in a ... similiar way. ... Three New Algorithms for Multivariate Polynomial GCD ...
    (sci.math)
  • Re: A GCD question
    ... it's not much more difficult to find the GCD if two polynomials in a ... I've been trying and failing to simplify ... Three New Algorithms for Multivariate Polynomial GCD ...
    (sci.math)
  • A GCD question
    ... I know it's easy to find the GCD of two integers using Euclid's ... it's not much more difficult to find the GCD if two polynomials in a ... I've been trying and failing to simplify ...
    (sci.math)
  • MACIS 2007 - CALL FOR PARTICIPATION
    ... Sciences (MACIS) is a new series of conferences where foundational research on theoretical and practical problems of mathematics for computing and information processing may be presented and discussed. ... Computing Roots of Polynomials using Bivariate Quadratic Clipping ... An algorithm for checking whether the toric ideal of an affine monomial curve is a complete intersection ...
    (comp.specification.z)