groebner(polynomials; options...)

Computes a Groebner basis of the ideal generated by polynomials.

Arguments

• polynomials: an array of polynomials. Currently supports polynomials from AbstractAlgebra.jl, Nemo.jl, and DynamicPolynomials.jl. For AbstractAlgebra.jl and Nemo.jl, the coefficients of polynomials must be either in GF(p), in Native.GF(p), or in QQ.

Possible Options

The groebner routine takes the following optional arguments:

• reduced: If the returned basis must be autoreduced and unique (default is true).

• ordering: Specifies the monomial ordering. Available monomial orderings are:

  • InputOrdering() for inferring the ordering from the given polynomials (default),

  • Lex(args...) for lexicographic,

  • DegLex(args...) for degree lexicographic,

  • DegRevLex(args...) for degree reverse lexicographic,

  • WeightedOrdering(args...) for weighted ordering,

  • ProductOrdering(args...) for block ordering,

  • MatrixOrdering(args...) for matrix ordering. For details and examples see the corresponding documentation page.

• certify: Certify the obtained basis. When this option is false, the algorithm is randomized, and the result is correct with high probability. When this option is true, the result is guaranteed to be correct in case the ideal is homogeneous (default is false).

• linalg: Linear algebra backend. Available options are:

  • :auto for the automatic choice (default),

  • :deterministic for deterministic sparse linear algebra,

  • :randomized for probabilistic sparse linear algebra.

• threaded: The use of multi-threading. Available options are:

  • :auto for the automatic choice (default),

  • :no never use multi-threading,

  • :yes allow the use of multi-threading.

  Additionally, you can set the environment variable GROEBNER_NO_THREADED to 1 to disable all multi-threading in Groebner.jl. In this case, the environment variable takes precedence over the threaded option.

• monoms: Monomial representation used in the computations. The algorithm tries to automatically choose the most suitable monomial representation. Otherwise, set monoms to one of the following:

  • :auto for the automatic choice (default),

  • :dense for classic dense exponent vectors,

  • :packed for packed representation,

  • :sparse for sparse representation.

• modular: Modular computation algorithm. Only has effect when computing basis over the rational numbers. Possible options are:

  • :auto for the automatic choice (default),

  • :classic_modular for the classic multi-modular algorithm,

  • :learn_and_apply for the learn & apply algorithm.

• seed: The seed for randomization. Default value is 42. Groebner uses Random.Xoshiro and Random.MersenneTwister for random number generation.

• loglevel: Logging level, one of :all, :debug, :info, :warn, :no, or an integer. An integer 0 is equivalent to :info, and lower integer values mean more verbose. Default is :info.

• maxpairs: The maximum number of critical pairs used at once in matrix construction in the F4 algorithm. By default, this is not specified. Tweak this option to try to lower the amount of RAM consumed.

• homogenize: Controls the use of homogenization in the algorithm. Possible options are:

  • :yes, always homogenize the input ideal,

  • :no, never homogenize the input ideal,

  • :auto, for the automatic choice (default).

• statistics: After the function exits, print some runtime statistics. Possible options are:

  • :no, print nothing (default),

  • :timings, print the table with timings and allocations. Note that Groebner.performance_counters_enabled() must be set to true for this to have effect.

Example

Using DynamicPolynomials.jl:

using Groebner, DynamicPolynomials
@polyvar x y
groebner([x*y^2 + x, y*x^2 + y])

Using AbstractAlgebra.jl:

using Groebner, AbstractAlgebra
R, (x, y) = QQ["x", "y"]
groebner([x*y^2 + x, y*x^2 + y])

Using Nemo.jl:

using Groebner, Nemo
R, (x, y) = GF(2^30+3)["x", "y"]
groebner([x*y^2 + x, y*x^2 + y])

Or, say, in another monomial ordering:

# y > x
groebner([x*y^2 + x, y*x^2 + y], ordering=Lex(y, x))

# degree reverse lexicographic
groebner([x*y^2 + x, y*x^2 + y], ordering=DegRevLex())

Notes

The function groebner is thread-safe.

The default algorithm is probabilistic (with certify=false). Results are correct with high probability, however, no precise bound on the probability is known.

groebner_with_change_matrix(polynomials; options...)

Computes a Groebner basis of the ideal generated by polynomials and emits a change matrix, that is, a map from the original generators to basis elements.

Arguments

• polynomials: an array of polynomials. Currently supports polynomials from AbstractAlgebra.jl, Nemo.jl, and DynamicPolynomials.jl. For AbstractAlgebra.jl and Nemo.jl, the coefficients of polynomials must be either in GF(p), in Native.GF(p), or in QQ.

