Opened 9 years ago

Closed 9 years ago

Last modified 9 years ago

#9717 closed defect (fixed)

fix variable substitution in PolyBoRi + finding M4RI

Reported by: malb Owned by: malb
Priority: critical Milestone: sage-4.5.3
Component: commutative algebra Keywords:
Cc: PolyBoRi, AlexanderDreyer, leif, mpatel Merged in: sage-4.5.3.alpha1
Authors: Alexander Dreyer, Martin Albrecht, Michael Brickenstein Reviewers: Martin Albrecht, Alexander Dreyer, Leif Leonhardy
Report Upstream: Fixed upstream, in a later stable release. Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by leif)

For some inputs our 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.

Attachments (1)

polybori-0.6.4.p2.patch (1.6 KB) - added by malb 9 years ago.
Sage library patch fixing an issue with substitute_variable()

Download all attachments as: .zip

Change History (38)

comment:1 Changed 9 years ago by malb

  • Status changed from new to needs_work

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.

comment:2 Changed 9 years ago by malb

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

comment:3 Changed 9 years ago by malb

  • Status changed from needs_work to needs_review

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.

comment:4 Changed 9 years ago by malb

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

comment:5 Changed 9 years ago by AlexanderDreyer

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

comment:6 Changed 9 years ago by AlexanderDreyer

  • Cc AlexanderDreyer added

comment:7 Changed 9 years ago by leif

  • Cc leif added

comment:8 follow-up: Changed 9 years ago by leif

  • Status changed from needs_review to needs_work
  • Work issues set to Update SPKG.txt

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

comment:9 in reply to: ↑ 8 Changed 9 years ago by malb

  • Summary changed from fix variable substitution in PolyBoRi to fix variable substitution in PolyBoRi + finding M4RI

Replying to leif:

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

comment:10 Changed 9 years ago by malb

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

comment:11 Changed 9 years ago by malb

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.

comment:12 Changed 9 years ago by malb

  • Status changed from needs_work to needs_review

comment:13 Changed 9 years ago by mpatel

  • Cc mpatel added

comment:14 Changed 9 years ago by leif

  • Status changed from needs_review to needs_work

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

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

comment:15 Changed 9 years ago by malb

  • Status changed from needs_work to needs_review
  • Work issues Update SPKG.txt deleted

Updated accordingly.

comment:16 Changed 9 years ago by AlexanderDreyer

Meanwhile, I took a look at the surrounding code also. (Just to ensure, that the patches also do the right thing in other contexts.) It's a good patch and it may fix even more issues. So I give a positive review from the mathematical point of view. (If I'm allowed to do so.) For the technical viewpoint: I'm waiting now for sage -testall to finish.

comment:17 Changed 9 years ago by leif

Passed ptestlong with Sage 4.5.3.alpha0 and libm4ri-20100701.p1 from #9475 on Fedora 13 x86 (Pentium 4 Prescott, gcc 4.4.4).

So I can give "positive review" from the technical side. ;-)

comment:18 follow-up: Changed 9 years ago by leif

The updated SPKG.txt is ok, too. (And the upstream fixes also look reasonable btw.)

comment:19 in reply to: ↑ 18 Changed 9 years ago by leif

Replying to leif:

The updated SPKG.txt is ok, too.

... except for the date(s), but I'll assume the intention was to avoid naming Friday 13th and accept it. ;-)

comment:20 follow-up: Changed 9 years ago by malb

So we have a positive review then?

comment:21 in reply to: ↑ 20 ; follow-ups: Changed 9 years ago by leif

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.

comment:22 in reply to: ↑ 21 Changed 9 years ago by leif

Replying to leif:

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)

comment:23 in reply to: ↑ 21 Changed 9 years ago by AlexanderDreyer

  • Authors set to malb,PolyBoRi
  • Report Upstream changed from N/A to Fixed upstream, in a later stable release.
  • Reviewers set to leif,AlexanderDreyer
  • Status changed from needs_review to positive_review

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

comment:24 Changed 9 years ago by leif

  • Authors changed from malb,PolyBoRi to Alexander Dreyer, Martin Albrecht, Michael Brickenstein
  • Reviewers changed from leif,AlexanderDreyer to Martin Albrecht, Alexander Dreyer, Leif Leonhardy

Note to the release managers

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

comment:25 Changed 9 years ago by leif

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

comment:26 follow-up: Changed 9 years ago by leif

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.

comment:27 in reply to: ↑ 26 Changed 9 years ago by malb

Replying to leif:

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.

comment:28 follow-up: Changed 9 years ago by malb

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

comment:29 in reply to: ↑ 28 Changed 9 years ago by leif

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

comment:30 Changed 9 years ago by malb

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

That's the commit message, is that alright?

comment:31 Changed 9 years ago by leif

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.

comment:32 Changed 9 years ago by malb

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.

Changed 9 years ago by malb

Sage library patch fixing an issue with substitute_variable()

comment:33 Changed 9 years ago by leif

  • Description modified (diff)

comment:34 Changed 9 years ago by mpatel

  • Merged in set to sage-4.5.3.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:35 Changed 9 years ago by mpatel

  • Merged in changed from sage-4.5.3.alpha0 to sage-4.5.3.alpha1

comment:36 Changed 9 years ago by mpatel

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

comment:37 Changed 9 years ago by AlexanderDreyer

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.

Note: See TracTickets for help on using tickets.