Re: euclidean algorithm over Q[i]


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

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]?

Hi Chip, yes i am using the Euclidean algorithm to compute gcd's of
univariate polynomials over Z,Z[i] and 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.

when you say 'normalization to a monic' what do you mean by that? sorry
if
that sounds a bit basic. is this what 'pseudo division' does?

When I say "normalization to a monic", I meant that
you should compare the two results (yours and the
one obtained by the wims software) by dividing each
through by their leading coefficients. The answers
should then agree. Since the coefficients are in Q(i),
a field, and the leading coefficient is nonzero, this is
always possible.

I'm not sure what 'pseudo division' may mean, as
there are various alternative algorithms to using as
the Euclidean algorithm does repeated steps of a
"division algorithm" in which the quotient and some
remainder "smaller" than the divisor are extracted.

yes should have explained terms here i guess, 'pseudo division' is a term i
came across in 'polynomials' by maurice mignotte & doru stefanescu and is
something i havent heard of before either, its defined as being :- Let F and
G be two polynomials with G =/= 0. Let b be the leading coefficient of G
and delta = max(deg(F) - deg(G) + 1, 0). there exist unique polynomials Q,R
such that

b^delta F = QG + R , where deg(R) < deg(F)

its basically a way of dividing two polynomials where the 'divisor'
polynomial is not monic. Later also there follows a 'Generalized Euclidean
Algorithm' which uses this pseudo-division seemingly, alongside concepts
such as 'content' and 'primitive polynomials' to find GCD's - I havent yet
implemented this algorithm instead I firstly implemented the much simple
straight euclidean algorithm... hence the problems i guess with large
coefficient growth



Working over Z[i] rather than Q(i), and using least
common multiples of leading coefficients (with
subtraction to reduce degree) seems like a good
strategy for minimizing coefficient sizes, and it
could reasonably be called 'pseudo division'.

yes i did do something similar, but not at each stage of the calculation,
just at the end. i guess thats the missing piece..


However note the article I referred you to on
"heuristic GCD", which claims that this very

different approach is widely adopted by CAS
packages.

regards, chip



.

Relevant Pages

  • 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)
  • Re: decomposition of polynomials
    ... but Googling "polynomial decomposition" will reveal ... problems for multivariate polynomials and for rational and algebraic ... O) algorithm for the decomposition of irreducible polynomials ... Technical Report TR87-826, Comput. ...
    (sci.math)
  • Re: Kroneckers method for polynomial factorization
    ... The algorithm as given is not really a good version. ... I hope this shows what you left out (factoring the integers). ... The polynomial interpolation step cannot always ... polynomials requiring rational coefficients cannot, however, be ...
    (sci.math.symbolic)
  • Re: euclidean algorithm over Q[i]
    ... Z, the Gaussian integers, may be what you remember seeing. ... written a pretty simplistic algorithm in java that carries out polynomial ... GCD, just using polynomial long division and the euclidean algorithm. ... GCD's of univariate polynomials over Q? ...
    (sci.math.symbolic)
  • Re: [OT] Re: Second largest
    ... million log N is larger than log N by an amount most people would find ... we were discussing an Oalgorithm. ... the additive constant of a million in connection with the ... of the coefficient does not diminish with increasing n). ...
    (comp.lang.c)
Loading