Diff for "MultivariateGCDBenchmarks"

Differences between revisions 3 and 21 (spanning 18 versions)

These are the polynomials found on this page: http://magma.maths.usyd.edu.au/users/allan/gcdcomp.html The files for Sage can be found at http://sage.math.washington.edu/home/mhansen/multivariate_gcd_benchmarks.tar.bz2 . Timings were done on a 2.0 GHz Core 2 Duo Linux system.

For the Sage/Singular timings, I did the following:

sage: load fermat_gcd_1var.py
sage: time a = p1.gcd(p2, algorithm='ezgcd')

For the Maxima timings, I did the following:

sage: mp1 = maxima(p1)
sage: mp2 = maxima(p2)
sage: time a = mp1.gcd(mp2)

1 variable over QQ

File: fermat_gcd_1var.py

	ezgcd	modular	maxima
p - 100	0.02	0.03	0.20
q - 1000	12.10	9.84	7.66
r - 10000	95.03	62.80	30.27

(Univariate)

p - 100	3.07
q - 1000	-
r - 2000	-

2 variables over QQ

File: fermat_gcd_2var.py

	ezgcd	modular	maxima
p - 20	0.05	0.33	0.11
q - 40	0.33	9.47	0.66
r - 100	8.71	-	14.40
s - 160	89.57	-

3 variables over QQ

File: fermat_gcd_3var.py

	ezgcd	modular	maxima
p - 20	0.30	-	1.42
q - 40	8.40	-	27.68
r - 60	92.03	-

4 variables over QQ

File: fermat_gcd_4var.py

	ezgcd	modular	maxima
p - 10	0.13	-	1.04
q - 16	0.93	-	8.08
r - 20	2.82	-	33.96
s - 30	40.06	-	80.86

1 variable over GF(43051)

File: fermat_gcd_1var.py

	ezgcd	modular
p - 100	0.03	0.03
q - 1000	10.65	8.33
r - 10000	75.74	85.41

2 variables over GF(43051)

File: fermat_gcd_mod_2var.py

	ezgcd	modular
p - 20	0.25	0.25
q - 40	14.23	14.00
r - 100	-	-
s - 160	-	-

3 variables over GF(43051)

File: fermat_gcd_mod_3var.sage

	ezgcd	modular
p - 10	0.84	0.86
q - 20	8.40	-
r - 60	92.03	-

4 variables over GF(43051)

File: fermat_gcd_4var.py

	ezgcd	modular
p - 10	99.75	102.57
q - 16
r - 20
s - 30

-  ⇤ ← Revision 3 as of 2008-04-01 00:24:27 → 
  Size: 314
  Editor: MikeHansen
  Comment:
+   ← Revision 21 as of 2008-04-01 04:19:47 → ⇥
  Size: 2663
  Editor: MikeHansen
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 1:
-Describe MultivariateFactoringBenchmarks here.
+## page was renamed from PolynomialGCDBenchmarks
## page was renamed from MultivariateFactoringBenchmarks

These are the polynomials found on this page: http://magma.maths.usyd.edu.au/users/allan/gcdcomp.html  The files for Sage can be found at http://sage.math.washington.edu/home/mhansen/multivariate_gcd_benchmarks.tar.bz2 . Timings were done on a 2.0 GHz Core 2 Duo Linux system.

For the Sage/Singular timings, I did the following:
{{{
sage: load fermat_gcd_1var.py
sage: time a = p1.gcd(p2, algorithm='ezgcd')
}}}


For the Maxima timings, I did the following:
{{{
sage: mp1 = maxima(p1)
sage: mp2 = maxima(p2)
sage: time a = mp1.gcd(mp2)
}}}
-Line 4:
+Line 21:
-|| || || ||
+File: fermat_gcd_1var.py

||           ||  ezgcd || modular || maxima ||
|| p - 100   ||  0.02  ||   0.03  || 0.20   ||
|| q - 1000  || 12.10  ||   9.84  || 7.66   ||
|| r - 10000 || 95.03  ||  62.80  || 30.27  ||

=== (Univariate) ===
-Line 10:
+Line 34:
-|| ||ezgcd ||modular ||
||p - 20 ||0.05 ||0.33 ||
||q - 40 ||0.33 ||9.47 ||
||r - 100 ||8.71 ||- ||
||s - 160 ||89.57 ||- ||
+File: fermat_gcd_2var.py

||        ||ezgcd ||modular || maxima ||
||p - 20  ||0.05  ||0.33    || 0.11   ||
||q - 40  ||0.33  ||9.47    || 0.66   ||
||r - 100 ||8.71  ||-       || 14.40  ||
||s - 160 ||89.57 ||-       ||   ||

== 3 variables over QQ ==
File: fermat_gcd_3var.py

||        || ezgcd || modular || maxima ||
|| p - 20 || 0.30  ||   -     ||  1.42  ||
|| q - 40 || 8.40  ||   -     || 27.68  ||
|| r - 60 ||92.03  ||   -     ||        ||

== 4 variables over QQ ==
File: fermat_gcd_4var.py

||        || ezgcd || modular || maxima ||
|| p - 10 ||  0.13 ||   -     || 1.04   ||
|| q - 16 ||  0.93 ||   -     || 8.08   ||
|| r - 20 ||  2.82 ||   -     || 33.96  ||
|| s - 30 || 40.06 ||   -     || 80.86  ||
 

== 1 variable over GF(43051) ==
File: fermat_gcd_1var.py

||           ||  ezgcd || modular ||
|| p - 100   ||  0.03  ||  0.03   ||
|| q - 1000  || 10.65  ||  8.33   ||
|| r - 10000 || 75.74   || 85.41  ||


== 2 variables over GF(43051) ==
File: fermat_gcd_mod_2var.py

||        || ezgcd  || modular ||
||p - 20  || 0.25   || 0.25    ||
||q - 40  || 14.23  || 14.00   ||
||r - 100 ||  -     || -     ||
||s - 160 ||  -     || -     ||


== 3 variables over GF(43051) ==
File: fermat_gcd_mod_3var.sage

||        || ezgcd || modular ||
|| p - 10 || 0.84  ||   0.86  ||
|| q - 20 || 8.40  ||   -     ||
|| r - 60 ||92.03  ||   -     ||

== 4 variables over GF(43051) ==
File: fermat_gcd_4var.py

||        || ezgcd || modular ||
|| p - 10 || 99.75 ||  102.57 ||
|| q - 16 ||   ||        ||
|| r - 20 ||   ||        ||
|| s - 30 ||   ||        ||