Reproducible CI failure on `choice-linear-form-qq`

[vneiger]

This appeared in a CI run, and I can reproduce it on my machine. Trying about 200 other seeds, I encountered no failures for those.

./msolve -f input_files/choice-linear-form-qq.ms -o test/diff/tmp42.res --random-seed 1772988447 -P 2 -d 0 -L 0 -l 44 -t 1

diff test/diff/tmp42.res output_files/choice-linear-form-qq.P2.d0.res
1c1,26
< [1, 9, -1, []]:
---
> [0, [0,
> 9,
> 3,
> ['_xx[1]', '_xx[2]', '_xx[3]', '_xx[4]', '_xx[5]', '_xx[6]', '_xx[7]', '_xx[8]', 'A'],
> [1,4,9,16,25,36,49,64,1],
> [1,
> [[2, [0, 37, 1]],
> [1, [37, 2]],
> [
> [[1, [0, 1]],
> 1],
> [[1, [0, 1]],
> 1],
> [[1, [0, 0]],
> 1],
> [[1, [0, 1]],
> 1],
> [[1, [0, 1]],
> 1],
> [[1, [0, -1]],
> 1],
> [[1, [0, 1]],
> 1],
> [[1, [0, -3]],
> 2]
> ]]]]]:

[dimpase]

this must be platform-specific; e.g. on x86_64 macOS without OpenMP the diff does not output anything

[vneiger]

this must be platform-specific; e.g. on x86_64 macOS without OpenMP the diff does not output anything

Thanks for the insight. In the CI case or in my case this was on x86_64 ubuntu 24.04.

[ederc]

Running this specific installment of the example there is a int32_t overflow when generating the random linear form, in particular in line 716 of msolve.c when adding to sum. I assume either sum must be int64_t or rand() must act on smaller values. Note that even so I have this overflow I do not encounter differences in the tests on my machine, but this might be a part of the stated issue depending on CC and system.

[vneiger]

there is a int32_t overflow when generating the random linear form, in particular in line 716 of msolve.c when adding to sum

This should probably not be the culprit, as it seems that this variable sum is never used (which is maybe not the intended behaviour..?). See #277 and #281 .

[jerebertho]

Hi,
It seems the culprit is the probabilistic linear algebra.
Calling this example with options -l 44 --random-seed 1772988448 (or many other seeds), -l 2, or -l 42 in verbose mode yields the following F4 steps

Adding a linear form with an extra variable (lowest w.r.t. monomial order)
[coefficients of linear form are k^1 for k looping over variable index 1...n]

--------------- INPUT DATA ---------------
#variables                       9
#equations                      10
#invalid equations               0
field characteristic             0
homogeneous input?               0
signature-based computation      0
monomial order                 DRL
basis hash table resetting     OFF
linear algebra option           44
initial hash table size     131072 (2^17)
max pair selection             ALL
reduce gb                        1
#threads                         1
info level                       2
generate pbm files               0
------------------------------------------
Initial prime is 1282912907

