Comparison of GCD in Several Systems www.bway.net/~lewis Dear Prof. Lewis, We have tested your CAS Fermat and we would like to show to you a table comparing timings for the computation of multivariate gcd's. We have run Magma V2.9-25, Fermat 3.4, Maple9 and Singular 2.0.4 on the same examples including polynomials in 1 to 4 variables with different degrees. In each case three dense polynomials a, b, c were taken randomly and the greatest common divisor of a*b and a*c was computed. The "total degree" in the table below indicates the degree of a*b and a*c. All computations were run on the same machine, namely a machine with 2 processors AMD Opteron(tm) Processor 248 2200 MHz, 8 GB Memory. As you can see, your system Fermat has the best built-in facilities for multivariate gcd computations. We would be very pleased to get any information about the algorithms that you use in Fermat for multivariate gcd's. If you have some references or even informal descriptions, we would be very interested in this. Magma V2.9-25 Fermat 3.4 Maple9 Singular 2.0.4 -------------------------------------------------------------------------------- 1 variable total degree 100 0.010 0.000 0.007 < 0.100 total degree 1000 0.050 0.160 0.391 7.800 total degree 2000 0.210 0.720 1.605 60.850 -------------------------------------------------------------------------------- 2 variables total degree 20 0.010 0.010 0.020 1.900 total degree 40 0.110 0.070 0.100 276.000 total degree 100 4.930 2.650 2.730 > 50000 total degree 160 43.710 19.900 15.548 / -------------------------------------------------------------------------------- 3 variables total degree 20 0.210 0.100 0.772 6511.000 total degree 40 6.740 2.600 50.777 / total degree 60 97.780 19.510 635.514 / -------------------------------------------------------------------------------- 4 variables total degree 10 0.160 0.040 0.406 / total degree 16 1.150 0.430 3.338 / total degree 20 4.170 1.570 16.061 / total degree 30 64.790 17.260 351.898 / -------------------------------------------------------------------------------- I tried some multivariate gcd computations in non-zero characteristic. Please find the resulting timings below and the data attached. All computations were done on a machine with 2 processors AMD Opteron (64 bit), 2200 MHz, 8 GB memory. characteristic 43051 Magma V2.9-25 Fermat 3.4 Maple9 Singular 2.0.4 -------------------------------------------------------------------------------- 1 variable total degree 100 0.000 0.000 0.001 0.000 total degree 1000 0.030 0.020 0.025 0.360 total degree 2000 0.080 0.070 0.091 1.340 -------------------------------------------------------------------------------- 2 variables total degree 20 0.000 0.000 0.010 0.410 total degree 40 0.050 0.060 0.029 23.940 total degree 100 1.540 2.340 0.253 5489.070 total degree 160 9.990 17.400 1.087 91107.230 -------------------------------------------------------------------------------- 3 variables total degree 20 0.010 0.000 0.112 1.960 total degree 40 0.130 0.080 3.452 / total degree 60 3.040 1.670 240.441 / -------------------------------------------------------------------------------- 4 variables total degree 10 0.100 0.040 0.773 256.600 total degree 16 0.810 0.340 11.721 / total degree 20 2.700 1.150 54.394 / -------------------------------------------------------------------------------- Best regards, Daniel Robertz Lehrstuhl B fuer Mathematik RWTH Aachen Germany and Vladimir Gerdt, Laboratory of Information Technologies Joint Institute for Nuclear Research 141980 Dubna, Russia The data is now at http://www.bway.net/~lewis/fermat/gcdcode.tar.gz May 29, 2004 __________________________________________________________________ To run the examples in Singular: The basic syntax of polynomials is the same as Fermat, but the setup is different. For example, in gcd_mod_4var: timer=1; ring r=43051,(x1,x2,x3,x4),lp; poly p1 = -10724099188*x1^5*x2*x4^2*x3+22203568489*x1^2*x2^3*x4^4-13285278966*x2^5*x3^2- 6182804012*x2^4*x3^2-10400108401*x2^2*x3^5-7184504872*x2^4*x3*x1*x4+762339382*x1*x2*x3+ 17646336440*x1^2*x3^3*x4^5+2027881264*x2^3*x3-36720920965*x2^4*x3*x1^3*x4 .... ; poly p2 = ... ; gcd(p1, p2); gcd(q1, q2); gcd(r1, r2); gcd(s1, s2); Running over Z, one would use: timer=1; ring r=0,(x1,x2,x3,x4),lp;