Gröbner basis + elimination order = random errors

[wegank]

The following example

using AlgebraicSolving
using Nemo

R = @polynomial_ring(QQ, [:u1, :u2, :u3, :u4, :u5, :u6, :u7, :u8, :u9, :l1, :l2, :l3, :l4, :l5, :l6, :l7, :l8, :l9, :l10, :l11, :l12, :l13, :l14, :l15, :l16, :l17, :l18, :x1, :x2])

f = [
    -95 * u1 * x1 + 53 * u4 * x1 + 63 * u1 * x2 + 89 * u4 * x2 + u1,
    -95 * u2 * x1 + 53 * u5 * x1 + 63 * u2 * x2 + 89 * u5 * x2 + u2,
    -95 * u3 * x1 + 53 * u6 * x1 + 63 * u3 * x2 + 89 * u6 * x2 + u3,
    53 * u1 * x1 + 95 * u4 * x1 + 89 * u1 * x2 - 63 * u4 * x2 + u4,
    53 * u2 * x1 + 95 * u5 * x1 + 89 * u2 * x2 - 63 * u5 * x2 + u5,
    53 * u3 * x1 + 95 * u6 * x1 + 89 * u3 * x2 - 63 * u6 * x2 + u6,
    -95 * u7 * x1 + 63 * u7 * x2,
    -95 * u8 * x1 + 63 * u8 * x2,
    -95 * u9 * x1 + 63 * u9 * x2,
    -23 * u1 + 9 * u4 + 79 * u7 + 33,
    -23 * u2 + 9 * u5 + 79 * u8 - 22,
    -23 * u3 + 9 * u6 + 79 * u9 - 19,
    21 * u1 - 80 * u4 - 76 * u7 + 57,
    21 * u2 - 80 * u5 - 76 * u8 + 97,
    21 * u3 - 80 * u6 - 76 * u9 + 78,
    46 * u1 - 50 * u4 + 28 * u7 - 7,
    46 * u2 - 50 * u5 + 28 * u8 - 32,
    46 * u3 - 50 * u6 + 28 * u9 + 29,
    -95 * u1 * l1 + 53 * u4 * l1 - 95 * u2 * l2 + 53 * u5 * l2 - 95 * u3 * l3 + 53 * u6 * l3 + 53 * u1 * l4 + 95 * u4 * l4 + 53 * u2 * l5 + 95 * u5 * l5 + 53 * u3 * l6 + 95 * u6 * l6 - 95 * u7 * l7 - 95 * u8 * l8 - 95 * u9 * l9 - 1,
    63 * u1 * l1 + 89 * u4 * l1 + 63 * u2 * l2 + 89 * u5 * l2 + 63 * u3 * l3 + 89 * u6 * l3 + 89 * u1 * l4 - 63 * u4 * l4 + 89 * u2 * l5 - 63 * u5 * l5 + 89 * u3 * l6 - 63 * u6 * l6 + 63 * u7 * l7 + 63 * u8 * l8 + 63 * u9 * l9,
    -95 * l1 * x1 + 53 * l4 * x1 + 63 * l1 * x2 + 89 * l4 * x2 + l1 - 23 * l10 + 21 * l13 + 46 * l16,
    -95 * l2 * x1 + 53 * l5 * x1 + 63 * l2 * x2 + 89 * l5 * x2 + l2 - 23 * l11 + 21 * l14 + 46 * l17,
    -95 * l3 * x1 + 53 * l6 * x1 + 63 * l3 * x2 + 89 * l6 * x2 + l3 - 23 * l12 + 21 * l15 + 46 * l18,
    53 * l1 * x1 + 95 * l4 * x1 + 89 * l1 * x2 - 63 * l4 * x2 + l4 + 9 * l10 - 80 * l13 - 50 * l16,
    53 * l2 * x1 + 95 * l5 * x1 + 89 * l2 * x2 - 63 * l5 * x2 + l5 + 9 * l11 - 80 * l14 - 50 * l17,
    53 * l3 * x1 + 95 * l6 * x1 + 89 * l3 * x2 - 63 * l6 * x2 + l6 + 9 * l12 - 80 * l15 - 50 * l18,
    -95 * l7 * x1 + 63 * l7 * x2 + 79 * l10 - 76 * l13 + 28 * l16,
    -95 * l8 * x1 + 63 * l8 * x2 + 79 * l11 - 76 * l14 + 28 * l17,
    -95 * l9 * x1 + 63 * l9 * x2 + 79 * l12 - 76 * l15 + 28 * l18
]

gb = groebner_basis(AlgebraicSolving.Ideal(f), eliminate=27)
println(gb)

gives, instead of the basis [1], random errors (at least of 10 different types) on both Linux and macOS. The issue does not occur when calling the msolve binary.

