Benchmarks

Warning

The actual benchmarks are moved to https://github.com/PoslavskySV/rings.benchmarks. Below information is outdated.

All benchmarks presented below were executed on MacBook Pro (15-inch, 2017), 3,1 GHz Intel Core i7, 16 GB 2133 MHz LPDDR3. The complete source code of benchmarks can be found at GitHub. The following software were used:

Multivariate GCD

Multivariate GCD performance was tested on random polynomials in the following way. Polynomials \(a\), \(b\) and \(g\) with 40 terms and degree 20 in each variable were generated at random. Then the GCDs \(gcd(a g, b g)\) (should result in multiple of \(g\)) and \(gcd(a g + 1, b g)\) (usually 1) were calculated. So the input polynomials had about ~1000 terms and degree 40 in each variable (so the total degree of input was \(40 * n\), where \(n\) is the number of variables). Tests were performed for polynomials in 3, 4 and 5 variables over \(Z\) and \(Z_2\) ground rings.

Brief conclusion

  • for non trivial GCD problems Rings are several orders of magnitude faster than Singular (on polynomials over all domains) and Mathematica (on polynomials over finite fields) and slightly faster than Mathematica for polynomials over Z

  • for a relatively prime polynomials, all tools show comparable (very good) performace

Multivariate GCD over \(Z_2\)

Mathematica failed to solve GCD problem for medium-sized polynomials considered in this benchmark in most cases in a reasonable time (minutes), so in this benchmark we compared only Rings and Singular.

GCD in \(Z_2[x,y,z]\)

Performance of GCD in \(Z_2[x,y,z]\)

_images/gcd_z2_3vars_rings_vs_singular.png

Rings vs Singular performance of \(gcd(a g, b g)\) for random polynomials \((a, b, g) \in Z_2[x,y,z]\) each with 40 terms and degree 20 in each variable

_images/gcd_coprime_z2_3vars_rings_vs_singular.png

Rings vs Singular performance of \(gcd(a g + 1, b g)\) (coprime input) for random polynomials \((a, b, g) \in Z_2[x,y,z]\) each with 40 terms and degree 20 in each variable

GCD in \(Z_2[x_1,x_2,x_3,x_4]\)

Performance of GCD in \(Z_2[x_1,x_2,x_3,x_4]\)

_images/gcd_z2_4vars_rings_vs_singular.png

Rings vs Singular performance of \(gcd(a g, b g)\) for random polynomials \((a, b, g) \in Z_2[x_1,x_2,x_3,x_4]\) each with 40 terms and degree 20 in each variable

_images/gcd_coprime_z2_4vars_rings_vs_singular.png

Rings vs Singular performance of \(gcd(a g + 1, b g)\) (coprime input) for random polynomials \((a, b, g) \in Z_2[x_1,x_2,x_3,x_4]\) each with 40 terms and degree 20 in each variable

GCD in \(Z_2[x_1,x_2,x_3,x_4, x_5]\)

In all these tests Singular failed to obtain result within 500 seconds, while Rings calculated GCD within less than 5 seconds.

Multivariate GCD over \(Z\)

GCD in \(Z[x,y,z]\)

_images/gcd_z_3vars_rings_vs_singular.png

Rings vs Singular performance of \(gcd(a g, b g)\) for random polynomials \((a, b, g) \in Z[x,y,z]\) each with 40 terms and degree 20 in each variable

_images/gcd_z_3vars_rings_vs_wolfram.png

Rings vs Mathematica performance of \(gcd(a g, b g)\) for random polynomials \((a, b, g) \in Z[x,y,z]\) each with 40 terms and degree 20 in each variable

_images/gcd_coprime_z_3vars_rings_vs_singular.png

Rings vs Singular performance of \(gcd(a g + 1, b g)\) (coprime input) for random polynomials \((a, b, g) \in Z[x,y,z]\) each with 40 terms and degree 20 in each variable

_images/gcd_coprime_z_3vars_rings_vs_wolfram.png

Rings vs Mathematica performance of \(gcd(a g + 1, b g)\) (coprime input) for random polynomials \((a, b, g) \in Z[x,y,z]\) each with 40 terms and degree 20 in each variable

GCD in \(Z[x_1,x_2,x_3,x_4]\)

_images/gcd_z_4vars_rings_vs_singular.png

Rings vs Singular performance of \(gcd(a g, b g)\) for random polynomials \((a, b, g) \in Z[x_1,x_2,x_3,x_4]\) each with 40 terms and degree 20 in each variable

_images/gcd_z_4vars_rings_vs_wolfram.png

Rings vs Mathematica performance of \(gcd(a g, b g)\) for random polynomials \((a, b, g) \in Z[x_1,x_2,x_3,x_4]\) each with 40 terms and degree 20 in each variable

