# poslavskysv / rings

Rings: efficient Java/Scala library for polynomial rings

Website GitHub

# Rings: efficient Java/Scala library for polynomial rings

Rings is an efficient implementation of univariate and multivariate polynomial algebra over arbitrary coefficient rings. It makes use of asymptotically fast algorithms for basic algebraic operations as well as for advanced methods like GCDs, factorization and Gröbner bases. Performance achieved in Rings is comparable to well known solutions like Singular/NTL/FLINT/Maple/Mathematica.

The key features of Rings include:

The full documentation is available at http://rings.readthedocs.io.

## Set up

### Interactive Rings shell and Rings scripts

To taste what Rings can do, one can try interactive session with Ammonite REPL. You can install Rings.repl with Homebrew:

$brew install PoslavskySV/rings/rings.repl or just by typing the following commands at the prompt: $ sudo curl -L -o /usr/local/bin/amm https://git.io/v5Tct && sudo chmod +x /usr/local/bin/amm
$sudo curl -L -o /usr/local/bin/rings.repl https://git.io/vd7EY && chmod +x /usr/local/bin/rings.repl Now run Rings.repl: $ rings.repl
Rings 2.3.1: efficient Java/Scala library for polynomial rings

@ implicit val ring = MultivariateRing(Z, Array("x", "y", "z"))
ring: MultivariateRing[IntZ] = MultivariateRing(Z, Array("x", "y", "z"), LEX)

@ val poly1 = ring("x + y - z").pow(8)
poly1: MultivariatePolynomial[IntZ] = z^8-8*y*z^7+28*y^2*z^6-56*y^3*z^5+70*...

@ val poly2 = ring("x - y + z").pow(8)
poly1: MultivariatePolynomial[IntZ] = z^8-8*y*z^7+28*y^2*z^6-56*y^3*z^5+70*...

@ Factor(poly1 - poly2)
res13: FactorDecomposition[MultivariatePolynomial[IntZ]] =
16*(x)*((-1)*z+y)
*(z^4-4*y*z^3+6*y^2*z^2-4*y^3*z+y^4+6*x^2*z^2-12*x^2*y*z+6*x^2*y^2+x^4)
*(z^2-2*y*z+y^2+x^2)

Additionally, Rings.repl can be used to run scripts with Rings code:

### Multivariate polynomials

Some math with multivariate polynomials from Z[x, y, z]:

// ring Z[x, y, z]
implicit val ring = MultivariateRing(Z, Array("x", "y", "z"))
// parse some ring elements
val (x, y, z) = ring("x", "y", "z")

// construct some polynomials using different math ops
val a = (x + y + z).pow(2) - 1
val b = (x - y - z - 1).pow(2) + x + y + z - 1
val c = (a + b + 1).pow(9) - a - b - 1

// reduce c modulo a and b (multivariate division with remainder)
val (div1, div2, rem) = c /%/% (a, b)

Multivariate GCD in Z[a, b, c]:

// ring Z[a, b, c]
implicit val ring = MultivariateRing(Z, Array("a", "b", "c"))

// parse polynomials from strings
val poly1 = ring("-b-b*c-b^2+a+a*c+a^2")
val poly2 = ring("b^2+b^2*c+b^3+a*b^2+a^2+a^2*c+a^2*b+a^3")

// compute multivariate GCD
val gcd   = PolynomialGCD(poly1, poly2)
assert (poly1 % gcd === 0)
assert (poly2 % gcd === 0)
println(gcd)

Factor polynomial in Z_{2}[x, y, z]:

// ring Z/2[x, y, z]
implicit val ring = MultivariateRingZp64(2, Array("x", "y", "z"))
val (x, y, z) = ring("x", "y", "z")

// factorize poly
val factors = Factor(1 + (1 + x + y + z).pow(2) + (x + y + z).pow(4))
println(factors)

Factor polynomial in Z[a, b, c]:

// ring Z[a, b, c]
implicit val ring = MultivariateRing(Z, Array("a", "b", "c"))
val (a, b, c) = ring("a", "b", "c")

// factorize poly
val factors = Factor(1 - (1 + a + b + c).pow(2) - (2 + a + b + c).pow(3))
println(ring show factors)

Factor polynomial in Q[x, y, z]:

// ring Q[x, y, z]
implicit val ring = MultivariateRing(Q, Array("x", "y", "z"))

