##
Fast Dense Gcds

A modification of the Collins/Brown
modular gcd algorithm has been programmed and made available (Maple V.5
format library: gcd.zip)
here on the web. This page demonstrates the usage and efficiency of this
algorithm.
First to load the new function you
need to unpack the library, and be sure the path is in your libname,
then type:

>` `**readlib(DGCD):**

The usage of DGCD is identical to
that of gcd (i.e. the additional arguments for the cofactors, etc.)

Now for the comparison, we choose
two dense degree 20 polynomials in 2 variables as cofactors with a degree
20 gcd (usually the worst case):

>` `**a:=randpoly([x,y],degree=20,dense):**

>` `**b:=randpoly([x,y],degree=20,dense):**

>` `**g:=randpoly([x,y],degree=20,dense):**

>` `**A:=expand(a*g): B:=expand(b*g):**

>` `**t:=time(): g1:=DGCD(A,B):
time()-t;**

1.021

>` `**t:=time(): g2:=gcd(A,B):
time()-t;**

1.719

So not much difference. Try three
variables, degree 10:

>` `**a:=randpoly([x,y,z],degree=10,dense):**

>` `**b:=randpoly([x,y,z],degree=10,dense):**

>` `**g:=randpoly([x,y,z],degree=10,dense):**

>` `**A:=expand(a*g): B:=expand(b*g):**

>` `**t:=time(): g1:=DGCD(A,B):
time()-t;**

2.449

>` `**t:=time(): g2:=gcd(A,B):
time()-t;**

27.141

Improvement is much more noticeable
here.

In general the new algorithm will
out perform the old whenever the inputs are dense in the input variables.

##
Coming Soon

A more general fast gcd algorithm
is in progress that will improve both dense and sparse gcd computation.

Last updated May-17-99. *wittkopf@cecm.sfu.ca*