#25889 closed defect (invalid)

Backport a fix for std(id,P) in Singular

Reported by: SimonKing Owned by:
Priority: major Milestone: sage-duplicate/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 slelievre)

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)

example.sing (18.4 MB) - added by SimonKing 21 months ago.

Change History (24)

comment:1 Changed 21 months ago by SimonKing

  • Branch set to u/SimonKing/backport_a_fix_for_std_id_p__in_singular

comment:2 Changed 21 months ago by SimonKing

  • Authors set to Simon King, Hans Schönemann
  • Commit set to 820b0c420d52b8b1fc0e8001937992317d398bf5
  • Status changed from new to needs_review

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:

820b0c4Backport fix for Singular's std(id,p)

Changed 21 months ago by SimonKing

comment:3 Changed 21 months ago by SimonKing

I have attached an example (actually from some cohomology computation, but the example is stand-alone).

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 tscrim

  • 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 git

  • Commit changed from 820b0c420d52b8b1fc0e8001937992317d398bf5 to 6bca984b793ed7af43715ca4f5fa13f224f4df2d

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

6bca984Bump patch level of Singular

comment:6 Changed 21 months ago by SimonKing

  • Status changed from needs_work to needs_review

Done.

comment:7 Changed 21 months ago by tscrim

  • Status changed from needs_review to positive_review

LGTM. Thank you.

comment:8 Changed 20 months ago by slelievre

  • Cc slelievre added
  • Description modified (diff)

comment:9 follow-up: Changed 20 months ago by 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.

comment:10 Changed 20 months ago by slelievre

  • 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 jdemeyer

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.

Last edited 20 months ago by jdemeyer (previous) (diff)

comment:12 Changed 20 months ago by jdemeyer

It seems that these patches are included in Singular-4.1.1p3 (#25993) but not in Singular-4.1.1p2 (#24735).

comment:13 Changed 20 months ago by jdemeyer

  • 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 follow-ups: Changed 20 months ago by 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.

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 Singular-4.1.1.p2 and ...p3, and this new ticket would be a dependency for #25933?

comment:15 in reply to: ↑ 14 ; follow-up: Changed 20 months ago by 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 Singular-4.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 Singular-4.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 jdemeyer

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 SimonKing

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 Singular-4.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 Singular-4.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 vbraun

  • 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 follow-up: Changed 20 months ago by vbraun

  • 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 ; follow-up: Changed 20 months ago by SimonKing

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 SimonKing

  • Milestone changed from sage-8.4 to sage-duplicate/invalid/wontfix
  • Status changed from new to needs_review

To Volker,

Replying to SimonKing:

  • "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.

I do believe this is the case.

comment:22 Changed 15 months ago by SimonKing

  • 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 embray

  • Resolution set to invalid
  • Status changed from positive_review to closed

Presuming these are all correctly reviewed as either duplicate, invalid, or wontfix.

Note: See TracTickets for help on using tickets.