On `Ideal.groebner_basis(algorithm='singular:stdfglm')`

[Georgi Guninski]

sage: Kx.<x,y>=QQ[]
sage: I=Ideal([x*y])
sage: gb=I.groebner_basis(algorithm='singular:stdfglm')

TypeError: Singular error:
? The ideal i has to be 0-dimensional

I believe computing the dimension of ideal requires computing groebner basis
and even if this a false, computing the dimension of ideal will detect
the constant ideal. If computing the dimension of ideal is efficient,
this will be a major achievement.

So `stdfglm` recognizes the ideal is not 0 dimensional, something else
did the heavy computation of the dimension, so `stdfglm` is slower than
the `else`.

Is the above reasoning correct?

Does the documentation address this?

[Nils Bruin]

No it is not. The error above only indicates that the algorithm found a contradiction to the assumption that the ideal is 0-dimensional; not that it computed what the dimension actually is.

groebner bases of 0-dimensional ideals have been proven to be easier to compute than the general case (there are better complexity bounds for them), so it is quite conceivable to that there is something to gain by writing an algorithm that proceeds on the assumption the ideal is 0-dimensional and bails as soon as it finds something that is inconsistent with that assumption. I'd assume the singular documentation would have a reference to a relevant paper discussing the strategy followed by stdfglm

[Oscar Benjamin]

The Singular documentation is here and it doesn't have any reference:

https://www.singular.uni-kl.de/Manual/4-0-3/sing_403.htm

The FGLM algorithm is for converting a zero-dimensional Groebner basis
for one monomial ordering to a basis for another ordering. It sounds
like stdfglm works in three steps:

1. Compute basis in degrevlex ordering.
2. Check the basis is zero dimensional.
3. Use FGLM to convert to lex ordering.

In this case the basis is not zero dimensional so the FGLM step is not
attempted (even though the basis conversion is trivial).

--
Oscar

[Vincent Neiger]

A minor comment : from the documentation of Singular it seems that the output Gröbner basis will be computed with respect to the monomial ordering of the base ring. So for the specific code snippet given above with the ring constructed as "Kx.<x,y>=QQ[]", I would expect step 3 (the actual change of ordering / FGLM step) to target the degrevlex ordering, since it is the one used by default when creating the polynomial ring. For this piece of code with degrevlex ordering, the point of step 3 -- or of trying to use FGLM at all -- is then not very clear since the first step is to use another algorithm (not FGLM) to compute the degrevlex basis, furthermore this other algorithm would likely not require that the ideal be zero-dimensional.

However using FGLM is indeed a good approach in the situation highlighted by Oscar, when the target order is the lex order:

sage: Kx = PolynomialRing(GF(9001), 5, 'x', order="lex")
sage: I = Kx.ideal([Kx.random_element(3) for k in range(5)])
sage: %time gb = I.groebner_basis(algorithm='singular:stdfglm')
CPU times: user 6.24 ms, sys: 10 ms, total: 16.3 ms
Wall time: 71.7 ms
sage: %time gb = I.groebner_basis()
CPU times: user 505 ms, sys: 1.04 ms, total: 506 ms
Wall time: 504 ms

[Georgi Guninski]

On Wed, Oct 16, 2024 at 6:45 PM Nils Bruin <nbr...@sfu.ca> wrote:
>

>
> Is the above reasoning correct?
>
>
> No it is not. The error above only indicates that the algorithm found a contradiction to the assumption that the ideal is 0-dimensional; not that it computed what the dimension actually is.
>

According to Singular's documentation and Oscar's first email in this
thread, stdfglm first computes groebner basis in order degrevlex, then
check the dimension.
I think this imply your claim that fglm can recognize 0 dimension is false.
Do you still claim that stdfglm recognizes 0 dimension without
computing groebner basis by using another oracle for basis?