Just to give an idea of the random nature of the errors: some of them come from export_groebner_qq (Linux);

$ julia src/julia/misc/bug.jl
free(): invalid pointer

[3044691] signal 6 (-6): Aborted
in expression starting at /home/weijia/phd/src/julia/misc/bug.jl:38
unknown function (ip: 0x7f75a440195c) at /lib/x86_64-linux-gnu/libc.so.6
gsignal at /lib/x86_64-linux-gnu/libc.so.6 (unknown line)
abort at /lib/x86_64-linux-gnu/libc.so.6 (unknown line)
unknown function (ip: 0x7f75a4396290) at /lib/x86_64-linux-gnu/libc.so.6
unknown function (ip: 0x7f75a440b464) at /lib/x86_64-linux-gnu/libc.so.6
__libc_free at /lib/x86_64-linux-gnu/libc.so.6 (unknown line)
full_free_hash_table at /workspace/srcdir/msolve/src/neogb/hash.c:297
gb_modpoly_clear at /workspace/srcdir/msolve/src/msolve/lifting-gb.c:517 [inlined]
export_groebner_qq at /workspace/srcdir/msolve/src/msolve/lifting-gb.c:1990
#_core_groebner_basis#6 at /home/weijia/.julia/packages/AlgebraicSolving/yFDlp/src/algorithms/groebner-bases.jl:190
_core_groebner_basis at /home/weijia/.julia/packages/AlgebraicSolving/yFDlp/src/algorithms/groebner-bases.jl:137 [inlined]
#4 at /home/weijia/.julia/packages/AlgebraicSolving/yFDlp/src/algorithms/groebner-bases.jl:127 [inlined]
get! at ./dict.jl:458
#groebner_basis#2 at /home/weijia/.julia/packages/AlgebraicSolving/yFDlp/src/algorithms/groebner-bases.jl:126 [inlined]
groebner_basis at /home/weijia/.julia/packages/AlgebraicSolving/yFDlp/src/algorithms/groebner-bases.jl:113
unknown function (ip: 0x7f7582f0e876) at (unknown file)
jl_apply at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/julia.h:2391 [inlined]
do_call at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/interpreter.c:123
eval_value at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/interpreter.c:243
eval_stmt_value at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/interpreter.c:194 [inlined]
eval_body at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/interpreter.c:707
jl_interpret_toplevel_thunk at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/interpreter.c:898
jl_toplevel_eval_flex at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/toplevel.c:1035
jl_toplevel_eval_flex at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/toplevel.c:975
ijl_toplevel_eval at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/toplevel.c:1047
ijl_toplevel_eval_in at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/toplevel.c:1092
eval at ./boot.jl:489
include_string at ./loading.jl:2842
_include at ./loading.jl:2902
include at ./Base.jl:306
exec_options at ./client.jl:317
_start at ./client.jl:550
jfptr__start_31204.1 at /software/julia/1.12/lib/julia/sys.so (unknown line)
jl_apply at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/julia.h:2391 [inlined]
true_main at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/jlapi.c:971
jl_repl_entrypoint at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/jlapi.c:1139
main at julia (unknown line)
unknown function (ip: 0x7f75a4396ca7) at /lib/x86_64-linux-gnu/libc.so.6
__libc_start_main at /lib/x86_64-linux-gnu/libc.so.6 (unknown line)
unknown function (ip: 0x4010b8) at julia
Allocations: 2162774 (Pool: 2162719; Big: 55); GC: 3
Aborted

some of them come from free_f4_julia_result_data (Linux);

$ julia src/julia/misc/bug.jl
free(): invalid next size (fast)