_images/gcd_coprime_z_4vars_rings_vs_singular.png

Rings vs Singular performance of \(gcd(a g + 1, b g)\) (coprime input) for random polynomials \((a, b, g) \in Z[x_1,x_2,x_3,x_4]\) each with 40 terms and degree 20 in each variable

_images/gcd_coprime_z_4vars_rings_vs_wolfram.png

Rings vs Mathematica performance of \(gcd(a g + 1, b g)\) (coprime input) for random polynomials \((a, b, g) \in Z[x_1,x_2,x_3,x_4]\) each with 40 terms and degree 20 in each variable

GCD in \(Z[x_1,x_2,x_3,x_4,x_5]\)

_images/gcd_z_5vars_rings_vs_singular.png

Rings vs Singular performance of \(gcd(a g, b g)\) for random polynomials \((a, b, g) \in Z[x_1,x_2,x_3,x_4,x_5]\) each with 40 terms and degree 20 in each variable

_images/gcd_z_5vars_rings_vs_wolfram.png

Rings vs Mathematica performance of \(gcd(a g, b g)\) for random polynomials \((a, b, g) \in Z[x_1,x_2,x_3,x_4,x_5]\) each with 40 terms and degree 20 in each variable

_images/gcd_coprime_z_5vars_rings_vs_singular.png

Rings vs Singular performance of \(gcd(a g + 1, b g)\) (coprime input) for random polynomials \((a, b, g) \in Z[x_1,x_2,x_3,x_4,x_5]\) each with 40 terms and degree 20 in each variable

_images/gcd_coprime_z_5vars_rings_vs_wolfram.png

Rings vs Mathematica performance of \(gcd(a g + 1, b g)\) (coprime input) for random polynomials \((a, b, g) \in Z[x_1,x_2,x_3,x_4,x_5]\) each with 40 terms and degree 20 in each variable

GCD in \(Z[x_1,x_2,x_3,x_4,x_5,x_6]\)

In all these tests Singular failed to obtain result within 500 seconds, so we present only Rings vs Mathematica comparison.

_images/gcd_z_6vars_rings_vs_wolfram.png

Rings vs Mathematica performance of \(gcd(a g, b g)\) for random polynomials \((a, b, g) \in Z[x_1,x_2,x_3,x_4,x_5,x_6]\) each with 40 terms and degree 20 in each variable

_images/gcd_coprime_z_6vars_rings_vs_wolfram.png

Rings vs Mathematica performance of \(gcd(a g + 1, b g)\) (coprime input) for random polynomials \((a, b, g) \in Z[x_1,x_2,x_3,x_4,x_5,x_6]\) each with 40 terms and degree 20 in each variable

Multivariate factorization

Multivariate factorization performance was tested on random polynomials in the following way. Three polynomials \(a\), \(b\) and \(c\) with 20 terms and degree 10 in each variable were generated at random. Then the factorizations of \((a b c)\) (should give at least three factors) and \((a b c + 1)\) (usually irreducible) were calculated. So the input polynomials had about ~8000 terms and degree 30 in each variable (so the total degree of input was \(30 * n\), where \(n\) is the number of variables). Tests were performed for polynomials in 3, 4, 5, 6 and 7 variables over \(Z\), \(Z_2\) and \(Z_{524287}\) ground rings.

Brief conclusion

  • Rings and Singular are comparably fast and Mathematica is hopelessly slow

  • for irreducible polynomials Rings are considerably faster than Singular

  • Rings perform better on dense problems

Multivariate factorization over \(Z_2\)

These tests were performed for Rings and Singular since Mathematica does not support multivariate factorization in finite fields.

Factorization in \(Z_2[x,y,z]\)

_images/factor_z2_3vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c)\) for random polynomials \((a, b, c) \in Z_2[x,y,z]\) each with 20 terms and degree 10 in each variable

_images/factor_irred_z2_3vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c + 1)\) (irreducible) for random polynomials \((a, b, c) \in Z_2[x,y,z]\) each with 20 terms and degree 10 in each variable

Factorization in \(Z_2[x_1,x_2,x_3,x_4]\)

_images/factor_z2_4vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c)\) for random polynomials \((a, b, c) \in Z_2[x_1,x_2,x_3,x_4]\) each with 20 terms and degree 10 in each variable

_images/factor_irred_z2_4vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c + 1)\) (irreducible) for random polynomials \((a, b, c) \in Z_2[x_1,x_2,x_3,x_4]\) each with 20 terms and degree 10 in each variable

Factorization in \(Z_2[x_1,x_2,x_3,x_4,x_5]\)

