Opened 21 months ago
Closed 13 months ago
#25889 closed defect (invalid)
Backport a fix for std(id,P) in Singular
Reported by:  SimonKing  Owned by:  

Priority:  major  Milestone:  sageduplicate/invalid/wontfix 
Component:  packages: standard  Keywords:  Singular std 
Cc:  slelievre  Merged in:  
Authors:  Simon King, Hans Schönemann  Reviewers:  Travis Scrimshaw, Simon King 
Report Upstream:  Fixed upstream, but not in a stable release.  Work issues:  
Branch:  6bca984 (Commits)  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
In Singular, if id
is an ideal given by a standard basis and P
is a list of polynomials, then std(id,P)
is computing a standard basis for the ideal generated by id
and P
. It is supposed to take into account that id
is a standard basis, which means that a lot of critical pairs can be discarded.
However, the current Singular version does in fact considers a lot of unnecessary critical pairs in std(id,P)
, as I uncovered in my cohomology computations.
Hans Schönemann found a fix that will be part of the next Singular release and also helped me to backport that fix to the Singular version that currently is in Sage. I suggest to add this to build/pkgs/singular/patches
.
Upstream fix:
Attachments (1)
Change History (24)
comment:1 Changed 21 months ago by
 Branch set to u/SimonKing/backport_a_fix_for_std_id_p__in_singular
comment:2 Changed 21 months ago by
 Commit set to 820b0c420d52b8b1fc0e8001937992317d398bf5
 Status changed from new to needs_review