Possible Options

Same as for groebner.

Example

Using AbstractAlgebra.jl:

using Groebner, AbstractAlgebra
R, (x, y) = QQ["x", "y"]
f = [x*y^2 + x, y*x^2 + y]

g, m = groebner_with_change_matrix(f, ordering=DegRevLex())

@assert isgroebner(g, ordering=DegRevLex())
@assert m * f == g

Notes

Same as for groebner.

isgroebner(polynomials; options...)

Checks if polynomials forms a Groebner basis.

Arguments

• polynomials: an array of polynomials. Currently supports polynomials from AbstractAlgebra.jl, Nemo.jl, and DynamicPolynomials.jl. For AbstractAlgebra.jl and Nemo.jl, the coefficients of polynomials must be either in GF(p), in Native.GF(p), or in QQ.

Possible Options

The isgroebner routine takes the following optional arguments:

• ordering: Specifies the monomial ordering. Available monomial orderings are:

  • InputOrdering() for inferring the ordering from the given polynomials (default),

  • Lex() for lexicographic,

  • DegLex() for degree lexicographic,

  • DegRevLex() for degree reverse lexicographic,

  • WeightedOrdering(weights) for weighted ordering,

  • ProductOrdering(args...) for block ordering,

  • MatrixOrdering(matrix) for matrix ordering.

  For details and examples see the corresponding documentation page.

• certify: Use deterministic algorithm (default is false).

• seed: The seed for randomization. Default value is 42. Groebner uses Random.Xoshiro and Random.MersenneTwister for random number generation.

• loglevel: Logging level, one of :all, :debug, :info, :warn, :no, or an integer. An integer 0 is equivalent to :info, and lower integer values mean more verbose. Default is :info.

• statistics: After the function exits, print some runtime statistics. Possible options are:

  • :no, do not print anything (default),

  • :timings, print the table with timings and allocations. Note that Groebner.performance_counters_enabled() must be set to true for this to have effect.

Example

Using DynamicPolynomials:

using Groebner, DynamicPolynomials
@polyvar x y;
isgroebner([x*y^2 + x, y*x^2 + y])

Using AbstractAlgebra:

using Groebner, AbstractAlgebra
R, (x, y) = QQ["x", "y"]
isgroebner([x*y^2 + x, y*x^2 + y])

Notes

The function isgroebner is thread-safe.

normalform(basis, tobereduced; options...)

Computes the normal form of polynomials tobereduced with respect to basis.

Arguments

• basis: an array of polynomials, a Groebner basis.

• tobereduced: can be either a single polynomial or an array of polynomials.

Possible Options

The normalform routine takes the following optional arguments:

• check: Check if the given array basis forms a Groebner basis (default is false).

• ordering: Specifies the monomial ordering. Available monomial orderings are:

  • InputOrdering() for inferring the ordering from the given polynomials (default),

  • Lex() for lexicographic,

  • DegLex() for degree lexicographic,

  • DegRevLex() for degree reverse lexicographic,

  • WeightedOrdering(weights) for weighted ordering,

  • ProductOrdering(args...) for block ordering,

  • MatrixOrdering(matrix) for matrix ordering.

  For details and examples see the corresponding documentation page.

• loglevel: Logging level, one of :all, :debug, :info, :warn, :no, or an integer. An integer 0 is equivalent to :info, and lower integer values mean more verbose. Default is :info.

• statistics: After the function exits, print some runtime statistics. Possible options are:

  • :no, do not print anything (default),

  • :timings, print the table with timings and allocations. Note that Groebner.performance_counters_enabled() must be set to true for this to have effect.

Example

Reducing a single polynomial:

using Groebner, DynamicPolynomials
@polyvar x y;
normalform([y^2 + x, x^2 + y], x^2 + y^2 + 1)

Or, reducing two polynomials at a time:

using Groebner, DynamicPolynomials
@polyvar x y;
normalform([y^2 + x, x^2 + y], [x^2 + y^2 + 1, x^10*y^10])

Notes

The function normalform is thread-safe.

kbase(basis; options...)

Returns the standard basis of the quotient space of the ideal generated by basis.

Arguments

• basis: an array of polynomials, a Groebner basis.

Possible Options

The kbase routine takes the following optional arguments:

• check: Check if the given array basis forms a Groebner basis (default is false).

• loglevel: Logging level, one of :all, :debug, :info, :warn, :no, or an integer. An integer 0 is equivalent to :info, and lower integer values mean more verbose. Default is :info.

