fix variable substitution in PolyBoRi + finding M4RI

[malb]

For some inputs our Trac macro PolyBoRi wrapper throws an error while upstream computes the example just fine. The reason we fail is that some rings don't match and thus coercion goes wrong. The problem was reported by Joan Daemen who also provided an example via private communication.

---

Note to the release managers

When merging the new PolyBoRi 0.6.4.p4 spkg, apply
the attached patch to the Sage library.

Upstream: Fixed upstream, in a later stable release.

CC: @sagetrac-PolyBoRi @alexanderdreyer @nexttime @qed777

Component: commutative algebra

Author: Alexander Dreyer, Martin Albrecht, Michael Brickenstein

Reviewer: Martin Albrecht, Alexander Dreyer, Leif Leonhardy

Merged: sage-4.5.3.alpha1

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

[malb]

comment:1

Alexander Dreyer provided a fix for the issue. I've packaged this fix into an SPKG

 http://sage.math.washington.edu/home/malb/spkgs/polybori-0.6.4.p2.spkg

I've also packaged his patch for Sage into a proper mercurial patch which I'll attach in a sec.

[malb]

comment:2

The attached patch + SPKG fix the original problem, however I'm getting segfaults now:

Program received signal SIGSEGV, Segmentation fault.
linalg_step_modified (polys=<value optimized out>, terms=<value optimized out>, 
    leads_from_strat=<value optimized out>, log=<value optimized out>, 
    optDrawMatrices=<value optimized out>, matrixPrefix=<value optimized out>)
    at groebner/src/nf.cc:2270
2270    groebner/src/nf.cc: No such file or directory.
        in groebner/src/nf.cc
Current language:  auto
The current source language is "auto; currently c++".
(gdb) bt
#0  linalg_step_modified (polys=<value optimized out>, terms=<value optimized out>, 
    leads_from_strat=<value optimized out>, log=<value optimized out>, 
    optDrawMatrices=<value optimized out>, matrixPrefix=<value optimized out>)
    at groebner/src/nf.cc:2270
#1  0x00007fffcf4f6c56 in polybori::groebner::GroebnerStrategy::faugereStepDense (
    this=<value optimized out>, orig_system=<value optimized out>) at groebner/src/nf.cc:2386
#2  0x00007fffcf3e2a0d in __pyx_pf_4sage_5rings_10polynomial_5pbori_16GroebnerStrategy_faugere_step_dense (__pyx_v_self=0x5997520, __pyx_v_v=0x12bf3500) at sage/rings/polynomial/pbori.cpp:31846
#3  0x00007ffff7b11316 in call_function (f=0x418a900, throwflag=<value optimized out>)
    at Python/ceval.c:3694

[malb]

comment:3

Ignore the SIGSEGV above, it is unrelated to this ticket but is caused by #9562. 

Alexander, can you review my SPKG + patch, i.e. that it does what you intended? I give your changes a positive review so all that's needed is some check whether I produced the SPKG correctly etc.

[malb]

comment:4

