benchmarks.rst

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:

• Mathematica (version 11.1.1.0)
• Singular (version 4.1.0)
• NTL (version 10.4.0)
• FLINT (version 2.5.2_1)

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]

|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

|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]

|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

|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]

|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

|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

|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

|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]

|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

|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

|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

|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]

|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

|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

|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

|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.

|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

|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]

|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

|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]

|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

|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]

|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

|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]

|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

|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]

|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

|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]

|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

|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]

|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

|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]

|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

|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]

|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

|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]

|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

|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]

|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

|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

|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

|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.

|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

|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.

|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

|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.

|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

|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.

|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

|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

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

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.

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.