// parse some poly from string
val poly = ring(
"""
|(1/6)*y*z + (1/6)*y^3*z^2 - (1/2)*y^6*z^5 - (1/2)*y^8*z^6
|-(1/3)*x*z - (1/3)*x*y^2*z^2 + x*y^5*z^5 + x*y^7*z^6
|+(1/9)*x^2*y^2*z - (1/3)*x^2*y^7*z^5 - (2/9)*x^3*y*z
|+(2/3)*x^3*y^6*z^5 - (1/2)*x^6*y - (1/2)*x^6*y^3*z
|+x^7 + x^7*y^2*z - (1/3)*x^8*y^2 + (2/3)*x^9*y
""".stripMargin)

// factorize poly
val factors = Factor(poly)
println(factors)

Ring of multivariate polynomials over elements of Galois field GF(7,3)[x, y, z]:

// elements of GF(7,3) are represented as polynomials
// over "z" modulo irreducible polynomial "1 + 3*z + z^2 + z^3"
val cfRing = GF(UnivariateRingZp64(7, "z")("1 + 3*z + z^2 + z^3"), "z")
// ring GF(7,3)[a,b,c]
implicit val ring = MultivariateRing(cfRing, Array("a", "b", "c"))

// parse poly in GF(7^3)[a,b,c] from string
// coefficients of polynomials in GF(7,3)[a,b,c] are elements
// of GF(7,3) that is polynomials over "z"
val poly = ring("1 - (1 - z^3) * a^6*b + (1 - 2*z) * c^33 + a^66")

//factorize poly
println(Factor(poly))

### Ideals and Groebner bases

Construct some ideal and check its properties:

// ring Z/17[x,y,z]
implicit val ring = MultivariateRingZp64(17, Array("x", "y", "z"))
val (x, y, z) = ring("x", "y", "z")

// create ideal with two generators using GREVLEX monomial order for underlying Groebner basis
val I = Ideal(ring, Seq(x.pow(2) + y.pow(12) - z, x.pow(2) * z + y.pow(2) - 1), GREVLEX)
// I is proper ideal
assert(I.isProper)

// get computed Groebner basis
val gb = I.groebnerBasis
println(gb)

// check some ideal properties
assert(I.dimension == 1)
assert(I.degree == 36)

Unions, intersections and quotients of ideals:

// create another ideal with only one generator
val J = Ideal(ring, Seq(x.pow(4) * y.pow(4) + 1), GREVLEX)
// J is principal ideal
assert(J.isPrincipal)

val union = I union J
// union is zero dimensional ideal
assert(union.dimension == 0)

val intersection = I intersection J
// intersection is still 2-dimensional
assert(intersection.dimension == 2)

// yet another ideal
val K = Ideal(ring, Seq(z * x.pow(4) - z * y.pow(14) + y * z.pow(16), (x + y + z).pow(4)), GREVLEX)
// compute complicated quotient ideal
val quotient = (I * J * K) :/ times
assert(quotient == K) 

Construct lexicographic Gröbner basis to solve a system of equations:

// ring Q[a, b, c]
implicit val ring = MultivariateRing(Q, Array("x", "y", "z"))

// parse some polynomials from strings
val a = ring("8*x^2*y^2 + 5*x*y^3 + 3*x^3*z + x^2*y*z")
val b = ring("x^5 + 2*y^3*z^2 + 13*y^2*z^3 + 5*y*z^4")
val c = ring("8*x^3 + 12*y^3 + x*z^2 + 3")
val d = ring("7*x^2*y^4 + 18*x*y^3*z^2 + y^3*z^3")

// construct ideal with Groebner basis in LEX order
val ideal = Ideal(ring, Seq(a, b, c, d), LEX)
// it is very simple: <z^2, x, 1+4*y^3>
println(ideal)

### Programming

Implement generic function for solving linear Diophantine equations:

/**
* Solves equation \sum f_i s_i  = gcd(f_1, \dots, f_N) for given f_i and unknown s_i
* @return a tuple (gcd, solution)
*/
def solveDiophantine[E](fi: Seq[E])(implicit ring: Ring[E]) =
fi.foldLeft((ring(0), Seq.empty[E])) { case ((gcd, seq), f) =>
val xgcd = ring.extendedGCD(gcd, f)
(xgcd(0), seq.map(_ * xgcd(1)) :+ xgcd(2))
}

