Fast Dense Gcds

A modification of the Collins/Brown modular gcd algorithm has been programmed and made available (Maple V.5 format library: 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;


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


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;


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


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.