[3044847] signal 6 (-6): Aborted
in expression starting at /home/weijia/phd/src/julia/misc/bug.jl:38
unknown function (ip: 0x7fb5e2fec95c) at /lib/x86_64-linux-gnu/libc.so.6
gsignal at /lib/x86_64-linux-gnu/libc.so.6 (unknown line)
abort at /lib/x86_64-linux-gnu/libc.so.6 (unknown line)
unknown function (ip: 0x7fb5e2f81290) at /lib/x86_64-linux-gnu/libc.so.6
unknown function (ip: 0x7fb5e2ff6464) at /lib/x86_64-linux-gnu/libc.so.6
unknown function (ip: 0x7fb5e2ff8796) at /lib/x86_64-linux-gnu/libc.so.6
__libc_free at /lib/x86_64-linux-gnu/libc.so.6 (unknown line)
ijl_gc_counted_free_with_size at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/gc-stock.c:3776
free_f4_julia_result_data at /workspace/srcdir/msolve/src/neogb/f4.c:91
#_core_groebner_basis#6 at /home/weijia/.julia/packages/AlgebraicSolving/yFDlp/src/algorithms/groebner-bases.jl:240
_core_groebner_basis at /home/weijia/.julia/packages/AlgebraicSolving/yFDlp/src/algorithms/groebner-bases.jl:137 [inlined]
#4 at /home/weijia/.julia/packages/AlgebraicSolving/yFDlp/src/algorithms/groebner-bases.jl:127 [inlined]
get! at ./dict.jl:458
#groebner_basis#2 at /home/weijia/.julia/packages/AlgebraicSolving/yFDlp/src/algorithms/groebner-bases.jl:126 [inlined]
groebner_basis at /home/weijia/.julia/packages/AlgebraicSolving/yFDlp/src/algorithms/groebner-bases.jl:113
unknown function (ip: 0x7fb5c5b10406) at (unknown file)
jl_apply at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/julia.h:2391 [inlined]
do_call at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/interpreter.c:123
eval_value at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/interpreter.c:243
eval_stmt_value at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/interpreter.c:194 [inlined]
eval_body at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/interpreter.c:707
jl_interpret_toplevel_thunk at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/interpreter.c:898
jl_toplevel_eval_flex at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/toplevel.c:1035
jl_toplevel_eval_flex at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/toplevel.c:975
ijl_toplevel_eval at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/toplevel.c:1047
ijl_toplevel_eval_in at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/toplevel.c:1092
eval at ./boot.jl:489
include_string at ./loading.jl:2842
_include at ./loading.jl:2902
include at ./Base.jl:306
exec_options at ./client.jl:317
_start at ./client.jl:550
jfptr__start_31204.1 at /software/julia/1.12/lib/julia/sys.so (unknown line)
jl_apply at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/julia.h:2391 [inlined]
true_main at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/jlapi.c:971
jl_repl_entrypoint at /cache/build/tester-amdci4-14/julialang/julia-release-1-dot-12/src/jlapi.c:1139
main at julia (unknown line)
unknown function (ip: 0x7fb5e2f81ca7) at /lib/x86_64-linux-gnu/libc.so.6
__libc_start_main at /lib/x86_64-linux-gnu/libc.so.6 (unknown line)
unknown function (ip: 0x4010b8) at julia
Allocations: 2162093 (Pool: 2162038; Big: 55); GC: 3
Aborted

and others come from nowhere (Linux / macOS):

$ julia src/julia/misc/bug.jl
free(): invalid next size (fast)

[3044901] signal 6 (-6): Aborted
in expression starting at /home/weijia/phd/src/julia/misc/bug.jl:38
unknown function (ip: 0x7f8bcb46495c) at /lib/x86_64-linux-gnu/libc.so.6
gsignal at /lib/x86_64-linux-gnu/libc.so.6 (unknown line)
abort at /lib/x86_64-linux-gnu/libc.so.6 (unknown line)
unknown function (ip: 0x7f8bcb3f9290) at /lib/x86_64-linux-gnu/libc.so.6
unknown function (ip: 0x7f8bcb46e464) at /lib/x86_64-linux-gnu/libc.so.6
unknown function (ip: 0x7f8bcb470796) at /lib/x86_64-linux-gnu/libc.so.6
__libc_free at /lib/x86_64-linux-gnu/libc.so.6 (unknown line)
corrupted double-linked list
Aborted

$ julia src/julia/misc/bug.jl

[92143] signal 4 (1): Illegal instruction: 4
in expression starting at /Users/weijiawang/Projects/phd/src/julia/misc/bug.jl:39
_xzm_xzone_malloc_freelist_outlined at /usr/lib/system/libsystem_malloc.dylib (unknown line)
_Znwm at /usr/lib/libc++abi.dylib (unknown line)
^C
[92143] signal 2: Interrupt: 2
in expression starting at /Users/weijiawang/Projects/phd/src/julia/misc/bug.jl:39
__psynch_cvwait at /usr/lib/system/libsystem_kernel.dylib (unknown line)
unknown function (ip: 0x0) at (unknown file)
_xzm_xzone_malloc_freelist_outlined at /usr/lib/system/libsystem_malloc.dylib (unknown line)
_CFRuntimeCreateInstance at /System/Library/Frameworks/CoreFoundation.framework/Versions/A/CoreFoundation (unknown line)
__CFStringCreateImmutableFunnel3 at /System/Library/Frameworks/CoreFoundation.framework/Versions/A/CoreFoundation (unknown line)
CreateStringFromFileSystemRepresentationByAddingPercentEscapes at /System/Library/Frameworks/CoreFoundation.framework/Versions/A/CoreFoundation (unknown line)
_CFURLCreateWithFileSystemRepresentation at /System/Library/Frameworks/CoreFoundation.framework/Versions/A/CoreFoundation (unknown line)

[ederc]

We will prepare a new release of msolve which should fix this issue (and #114).