Legend for f4 information
--------------------------------------------------------
deg       current degree of pairs selected in this round
sel       number of pairs selected in this round
pairs     total number of pairs in pair list
mat       matrix dimensions (# rows x # columns)
density   density of the matrix
new data  # new elements for basis in this round
          # zero reductions during linear algebra
time(rd)  time of the current f4 round in seconds given
          for real and cpu time
--------------------------------------------------------

deg     sel   pairs        mat          density            new data         time(rd) in sec (real|cpu)
------------------------------------------------------------------------------------------------------
  1       5       9       6 x 9          35.19%        5 new       0 zero         0.00 | 0.00         
  2       4       4      19 x 21         12.78%        3 new       1 zero         0.00 | 0.00         
  3       3       3       9 x 12         33.33%        3 new       0 zero         0.00 | 0.00         
  2       3       6       9 x 9          39.51%        1 new       2 zero         0.00 | 0.00         
  3       4       4      15 x 13         26.15%        0 new       4 zero         0.00 | 0.00         
------------------------------------------------------------------------------------------------------
reduce final basis       10 x 12         28.33%       10 new       0 zero         0.00 | 0.00         
------------------------------------------------------------------------------------------------------

---------------- TIMINGS ----------------
overall(elapsed)        0.00 sec
overall(cpu)            0.00 sec
select                  0.00 sec   5.1%
symbolic prep.          0.00 sec   2.2%
update                  0.00 sec  53.0%
convert                 0.00 sec   7.3%
linear algebra          0.00 sec   3.8%
reduce gb               0.00 sec   0.0%
-----------------------------------------

---------- COMPUTATIONAL DATA -----------
size of basis                    10
#terms in basis                  28
#pairs reduced                   19
#GM criterion                   212
#redundant elements              12
#rows reduced                    48
#zero reductions                  7
max. matrix data                 19 x 21 (12.782%)
max. symbolic hash table size  2^11
max. basis hash table size     2^16
-----------------------------------------

Yet, the failing call yields

Adding a linear form with an extra variable (lowest w.r.t. monomial order)
[coefficients of linear form are k^1 for k looping over variable index 1...n]

--------------- INPUT DATA ---------------
#variables                       9
#equations                      10
#invalid equations               0
field characteristic             0
homogeneous input?               0
signature-based computation      0
monomial order                 DRL
basis hash table resetting     OFF
linear algebra option           44
initial hash table size     131072 (2^17)
max pair selection             ALL
reduce gb                        1
#threads                         1
info level                       2
generate pbm files               0
------------------------------------------
Initial prime is 1191100583

Legend for f4 information
--------------------------------------------------------
deg       current degree of pairs selected in this round
sel       number of pairs selected in this round
pairs     total number of pairs in pair list
mat       matrix dimensions (# rows x # columns)
density   density of the matrix
new data  # new elements for basis in this round
          # zero reductions during linear algebra
time(rd)  time of the current f4 round in seconds given
          for real and cpu time
--------------------------------------------------------

deg     sel   pairs        mat          density            new data         time(rd) in sec (real|cpu)
------------------------------------------------------------------------------------------------------
  1       5       9       6 x 9          35.19%        5 new       0 zero         0.00 | 0.00         
  2       4       4      19 x 21         12.78%        2 new       2 zero         0.00 | 0.00         
  3       1       1       4 x 9          44.44%        1 new       0 zero         0.00 | 0.00         
  3       1       1       7 x 12         38.10%        0 new       1 zero         0.00 | 0.00         
------------------------------------------------------------------------------------------------------
reduce final basis        9 x 14         27.78%        9 new       0 zero         0.00 | 0.00         
------------------------------------------------------------------------------------------------------

---------------- TIMINGS ----------------
overall(elapsed)        0.00 sec
overall(cpu)            0.00 sec
select                  0.00 sec   5.1%
symbolic prep.          0.00 sec   1.7%
update                  0.00 sec  47.9%
convert                 0.00 sec   7.2%
linear algebra          0.00 sec   3.8%
reduce gb               0.00 sec   0.0%
-----------------------------------------

---------- COMPUTATIONAL DATA -----------
size of basis                     9
#terms in basis                  28
#pairs reduced                   11
#GM criterion                   142
#redundant elements               9
#rows reduced                    31
#zero reductions                  3
max. matrix data                 19 x 21 (12.782%)
max. symbolic hash table size  2^11
max. basis hash table size     2^16
-----------------------------------------

Positive dimensional Grobner basis

So, as we can see, in degree 2, there is an extraneous reduction to 0 which prevents detecting a low degree polynomial who shall close the staircase.

In my opinion, this kind of behavior is expected from such a probabilistic method: bad random numbers may lead to a wrong answer. However, in this example, we are introducing a linear form to compute the parametrizations so we already know from previous F4 computations that the ideal is 0-dimensional. I will work on a fix in this situation.