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

[simon-king-jena]

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:

• https://www.singular.uni-kl.de:8002/trac/changeset/d25e3f8d83dc8b6ba3e87362ed1646bf600778bb/git
• https://www.singular.uni-kl.de:8002/trac/changeset/cebb9879c2629291abb5ffeb202af73fa0749eb3/git

Upstream: Fixed upstream, but not in a stable release.

CC: @slel

Component: packages: standard

Keywords: Singular std

Author: Simon King, Hans Schönemann

Branch: 6bca984

Reviewer: Travis Scrimshaw, Simon King

Issue created by migration from https://trac.sagemath.org/ticket/25889

[simon-king-jena]

Branch: u/SimonKing/backport_a_fix_for_std_id_p__in_singular

[simon-king-jena]

comment:2

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:

820b0c4

Backport fix for Singular's std(id,p)

[simon-king-jena]

Author: Simon King, Hans Schönemann

[simon-king-jena]

Commit: 820b0c4

[simon-king-jena]

comment:3

Attachment: example.sing.gz

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.

[tscrim]

comment:4

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...).

[tscrim]

Reviewer: Travis Scrimshaw

[sagetrac-git]

Changed commit from 820b0c4 to 6bca984

[sagetrac-git]

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

6bca984

Bump patch level of Singular

[simon-king-jena]

comment:6

Done.

[tscrim]

comment:7

LGTM. Thank you.

[simon-king-jena]

comment:9

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.

[slel]

comment:10

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.

[slel]

Changed upstream from Fixed upstream, in a later stable release. to Fixed upstream, but not in a stable release.

[jdemeyer]

comment:11

Replying to @simon-king-jena:

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.

[jdemeyer]

comment:12

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

[jdemeyer]

comment:13

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.

[simon-king-jena]

comment:14

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?

[jdemeyer]

comment:15

Replying to @simon-king-jena:

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.

[jdemeyer]

comment:16

Replying to @simon-king-jena:

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.

[simon-king-jena]

comment:17

Replying to @jdemeyer:

Replying to @simon-king-jena:

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

[vbraun]

Changed branch from u/SimonKing/backport_a_fix_for_std_id_p__in_singular to 6bca984

[vbraun]

Changed commit from 6bca984 to none

[vbraun]

comment:19

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.

[simon-king-jena]

comment:20

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 Upgrade: Singular 4.2.0, pysingular 0.9.7 #25993, so, the future is there. One could argue that Add ability to generate graphs based on correlations of sequences #25933 supersedes this ticket, making this ticket a duplicate.
• Did you delete the commit on purpose?

[simon-king-jena]

comment:21

To Volker,

Replying to @simon-king-jena:

• "Some point in the future" is Upgrade: Singular 4.2.0, pysingular 0.9.7 #25993, so, the future is there. One could argue that Add ability to generate graphs based on correlations of sequences #25933 supersedes this ticket, making this ticket a duplicate.

I do believe this is the case.

[simon-king-jena]

Changed reviewer from Travis Scrimshaw to Travis Scrimshaw, Simon King

[embray]

comment:23

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