Use this SPKG instead (it is based on the latest PolyBoRi SPKG which the previous SPKG wasn't) 

 http://sage.math.washington.edu/home/malb/spkgs/polybori-0.6.4.p3.spkg

[alexanderdreyer]

comment:5

There was some unrelated issue with the previous spkg (libm4ri was not found, because Sage's lib directory was not given to PolyBoRi)
I updated the spkg accordingly:
http://sage.math.washington.edu/home/dreyer/pb/polybori-0.6.4.p4.spkg

[nexttime]

Work Issues: Update SPKG.txt

[nexttime]

comment:8

SPKG.txt has to be updated for p4.

Alexander's patch looks reasonable, though libm4ri (and the GD library) were previously found (in the second attempt)... (The only issue I'm aware of is with updating from 4.5.2 on MacOS X 10.6, which Mitesh Patel couldn't reproduce either; see #9721.)

(The change to p4 is of course unrelated to the original intent of this ticket; perhaps adapt its title, too.)

[malb]

comment:9

Replying to @nexttime:

SPKG.txt has to be updated for p4.

I have a new SPKG which does exactly that. I'll upload it later.

Alexander's patch looks reasonable, though libm4ri (and the GD library) were previously found (in the second attempt)... (The only issue I'm aware of is with updating from 4.5.2 on MacOS X 10.6, which Mitesh Patel couldn't reproduce either; see #9721.) (The change to p4 is of course unrelated to the original intent of this ticket; perhaps adapt its title, too.)

[malb]

comment:10

The new SPKG is here

 http://sage.math.washington.edu/home/malb/spkgs/polybori-0.6.4.p4.spkg

I just added an entry to SPKG.txt

[malb]

comment:11

PolyBoRi makes assumptions about M4RI which are not met with the newest upstream release (#9475). Thus, we should fix this here asap since the new M4RI is about to go in.

[malb]

comment:12

I've replaced the SPKG here 

   http://sage.math.washington.edu/home/malb/spkgs/polybori-0.6.4.p4.spkg

and the new SPKG fixes the SIGSEGV and all doctests pass.

These fixes are:

 http://bitbucket.org/brickenstein/polybori/changeset/6ef7402d935b

 http://bitbucket.org/brickenstein/polybori/changeset/b692c8181e94

[nexttime]

comment:14

Work issues field ( = "Update SPKG.txt") still (or again) valid... ;-)

(Perhaps also add this ticket number, and mention the PolyBoRi upstream fixes there.)

[malb]

comment:15

Updated accordingly.

[malb]

Changed work issues from Update SPKG.txt to none

[nexttime]

comment:21

Replying to @malb:

So we have a positive review then?

Once Alexander's testall has finished, I think yes. :)

I'll perhaps test later on a 64-bit platform, although I don't expect any issues.

[nexttime]

comment:22

Replying to @nexttime:

I'll perhaps test later on a 64-bit platform, although I don't expect any issues.

Passed all long tests in sage/matrix; currently running make testlong, but this will take some time since the system is already fully loaded... (Ubuntu 9.04 x86_64, Core2, gcc 4.3.3)

[alexanderdreyer]

comment:23

Once Alexander's testall has finished, I think yes. :)

They have successfully finished (SuSE 11.1 64 Bits). So we have the positive review now

[alexanderdreyer]

Author: malb,PolyBoRi

[alexanderdreyer]

Upstream: Fixed upstream, in a later stable release.

[alexanderdreyer]

Reviewer: leif,AlexanderDreyer

[nexttime]

comment:24

Note to the release managers

I think this should (only) be merged together with #9475, but I'm not that sure.

[nexttime]

Changed reviewer from leif,AlexanderDreyer to Martin Albrecht, Alexander Dreyer, Leif Leonhardy

[nexttime]

Changed author from malb,PolyBoRi to Alexander Dreyer, Martin Albrecht, Michael Brickenstein

[nexttime]

comment:25

As expected, also passed testlong with Sage 4.5.3.alpha0 and #9475 on Ubuntu 9.04 x86_64 (Core2, gcc 4.3.3, native code, O2).

[nexttime]

comment:26

Ooops, I just noticed the attached patch is to the Sage library (I assumed it is an spkg patch). So I did not apply that patch in any of the tests I made, which despite that all passed...

Martin, is that patch now obsolete or do we just not test an example which would fail without it? Or is it platform-specific?

(Btw, the patch's commit message lacks a ticket number; also, a back-reference/comment in the code wouldn't be bad.)

Perhaps you could add Joan Daemen's example to the ticket.

[malb]

comment:27

Replying to @nexttime:

Ooops, I just noticed the attached patch is to the Sage library (I assumed it is an spkg patch). So I did not apply that patch in any of the tests I made, which despite that all passed... Martin, is that patch now obsolete or do we just not test an example which would fail without it?

The patch is necessary, Sage will SIGSEGV in some cases otherwise. I'll try to update the patch with an example.

Or is it platform-specific? (Btw, the patch's commit message lacks a ticket number; also, a back-reference/comment in the code wouldn't be bad.)

I'll add the ticket number.

Perhaps you could add Joan Daemen's example to the ticket.

The problem is a bit bigger and I have no permission to publish it, sorry.

[malb]

comment:28

I've updated the patch with an example and this ticket's number.

[nexttime]

comment:29

Replying to @malb:

I've updated the patch with an example and this ticket's number.

Ok, I'll rerun some of the tests later. Currently all machines busy with new PARI testing... ;-)

(I don't see the ticket number in the patched code though.)

[malb]

comment:30

#9717 fixing parent ring in substitute_variable() (fix due to Alexander Dreyer)

That's the commit message, is that alright?

[nexttime]

comment:31

And an attachment comment would be nice... ("Sage library patch - ...")

I HATE TRAC! [concurrent "editing" grrrrr...]

---

I meant putting the ticket number also into a comment in the code; you don't see the commit messages when looking just at source files. E.g.

        ... # fixes #9717

or in the TESTS:: section:

    Substitution is (now) also allowed with different rings (cf. #9717)::

Something like that.

[malb]

comment:32

I'm not too convinced by that. This was a serious bug which just wasn't reported to far. I don't want to clutter the code with track ticket numbers. When reading the code it is relatively simple to see (I'd say) that the new code is correct, thus I'd say it doesn't need a ticket to explain why it is there. Also, the new example isn't just a test, it shows a real use case.

[malb]

Sage library patch fixing an issue with substitute_variable()

[nexttime]

comment:33

Attachment: polybori-0.6.4.p2.patch.gz

[qed777]

Merged: sage-4.5.3.alpha0

[qed777]

Changed merged from sage-4.5.3.alpha0 to sage-4.5.3.alpha1

[qed777]

comment:36

How does one run PolyBoRi's test suite? I'm curious about whether we can add an spkg-check file (at a new ticket).

[alexanderdreyer]

comment:37

The testsuite, which is included in PolyBoRi is not up to date, we use another suite for developing internally. On the one hand, it is lange, on the other, some examples are not freely available. We'll try to deliver a suitable subset of the examples in the future.