• statistics: After the function exits, print some runtime statistics. Possible options are:

  • :no, do not print anything (default),

  • :timings, print the table with timings and allocations. Note that Groebner.performance_counters_enabled() must be set to true for this to have effect.

Example

using Groebner, DynamicPolynomials
@polyvar x y;
kbase([y^2 + x, x^2 + y])

Notes

The function kbase is thread-safe.

Lex()
Lex(variables)
Lex(variables...)

Lexicographical monomial ordering.

We use the definition from Chapter 1, Computational Commutative Algebra 1, by Martin Kreuzer, Lorenzo Robbiano.

DOI: https://doi.org/10.1007/978-3-540-70628-1.

Dura Lex, sed Lex.

Possible Options

• compile: If true, compiles and uses a specialized monomial comparator function, which may speed up the runtime (default is false). This option is experimental.

Example

using Groebner, AbstractAlgebra
R, (x, y) = QQ["x", "y"];

# Lexicographical ordering with x > y
groebner([x*y + x, x + y^2], ordering=Lex())

# Lexicographical ordering with y > x
groebner([x*y + x, x + y^2], ordering=Lex([y, x]))

# Lexicographical ordering with x > y
# Note that both syntax -- Lex([...]) and Lex(...) -- are allowed
groebner([x*y + x, x + y^2], ordering=Lex(x, y))

DegLex()
DegLex(variables)
DegLex(variables...)

Degree lexicographical monomial ordering.

We use the definition from Chapter 1, Computational Commutative Algebra 1, by Martin Kreuzer, Lorenzo Robbiano.

DOI: https://doi.org/10.1007/978-3-540-70628-1.

Example

using Groebner, AbstractAlgebra
R, (x, y) = QQ["x", "y"];

# Degree lexicographical ordering with x > y
groebner([x*y + x, x + y^2], ordering=DegLex())

# Degree lexicographical ordering with y > x
groebner([x*y + x, x + y^2], ordering=DegLex([y, x]))

DegRevLex()
DegRevLex(variables)
DegRevLex(variables...)

Degree reverse lexicographical monomial ordering.

We use the definition from Chapter 1, Computational Commutative Algebra 1, by Martin Kreuzer, Lorenzo Robbiano.

DOI: https://doi.org/10.1007/978-3-540-70628-1.

Example

using Groebner, AbstractAlgebra
R, (x, y) = QQ["x", "y"];

# Degree reverse lexicographical ordering with x > y
groebner([x*y + x, x + y^2], ordering=DegRevLex())

# Degree reverse lexicographical ordering with y > x
groebner([x*y + x, x + y^2], ordering=DegRevLex(y, x))

InputOrdering()

Preserves the monomial ordering defined on the input polynomials.

This is the default value for the ordering keyword argument in the exported functions.

Example

using Groebner, AbstractAlgebra
R, (x, y) = QQ["x", "y"]

# Uses the ordering `InputOrdering`, which, in this case, 
# defaults to the lexicographical ordering with x > y
groebner([x*y + x, x + y^2])

WeightedOrdering(weights)

Weighted monomial ordering.

Only positive weights are supported.

Example

using Groebner, AbstractAlgebra
R, (x, y) = QQ["x", "y"];

# x has weight 3, y has weight 1
ord = WeightedOrdering([3, 1])
groebner([x*y + x, x + y^2], ordering=ord)

ProductOrdering(ord1, ord2)

Product monomial ordering. Compares monomials by ord1, then breaks ties by ord2.

Can also be constructed with *.

Example

using Groebner, AbstractAlgebra
R, (x, y, z, w) = QQ["x", "y", "z", "w"];

# Ordering with x, y > w, z
ord = ProductOrdering(DegRevLex(x, y), DegRevLex(w, z))
groebner([x*y + w, y*z - w], ordering=ord)

You can also use the * operator:

using Groebner, AbstractAlgebra
R, (x, y, z, t) = QQ["x", "y", "z", "t"];

ord1 = Lex(t)
ord2 = DegRevLex(x, y, z)
# t >> x, y, z
ord = ord1 * ord2
groebner([x*y*z + z, t * z - 1], ordering=ord)

MatrixOrdering(matrix)
MatrixOrdering(Vector{Vector})

Matrix monomial ordering.

Example

using Groebner, AbstractAlgebra
R, (x, y, z, w) = QQ["x", "y", "z", "w"];

# the number of columns equal to the number of variables
ord = MatrixOrdering([
    1 0  0  2;
    0 0  1  2;
    0 1  1  1;
])
groebner([x*y + w, y*z - w], ordering=ord)

groebner_learn(polynomials; options...)

Computes a Groebner basis of the ideal generated by polynomials and emits the trace.

