sumiya11 / groebner.jl Goto Github PK

View Code? Open in Web Editor NEW

55.0 2.0 13.0 148 MB

Groebner bases in (almost) pure Julia

Home Page: https://sumiya11.github.io/Groebner.jl/

License: GNU General Public License v2.0

Julia 91.58% JetBrains MPS 7.86% LLVM 0.56%

groebner-basis julia f4 grobner-basis symbolic-computation

groebner.jl's Introduction

Groebner.jl is a Julia package for computing Groebner bases over fields. Groebner.jl is distributed under GNU GPL v2.

For documentation please check out https://sumiya11.github.io/Groebner.jl. For a simple example, see below.

Installation

You can install Groebner.jl using the Julia package manager. From the Julia REPL, type

import Pkg; Pkg.add("Groebner")

After the installation, you can run the package tests with

import Pkg; Pkg.test("Groebner")

How to use Groebner.jl?

The main function provided by Groebner.jl is groebner. It works with polynomials from AbstractAlgebra.jl, DynamicPolynomials.jl, and Nemo.jl.

with AbstractAlgebra.jl

We create a ring of polynomials in 3 variables

using AbstractAlgebra

R, (x1, x2, x3) = QQ["x1", "x2", "x3"]

Then, we can define a simple polynomial system

system = [
  x1 + x2 + x3,
  x1*x2 + x1*x3 + x2*x3,
  x1*x2*x3 - 1
]

And compute the Groebner basis by passing the system to groebner

using Groebner

G = groebner(system)

# result
3-element Vector{AbstractAlgebra.Generic.MPoly{Rational{BigInt}}}:
 x1 + x2 + x3
 x2^2 + x2*x3 + x3^2
 x3^3 - 1

with DynamicPolynomials.jl

Similarly to AbstractAlgebra.jl, we create a system of polynomials and pass it to groebner

using DynamicPolynomials, Groebner

@polyvar x1 x2
system = [10*x1*x2^2 - 11*x1 + 10,
        10*x1^2*x2 - 11*x2 + 10]

G = groebner(system)

# result
3-element Vector{Polynomial{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, Graded{LexOrder}, Int64}}:
 10x2 - 10x1 - 11x2² + 11x1²
 110 - 121x2 - 100x2² + 100x1x2 + 110x2³
 10 - 11x1 + 10x1x2²

Contacts

This library is maintained by Alexander Demin ([email protected]).

Contributing

Contributions are very welcome, as are feature requests and suggestions. In particular additional examples and documentation improvements are encouraged. If you encounter any problems, please open an issue or contact a maintainer.

Acknowledgement