Implement generic function for computing partial fraction decomposition:

/** Computes partial fraction decomposition of given rational */
def apart[E](frac: Rational[E]) = {
implicit val ring: Ring[E] = frac.ring
val factors = ring.factor(frac.denominator).map {case (f, exp) => f.pow(exp)}
val (gcd,  nums) = solveDiophantine(factors.map(frac.denominator / _))
val (ints, rats) = (nums zip factors)
.map { case (num, den) => Rational(frac.numerator * num, den * gcd) }
.flatMap(_.normal)       // extract integral parts from fractions
.partition(_.isIntegral) // separate integrals and fractions
rats :+ ints.foldLeft(Rational(ring(0)))(_ + _)
}

Apply that function to elements of different rings:

// partial fraction decomposition for rationals
// gives List(184/479, (-10)/13, 1/8, (-10)/47, 1)
val qFracs = apart( Q("1234213 / 2341352"))

// partial fraction decomposition for rational functions
val ufRing = Frac(UnivariateRingZp64(17, "x"))
// gives List(4/(16+x), 1/(10+x), 15/(1+x), (14*x)/(15+7*x+x^2))
val pFracs = apart( ufRing("1 / (3 - 3*x^2 - x^3 + x^5)") )

Implement Lagrange method for univariate interpolation:

    p(x) = \sum_i p(x_i) \Pi_{j \ne i} \frac{x_{\phantom{i}} - x_j}{x_i -x_j}
/** Lagrange polynomial interpolation formula */
def interpolate[Poly <: IUnivariatePolynomial[Poly], Coef]
(points: Seq[(Coef, Coef)])
(implicit ring: IUnivariateRing[Poly, Coef]) = {
// implicit coefficient ring (setups algebraic operators on type Coef)
implicit val cfRing: Ring[Coef] = ring.cfRing
if (!cfRing.isField) throw new IllegalArgumentException
points.indices
.foldLeft(ring(0)) { case (sum, i) =>
sum + points.indices
.filter(_ != i)
.foldLeft(ring(points(i)._2)) { case (product, j) =>
product * (ring.x - points(j)._1) / (points(i)._1 - points(j)._1)
}
}
}

Interpolate polynomial from Frac(Z_{13}[a,b,c])[x]:

// coefficient ring Frac(Z/13[a,b,c])
val cfRing = Frac(MultivariateRingZp64(2, Array("a", "b", "c")))
val (a, b, c) = cfRing("a", "b", "c")

implicit val ring = UnivariateRing(cfRing, "x")
// interpolate with Lagrange formula
val data = Seq(a -> b, b -> c, c -> a)
val poly = interpolate(data)
assert(data.forall { case (p, v) => poly.eval(p) == v })

## Highlighted benchmarks

In the following plots performance of Rings is compared to Wolfram Mathematica 11. All tests were performed on MacBook Pro (15-inch, 2017), 3,1 GHz Intel Core i7, 16 GB 2133 MHz LPDDR3. The code of benchmarks can be found at GitHub. In all benchamrks random polynomials were used.

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

Univariate factorization performance on polynomials of the form (1 + \sum_{i = 1}^{i \leq deg} i \times x^i) in Z_{17}[x]. 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).

## Index of algorithms implemented in Rings

### Univariate polynomials

1. Karatsuba multiplication (Sec. 8.1 in [GaGe03])

used with some adaptations for multiplication of univariate polynomials:

2. Half-GCD and Extended Half-GCD (Sec. 11 in [GaGe03])

used (with adaptations inspired by [ShoNTL]) for univariate GCD:

3. Subresultant polynomial remainder sequences (Sec. 7.3 in [GeCL92]):

4. Modular GCD in Z[x] and Q[x] (Sec. 6.7 in [GaGe03], small primes version):

5. Fast univariate division with Newton iteration (Sec. 9.1 in [GaGe03])

used everywhere where multiple divisions (remainders) by the same divider are performed:

6. Univariate square-free factorization in zero characteristic (Yun's algorithm) (Sec. 14.6 in [GaGe03]):

7. Univariate square-free factorization in non-zero characteristic (Musser's algorithm) (Sec. 8.3 in [GeCL92], [Muss71]):

8. Distinct-degree factorization (Sec. 14.2 in [GaGe03])

plain version and adapted version with precomputed x-powers (used by default):

9. Shoup's baby-step giant-step algorithm for distinct-degree factorization ([Shou95])

used for factorization over fields with large cardinality:

10. Univariate modular composition

plain algorithm with Horner schema:

11. Brent-Kung univariate modular composition ([BreK98], [Shou95]):

12. Cantor-Zassenhaus algorithm (equal-degree splitting) (Sec. 14.3 in [GaGe03])

both for odd and even characteristic:

13. Univaraite linear p-adic Hensel lifting (Sec. 6.5 in [GeCL92]):

15. Univariate polynomial factorization over finite fields

uses Musser's square free factorization followed by distinct-degree factorization (either x-powers or Shoup's algorithm) followed by Cantor-Zassenhaus equal-degree factorization:

16. Univariate polynomial factorization over Z and Q

uses factorization modulo small prime followed by Hensel lifting (adaptive linear/quadratic) and naive recombination:

17. Univariate irreducibility test (Sec. 14.9 in [GaGe03]):

18. Ben-Or’s generation of irreducible polynomials (Sec. 14.9 in [GaGe03]):

19. Univariate polynomial interpolation

Lagrange and Newton methods:

### Multivariate polynomials

1. Brown GCD over finite fields ([Brow71], Sec. 7.4 in [GeCL92], [Yang09]):

2. Zippel's sparse GCD over finite fields ([Zipp79], [Zipp93], [dKMW05], [Yang09])

both for monic (with fast Vandermonde systems) and non-monic (LINZIP) cases:

3. Extended Zassenhaus GCD (EZ-GCD) over finite fields (Sec. 7.6 in [GeCL92], [MosY73]):

4. Enhanced Extended Zassenhaus GCD (EEZ-GCD) over finite fields ([Wang80]):

5. Modular GCD over Z with sparse interpolation ([Zipp79], [Zipp93], [dKMW05])

(the same interpolation techniques as in ZippelGCD is used):

6. Modular GCD over Z (small primes version):

7. Kaltofen's & Monagan's generic modular GCD with sparse interpolation ([KalM99])

used for computing multivariate GCD over finite fields of very small cardinality:

8. Kaltofen's & Monagan's generic modular GCD with EEZ-GCD for modular images ([KalM99])

used for computing multivariate GCD over finite fields of very small cardinality:

9. Multivariate square-free factorization in zero characteristic (Yun's algorithm) ([LeeM13]):

10. Multivariate square-free factorization in non-zero characteristic (Musser's algorithm) ([Muss71], Sec. 8.3 in [GeCL92]):

11. Bernardin's fast dense multivariate Hensel lifting ([Bern99], [LeeM13])

both for bivariate case (original Bernardin's paper) and multivariate case (Lee thesis) and both with and without precomputed leading coefficients:

12. Sparse Hensel lifting ([Kalt85], [LeeM13])

13. Fast dense bivariate factorization with recombination ([Bern99], [LeeM13]):

14. Kaltofen's multivariate factorization in finite fields ([Kalt85], [LeeM13])

modified version of original Kaltofen's algorithm for leading coefficient precomputation with square-free decomposition (instead of distinct variables decomposition) due to Lee is used; further adaptations are made to work in finite fields of very small cardinality; the resulting algorithm is close to [LeeM13], but at the same time has many differences in details:

15. Kaltofen's multivariate factorization Z ([Kalt85], [LeeM13])

(with the same modifications as for algorithm for finite fields):

16. Multivariate polynomial interpolation with Newton method:

17. Buchberger algorihm for Groebner basis ([Buch76], [BecW93], [CLOS97])

with Gebauer-Moller installation of Buchberger criteria ([GebM88], [BecW93]) and sugar strategy for lexicographic orders ([GMNR88]):

18. Faugere's F4 algorithm for Groebner basis ([Faug99])

with fast sparse linear algebra [FauL10] and simplification algoritm from [JouV11]:

19. Hilbert-Poincare series and Hilbert-driven methods for Groebner bases ([Trav96]):

20. Modular Groebner bases in Z ([Arno03]):

### References

• [GaGe03] J von zur Gathen and J Gerhard. Modern computer algebra (2 ed.). Cambridge University Press, 2003.
• [ShoNTL] V Shoup. NTL: A library for doing number theory. www.shoup.net/ntl
• [GeCL92] K O Geddes, S R Czapor, G Labahn. Algorithms for Computer Algebra. 1992.
• [Muss71] D R Musser. Algorithms for polynomial factorization, Ph.D. Thesis, University of Wisconsin, 1971.
• [Shou95] V Shoup. A new polynomial factorization algorithm and its implementation. J. Symb. Comput., 20(4):363–397, 1995.
• [BreK98] R P Brent and H T Kung. Fast algorithms for manipulating formal power series. J. Assoc. Comput. Math. 25:581-595, 1978
• [Brow71] W S Brown. On Euclid’s algorithm and the computation of polynomial greatest common divisors. J. ACM, 18(4):478–504, 1971.
• [Zipp79] R E Zippel. Probabilistic algorithms for sparse polynomials. In Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, EUROSAM ’79, pages 216–226, London, UK, UK, 1979. ringer-Verlag.
• [Zipp93] R E Zippel. Effective Polynomial Computation. Kluwer International Series in Engineering and Computer Science. Kluwer Academic Publishers, 1993.
• [dKMW05] J de Kleine, M B Monagan, A D Wittkopf. Algorithms for the Non-monic Case of the Sparse Modular GCD Algorithm. Proceeding of ISSAC ’05, ACM Press, pp. 124-131 , 2005.
• [Yang09] S Yang. Computing the greatest common divisor of multivariate polynomials over finite fields. Master’s thesis, Simon Fraser University, 2009.
• [MosY73] J Moses and D Y Y Yun, "The EZGCD Algorithm," pp. 159-166 in Proc. ACM Annual Conference, (1973).
• [Wang80] P S Wang, "The EEZ-GCD Algorithm," ACM SIGSAMBull., 14 pp. 50-60 (1980).
• [KalM99] E Kaltofen, M. B. Monagan. On the Genericity of the Modular Polynomial GCD Algorithm. Proceeding of ISSAC ’99, ACM Press, 59-66, 1999.
• [Bern99] L Bernardin. Factorization of Multivariate Polynomials over Finite Fields. PhD thesis, ETH Zurich, 1999.
• [LeeM13] M M-D Lee, Factorization of multivariate polynomials, Ph.D. thesis, University of Kaiserslautern, 2013
• [Kalt85] E Kaltofen. Sparse Hensel lifting. In EUROCAL 85 European Conf. Comput. Algebra Proc. Vol. 2, pages 4–17, 1985.
• [Trav96] C Traverso, Hilbert Functions and the Buchberger Algorithm, J. Symbolic Comp., 22(4):355–376, 1996.
• [Faug99] J-C Faugere, A new efficient algorithm for computing Gröbner bases (F4), Journal of Pure and Applied Algebra. Elsevier Science. 139 (1): 61–88, 1999
• [FauL10] J-C Faugere, S Lachartre, Parallel Gaussian elimination for Gröbner bases computations in finite fields, PASCO (2010)
• [JouV11] A Joux, V Vitse, A Variant of the F4 Algorithm. In: Kiayias A. (eds) Topics in Cryptology – CT-RSA 2011. CT-RSA 2011. Lecture Notes in Computer Science, vol 6558. Springer, Berlin, Heidelberg
• [Buch76] B Buchberger, Theoretical Basis for the Reduction of Polynomials to Canonical Forms, ACM SIGSAM Bulletin. ACM. 10 (3): 19–29
• [GebM88] R Gebauer and H Moller, On an Installation of Buchberger’s Algorithm, Journal of Symbolic Computation, 6(2 and 3):275–286, October/December 1988
• [GMNR88] A Giovini, T Mora, G Niesi, L Robbiano and C Traverso, One sugar cube, please, or Selection strategies in the Buchberger Algorithm. In S. M. Watt, editor, Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation. ISSAC’ 91, ACM Press, 1991.
• [BecW93] T Becker and V Weispfenning, Groebner Bases, a Computationnal Approach to Commutative Algebra. Graduate Texts in Mathematics. Springer-Verlag, 1993.
• [CLOS97] D Cox, J Little and D O’Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Springer, 1997
• [Arno03] E Arnold, Modular algorithms for computing Gröbner bases, Journal of Symbolic Computation Vol. 35, Issue 4, April 2003, Pages 403-419