Changed 21 months ago by
comment:3 Changed 21 months ago by
I have attached an example (actually from some cohomology computation, but the example is standalone).
Start Sage's Singular (sage singular
) and do
> execute(read("example.sing"));
With the patch, it finishes quite soon, and the protocol output shows that almost no work needed to be done. Without the patch, you have to be very patient.
By the way, I tested that make test
passes with the patch.
comment:4 Changed 21 months ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to needs_work
You will also need to bump the patch level for singular: 4.1.0p3.p2
> 4.1.0p3.p3
(I don't know why this has such a strange numbering system...).
comment:5 Changed 21 months ago by
 Commit changed from 820b0c420d52b8b1fc0e8001937992317d398bf5 to 6bca984b793ed7af43715ca4f5fa13f224f4df2d
Branch pushed to git repo; I updated commit sha1. New commits:
6bca984  Bump patch level of Singular

comment:7 Changed 21 months ago by
 Status changed from needs_review to positive_review
LGTM. Thank you.
comment:8 Changed 20 months ago by
 Cc slelievre added
 Description modified (diff)
comment:9 followup: ↓ 11 Changed 20 months ago by
Hi Samuel, the links you gave are correct. Note, however, that they are not identical with the patch provided here, as the upstream changeset is applied to a different version than the one provided by Sage. Hans Schönemann helped me to backport it.
comment:10 Changed 20 months ago by
 Report Upstream changed from Fixed upstream, in a later stable release. to Fixed upstream, but not in a stable release.
Thanks for clarifying. It's still useful to have some concrete reference so we can track when this does appear in a stable upstream release.
comment:11 in reply to: ↑ 9 Changed 20 months ago by
Replying to SimonKing:
Hi Samuel, the links you gave are correct. Note, however, that they are not identical with the patch provided here, as the upstream changeset is applied to a different version than the one provided by Sage. Hans Schönemann helped me to backport it.
You should really include those links in the .patch
files. That way, it is easy for packagers to find the origin of the patches. In my opinion, we should never accept patches like on this ticket without any explanation or reference.
comment:12 Changed 20 months ago by
comment:13 Changed 20 months ago by
 Status changed from positive_review to needs_work
Given that this patch will conflict (in the git merge
sense) with #24735, given that it won't be needed anymore after #25993 and given that it needs_work to add the links, I would propose to put this ticket on hold for now. If #25993 turns out to be easy, then we can close this ticket. Otherwise, we can rebase it on top of #24735. That ticket is ready, it just requires somebody to push the "positive_review" button.
comment:14 followups: ↓ 15 ↓ 16 Changed 20 months ago by
Well, the bug fixed by this patch is not yielding wrong results but yielding very slow computations in a situation that I care about.
From my perspective, it would be perfectly alright to resolve this ticket as "wontfix", given that there is a realistic perspective that soonish (namely with #25993) the issue will be fixed without a backported patch.
Jeroen, do I understand correctly: Based on #24735, I should create a new ticket for group cohomology, implementing things so that it works both with Singular4.1.1.p2 and ...p3, and this new ticket would be a dependency for #25933?
comment:15 in reply to: ↑ 14 ; followup: ↓ 17 Changed 20 months ago by
Replying to SimonKing:
Jeroen, do I understand correctly: Based on #24735, I should create a new ticket for group cohomology, implementing things so that it works both with Singular4.1.1.p2 and ...p3, and this new ticket would be a dependency for #25933?
Yes, except that it doesn't have to be on top of #24735. I don't know whether there are any changes between Singular4.1.0p3 (currently in Sage) and 4.1.1p2 (in #24735) that are relevant to p_group_cohomology.
comment:16 in reply to: ↑ 14 Changed 20 months ago by
Replying to SimonKing:
Well, the bug fixed by this patch is not yielding wrong results but yielding very slow computations in a situation that I care about.
From my perspective, it would be perfectly alright to resolve this ticket as "wontfix", given that there is a realistic perspective that soonish (namely with #25993) the issue will be fixed without a backported patch.
Well, I would like to keep open the possibility that #25993 gives unexpected problems.
comment:17 in reply to: ↑ 15 Changed 20 months ago by
Replying to jdemeyer:
Replying to SimonKing:
Jeroen, do I understand correctly: Based on #24735, I should create a new ticket for group cohomology, implementing things so that it works both with Singular4.1.1.p2 and ...p3, and this new ticket would be a dependency for #25933?
Yes, except that it doesn't have to be on top of #24735. I don't know whether there are any changes between Singular4.1.0p3 (currently in Sage) and 4.1.1p2 (in #24735) that are relevant to p_group_cohomology.
Right, you said that p_group_cohomology still works with #24735, and trouble only start with #25993. Anyway, I should create a package version that works with both...
comment:18 Changed 20 months ago by
 Branch changed from u/SimonKing/backport_a_fix_for_std_id_p__in_singular to 6bca984b793ed7af43715ca4f5fa13f224f4df2d
 Resolution set to fixed
 Status changed from needs_work to closed
comment:19 followup: ↓ 20 Changed 20 months ago by
 Commit 6bca984b793ed7af43715ca4f5fa13f224f4df2d deleted
 Resolution fixed deleted
 Status changed from closed to new
I don't understand the rationale of "lets not fix the bug because at some point in the future I'll have a branch that fixes it, too". Just deal with git conflicts by merging already positively reviewed tickets into your branch as necessary. In any case, I'll leave this ticket for you to figure out.
comment:20 in reply to: ↑ 19 ; followup: ↓ 21 Changed 20 months ago by
Replying to vbraun:
I don't understand the rationale of "lets not fix the bug because at some point in the future I'll have a branch that fixes it, too". Just deal with git conflicts by merging already positively reviewed tickets into your branch as necessary. In any case, I'll leave this ticket for you to figure out.
 The bug is not a bug in the sense of giving wrong results, but a bug in the sense of "slow in some exotic situations that is relevant in some extreme examples of the pet project of one developer (me)". In fact I only know a single example (computation of a filter regular system of parameters of the modular cohomology ring of group number 299 of order 256) where not fixing the bug really hurts. So, one could argue that it isn't particularly urgent to fix.
 "Some point in the future" is #25993, so, the future is there. One could argue that #25933 supersedes this ticket, making this ticket a duplicate.
 Did you delete the commit on purpose?
comment:21 in reply to: ↑ 20 Changed 15 months ago by
 Milestone changed from sage8.4 to sageduplicate/invalid/wontfix
 Status changed from new to needs_review
comment:22 Changed 15 months ago by
 Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, Simon King
 Status changed from needs_review to positive_review
comment:23 Changed 13 months ago by
 Resolution set to invalid
 Status changed from positive_review to closed
Presuming these are all correctly reviewed as either duplicate, invalid, or wontfix.
With the added patch, the first step in the construction of a filter regular sequence in a certain complicated cohomology ring improved from more than two days to less than 10 seconds.
New commits:
Backport fix for Singular's std(id,p)