We would like to acknowledge the developers of the msolve library (https://msolve.lip6.fr/), as several components of Groebner.jl were adapted from msolve. In our F4 implementation, we adapt and adjust the code of monomial hashtable, critical pair handling and symbolic preprocessing, and linear algebra from msolve. The source code of msolve is available at https://github.com/algebraic-solving/msolve.

We thank Vladimir Kuznetsov for helpful discussions and providing the sources of his F4 implementation.

We are grateful to The Max Planck Institute for Informatics and The MAX team at l'X for providing computational resources.

Citing Groebner.jl

If you find Groebner.jl useful in your work, you can star this repository and cite this paper

@misc{demin2024groebnerjl,
      title={Groebner.jl: A package for Gr\"obner bases computations in Julia}, 
      author={Alexander Demin and Shashi Gowda},
      year={2024},
      eprint={2304.06935},
      archivePrefix={arXiv},
      primaryClass={cs.MS}
}

groebner.jl's People

Contributors

Stargazers

Watchers

Forkers

shashi yingboma aabouman iliailmer rexwzh jpcurbelo krastanov bradcarman rafaeldavidmohr dannyb2018 vvvvvickywei ooinaruhugh yuyichao

groebner.jl's Issues

Add randomized linear algebra option

FindInstance and boolean minimization

Hello, I've been using this package a lot recently and I love it.

I know fairly little about this subject, but I have a couple of applications that are really benefiting from the Symbolic polynomial improvements and I'm looking to help out.

The first application is balancing chemical reactions and the second is minimizing boolean expressions.

Lots of chemical reactions have an infinite number of possible stoichiometric coefficients that satisfy being balanced.
For example, the following equations represent the reaction OH- + H+ <-> H2O in mathematica. To the human eye, it's clear that the coefficients [1, 1, 1] are the "best". I'd like to try to write my own FindInstance, but having trouble finding resources on how this function is implemented. I'm wondering if you know.

eqs = {
    u[1] == u[3],
    u[1] + u[2] == 2*u[3],
    -u[1] + u[2] == 0
}
possible = FindInstance[eqs, {u[1], u[2], u[3]}, PositiveIntegers]
xs = Map[Last, First[possible]]
sol = xs / Min[xs] # {1,1,1}

My second question is more concrete. I stumbled on https://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm, which mentions that it is an analogous algorithm to Buchberger's for boolean expressions. I'm curious if your F4 implementation might be general enough that I don't have to reimplement Quine McCluskey, or what I'd need to do to make it work.

Thanks and feel free to close since this issue is pretty off topic to the core purpose of this package

Error with `hashnextindex(::UInt32, ::Int64, ::UInt32)`

Getting an error during a run of SIAN.jl, here is the full message:

ERROR: MethodError: no method matching hashnextindex(::UInt32, ::Int64, ::UInt32)
Closest candidates are:
  hashnextindex(::UInt32, ::UInt32, ::UInt32) at ~/.julia/packages/Groebner/XcPUi/src/f4/structs.jl:79
Stacktrace:
 [1] insert_plcms_in_basis_hash_table!(pairset::Groebner.Pairset, off::Int64, ht::Groebner.MonomialHashtable, update_ht::Groebner.MonomialHashtable, basis::Groebner.Basis{UInt64}, plcm::Vector{Int64}, ifirst::Int64, ilast::Int64)
   @ Groebner ~/.julia/packages/Groebner/XcPUi/src/f4/hash.jl:485
 [2] update_pairset!(pairset::Groebner.Pairset, basis::Groebner.Basis{UInt64}, ht::Groebner.MonomialHashtable, update_ht::Groebner.MonomialHashtable, idx::Int64, plcm::Vector{Int64})
   @ Groebner ~/.julia/packages/Groebner/XcPUi/src/f4/symbolic.jl:563
 [3] update!(pairset::Groebner.Pairset, basis::Groebner.Basis{UInt64}, ht::Groebner.MonomialHashtable, update_ht::Groebner.MonomialHashtable, plcm::Vector{Int64})
   @ Groebner ~/.julia/packages/Groebner/XcPUi/src/f4/symbolic.jl:697
 [4] f4!(ring::Groebner.PolyRing, basis::Groebner.Basis{UInt64}, ht::Groebner.MonomialHashtable, reduced::Bool, linalg::Symbol, rng::Random.MersenneTwister)
   @ Groebner ~/.julia/packages/Groebner/XcPUi/src/f4/f4.jl:634
 [5] groebner_ff(ring::Groebner.PolyRing, exps::Vector{Vector{Vector{UInt16}}}, coeffs::Vector{Vector{UInt64}}, reduced::Bool, meta::Groebner.GroebnerMetainfo{Random.MersenneTwister})
   @ Groebner ~/.julia/packages/Groebner/XcPUi/src/f4/groebner.jl:65
 [6] groebner(polynomials::Vector{Nemo.gfp_mpoly}; reduced::Bool, ordering::Symbol, certify::Bool, forsolve::Bool, linalg::Symbol, rng::Random.MersenneTwister, loglevel::Base.CoreLogging.LogLevel)
   @ Groebner ~/.julia/packages/Groebner/XcPUi/src/interface.jl:82
 [7] identifiability_ode(ode::ODE{fmpq_mpoly}, params_to_assess::Vector{fmpq_mpoly}; p::Float64, p_mod::Int64, nthrds::Int64, infolevel::Int64, weighted_ordering::Bool, local_only::Bool)
   @ SIAN ~/cuny/research/SIAN-Julia/SIAN/src/SIAN.jl:245
 [8] top-level scope
   @ REPL[9]:1

Here is the code to reproduce the error:

>using SIAN
>ode = @ODEmodel(
           s'(t) = mu - bi * s(t) * i(t) - bw * s(t) * w(t) - mu * s(t) + al * r(t),
           i'(t) = bw * s(t) * w(t) + bi * s(t) * i(t) - g * i(t) - mu * i(t),
           w'(t) = dz * (i(t) - w(t)),
           r'(t) = g * i(t) - mu * r(t) - al * r(t),
           y1(t) = k * i(t),
           y2(t) = i(t) + r(t) + s(t)
       )
>res = identifiability_ode(ode, get_parameters(ode); p=0.99, p_mod=2^29 - 3, weighted_ordering=true)

It seems that another version of hashnextindex(::UInt32, ::Int64, ::UInt32) is required?

Set up reverse CI

Run Symbolics.jl tests along with this package's CI, so that we don't accidentally break anything.

See how we do it in Symbolics.jl https://github.com/JuliaSymbolics/Symbolics.jl/blob/master/.github/workflows/Downstream.yml

Compute basis in parallel

Hello! I was wondering if Groebner.jl currently supports parallel computation for Groebner basis?

Not working for univariate AA polynomials

Add fglm step

Currently there is only a slow monomial conversion algorithm implemented. Would be nice to implement a better version

Reduce a Polynomial by a Groebner Basis

Hi, is there a way to reduce a polynomial by a Groebner basis?

Say, I have

using Groebner
@polyvar x y
basis = Groebner.groebner([x - y, x*y])
p = x^2

Now I want to check whether $p$ belongs to the ideal, and want to have something like Groebner.reduce(p, basis) == 0, is there any way to express this?

Bug in `groebner` in Z_2

using AbstractAlgebra, Groebner

R, (x,y,z) = GF(2)["x","y","z"]

groebner([x^2 + 1, x*y, y*z + 1])
3-element Vector{AbstractAlgebra.Generic.MPoly{AbstractAlgebra.GFElem{Int64}}}:
 y*z + 1
 x*y
 x^2 + 1

The actual basis is 1. The bug probably happens because of the randomized linear algebra.

TagBot trigger issue

This issue is used to trigger TagBot; feel free to unsubscribe.

If you haven't already, you should update your TagBot.yml to include issue comment triggers.
Please see this post on Discourse for instructions and more details.

If you'd like for me to do this for you, comment TagBot fix on this issue.
I'll open a PR within a few hours, please be patient!

Possible to make Groebner.jl support 32bit Julia?

I have an application where I'm restricted to 32bit. Developing a model in ModelingToolkit.jl, which depends on Symbolics.jl which depends on this package. I can disable SnoopPrecompile, but I do need to at least precompile the functions when I run PackageCompiler.jl, therefore use of Int64 needs to be somehow removed or conditional. Do you think this might be possible?

fix reducegb_f4 to work with noon systems

Does Groebner use checked arithmetic, or does it fail silently if a coefficient overflows?

I guess that overflow could happen during some calculation when using Groebner.jl with DynamicPolynomials over Int32 or Int64. Will Groebner safely error or fail silently in such a case?

Allow tracking several Statistics during the computation

Write simple docs page

Julia 1.6 support

Is there a good reason not to support Julia 1.6?

x-ref: SciML/Optimization.jl#274 (comment)

Issues with `normalform`

Hello!

I am trying to use your package for an algorithm I'm developing. Unfortunately, sometimes normalform does not return the correct result. Here is an example that occured while running my algorithm:

using AbstractAlgebra, Groebner
P, (u,v,w,x) = PolynomialRing(GF(1119649), ["u", "v", "w", "x"]);
F = [-64*u^3*v^4*w^4*x+48*u^2*v^5*w^3*x^2+48*u^2*v^3*w^5*x^2-8*u*v^6*w^2*x^3-32*u*v^4*w^4*x^3-8*u*v^2*w^6*x^3+4*v^5*w^3*x^4+4*v^3*w^5*x^4+48*u^2*v^5*w^3*x+48*u^2*v^3*w^5*x+16*u*v^6*w^2*x^2-128*u*v^4*w^4*x^2+16*u*v^2*w^6*x^2+12*v^5*w^3*x^3+12*v^3*w^5*x^3+160*u^4*v^3*w^3-96*u^3*v^4*w^2*x-96*u^3*v^2*w^4*x-36*u^2*v^5*w*x^2+48*u^2*v^3*w^3*x^2-36*u^2*v*w^5*x^2-8*u*v^6*w^2*x+8*u*v^6*x^3+16*u*v^4*w^4*x+36*u*v^4*w^2*x^3-8*u*v^2*w^6*x+36*u*v^2*w^4*x^3+8*u*w^6*x^3-4*v^5*w*x^4-16*v^3*w^3*x^4-4*v*w^5*x^4-192*u^3*v^4*w^2-192*u^3*v^2*w^4-36*u^2*v^5*w*x+456*u^2*v^3*w^3*x-36*u^2*v*w^5*x-24*u*v^6*x^2-24*u*w^6*x^2-16*v^5*w^3*x-4*v^5*w*x^3-16*v^3*w^5*x-16*v^3*w^3*x^3-4*v*w^5*x^3+108*u^3*v^4*x-24*u^3*v^2*w^2*x+108*u^3*w^4*x+72*u^2*v^5*w+48*u^2*v^3*w^3-72*u^2*v^3*w*x^2+72*u^2*v*w^5-72*u^2*v*w^3*x^2+24*u*v^6*x-120*u*v^4*w^2*x-12*u*v^4*x^3-120*u*v^2*w^4*x+24*u*w^6*x-12*u*w^4*x^3-4*v^5*w*x^2+80*v^3*w^3*x^2+12*v^3*w*x^4-4*v*w^5*x^2+12*v*w^3*x^4-144*u^2*v^3*w*x-144*u^2*v*w^3*x-8*u*v^6+72*u*v^4*w^2+96*u*v^4*x^2+72*u*v^2*w^4-8*u*w^6+96*u*w^4*x^2+36*v^5*w*x-72*v^3*w^3*x-12*v^3*w*x^3+36*v*w^5*x-12*v*w^3*x^3+72*u^2*v*w*x^2-84*u*v^4*x+168*u*v^2*w^2*x-12*u*v^2*x^3-84*u*w^4*x-12*u*w^2*x^3-24*v^5*w-48*v^3*w^3-24*v^3*w*x^2-24*v*w^5-24*v*w^3*x^2-8*v*w*x^4-24*u*v^2*x^2-24*u*w^2*x^2+48*v^3*w*x+48*v*w^3*x+24*v*w*x^3+8*u*x^3-24*v*w*x^2, -64*u^4*v^3*w^4*x+80*u^3*v^4*w^3*x^2+48*u^3*v^2*w^5*x^2-24*u^2*v^5*w^2*x^3-64*u^2*v^3*w^4*x^3-8*u^2*v*w^6*x^3+20*u*v^4*w^3*x^4+12*u*v^2*w^5*x^4-4*v^3*w^4*x^5+80*u^3*v^4*w^3*x+48*u^3*v^2*w^5*x+48*u^2*v^5*w^2*x^2-256*u^2*v^3*w^4*x^2+16*u^2*v*w^6*x^2+60*u*v^4*w^3*x^3+36*u*v^2*w^5*x^3-24*v^5*w^2*x^4+16*v^3*w^4*x^4-8*v*w^6*x^4+96*u^5*v^2*w^3-96*u^4*v^3*w^2*x-48*u^4*v*w^4*x-60*u^3*v^4*w*x^2+48*u^3*v^2*w^3*x^2-12*u^3*w^5*x^2-24*u^2*v^5*w^2*x+24*u^2*v^5*x^3+32*u^2*v^3*w^4*x+72*u^2*v^3*w^2*x^3-8*u^2*v*w^6*x+36*u^2*v*w^4*x^3-20*u*v^4*w*x^4-48*u*v^2*w^3*x^4-4*u*w^5*x^4+72*v^5*w^2*x^3-96*v^3*w^4*x^3+8*v^3*w^2*x^5+24*v*w^6*x^3+4*v*w^4*x^5-192*u^4*v^3*w^2-96*u^4*v*w^4-60*u^3*v^4*w*x+456*u^3*v^2*w^3*x-12*u^3*w^5*x-72*u^2*v^5*x^2-80*u*v^4*w^3*x-20*u*v^4*w*x^3-48*u*v^2*w^5*x-48*u*v^2*w^3*x^3-4*u*w^5*x^3-72*v^5*w^2*x^2+24*v^5*x^4+160*v^3*w^4*x^2-24*v*w^6*x^2+108*u^4*v^3*x-12*u^4*v*w^2*x+120*u^3*v^4*w+48*u^3*v^2*w^3-72*u^3*v^2*w*x^2+24*u^3*w^5-24*u^3*w^3*x^2+72*u^2*v^5*x-240*u^2*v^3*w^2*x-24*u^2*v^3*x^3-120*u^2*v*w^4*x-20*u*v^4*w*x^2+240*u*v^2*w^3*x^2+36*u*v^2*w*x^4-4*u*w^5*x^2+12*u*w^3*x^4+24*v^5*w^2*x-96*v^5*x^3+32*v^3*w^4*x+24*v^3*w^2*x^3-4*v^3*x^5+8*v*w^6*x+12*v*w^4*x^3-8*v*w^2*x^5-144*u^3*v^2*w*x-48*u^3*w^3*x-24*u^2*v^5+144*u^2*v^3*w^2+192*u^2*v^3*x^2+72*u^2*v*w^4+180*u*v^4*w*x-216*u*v^2*w^3*x-36*u*v^2*w*x^3+36*u*w^5*x-12*u*w^3*x^3+144*v^5*x^2-176*v^3*w^2*x^2-16*v^3*x^4-88*v*w^4*x^2+16*v*w^2*x^4+24*u^3*w*x^2-168*u^2*v^3*x+168*u^2*v*w^2*x-12*u^2*v*x^3-120*u*v^4*w-144*u*v^2*w^3-72*u*v^2*w*x^2-24*u*w^5-24*u*w^3*x^2-8*u*w*x^4-96*v^5*x+96*v^3*w^2*x+104*v^3*x^3+48*v*w^4*x-32*v*w^2*x^3+4*v*x^5-24*u^2*v*x^2+144*u*v^2*w*x+48*u*w^3*x+24*u*w*x^3+24*v^5+48*v^3*w^2-144*v^3*x^2+24*v*w^4+144*v*w^2*x^2-8*v*x^4-24*u*w*x^2+60*v^3*x-156*v*w^2*x-12*v*x^3+24*v*x^2, -64*u^4*v^4*w^3*x+48*u^3*v^5*w^2*x^2+80*u^3*v^3*w^4*x^2-8*u^2*v^6*w*x^3-64*u^2*v^4*w^3*x^3-24*u^2*v^2*w^5*x^3+12*u*v^5*w^2*x^4+20*u*v^3*w^4*x^4-4*v^4*w^3*x^5+48*u^3*v^5*w^2*x+80*u^3*v^3*w^4*x+16*u^2*v^6*w*x^2-256*u^2*v^4*w^3*x^2+48*u^2*v^2*w^5*x^2+36*u*v^5*w^2*x^3+60*u*v^3*w^4*x^3-8*v^6*w*x^4+16*v^4*w^3*x^4-24*v^2*w^5*x^4+96*u^5*v^3*w^2-48*u^4*v^4*w*x-96*u^4*v^2*w^3*x-12*u^3*v^5*x^2+48*u^3*v^3*w^2*x^2-60*u^3*v*w^4*x^2-8*u^2*v^6*w*x+32*u^2*v^4*w^3*x+36*u^2*v^4*w*x^3-24*u^2*v^2*w^5*x+72*u^2*v^2*w^3*x^3+24*u^2*w^5*x^3-4*u*v^5*x^4-48*u*v^3*w^2*x^4-20*u*v*w^4*x^4+24*v^6*w*x^3-96*v^4*w^3*x^3+4*v^4*w*x^5+72*v^2*w^5*x^3+8*v^2*w^3*x^5-96*u^4*v^4*w-192*u^4*v^2*w^3-12*u^3*v^5*x+456*u^3*v^3*w^2*x-60*u^3*v*w^4*x-72*u^2*w^5*x^2-48*u*v^5*w^2*x-4*u*v^5*x^3-80*u*v^3*w^4*x-48*u*v^3*w^2*x^3-20*u*v*w^4*x^3-24*v^6*w*x^2+160*v^4*w^3*x^2-72*v^2*w^5*x^2+24*w^5*x^4-12*u^4*v^2*w*x+108*u^4*w^3*x+24*u^3*v^5+48*u^3*v^3*w^2-24*u^3*v^3*x^2+120*u^3*v*w^4-72*u^3*v*w^2*x^2-120*u^2*v^4*w*x-240*u^2*v^2*w^3*x+72*u^2*w^5*x-24*u^2*w^3*x^3-4*u*v^5*x^2+240*u*v^3*w^2*x^2+12*u*v^3*x^4-20*u*v*w^4*x^2+36*u*v*w^2*x^4+8*v^6*w*x+32*v^4*w^3*x+12*v^4*w*x^3+24*v^2*w^5*x+24*v^2*w^3*x^3-8*v^2*w*x^5-96*w^5*x^3-4*w^3*x^5-48*u^3*v^3*x-144*u^3*v*w^2*x+72*u^2*v^4*w+144*u^2*v^2*w^3-24*u^2*w^5+192*u^2*w^3*x^2+36*u*v^5*x-216*u*v^3*w^2*x-12*u*v^3*x^3+180*u*v*w^4*x-36*u*v*w^2*x^3-88*v^4*w*x^2-176*v^2*w^3*x^2+16*v^2*w*x^4+144*w^5*x^2-16*w^3*x^4+24*u^3*v*x^2+168*u^2*v^2*w*x-168*u^2*w^3*x-12*u^2*w*x^3-24*u*v^5-144*u*v^3*w^2-24*u*v^3*x^2-120*u*v*w^4-72*u*v*w^2*x^2-8*u*v*x^4+48*v^4*w*x+96*v^2*w^3*x-32*v^2*w*x^3-96*w^5*x+104*w^3*x^3+4*w*x^5-24*u^2*w*x^2+48*u*v^3*x+144*u*v*w^2*x+24*u*v*x^3+24*v^4*w+48*v^2*w^3+144*v^2*w*x^2+24*w^5-144*w^3*x^2-8*w*x^4-24*u*v*x^2-156*v^2*w*x+60*w^3*x-12*w*x^3+24*w*x^2, -16*u^4*v^4*w^4+32*u^3*v^5*w^3*x+32*u^3*v^3*w^5*x-12*u^2*v^6*w^2*x^2-48*u^2*v^4*w^4*x^2-12*u^2*v^2*w^6*x^2+16*u*v^5*w^3*x^3+16*u*v^3*w^5*x^3-5*v^4*w^4*x^4+16*u^3*v^5*w^3+16*u^3*v^3*w^5+16*u^2*v^6*w^2*x-128*u^2*v^4*w^4*x+16*u^2*v^2*w^6*x+36*u*v^5*w^3*x^2+36*u*v^3*w^5*x^2-16*v^6*w^2*x^3+16*v^4*w^4*x^3-16*v^2*w^6*x^3-24*u^4*v^4*w^2-24*u^4*v^2*w^4-24*u^3*v^5*w*x+32*u^3*v^3*w^3*x-24*u^3*v*w^5*x-4*u^2*v^6*w^2+12*u^2*v^6*x^2+8*u^2*v^4*w^4+54*u^2*v^4*w^2*x^2-4*u^2*v^2*w^6+54*u^2*v^2*w^4*x^2+12*u^2*w^6*x^2-16*u*v^5*w*x^3-64*u*v^3*w^3*x^3-16*u*v*w^5*x^3+36*v^6*w^2*x^2-72*v^4*w^4*x^2+10*v^4*w^2*x^4+36*v^2*w^6*x^2+10*v^2*w^4*x^4-12*u^3*v^5*w+152*u^3*v^3*w^3-12*u^3*v*w^5-24*u^2*v^6*x-24*u^2*w^6*x-16*u*v^5*w^3-12*u*v^5*w*x^2-16*u*v^3*w^5-48*u*v^3*w^3*x^2-12*u*v*w^5*x^2-24*v^6*w^2*x+16*v^6*x^3+80*v^4*w^4*x-24*v^2*w^6*x+16*w^6*x^3+27*u^4*v^4-6*u^4*v^2*w^2+27*u^4*w^4-48*u^3*v^3*w*x-48*u^3*v*w^3*x+12*u^2*v^6-60*u^2*v^4*w^2-18*u^2*v^4*x^2-60*u^2*v^2*w^4+12*u^2*w^6-18*u^2*w^4*x^2-8*u*v^5*w*x+160*u*v^3*w^3*x+48*u*v^3*w*x^3-8*u*v*w^5*x+48*u*v*w^3*x^3+4*v^6*w^2-48*v^6*x^2+8*v^4*w^4+18*v^4*w^2*x^2-5*v^4*x^4+4*v^2*w^6+18*v^2*w^4*x^2-20*v^2*w^2*x^4-48*w^6*x^2-5*w^4*x^4-48*u^3*v^3*w-48*u^3*v*w^3+96*u^2*v^4*x+96*u^2*w^4*x+36*u*v^5*w-72*u*v^3*w^3-36*u*v^3*w*x^2+36*u*v*w^5-36*u*v*w^3*x^2+48*v^6*x-88*v^4*w^2*x-16*v^4*x^3-88*v^2*w^4*x+32*v^2*w^2*x^3+48*w^6*x-16*w^4*x^3+48*u^3*v*w*x-42*u^2*v^4+84*u^2*v^2*w^2-18*u^2*v^2*x^2-42*u^2*w^4-18*u^2*w^2*x^2-48*u*v^3*w*x-48*u*v*w^3*x-32*u*v*w*x^3-16*v^6+24*v^4*w^2+78*v^4*x^2+24*v^2*w^4-48*v^2*w^2*x^2+10*v^2*x^4-16*w^6+78*w^4*x^2+10*w^2*x^4-24*u^2*v^2*x-24*u^2*w^2*x+48*u*v^3*w+48*u*v*w^3+72*u*v*w*x^2-72*v^4*x+144*v^2*w^2*x-16*v^2*x^3-72*w^4*x-16*w^2*x^3+12*u^2*x^2-48*u*v*w*x+15*v^4-78*v^2*w^2-18*v^2*x^2+15*w^4-18*w^2*x^2-5*x^4+24*v^2*x+24*w^2*x+16*x^3-12*x^2];
ev = [u, v, w + 333, x + 1118655];
G = [f(ev...) for f in F];
pt_id = [w^17, w^16*x, w^15*x^2, w^14*x^3, w^13*x^4, w^12*x^5, w^11*x^6, w^10*x^7, w^9*x^8, w^8*x^9, w^7*x^10, w^6*x^11, w^5*x^12, w^4*x^13, w^3*x^14, w^2*x^15, w*x^16, x^17];
gb = groebner(vcat(G, pt_id), ordering = DegRevLex());
f = 450896*u^4*w^9 + 636965*u^4*w^8 + 60208*u^4*w^7*x + 993939*u^4*w^7 + 530964*u^4*w^6*x^2 + 493233*u^4*w^6*x + 872754*u^4*w^6 + 766552*u^4*w^5*x^3 + 377321*u^4*w^5*x^2 + 821387*u^4*w^5*x + 488787*u^4*w^5 + 271677*u^4*w^4*x^4 + 1041343*u^4*w^4*x^3 + 457868*u^4*w^4*x^2 + 587803*u^4*w^4*x + 246704*u^4*w^4 + 363860*u^4*w^3*x^5 + 768695*u^4*w^3*x^4 + 961329*u^4*w^3*x^3 + 275911*u^4*w^3*x^2 + 76885*u^4*w^3*x + 803216*u^4*w^3 + 295653*u^4*w^2*x^6 + 364160*u^4*w^2*x^5 + 928023*u^4*w^2*x^4 + 327855*u^4*w^2*x^3 + 1028044*u^4*w^2*x^2 + 972958*u^4*w^2*x + 186556*u^4*w^2 + 941103*u^4*w*x^7 + 454603*u^4*w*x^6 + 586672*u^4*w*x^5 + 916178*u^4*w*x^4 + 921312*u^4*w*x^3 + 229078*u^4*w*x^2 + 994137*u^4*w*x + 716941*u^4*w + 647653*u^4*x^8 + 994117*u^4*x^7 + 729898*u^4*x^6 + 606082*u^4*x^5 + 260511*u^4*x^4 + 1014894*u^4*x^3 + 855066*u^4*x^2 + 1054319*u^4*x + 912264*u^4 + u^3*v^3 + 872131*u^3*v*w^9 + 644202*u^3*v*w^8 + 533271*u^3*v*w^7*x + 196381*u^3*v*w^7 + 146105*u^3*v*w^6*x^2 + 268307*u^3*v*w^6*x + 648313*u^3*v*w^6 + 222866*u^3*v*w^5*x^3 + 319392*u^3*v*w^5*x^2 + 72327*u^3*v*w^5*x + 110934*u^3*v*w^5 + 525671*u^3*v*w^4*x^4 + 607065*u^3*v*w^4*x^3 + 693775*u^3*v*w^4*x^2 + 1052902*u^3*v*w^4*x + 309532*u^3*v*w^4 + 1097581*u^3*v*w^3*x^5 + 623304*u^3*v*w^3*x^4 + 682689*u^3*v*w^3*x^3 + 895620*u^3*v*w^3*x^2 + 316169*u^3*v*w^3*x + 1021065*u^3*v*w^3 + 865166*u^3*v*w^2*x^6 + 91162*u^3*v*w^2*x^5 + 534882*u^3*v*w^2*x^4 + 892859*u^3*v*w^2*x^3 + 548724*u^3*v*w^2*x^2 + 312870*u^3*v*w^2*x + 742475*u^3*v*w^2 + 941585*u^3*v*w*x^7 + 650007*u^3*v*w*x^6 + 233663*u^3*v*w*x^5 + 928909*u^3*v*w*x^4 + 908812*u^3*v*w*x^3 + 115723*u^3*v*w*x^2 + 784014*u^3*v*w*x + 1037529*u^3*v*w + 562819*u^3*v*x^8 + 955329*u^3*v*x^7 + 10525*u^3*v*x^6 + 320564*u^3*v*x^5 + 452211*u^3*v*x^4 + 406950*u^3*v*x^3 + 549226*u^3*v*x^2 + 487919*u^3*v*x + 800050*u^3*v + 798373*u^2*v^4*w^9 + 207426*u^2*v^4*w^8 + 369146*u^2*v^4*w^7*x + 970053*u^2*v^4*w^7 + 544658*u^2*v^4*w^6*x^2 + 915427*u^2*v^4*w^6*x + 2447*u^2*v^4*w^6 + 349526*u^2*v^4*w^5*x^3 + 481047*u^2*v^4*w^5*x^2 + 1007397*u^2*v^4*w^5*x + 692921*u^2*v^4*w^5 + 857534*u^2*v^4*w^4*x^4 + 697790*u^2*v^4*w^4*x^3 + 70343*u^2*v^4*w^4*x^2 + 397470*u^2*v^4*w^4*x + 291860*u^2*v^4*w^4 + 319387*u^2*v^4*w^3*x^5 + 58431*u^2*v^4*w^3*x^4 + 620445*u^2*v^4*w^3*x^3 + 534998*u^2*v^4*w^3*x^2 + 828052*u^2*v^4*w^3*x + 1102158*u^2*v^4*w^3 + 568111*u^2*v^4*w^2*x^6 + 949775*u^2*v^4*w^2*x^5 + 730558*u^2*v^4*w^2*x^4 + 506593*u^2*v^4*w^2*x^3 + 663404*u^2*v^4*w^2*x^2 + 776491*u^2*v^4*w^2*x + 501855*u^2*v^4*w^2 + 510377*u^2*v^4*w*x^7 + 538887*u^2*v^4*w*x^6 + 521745*u^2*v^4*w*x^5 + 1067839*u^2*v^4*w*x^4 + 713501*u^2*v^4*w*x^3 + 986658*u^2*v^4*w*x^2 + 41615*u^2*v^4*w*x + 742536*u^2*v^4*w + 804575*u^2*v^4*x^8 + 511254*u^2*v^4*x^7 + 572526*u^2*v^4*x^6 + 349196*u^2*v^4*x^5 + 539502*u^2*v^4*x^4 + 610782*u^2*v^4*x^3 + 895668*u^2*v^4*x^2 + 123901*u^2*v^4*x + 390617*u^2*v^4 + 1010072*u^2*v^2*w^9 + 665896*u^2*v^2*w^8 + 607276*u^2*v^2*w^7*x + 113601*u^2*v^2*w^7 + 1054302*u^2*v^2*w^6*x^2 + 552418*u^2*v^2*w^6*x + 477385*u^2*v^2*w^6 + 741063*u^2*v^2*w^5*x^3 + 83967*u^2*v^2*w^5*x^2 + 917037*u^2*v^2*w^5*x + 918867*u^2*v^2*w^5 + 1098773*u^2*v^2*w^4*x^4 + 118156*u^2*v^2*w^4*x^3 + 972673*u^2*v^2*w^4*x^2 + 1018123*u^2*v^2*w^4*x + 267696*u^2*v^2*w^4 + 1027031*u^2*v^2*w^3*x^5 + 231663*u^2*v^2*w^3*x^4 + 219066*u^2*v^2*w^3*x^3 + 965539*u^2*v^2*w^3*x^2 + 751754*u^2*v^2*w^3*x + 643911*u^2*v^2*w^3 + 144481*u^2*v^2*w^2*x^6 + 1056586*u^2*v^2*w^2*x^5 + 881203*u^2*v^2*w^2*x^4 + 520149*u^2*v^2*w^2*x^3 + 145005*u^2*v^2*w^2*x^2 + 442431*u^2*v^2*w^2*x + 704740*u^2*v^2*w^2 + 187349*u^2*v^2*w*x^7 + 823866*u^2*v^2*w*x^6 + 127598*u^2*v^2*w*x^5 + 511611*u^2*v^2*w*x^4 + 845840*u^2*v^2*w*x^3 + 596482*u^2*v^2*w*x^2 + 766177*u^2*v^2*w*x + 596534*u^2*v^2*w + 832012*u^2*v^2*x^8 + 612147*u^2*v^2*x^7 + 116521*u^2*v^2*x^6 + 35089*u^2*v^2*x^5 + 483204*u^2*v^2*x^4 + 367114*u^2*v^2*x^3 + 465787*u^2*v^2*x^2 + 1035957*u^2*v^2*x + 489348*u^2*v^2 + 1097754*u^2*w^9 + 632258*u^2*w^8 + 746186*u^2*w^7*x + 1026887*u^2*w^7 + 495432*u^2*w^6*x^2 + 96704*u^2*w^6*x + 491674*u^2*w^6 + 313457*u^2*w^5*x^3 + 99998*u^2*w^5*x^2 + 794456*u^2*w^5*x + 68194*u^2*w^5 + 888407*u^2*w^4*x^4 + 587090*u^2*w^4*x^3 + 330060*u^2*w^4*x^2 + 469616*u^2*w^4*x + 551528*u^2*w^4 + 593912*u^2*w^3*x^5 + 1080936*u^2*w^3*x^4 + 332576*u^2*w^3*x^3 + 118198*u^2*w^3*x^2 + 463415*u^2*w^3*x + 754468*u^2*w^3 + 128304*u^2*w^2*x^6 + 285491*u^2*w^2*x^5 + 302634*u^2*w^2*x^4 + 505845*u^2*w^2*x^3 + 1029298*u^2*w^2*x^2 + 1018344*u^2*w^2*x + 141860*u^2*w^2 + 901421*u^2*w*x^7 + 438943*u^2*w*x^6 + 483682*u^2*w*x^5 + 912585*u^2*w*x^4 + 775024*u^2*w*x^3 + 762939*u^2*w*x^2 + 1088518*u^2*w*x + 904056*u^2*w + 1042964*u^2*x^8 + 48350*u^2*x^7 + 733274*u^2*x^6 + 617313*u^2*x^5 + 233865*u^2*x^4 + 743843*u^2*x^3 + 278704*u^2*x^2 + 455020*u^2*x + 742391*u^2 + 634247*u*v^5*w^9 + 1057383*u*v^5*w^8 + 438681*u*v^5*w^7*x + 1054350*u*v^5*w^7 + 668076*u*v^5*w^6*x^2 + 412595*u*v^5*w^6*x + 738273*u*v^5*w^6 + 211885*u*v^5*w^5*x^3 + 426847*u*v^5*w^5*x^2 + 405343*u*v^5*w^5*x + 915442*u*v^5*w^5 + 347682*u*v^5*w^4*x^4 + 206812*u*v^5*w^4*x^3 + 497425*u*v^5*w^4*x^2 + 342165*u*v^5*w^4*x + 681437*u*v^5*w^4 + 175594*u*v^5*w^3*x^5 + 1069253*u*v^5*w^3*x^4 + 990474*u*v^5*w^3*x^3 + 66154*u*v^5*w^3*x^2 + 693247*u*v^5*w^3*x + 146719*u*v^5*w^3 + 147758*u*v^5*w^2*x^6 + 738899*u*v^5*w^2*x^5 + 516620*u*v^5*w^2*x^4 + 544702*u*v^5*w^2*x^3 + 1028*u*v^5*w^2*x^2 + 376575*u*v^5*w^2*x + 297083*u*v^5*w^2 + 228450*u*v^5*w*x^7 + 166520*u*v^5*w*x^6 + 1028591*u*v^5*w*x^5 + 149958*u*v^5*w*x^4 + 982133*u*v^5*w*x^3 + 1032861*u*v^5*w*x^2 + 567958*u*v^5*w*x + 596819*u*v^5*w + 145910*u*v^5*x^8 + 105331*u*v^5*x^7 + 897960*u*v^5*x^6 + 671019*u*v^5*x^5 + 426459*u*v^5*x^4 + 127597*u*v^5*x^3 + 365957*u*v^5*x^2 + 239778*u*v^5*x + 664286*u*v^5 + 993567*u*v^3*w^9 + 1065333*u*v^3*w^8 + 709981*u*v^3*w^7*x + 475681*u*v^3*w^7 + 1043424*u*v^3*w^6*x^2 + 1093258*u*v^3*w^6*x + 102276*u*v^3*w^6 + 520107*u*v^3*w^5*x^3 + 798456*u*v^3*w^5*x^2 + 859147*u*v^3*w^5*x + 410099*u*v^3*w^5 + 848679*u*v^3*w^4*x^4 + 1075750*u*v^3*w^4*x^3 + 356297*u*v^3*w^4*x^2 + 422403*u*v^3*w^4*x + 356269*u*v^3*w^4 + 1061535*u*v^3*w^3*x^5 + 845041*u*v^3*w^3*x^4 + 412989*u*v^3*w^3*x^3 + 108809*u*v^3*w^3*x^2 + 73538*u*v^3*w^3*x + 933682*u*v^3*w^3 + 466433*u*v^3*w^2*x^6 + 120262*u*v^3*w^2*x^5 + 964873*u*v^3*w^2*x^4 + 1043645*u*v^3*w^2*x^3 + 249582*u*v^3*w^2*x^2 + 929193*u*v^3*w^2*x + 646519*u*v^3*w^2 + 799456*u*v^3*w*x^7 + 38744*u*v^3*w*x^6 + 1022524*u*v^3*w*x^5 + 383242*u*v^3*w*x^4 + 261019*u*v^3*w*x^3 + 928114*u*v^3*w*x^2 + 732128*u*v^3*w*x + 422869*u*v^3*w + 658403*u*v^3*x^8 + 5082*u*v^3*x^7 + 561475*u*v^3*x^6 + 223882*u*v^3*x^5 + 90116*u*v^3*x^4 + 555824*u*v^3*x^3 + 38098*u*v^3*x^2 + 1680*u*v^3*x + 190421*u*v^3 + 420873*u*v*w^9 + 271476*u*v*w^8 + 1091728*u*v*w^7*x + 952769*u*v*w^7 + 1017307*u*v*w^6*x^2 + 569202*u*v*w^6*x + 415093*u*v*w^6 + 199217*u*v*w^5*x^3 + 687570*u*v*w^5*x^2 + 259129*u*v*w^5*x + 440236*u*v*w^5 + 902141*u*v*w^4*x^4 + 701201*u*v*w^4*x^3 + 996894*u*v*w^4*x^2 + 546679*u*v*w^4*x + 862454*u*v*w^4 + 900411*u*v*w^3*x^5 + 127201*u*v*w^3*x^4 + 187473*u*v*w^3*x^3 + 19905*u*v*w^3*x^2 + 739988*u*v*w^3*x + 435433*u*v*w^3 + 392234*u*v*w^2*x^6 + 554875*u*v*w^2*x^5 + 661956*u*v*w^2*x^4 + 676989*u*v*w^2*x^3 + 174652*u*v*w^2*x^2 + 156986*u*v*w^2*x + 714896*u*v*w^2 + 994660*u*v*w*x^7 + 11077*u*v*w*x^6 + 660536*u*v*w*x^5 + 927642*u*v*w*x^4 + 572364*u*v*w*x^3 + 257978*u*v*w*x^2 + 975856*u*v*w*x + 446597*u*v*w + 948479*u*v*x^8 + 692824*u*v*x^7 + 927821*u*v*x^6 + 591599*u*v*x^5 + 46837*u*v*x^4 + 268906*u*v*x^3 + 198983*u*v*x^2 + 510264*u*v*x + 117541*u*v + 37582*v^6*w^9 + 608086*v^6*w^8 + 496208*v^6*w^7*x + 985684*v^6*w^7 + 697752*v^6*w^6*x^2 + 1100139*v^6*w^6*x + 851254*v^6*w^6 + 288384*v^6*w^5*x^3 + 367811*v^6*w^5*x^2 + 1026567*v^6*w^5*x + 979864*v^6*w^5 + 464539*v^6*w^4*x^4 + 59761*v^6*w^4*x^3 + 633544*v^6*w^4*x^2 + 421399*v^6*w^4*x + 75305*v^6*w^4 + 179051*v^6*w^3*x^5 + 11218*v^6*w^3*x^4 + 1023136*v^6*w^3*x^3 + 661803*v^6*w^3*x^2 + 33900*v^6*w^3*x + 867528*v^6*w^3 + 987542*v^6*w^2*x^6 + 38033*v^6*w^2*x^5 + 751434*v^6*w^2*x^4 + 252849*v^6*w^2*x^3 + 866210*v^6*w^2*x^2 + 660196*v^6*w^2*x + 297242*v^6*w^2 + 939360*v^6*w*x^7 + 663010*v^6*w*x^6 + 630286*v^6*w*x^5 + 851423*v^6*w*x^4 + 710055*v^6*w*x^3 + 437568*v^6*w*x^2 + 178873*v^6*w*x + 10833*v^6*w + 682904*v^6*x^8 + 220908*v^6*x^7 + 112724*v^6*x^6 + 503681*v^6*x^5 + 1118765*v^6*x^4 + 199657*v^6*x^3 + 625650*v^6*x^2 + 892702*v^6*x + 626632*v^6 + 102218*v^4*w^9 + 926585*v^4*w^8 + 260833*v^4*w^7*x + 742119*v^4*w^7 + 577263*v^4*w^6*x^2 + 868681*v^4*w^6*x + 336657*v^4*w^6 + 828423*v^4*w^5*x^3 + 77335*v^4*w^5*x^2 + 64088*v^4*w^5*x + 637864*v^4*w^5 + 1014105*v^4*w^4*x^4 + 1106725*v^4*w^4*x^3 + 15029*v^4*w^4*x^2 + 239673*v^4*w^4*x + 1091827*v^4*w^4 + 88488*v^4*w^3*x^5 + 70256*v^4*w^3*x^4 + 681765*v^4*w^3*x^3 + 354330*v^4*w^3*x^2 + 281687*v^4*w^3*x + 315060*v^4*w^3 + 343289*v^4*w^2*x^6 + 242696*v^4*w^2*x^5 + 591769*v^4*w^2*x^4 + 259332*v^4*w^2*x^3 + 704558*v^4*w^2*x^2 + 204360*v^4*w^2*x + 988455*v^4*w^2 + 983220*v^4*w*x^7 + 1107320*v^4*w*x^6 + 861576*v^4*w*x^5 + 596047*v^4*w*x^4 + 357001*v^4*w*x^3 + 790158*v^4*w*x^2 + 854996*v^4*w*x + 426694*v^4*w + 482996*v^4*x^8 + 1040334*v^4*x^7 + 1024600*v^4*x^6 + 747399*v^4*x^5 + 137975*v^4*x^4 + 844424*v^4*x^3 + 303080*v^4*x^2 + 1031883*v^4*x + 90990*v^4 + 101945*v^2*w^9 + 339618*v^2*w^8 + 59364*v^2*w^7*x + 958126*v^2*w^7 + 194473*v^2*w^6*x^2 + 524987*v^2*w^6*x + 532897*v^2*w^6 + 647305*v^2*w^5*x^3 + 1098487*v^2*w^5*x^2 + 1087315*v^2*w^5*x + 838029*v^2*w^5 + 81201*v^2*w^4*x^4 + 814253*v^2*w^4*x^3 + 29075*v^2*w^4*x^2 + 929653*v^2*w^4*x + 246498*v^2*w^4 + 990573*v^2*w^3*x^5 + 941426*v^2*w^3*x^4 + 541231*v^2*w^3*x^3 + 16698*v^2*w^3*x^2 + 840080*v^2*w^3*x + 613546*v^2*w^3 + 1100949*v^2*w^2*x^6 + 317093*v^2*w^2*x^5 + 45974*v^2*w^2*x^4 + 863165*v^2*w^2*x^3 + 1018537*v^2*w^2*x^2 + 817245*v^2*w^2*x + 19148*v^2*w^2 + 428001*v^2*w*x^7 + 171184*v^2*w*x^6 + 853675*v^2*w*x^5 + 203650*v^2*w*x^4 + 925425*v^2*w*x^3 + 891338*v^2*w*x^2 + 271147*v^2*w*x + 397568*v^2*w + 206806*v^2*x^8 + 323834*v^2*x^7 + 677335*v^2*x^6 + 568191*v^2*x^5 + 276736*v^2*x^4 + 676785*v^2*x^3 + 431725*v^2*x^2 + 618592*v^2*x + 296597*v^2 + 381318*w^9 + 732950*w^8 + 611890*w^7*x + 655965*w^7 + 174770*w^6*x^2 + 793446*w^6*x + 905912*w^6 + 815049*w^5*x^3 + 303904*w^5*x^2 + 315804*w^5*x + 195907*w^5 + 782803*w^4*x^4 + 1079077*w^4*x^3 + 501854*w^4*x^2 + 636148*w^4*x + 502259*w^4 + 1096652*w^3*x^5 + 374954*w^3*x^4 + 416901*w^3*x^3 + 772346*w^3*x^2 + 528848*w^3*x + 1015535*w^3 + 348425*w^2*x^6 + 962428*w^2*x^5 + 1014098*w^2*x^4 + 335832*w^2*x^3 + 557274*w^2*x^2 + 392298*w^2*x + 119512*w^2 + 586159*w*x^7 + 896067*w*x^6 + 908156*w*x^5 + 1060675*w*x^4 + 624956*w*x^3 + 1033800*w*x^2 + 452973*w*x + 6942*w + 708082*x^8 + 1109250*x^7 + 692713*x^6 + 275097*x^5 + 270775*x^4 + 798716*x^3 + 352318*x^2 + 724186*x + 516013;
f_nf = normalform(gb, f, ordering = DegRevLex());
iszero(normalform(gb, f - f_nf, ordering = DegRevLex()) # returns false on my machine

For context, I am using Groebner.jl at commit 4845931 and AbstractAlgebra at version 0.31.1.

If the above example is too large to do debugging with, then I can try to find a smaller non-working example.

EDIT: I checked, using msolve, that groebner computes a correct Gröbner basis for this example, so this part should be fine.

make struct Hashvalue immutable

Issues with Computing Groebner Basis for High-Order Runge Kutta Systems with 8 Stages and Order 7

I'm having trouble computing the Groebner basis for high-order Runge Kutta systems. Specifically, I'm working with a problem that has 8 stages and order 7, and the system of equations is given in this file. However, when I try to compute the Groebner basis for this problem, it seems to require more than 1Tb of RAM, which is causing issues.

For lower-order problems, it seems to work just fine. However, for the higher-order problem, I'm not sure if there's some workaround in the inputs that I might be missing, or if this behavior is to be expected for this type of problem. If anyone has any suggestions or insights into this issue, I would greatly appreciate it. Thank you!

bad selection strategy for lex ordering

Currently, the selection strategy for lexicographical ordering is neither normal nor sugar. That makes :lex computation nearly impossible on some examples

Computing bases up to some degree

As proposed in a private communication by X, it would be nice to have an option to compute bases up to some given total degree. For example,

groebner(polynomials, max_degree=42)

Huge amount of dynamic dispatch

julia> using JET, Groebner, AbstractAlgebra

julia> _, x = QQ["x"]
(Univariate polynomial ring in x over rationals, x)

julia> @report_opt groebner([x^3-x^2-1])

The @report_opt command prints so many entries that I can't even scroll up to the beginning. I'm guessing that improving the situation here would tremendously improve performance.

RecoverableException in Groebner\to18i\src\interface.jl:100

I get (Version julia-1.9.0-win64) the exception

┌ Warning: RecoverableException caught. Restarting with safe parameters..
└ @ Groebner xxx.julia\packages\Groebner\to18i\src\interface.jl:100

, if I run the following code :

using AbstractAlgebra

R, (z1, z2, z3, y1, y2, y3) = PolynomialRing(QQ, ["z1", "z2", "z3", "y1", "y2", "y3"])

polys = [z2^2 * z3 + z1 * z3^2 + z1 * z2    - 3 * z1^2 * z2 * z3,
         z2 * z3^2 + z1 * z3    + z1^2 * z2 - 3 * z1 * z2^2 * z3,
         z2 * z3    + z1^2 * z3 + z1 * z2^2 - 3 * z1 * z2 * z3^2,
         y1*z1 - 1, y2*z2 - 1, y3*z3 - 1]

using Groebner

basis = groebner(polys)

In Sympy I get the groebner basis without problems .

Fails to compute correct Gröbner basis on DynamicPolynomials variable with non-standard monomial ordering

I think the issue is best described by the following two examples:

When using variables with a designated monomial order, Gröbner basis computations seem to fail, sometimes (the failure isn't random, it is repeatable. But I don't see a pattern)

julia> using DynamicPolynomials
julia> using Groebner
julia> @polyvar x y z monomial_order=LexOrder
(x, y, z)
julia> isgroebner(groebner([1+z*x, 1+z*y^2]))
false
julia> isgroebner(groebner([1+z*x, 1+z*y^2], ordering=Lex()), ordering=Lex())
true
julia> isgroebner(groebner([1+z*x, 1+z*y^2], ordering=DegLex()), ordering=DegLex())
false

However, with standard monomial order, the problem disappears:

julia> using DynamicPolynomials
julia> using Groebner
julia> @polyvar x y z
(x, y, z)
julia> isgroebner(groebner([1+z*x, 1+z*y^2]))
true
julia> isgroebner(groebner([1+z*x, 1+z*y^2], ordering=Lex()), ordering=Lex())
true
julia> isgroebner(groebner([1+z*x, 1+z*y^2], ordering=DegLex()), ordering=DegLex())
true

The workaround, for now, is to use the default monomial order and specify the wanted order in each call to groebner.

I'm on julia 1.10.0 and using Grobner.jl v0.6.3 from the registry.

Bests, Andreas

Many invalidations

Currently on 1.10, I have

@time begin
           using AbstractAlgebra
           R, (x,y) = polynomial_ring(QQ, ["x","y"], ordering=:degrevlex)
           using Groebner
           groebner([x^2 - y^2, x*y^2 + x])
       end
 10.243601 seconds (4.98 M allocations: 336.788 MiB, 3.64% gc time, 73.70% compilation time)

Running this

# from https://sciml.ai/news/2022/09/21/compile_time/
using SnoopCompile

invalidations = @snoopr begin
    using AbstractAlgebra
    R, (x,y) = polynomial_ring(QQ, ["x","y"], ordering=:degrevlex)
    using Groebner
    groebner([x^2 - y^2, x*y^2 + x])
end

trees = SnoopCompile.invalidation_trees(invalidations);

@show length(SnoopCompile.uinvalidated(invalidations)) # show total invalidations

show(trees[end]) # show the most invalidated method

# Count number of children (number of invalidations per invalidated method)
n_invalidations = map(trees) do methinvs
    SnoopCompile.countchildren(methinvs)
end

Gives me

julia> n_invalidations[end]
625

julia> n_invalidations[end-1]
452

julia> n_invalidations[end-2]
333

julia> n_invalidations[end-3]
71

julia> trees[end]
inserting lock(io::AbstractAlgebra.PrettyPrinting.IOCustom) @ AbstractAlgebra.PrettyPrinting C:\Users\User\.julia\packages\AbstractAlgebra\TPsmz\src\PrettyPrinting.jl:1537 invalidated:
   backedges: 1: superseding lock(::IO) @ Base io.jl:26 with MethodInstance for lock(::IO) (621 children)
              2: superseding lock(::IO) @ Base io.jl:26 with MethodInstance for lock(::IO) (4 children)


julia> trees[end-1]
inserting ==(p::MultivariatePolynomials.AbstractPolynomialLike, α) @ MultivariatePolynomials C:\Users\User\.julia\packages\MultivariatePolynomials\TpRhf\src\operators.jl:65 invalidated:
   backedges: 1: superseding ==(x, y) @ Base Base.jl:165 with MethodInstance for ==(::Any, ::Cthulhu.DInfo.DebugInfo) (6 children)
              2: superseding ==(x, y) @ Base Base.jl:165 with MethodInstance for ==(::Any, ::Core.MethodInstance) (8 children)
              3: superseding ==(x, y) @ Base Base.jl:165 with MethodInstance for ==(::Any, ::Symbol) (420 children)
              4: superseding ==(x, y) @ Base Base.jl:165 with MethodInstance for ==(::Any, ::typeof(display)) (2 children)
              5: superseding ==(x, y) @ Base Base.jl:165 with MethodInstance for ==(::Any, ::Symbol) (1 children)
              6: superseding ==(x, y) @ Base Base.jl:165 with MethodInstance for ==(::Any, ::Symbol) (1 children)
              7: superseding ==(x, y) @ Base Base.jl:165 with MethodInstance for ==(::Any, ::typeof(display)) (1 children)
              8: superseding ==(x, y) @ Base Base.jl:165 with MethodInstance for ==(::Any, ::typeof(display)) (11 children)
              9: superseding ==(x, y) @ Base Base.jl:165 with MethodInstance for ==(::Any, ::Symbol) (2 children)


julia> trees[end-2]
inserting ==(α, q::MultivariatePolynomials.RationalPoly) @ MultivariatePolynomials C:\Users\User\.julia\packages\MultivariatePolynomials\TpRhf\src\comparison.jl:118 invalidated:
   backedges: 1: superseding ==(x, y) @ Base Base.jl:165 with MethodInstance for ==(::Core.MethodInstance, ::Any) (6 children)
              2: superseding ==(x, y) @ Base Base.jl:165 with MethodInstance for ==(::Module, ::Any) (11 children)
              3: superseding ==(x, y) @ Base Base.jl:165 with MethodInstance for ==(::Method, ::Any) (33 children)
              4: superseding ==(x, y) @ Base Base.jl:165 with MethodInstance for ==(::Core.TypeName, ::Any) (124 children)
              5: superseding ==(x, y) @ Base Base.jl:165 with MethodInstance for ==(::Symbol, ::Any) (154 children)
              6: superseding ==(x, y) @ Base Base.jl:165 with MethodInstance for ==(::Symbol, ::Any) (1 children)
              7: superseding ==(x, y) @ Base Base.jl:165 with MethodInstance for ==(::Symbol, ::Any) (4 children)


julia> trees[end-3]
inserting keys(ba::DataStructures.SortedDict) @ DataStructures C:\Users\User\.julia\packages\DataStructures\t9DKl\src\container_loops.jl:233 invalidated:
   backedges: 1: superseding keys(a::AbstractDict) @ Base abstractdict.jl:105 with MethodInstance for keys(::AbstractDict) (25 children)
              2: superseding keys(a::AbstractDict) @ Base abstractdict.jl:105 with MethodInstance for keys(::AbstractDict) (14 children)
              3: superseding keys(a::AbstractDict) @ Base abstractdict.jl:105 with MethodInstance for keys(::AbstractDict) (32 children)

Would be nice to fix the three most heavy sources of invalidation.

⌅ [c3fe647b] AbstractAlgebra v0.36.6
   [0b43b601] Groebner v0.7.0 `..\..\..\..\..\data\projects\gbgb\Groebner.jl`

Groebner Basis with parameters

Is there a way to specify what are variables vs constants using the Symbolics.jl interface? Basically I want to specify that certain variables should be ordered lexicographically after all others.

Mathematica is capable of doing something similar via:

polys = {-5*x^2 + y*z - x - 1, 2*x + 3*x*y + y^2, x - 3*y + x*z - 2*z^2};
GroebnerBasis[polys, ParameterVariables -> x]

This way the Groebner basis can be computed off line and used to solve a series of univariate polynomials online.

Test groebner for DynamicPolynomials better

speed up unsigned muladd

Integer Type Error

Hi thanks for writing such an awesome package. I wanted to let you know I think there is a small bug here:

Groebner.jl/src/f4/hash.jl

Line 499 in 8c2a490

i += 1

As i is of type UInt32 and hashnextindex only operates on types UInt32 I suspect this is a small typo. I'd be happy to submit a PR to correct it.

Thanks!

Calculate transformation matrix

Can we add an option for calculating the transformation matrix/change of basis matrix? That is, the matrix that maps the generators of the ideal to the Gröbner basis (see for example Oscar.jl or Macaualay2).

I don't know how much work this is, but it would be helpful for what I'm trying to do.

groebner does not return leading coefficient 1

Hi,

The groebner returns the unique Reduced Gröbner bases by default, for any ordering, correct? Then why does the example below NOT have leading coefficient 1 ? This is an example from the documentation. Thanks!

I'm using this version if that matters: [0b43b601] Groebner v0.6.4

using DynamicPolynomials

@polyvar x1 x2
system = [10*x1*x2^2 - 11*x1 + 10,
        10*x1^2*x2 - 11*x2 + 10]

groebner(system)

3-element Vector{DynamicPolynomials.Polynomial{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, MultivariatePolynomials.Graded{MultivariatePolynomials.LexOrder}, Int64}}:
 10x2 - 10x1 - 11x2² + 11x1²
 110 - 121x2 - 100x2² + 100x1x2 + 110x2³
 10 - 11x1 + 10x1x2²

Use f4 in `isgroebner`

exponent vector overflow, restarting

While trying to find a Groebner basis, a message like this is output:

Info: Possible overflow of exponent vector detected.
Restarting with at least 32 bits per exponent.

Does this mean that my computation is restarting completely, from scratch?

I don't know what is an exponent vector, but I wonder whether there's a way to increase the exponent size in advance, before starting the computation. Otherwise there's a lot of wasted computational effort, if the computation restarts multiple times each time I start the process.