_images/factor_z2_5vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c)\) for random polynomials \((a, b, c) \in Z_2[x_1,x_2,x_3,x_4,x_5]\) each with 20 terms and degree 10 in each variable

_images/factor_irred_z2_5vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c + 1)\) (irreducible) for random polynomials \((a, b, c) \in Z_2[x_1,x_2,x_3,x_4,x_5]\) each with 20 terms and degree 10 in each variable

Factorization in \(Z_2[x_1,x_2,x_3,x_4,x_5,x_6]\)

_images/factor_z2_6vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c)\) for random polynomials \((a, b, c) \in Z_2[x_1,x_2,x_3,x_4,x_5,x_6]\) each with 20 terms and degree 10 in each variable

_images/factor_irred_z2_6vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c + 1)\) (irreducible) for random polynomials \((a, b, c) \in Z_2[x_1,x_2,x_3,x_4,x_5,x_6]\) each with 20 terms and degree 10 in each variable

Factorization in \(Z_2[x_1,x_2,x_3,x_4,x_5,x_6,x_7]\)

_images/factor_z2_7vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c)\) for random polynomials \((a, b, c) \in Z_2[x_1,x_2,x_3,x_4,x_5,x_6,x_7]\) each with 20 terms and degree 10 in each variable

_images/factor_irred_z2_7vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c + 1)\) (irreducible) for random polynomials \((a, b, c) \in Z_2[x_1,x_2,x_3,x_4,x_5,x_6,x_7]\) each with 20 terms and degree 10 in each variable

Multivariate factorization over \(Z_{524287}\)

Factorization in \(Z_{524287}[x,y,z]\)

_images/factor_z524287_3vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c)\) for random polynomials \((a, b, c) \in Z_{524287}[x,y,z]\) each with 20 terms and degree 10 in each variable

_images/factor_irred_z524287_3vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c + 1)\) (irreducible) for random polynomials \((a, b, c) \in Z_{524287}[x,y,z]\) each with 20 terms and degree 10 in each variable

Factorization in \(Z_{524287}[x_1,x_2,x_3,x_4]\)

_images/factor_z524287_4vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c)\) for random polynomials \((a, b, c) \in Z_{524287}[x_1,x_2,x_3,x_4]\) each with 20 terms and degree 10 in each variable

_images/factor_irred_z524287_4vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c + 1)\) (irreducible) for random polynomials \((a, b, c) \in Z_{524287}[x_1,x_2,x_3,x_4]\) each with 20 terms and degree 10 in each variable

Factorization in \(Z_{524287}[x_1,x_2,x_3,x_4,x_5]\)

_images/factor_z524287_5vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c)\) for random polynomials \((a, b, c) \in Z_{524287}[x_1,x_2,x_3,x_4,x_5]\) each with 20 terms and degree 10 in each variable

_images/factor_irred_z524287_5vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c + 1)\) (irreducible) for random polynomials \((a, b, c) \in Z_{524287}[x_1,x_2,x_3,x_4,x_5]\) each with 20 terms and degree 10 in each variable

Factorization in \(Z_{524287}[x_1,x_2,x_3,x_4,x_5,x_6]\)

_images/factor_z524287_6vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c)\) for random polynomials \((a, b, c) \in Z_{524287}[x_1,x_2,x_3,x_4,x_5,x_6]\) each with 20 terms and degree 10 in each variable

_images/factor_irred_z524287_6vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c + 1)\) (irreducible) for random polynomials \((a, b, c) \in Z_{524287}[x_1,x_2,x_3,x_4,x_5,x_6]\) each with 20 terms and degree 10 in each variable

Factorization in \(Z_{524287}[x_1,x_2,x_3,x_4,x_5,x_6,x_7]\)

_images/factor_z524287_7vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c)\) for random polynomials \((a, b, c) \in Z_{524287}[x_1,x_2,x_3,x_4,x_5,x_6,x_7]\) each with 20 terms and degree 10 in each variable

_images/factor_irred_z524287_7vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c + 1)\) (irreducible) for random polynomials \((a, b, c) \in Z_{524287}[x_1,x_2,x_3,x_4,x_5,x_6,x_7]\) each with 20 terms and degree 10 in each variable

Multivariate factorization over \(Z\)

Factorization in \(Z[x,y,z]\)

_images/factor_z_3vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c)\) for random polynomials \((a, b, c) \in Z[x,y,z]\) each with 20 terms and degree 10 in each variable

_images/factor_z_3vars_rings_vs_wolfram.png

Rings vs Mathematica performance of \(factor(a b c)\) for random polynomials \((a, b, c) \in Z[x,y,z]\) each with 20 terms and degree 10 in each variable

