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 Le mercredi 16 octobre 2024 à 17:59:59 UTC+2, oscar.j....@gmail.com a écrit : > On Wed, 16 Oct 2024 at 16:45, Nils Bruin <nbr...@sfu.ca> wrote: > > > > On Wednesday 16 October 2024 at 06:43:30 UTC-7 Georgi Guninski wrote: > > > > 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? > > > > 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 > > 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 > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/a4775838-d698-44e8-a7db-eb5fdfd54a51n%40googlegroups.com.
