Opened 3 years ago

Closed 3 years ago

#27445 closed enhancement (fixed)

groebner_basis for multivariate polynomial ring with no variables

Reported by: dkrenn Owned by:
Priority: major Milestone: sage-8.8
Component: commutative algebra Keywords:
Cc: Merged in:
Authors: Daniel Krenn Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: df26e69 (Commits, GitHub, GitLab) Commit: df26e69a651d64cfd0edb8cffc6e2a47cdbf7722
Dependencies: Stopgaps:

Status badges

Description

On all of the following examples, the warning

Warning: falling back to very slow toy implementation.

appear:

            sage: P = PolynomialRing(QQ, 't', 0)
            sage: P.ideal([P(2)]).groebner_basis()
            [1]
            sage: P.ideal([]).groebner_basis()
            []
            sage: P.ideal([0]).groebner_basis()
            []
            sage: P.ideal([3,4,0,5]).groebner_basis()
            [1]

Handle these cases separately! (Reason: singular does not handle these cases.)

Change History (12)

comment:1 Changed 3 years ago by dkrenn

  • Branch set to u/dkrenn/gb-no-var

comment:2 Changed 3 years ago by dkrenn

  • Commit set to 9d4ffa65de786bf0cbeb2e369062964c1dab2aac
  • Status changed from new to needs_review

New commits:

9d4ffa6Trac #27445: groebner basis for multi-variate polynomial ring with no variables

comment:3 Changed 3 years ago by embray

  • Milestone changed from sage-8.7 to sage-8.8

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)

comment:4 follow-up: Changed 3 years ago by tscrim

  • Reviewers set to Travis Scrimshaw

Can you also add a test when the base ring is not a field (e.g., ZZ)? Otherwise LGTM.

comment:5 in reply to: ↑ 4 ; follow-up: Changed 3 years ago by dkrenn

Replying to tscrim:

Can you also add a test when the base ring is not a field (e.g., ZZ)? Otherwise LGTM.

A test would always result in

TypeError: Can only reduce polynomials over fields.

also with this patch. Is this what you mean? (The situation for non-fields is more complex as coefficients do not need to divide each other...)

comment:6 in reply to: ↑ 5 ; follow-up: Changed 3 years ago by tscrim

Replying to dkrenn:

Replying to tscrim:

Can you also add a test when the base ring is not a field (e.g., ZZ)? Otherwise LGTM.

A test would always result in

TypeError: Can only reduce polynomials over fields.

also with this patch. Is this what you mean? (The situation for non-fields is more complex as coefficients do not need to divide each other...)

I believe that in general, but over ZZ Singular does GB computations:

sage: R.<x,y,z> = ZZ[]
sage: R.ideal([x^2-y,x*y-z*y+2,5*x*z-x]).groebner_basis()
[y*z^2 - y^2 - 2*x - 2*z, x^2 - y, x*y - y*z + 2, 5*y^2 - y*z + 10*x + 2, 5*x*z - x, 5*y*z - y, 10*z - 2]
sage: R.ideal([5,2]).groebner_basis()
[1]

So since singular works for ZZ, I think this patch should also fix it at least for that ring.

comment:7 Changed 3 years ago by git

  • Commit changed from 9d4ffa65de786bf0cbeb2e369062964c1dab2aac to 6afce663221bcd4beb97453226e8952a1ce45bf1

Branch pushed to git repo; I updated commit sha1. New commits:

6afce66Trac #27445: polynomial rings over non-fields + major restructure of relevant code

comment:8 in reply to: ↑ 6 Changed 3 years ago by dkrenn

Replying to tscrim:

I believe that in general, but over ZZ Singular does GB computations:

sage: R.<x,y,z> = ZZ[]
sage: R.ideal([x^2-y,x*y-z*y+2,5*x*z-x]).groebner_basis()
[y*z^2 - y^2 - 2*x - 2*z, x^2 - y, x*y - y*z + 2, 5*y^2 - y*z + 10*x + 2, 5*x*z - x, 5*y*z - y, 10*z - 2]
sage: R.ideal([5,2]).groebner_basis()
[1]

So since singular works for ZZ, I think this patch should also fix it at least for that ring.

Ok, did it now more general. It needed a restructuring of the existing relevant code.

comment:9 Changed 3 years ago by git

  • Commit changed from 6afce663221bcd4beb97453226e8952a1ce45bf1 to df26e69a651d64cfd0edb8cffc6e2a47cdbf7722

Branch pushed to git repo; I updated commit sha1. New commits:

df26e69Merge tag '8.7' into t/27445/gb-no-var

comment:10 follow-up: Changed 3 years ago by tscrim

  • Status changed from needs_review to positive_review

Thank you. I think this is much better and more consistent.

comment:11 in reply to: ↑ 10 Changed 3 years ago by dkrenn

Replying to tscrim:

Thank you. I think this is much better and more consistent.

I think so as well. Thank you.

comment:12 Changed 3 years ago by vbraun

  • Branch changed from u/dkrenn/gb-no-var to df26e69a651d64cfd0edb8cffc6e2a47cdbf7722
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.