_images/factor_irred_z_3vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c + 1)\) (irreducible) for random polynomials \((a, b, c) \in Z[x,y,z]\) each with 20 terms and degree 10 in each variable

_images/factor_irred_z_3vars_rings_vs_wolfram.png

Rings vs Mathematica performance of \(factor(a b c + 1)\) (irreducible) for random polynomials \((a, b, c) \in Z[x,y,z]\) each with 20 terms and degree 10 in each variable

Factorization in \(Z[x_1,x_2,x_3,x_4]\)

For non-trivial factorization problems, Mathematica failed to obtain result in a reasonable time, so it is not shown here.

_images/factor_z_4vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c)\) for random polynomials \((a, b, c) \in Z[x_1,x_2,x_3,x_4]\) each with 20 terms and degree 10 in each variable

_images/factor_irred_z_4vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c + 1)\) (irreducible) for random polynomials \((a, b, c) \in Z[x_1,x_2,x_3,x_4]\) each with 20 terms and degree 10 in each variable

Factorization in \(Z[x_1,x_2,x_3,x_4,x_5]\)

Mathematica failed to obtain result in a reasonable time, so it is not shown here.

_images/factor_z_5vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c)\) for random polynomials \((a, b, c) \in Z[x_1,x_2,x_3,x_4,x_5]\) each with 20 terms and degree 10 in each variable

_images/factor_irred_z_5vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c + 1)\) (irreducible) for random polynomials \((a, b, c) \in Z[x_1,x_2,x_3,x_4,x_5]\) each with 20 terms and degree 10 in each variable

Factorization in \(Z[x_1,x_2,x_3,x_4,x_5,x_6]\)

Mathematica failed to obtain result in a reasonable time, so it is not shown here.

_images/factor_z_6vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c)\) for random polynomials \((a, b, c) \in Z[x_1,x_2,x_3,x_4,x_5,x_6]\) each with 20 terms and degree 10 in each variable

_images/factor_irred_z_6vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c + 1)\) (irreducible) for random polynomials \((a, b, c) \in Z[x_1,x_2,x_3,x_4,x_5,x_6]\) each with 20 terms and degree 10 in each variable

Factorization in \(Z[x_1,x_2,x_3,x_4,x_5,x_6,x_7]\)

Mathematica failed to obtain result in a reasonable time, so it is not shown here.

_images/factor_z_7vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c)\) for random polynomials \((a, b, c) \in Z[x_1,x_2,x_3,x_4,x_5,x_6,x_7]\) each with 20 terms and degree 10 in each variable

_images/factor_irred_z_7vars_rings_vs_singular.png

Rings vs Singular performance of \(factor(a b c + 1)\) (irreducible) for random polynomials \((a, b, c) \in Z[x_1,x_2,x_3,x_4,x_5,x_6,x_7]\) each with 20 terms and degree 10 in each variable

Multivariate factorization on large not very sparse polynomials

To check how the above plots obtained with random polynomials scale to a really huge and more dense input, the following factorizations were tested.

Factor

\[poly = (1 + 3 x_1 + 5 x_2 + 7 x_3 + 9 x_4 + 11 x_5 + 13 x_6 + 15 x_7)^{15} - 1\]

over \(Z\), \(Z_2\) and \(Z_{524287}\) coefficient rings:

Coefficient ring

Rings

Singular

Mathematica

\(Z\)

55s

20s

271s

\(Z_2\)

250ms

> 1 hour

N/A

\(Z_{524287}\)

28s

109s

N/A

Factor

\[\begin{split}poly = (1 + 3ab + 5bc + 7cd + 9de + 11ef + 13fg + 15ga)^3\\ \quad \times (1 + 3ac + 5bd + 7ce + 9fe + 11gf + 13fa + 15gb)^3\\ \quad \quad \times (1 + 3ad + 5be + 7cf + 9fg + 11ga + 13fb + 15gc)^3\\ \quad \quad \quad -1\end{split}\]

over \(Z\), \(Z_2\) and \(Z_{524287}\) coefficient rings:

Coefficient ring

Rings

Singular

Mathematica

\(Z\)

23s

12s

206s

\(Z_2\)

6s

3s

N/A

\(Z_{524287}\)

26s

9s

N/A

Univariate factorization

Performance of univariate factorization was compared to NTL, FLINT and Mathematica. Polynomials in \(Z_{17}[x]\) of the form:

\[p_{deg} = 1 + \sum_{i = 1}^{i \leq deg} i \times x^i\]

were used.

_images/bench_fac_uni_Zp_flint_ntl.png

At small degrees the performance is identical, while at large degrees NTL and FLINT have much better asymptotic, probably due to more advanced algorithms for polynomial multiplication.