The trace can be used to speed up the computation of other Groebner bases, which should be specializations of the same ideal as the one groebner_learn has been applied to.

See also groebner_apply!.

Arguments

• polynomials: an array of polynomials. Must be polynomials from AbstractAlgebra.jl over GF(p).

Example

Using groebner_learn and groebner_apply! over the same ground field:

using Groebner, AbstractAlgebra
R, (x, y) = GF(2^31-1)["x", "y"]

# Learn
trace, gb_1 = groebner_learn([x*y^2 + x, y*x^2 + y])

# Apply (same support, different coefficients)
flag, gb_2 = groebner_apply!(trace, [2x*y^2 + 3x, 4y*x^2 + 5y])

@assert flag

Using groebner_learn and groebner_apply! over different ground fields:

using Groebner, AbstractAlgebra
R, (x, y) = GF(2^31-1)["x", "y"]

# Learn
trace, gb_1 = groebner_learn([x*y^2 + x, y*x^2 + y], ordering=DegRevLex())

# Create a ring with a different modulo
R2, (x2, y2) = GF(2^30+3)["x", "y"]

# Apply (different modulo)
flag, gb_2 = groebner_apply!(
    trace, 
    [2x2*y2^2 + 3x2, 4y2*x2^2 + 5y2], 
    ordering=DegRevLex()
)

@assert flag
@assert gb_2 == groebner([2x2*y2^2 + 3x2, 4y2*x2^2 + 5y2], ordering=DegRevLex())

Using groebner_apply! in batches (works only in :degrevlex at the moment):

using Groebner, AbstractAlgebra
R, (x, y) = polynomial_ring(GF(2^31-1), ["x", "y"], internal_ordering=:degrevlex)

# Learn
trace, gb_1 = groebner_learn([x*y^2 + x, y*x^2 + y])

# Create rings with some other moduli
R2, (x2, y2) = polynomial_ring(GF(2^30+3), ["x", "y"], internal_ordering=:degrevlex)
R3, (x3, y3) = polynomial_ring(GF(2^27+29), ["x", "y"], internal_ordering=:degrevlex)

# Two specializations of the same ideal
batch = ([2x2*y2^2 + 3x2, 4y2*x2^2 + 5y2], [4x3*y3^2 + 4x3, 5y3*x3^2 + 7y3])

# Apply for two sets of polynomials at once
flag, (gb_2, gb_3) = groebner_apply!(trace, batch)

@assert flag
@assert (gb_2, gb_3) == map(groebner, batch)

Perhaps, in a more involved example, we will compute Groebner bases of the Katsura-9 system:

using Groebner, AbstractAlgebra, BenchmarkTools

# Create the system
kat = Groebner.katsuran(9, k=ZZ, internal_ordering=:degrevlex)

# Reduce the coefficients modulo 5 different primes
kat_0 = map(f -> map_coefficients(c -> GF(2^30 + 3)(c), f), kat)
kat_1 = map(f -> map_coefficients(c -> GF(2^30 + 7)(c), f), kat)
kat_2 = map(f -> map_coefficients(c -> GF(2^30 + 9)(c), f), kat)
kat_3 = map(f -> map_coefficients(c -> GF(2^30 + 15)(c), f), kat)
kat_4 = map(f -> map_coefficients(c -> GF(2^30 + 19)(c), f), kat)

# Learn the trace
trace, gb_0 = groebner_learn(kat_0);

# Compare the performance of applying with 1 input and with 4 different inputs:

# Apply for one system
@btime groebner_apply!($trace, $kat_1);
#  46.824 ms (19260 allocations: 24.48 MiB)

# Apply for a batch of four systems
@btime groebner_apply!($trace, $(kat_1, kat_2, kat_3, kat_4));
#  72.813 ms (23722 allocations: 59.44 MiB)

Observe the better amortized performance of the batched groebner_apply!.

Notes

The function groebner_learn is thread-safe.

groebner_apply!(trace, polynomials; options...)
groebner_apply!(trace, batch::NTuple{N, Vector}; options...)

Computes a Groebner basis of the ideal generated by polynomials following the given trace.

See also groebner_learn.

Arguments

• trace: a trace from groebner_learn.

• polynomials: an array of polynomials. Must be polynomials from AbstractAlgebra.jl over GF(p). It is possible to supply a tuple of N arrays to compute N Groebner bases simultaneously, which could be more efficient overall than computing them in separate.

Possible Options

The groebner_apply! routine automatically inherits most parameters from the given trace.

Example

For examples, see the documentation of groebner_learn.

Notes

This function is not thread-safe, since it mutates the trace.