Rings
Rings: efficient JVM library for polynomial rings
Install / Use
/learn @PoslavskySV/RingsREADME
Rings: efficient Java/Scala library for polynomial rings
Rings is an efficient lightweight library for commutative algebra. Polynomial arithmetic, GCDs, polynomial factorization and Groebner bases are implemented with the use of modern asymptotically fast algorithms. Rings can be easily interacted or embedded in applications via simple API with fully typed hierarchy of algebraic structures and algorithms for commutative algebra. As well, an interactive REPL is also provided. The use of Scala language brings a quite novel powerful strongly typed functional programming model allowing to write short, expressive and fast code for applications. At the same time Rings shows one of the best or even unmatched in some cases performance among existing software for algebraic calculations.
The key features of Rings include:
- Rings → Integers, fractions, finite and algebraic fields, multiple field extensions, polynomial rings and more
- Polynomials → Efficient univariate and multivariate polynomials over arbitrary coefficient rings
- Polynomial GCD → Highly performant polynomial GCD over arbitrary coefficient domains
- Univariate and multivariate polynomial factorization → Highly performant polynomial factorization over almost arbitrary rings
- Ideals and Gröbner bases → Polynomial ideals and efficient algorithms for Gröbner bases
- Scala DSL → Powerful domain specific language in Scala
- Fast → Really fast library suitable for real-world computational challenges
The full documentation is available at http://rings.readthedocs.io.
A more academic description of the library can be found in:
Stanislav Poslavsky, Rings: An efficient Java/Scala library for polynomial rings, Computer Physics Communications, Volume 235, 2019, Pages 400-413, doi:10.1016/j.cpc.2018.09.005
(please, cite this paper if you use Rings)
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<i>.repl</i> with Homebrew:
$ brew install PoslavskySV/rings/rings.repl
or just by typing the following commands at the prompt:
$ sudo sh -c '(echo "#!/usr/bin/env sh" && curl -L https://github.com/lihaoyi/Ammonite/releases/download/1.1.2/2.12-1.1.2) > /usr/local/bin/amm && chmod +x /usr/local/bin/amm'
$ sudo sh -c 'curl -L -o /usr/local/bin/rings.repl https://git.io/vd7EY && chmod +x /usr/local/bin/rings.repl'
Now run Rings<i>.repl</i>:
$ rings.repl
Loading...
Rings 2.5.5: 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<i>.repl</i> can be used to run scripts with Rings code:
$ rings.repl myRingsScript.sc
Java/Scala library
Rings is currently available for Java and Scala. To get started with Scala SBT, simply add the following dependence to your build.sbt file:
libraryDependencies += "cc.redberry" %% "rings.scaladsl" % "2.5.5"
For using Rings solely in Java there is Maven artifact:
<dependency>
<groupId>cc.redberry</groupId>
<artifactId>rings</artifactId>
<version>2.5.5</version>
</dependency>
Development version
Download latest Rings from the develop:
git clone https://github.com/PoslavskySV/rings.git
cd rings
Install Java artifact locally:
cd rings
mvn install -DskipTests
Install Rings.scaladsl locally:
cd rings.scaladsl
sbt publishLocal
To run a simple REPL run e.g.:
cd rings.scaladsl
sbt console
@
import cc.redberry.rings
import cc.redberry.rings.primes.{SmallPrimes, BigPrimes}
import rings.{bigint, primes, linear, poly}
import poly.{univar, multivar}
import poly.PolynomialMethods._
import multivar.MonomialOrder._
import multivar.GroebnerMethods
import rings.scaladsl._
import util._
import syntax._
@ 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)
Examples: rings, ideals, Gröbner bases, GCDs & factorization
Below examples can be evaluated directly in the Rings<i>.repl</i>. If using Rings in Scala, the following preambula will import all required things from Rings library:
import cc.redberry.rings
import rings.poly.PolynomialMethods._
import rings.scaladsl._
import syntax._
Java examples can be found in the complete documentation pages.
Some built-in rings
Polynomial rings over Z and Q:
// Ring Z[x]
UnivariateRing(Z, "x")
// Ring Z[x, y, z]
MultivariateRing(Z, Array("x", "y", "z"))
// Ring Q[a, b, c]
MultivariateRing(Q, Array("a", "b", "c"))
Polynomial rings over Z_p:
// Ring Z/3[x]
UnivariateRingZp64(3, "x")
// Ring Z/3[x, y, z]
MultivariateRingZp64(3, Array("x", "y", "z"))
// Ring Z/p[x, y, z] with p = 2^107 - 1 (Mersenne prime)
MultivariateRing(Zp(Z(2).pow(107) - 1), Array("x", "y", "z"))
Galois fields:
// Galois field with cardinality 7^10
// (irreducible polynomial will be generated automatically)
GF(7, 10, "x")
// GF(7^3) generated by irreducible polynomial "1 + 3*z + z^2 + z^3"
GF(UnivariateRingZp64(7, "z")("1 + 3*z + z^2 + z^3"), "z")
Fields of rational functions:
// Field of fractions of univariate polynomials Z[x]
Frac(UnivariateRing(Z, "x"))
// Field of fractions of multivariate polynomials Z/19[x, y, z]
Frac(MultivariateRingZp64(19, Array("x", "y", "z")))
Univariate polynomials
Some algebra in Galois field GF(17,9):
// Galois field GF(17, 9) with irreducible
// poly in Z/17[t] generated automaticaly
implicit val ring = GF(17, 9, "t")
// pick some random field element
val a = ring.randomElement()
// raise field element to the power of 1000
val b = a.pow(1000)
// reciprocal of field element
val c = 1 / b
assert ( b * c === 1)
// explicitly parse field element from string:
// input poly will be automatically converted to
// element of GF(17, 9) (reduced modulo field generator)
val d = ring("1 + t + t^2 + t^3 + 15 * t^999")
// do some arbitrary math ops in the field
val some = a / (b + c) + a.pow(6) - a * b * c * d
Extended GCD in Z_{17}[x]:
// polynomial ring Z/17[x]
implicit val ring = UnivariateRingZp64(17, "x")
// parse ring element
val x = ring("x")
// construct some polynomials
val poly1 = 1 + x + x.pow(2) + x.pow(3)
val poly2 = 1 + 2 * x + 9 * x.pow(2)
// compute (gcd, s, t) such that s * poly1 + t * poly2 = gcd
val Array(gcd, s, t) = PolynomialExtendedGCD(poly1, poly2)
assert (s * poly1 + t * poly2 == gcd)
println((gcd, s, t))
Factor polynomial in Z_{17}[x]:
// polynomial ring Z/17[x]
implicit val ring = UnivariateRingZp64(17, "x")x
// parse polynomial from string
val poly = ring("4 + 8*x + 12*x^2 + 5*x^5 - x^6 + 10*x^7 + x^8")
// factorize poly
val factors = Factor(poly)
println(factors)
Coefficient rings with arbitrary large characteristic are available:
// coefficient ring Z/1237940039285380274899124357 (the next p
