- Notifications
You must be signed in to change notification settings - Fork10
Rings: efficient JVM library for polynomial rings
PoslavskySV/rings
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
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 athttp://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)
To taste what Rings can do, one can try interactive session withAmmonite 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 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.repl:
$ rings.replLoading...Rings2.5.5: efficientJava/Scala libraryfor polynomial rings@implicitvalring=MultivariateRing(Z,Array("x","y","z"))ring:MultivariateRing[IntZ]=MultivariateRing(Z,Array("x","y","z"),LEX)@valpoly1= 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*...@valpoly2= 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:
$ rings.repl myRingsScript.scRings is currently available for Java and Scala. To get started with Scala SBT, simply add the following dependence to yourbuild.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>
Download latest Rings from the develop:
git clone https://github.com/PoslavskySV/rings.gitcd ringsInstall Java artifact locally:
cd ringsmvn install -DskipTestsInstall Rings.scaladsl locally:
cd rings.scaladslsbt publishLocalTo run a simple REPL run e.g.:
cd rings.scaladslsbt console@importcc.redberry.ringsimportcc.redberry.rings.primes.{SmallPrimes,BigPrimes}importrings.{bigint,primes,linear,poly}importpoly.{univar,multivar}importpoly.PolynomialMethods._importmultivar.MonomialOrder._importmultivar.GroebnerMethodsimportrings.scaladsl._importutil._importsyntax._@implicitvalring=MultivariateRing(Z,Array("x","y","z"))ring:MultivariateRing[IntZ]=MultivariateRing(Z,Array("x","y","z"),LEX)@valpoly1= 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*...@valpoly2= 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)
Below examples can be evaluated directly in the Rings.repl. If using Rings in Scala, the following preambula will import all required things from Rings library:
importcc.redberry.ringsimportrings.poly.PolynomialMethods._importrings.scaladsl._importsyntax._
Java examples can be found in thecomplete documentation pages.
Polynomial rings overZ andQ:
// 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 overZ_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")))
Some algebra in Galois fieldGF(17,9):
// Galois field GF(17, 9) with irreducible// poly in Z/17[t] generated automaticalyimplicitvalring=GF(17,9,"t")// pick some random field elementvala= ring.randomElement()// raise field element to the power of 1000valb= a.pow(1000)// reciprocal of field elementvalc=1/ bassert ( 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)vald= ring("1 + t + t^2 + t^3 + 15 * t^999")// do some arbitrary math ops in the fieldvalsome= a/ (b+ c)+ a.pow(6)- a* b* c* d
Extended GCD inZ_{17}[x]:
// polynomial ring Z/17[x]implicitvalring=UnivariateRingZp64(17,"x")// parse ring elementvalx= ring("x")// construct some polynomialsvalpoly1=1+ x+ x.pow(2)+ x.pow(3)valpoly2=1+2* x+9* x.pow(2)// compute (gcd, s, t) such that s * poly1 + t * poly2 = gcdvalArray(gcd, s, t)=PolynomialExtendedGCD(poly1, poly2)assert (s* poly1+ t* poly2== gcd)println((gcd, s, t))
Factor polynomial inZ_{17}[x]:
// polynomial ring Z/17[x]implicitvalring=UnivariateRingZp64(17,"x")x// parse polynomial from stringvalpoly= ring("4 + 8*x + 12*x^2 + 5*x^5 - x^6 + 10*x^7 + x^8")// factorize polyvalfactors=Factor(poly)println(factors)
Coefficient rings with arbitrary large characteristic are available:
// coefficient ring Z/1237940039285380274899124357 (the next prime to 2^100)valmodulus=Z("1267650600228229401496703205653")valcfRing=Zp(modulus)// ring Z/1237940039285380274899124357[x]implicitvalring=UnivariateRing(cfRing,"x")valpoly= ring("4 + 8*x + 12*x^2 + 5*x^5 + 16*x^6 + 27*x^7 + 18*x^8")// factorize polyprintln(Factor(poly))
(large primes can be generated withBigPrimes.nextPrime method, seePrime numbers).
Ring of univariate polynomials over elements of Galois fieldGF(7,3)[x]:
// elements of coefficient field GF(7,3) are represented as polynomials// over "z" modulo irreducible polynomial "1 + 3*z + z^2 + z^3"valcfRing=GF(UnivariateRingZp64(7,"z")("1 + 3*z + z^2 + z^3"),"z")assert(cfRing.characteristic().intValue()==7)assert(cfRing.cardinality().intValue()==343)// polynomial ring GF(7^3)[x]implicitvalring=UnivariateRing(cfRing,"x")// parse poly in GF(7^3)[x] from string// coefficients of polynomials in GF(7,3)[x] are elements// of GF(7,3) that is polynomials over "z"valpoly= ring("1 - (1 - z^3) * x^6 + (1 - 2*z) * x^33 + x^66")// factorize polyvalfactors=Factor(poly)println(s"${ring show factors}")
Some math with multivariate polynomials fromZ[x, y, z]:
// ring Z[x, y, z]implicitvalring=MultivariateRing(Z,Array("x","y","z"))// parse some ring elementsval (x, y, z)= ring("x","y","z")// construct some polynomials using different math opsvala= (x+ y+ z).pow(2)-1valb= (x- y- z-1).pow(2)+ x+ y+ z-1valc= (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 inZ[a, b, c]:
// ring Z[a, b, c]implicitvalring=MultivariateRing(Z,Array("a","b","c"))// parse polynomials from stringsvalpoly1= ring("-b-b*c-b^2+a+a*c+a^2")valpoly2= ring("b^2+b^2*c+b^3+a*b^2+a^2+a^2*c+a^2*b+a^3")// compute multivariate GCDvalgcd=PolynomialGCD(poly1, poly2)assert (poly1% gcd===0)assert (poly2% gcd===0)println(gcd)
Factor polynomial inZ_{2}[x, y, z]:
// ring Z/2[x, y, z]implicitvalring=MultivariateRingZp64(2,Array("x","y","z"))val (x, y, z)= ring("x","y","z")// factorize polyvalfactors=Factor(1+ (1+ x+ y+ z).pow(2)+ (x+ y+ z).pow(4))println(factors)
Factor polynomial inZ[a, b, c]:
// ring Z[a, b, c]implicitvalring=MultivariateRing(Z,Array("a","b","c"))val (a, b, c)= ring("a","b","c")// factorize polyvalfactors=Factor(1- (1+ a+ b+ c).pow(2)- (2+ a+ b+ c).pow(3))println(ring show factors)
Factor polynomial inQ[x, y, z]:
// ring Q[x, y, z]implicitvalring=MultivariateRing(Q,Array("x","y","z"))// parse some poly from stringvalpoly= 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 polyvalfactors=Factor(poly)println(factors)
Ring of multivariate polynomials over elements of Galois fieldGF(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"valcfRing=GF(UnivariateRingZp64(7,"z")("1 + 3*z + z^2 + z^3"),"z")// ring GF(7,3)[a,b,c]implicitvalring=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"valpoly= ring("1 - (1 - z^3) * a^6*b + (1 - 2*z) * c^33 + a^66")//factorize polyprintln(Factor(poly))
Define a field of rational functionsFrac(Z[x,y,z]) and input some functions:
// Frac(Z[x,y,z])implicitvalfield=Frac(MultivariateRing(Z,Array("x","y","z")))// parse some math expression from string// it will be automatically reduced to a common denominator// with the gcd being automatically cancelledvalexpr1= field("(x/y/(x - z) + (x + z)/(y - z))^2 - 1")// do some math ops programmaticallyval (x, y, z)= field("x","y","z")valexpr2= expr1.pow(2)+ x/ y- z
Greatest common divisors of numerators and denominators are always cancelled automatically.
UseCoder to parse more complicated expressions:
// bind expr1 and expr2 to variables to use them further in parserfield.coder.bind("expr1", expr1)field.coder.bind("expr2", expr2)// parse some complicated expression from string// it will be automatically reduced to a common denominator// with the gcd being automatically cancelledvalexpr3= field(""" expr1 / expr2 - (x*y - z)/(x-y)/expr1 + x / expr2 - (x*z - y)/(x-y)/expr1/expr2 + x^2*y^2 - z^3 * (x - y)^2""")// export expression to stringprintln(field.stringify(expr3))// take numerator and denominatorvalnum= expr3.numerator()valden= expr3.denominator()// common GCD is always cancelled automaticallyassert( field.ring.gcd(num, den).isOne )
Compute unique factor decomposition of rational function:
// compute unique factor decomposition of expressionvalfactors= field.factor(expr3)println(field.stringify(factors))
Construct some ideal and check its properties:
// ring Z/17[x,y,z]implicitvalring=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 basisvalI=Ideal(ring,Seq(x.pow(2)+ y.pow(12)- z, x.pow(2)* z+ y.pow(2)-1),GREVLEX)// I is proper idealassert(I.isProper)// get computed Groebner basisvalgb=I.groebnerBasisprintln(gb)// check some ideal propertiesassert(I.dimension==1)assert(I.degree==36)
Unions, intersections and quotients of ideals:
// create another ideal with only one generatorvalJ=Ideal(ring,Seq(x.pow(4)* y.pow(4)+1),GREVLEX)// J is principal idealassert(J.isPrincipal)valunion=I unionJ// union is zero dimensional idealassert(union.dimension==0)valintersection=I intersectionJ// intersection is still 2-dimensionalassert(intersection.dimension==2)// yet another idealvalK=Ideal(ring,Seq(z* x.pow(4)- z* y.pow(14)+ y* z.pow(16), (x+ y+ z).pow(4)),GREVLEX)// compute complicated quotient idealvalquotient= (I*J*K):/ timesassert(quotient==K)
Construct lexicographic Gröbner basis to solve a system of equations:
// ring Q[a, b, c]implicitvalring=MultivariateRing(Q,Array("x","y","z"))// parse some polynomials from stringsvala= ring("8*x^2*y^2 + 5*x*y^3 + 3*x^3*z + x^2*y*z")valb= ring("x^5 + 2*y^3*z^2 + 13*y^2*z^3 + 5*y*z^4")valc= ring("8*x^3 + 12*y^3 + x*z^2 + 3")vald= ring("7*x^2*y^4 + 18*x*y^3*z^2 + y^3*z^3")// construct ideal with Groebner basis in LEX ordervalideal=Ideal(ring,Seq(a, b, c, d),LEX)// it is very simple: <z^2, x, 1+4*y^3>println(ideal)
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)*/defsolveDiophantine[E](fi:Seq[E])(implicitring:Ring[E])= fi.foldLeft((ring(0),Seq.empty[E])) {case ((gcd, seq), f)=>valxgcd= 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*/defapart[E](frac:Rational[E])= {implicitvalring:Ring[E]= frac.ringvalfactors= 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)valqFracs= apart(Q("1234213 / 2341352"))// partial fraction decomposition for rational functionsvalufRing=Frac(UnivariateRingZp64(17,"x"))// gives List(4/(16+x), 1/(10+x), 15/(1+x), (14*x)/(15+7*x+x^2))valpFracs= 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*/definterpolate[Poly<:IUnivariatePolynomial[Poly],Coef] (points:Seq[(Coef,Coef)]) (implicitring:IUnivariateRing[Poly,Coef])= {// implicit coefficient ring (setups algebraic operators on type Coef)implicitvalcfRing:Ring[Coef]= ring.cfRingif (!cfRing.isField)thrownewIllegalArgumentException 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 fromFrac(Z_{13}[a,b,c])[x]:
// coefficient ring Frac(Z/13[a,b,c])valcfRing=Frac(MultivariateRingZp64(2,Array("a","b","c")))val (a, b, c)= cfRing("a","b","c")implicitvalring=UnivariateRing(cfRing,"x")// interpolate with Lagrange formulavaldata=Seq(a-> b, b-> c, c-> a)valpoly= interpolate(data)assert(data.forall {case (p, v)=> poly.eval(p)== v })
Dependence of multivariate GCD performance on the number of variables. For details seebenchmarks
Dependence of multivariate GCD performance on the size of input polynomials. For details seebenchmarks
Dependence of multivariate factorization performance on the number of variables. For details seebenchmarks
Univariate factorization performance on polynomials of the form(1 + \sum_{i = 1}^{i \leq deg} i \times x^i) inZ_{17}[x].
The list of algorithms implemented in Rings (and references to the literature) can be found atRings RTD page
Apache License, Version 2.0http://www.apache.org/licenses/LICENSE-2.
About
Rings: efficient JVM library for polynomial rings