Opened 12 years ago

Closed 9 years ago

Last modified 9 years ago

#10108 closed defect (fixed)

Calling mwrank(-10) hangs Sage, but uses very little CPU time

Reported by: David Kirkby Owned by: John Cremona
Priority: major Milestone: sage-6.2
Component: elliptic curves Keywords: mwrank
Cc: John Cremona Merged in:
Authors: John Cremona Reviewers: Mike Hansen, Chris Wuthrich
Report Upstream: N/A Work issues:
Branch: u/wuthrich/ticket/10108 (Commits, GitHub, GitLab) Commit: 0fb4c7dadbe5b82ffccff51cccfc03b33ca895f4
Dependencies: Stopgaps:

Status badges

Description

Following some very quick hacks at using "fuzz testing" techniques, I found that

sage: mwrank(-10)

just hangs, but does not appear to be using any CPU time. Although I don't know what this is supposed to do, from discussions on sage-devel, I understand my suspicions this behavior is an error were correct.

Can someone please select the component appropriately, as I don't have a clue myself.

Attachments (5)

trac_10108-mwrank.patch (6.6 KB) - added by John Cremona 12 years ago.
applies to 4.6.alpha3
trac_10108-mwrank.2.patch (6.6 KB) - added by Mike Hansen 12 years ago.
trac_10105-mwrank.patch (6.6 KB) - added by John Cremona 12 years ago.
renamed version of previous -- applies to 4.6.rc0
trac_10108-mwrank.3.patch (6.6 KB) - added by John Cremona 12 years ago.
trac_10108-mwrank.4.patch (6.6 KB) - added by Jeroen Demeyer 12 years ago.
Ticket number fixed, apply only this patch

Download all attachments as: .zip

Change History (36)

comment:1 Changed 12 years ago by John Cremona

Component: PLEASE CHANGEelliptic curves
Keywords: mwrank added
Owner: changed from tbd to John Cremona

I have a patch for this which I will post soon.

comment:2 in reply to:  1 Changed 12 years ago by John Cremona

Replying to cremona:

I have a patch for this which I will post soon.

Delays caused by break in internet access -- hope to post patch Sunday.

Changed 12 years ago by John Cremona

Attachment: trac_10108-mwrank.patch added

applies to 4.6.alpha3

comment:3 Changed 12 years ago by John Cremona

Authors: John Cremona
Status: newneeds_review

This was harder than expected. Without either (1) rewriting mwrank's in put parser or (2) writing a full parser within Sage and only sending to mwrank when certainly correct, which I do not want to do. If you feed mwrank correct but incomplete input (such as <5 integers separated by whitespace) it quietly waits for the rest of the input (with no prompts).

To get around this I pad the strings sent to mwrank with ' 0 0 0 0 0 ' which means that this never happens, and then to get repeated calls to mwrank to work properly need a bit of fiddling. I tested the patch on two machines (4.6.alpha3).

comment:4 in reply to:  3 Changed 12 years ago by David Kirkby

Replying to cremona:

This was harder than expected. Without either (1) rewriting mwrank's in put parser or (2) writing a full parser within Sage and only sending to mwrank when certainly correct, which I do not want to do. If you feed mwrank correct but incomplete input (such as <5 integers separated by whitespace) it quietly waits for the rest of the input (with no prompts).

If this hard, then perhaps it's more effort to fix properly than it is worth. You are a better judge of that than me.

I can't help feeling if this is supposed to take 5 integers then it should take 5, and not accept fewer or more, as it does. For example:

sage: mwrank('1 2 3')
"Curve [0,0,0,1,2] :     \n1 points of order 2:\n[-1:0:1]\n\nUsing 2-isogenous curve [0,6,0,-7,0] (minimal model [0,0,0,-19,30])\n-------------------------------------------------------\nFirst step, determining 1st descent Selmer groups\n-------------------------------------------------------\nAfter first local descent, rank bound = 0\nrk(S^{phi}(E'))=        1\nrk(S^{phi'}(E))=        1\n\n-------------------------------------------------------\nSecond step, determining 2nd descent Selmer groups\n-------------------------------------------------------\n...skipping since we already know rank=0\nAfter second local descent, rank bound = 0\nrk(phi'(S^{2}(E)))=     1\nrk(phi(S^{2}(E')))=     1\nrk(S^{2}(E))=   1\nrk(S^{2}(E'))=  2\n\nThird step, determining E(Q)/phi(E'(Q)) and E'(Q)/phi'(E(Q))\n-------------------------------------------------------\n1. E(Q)/phi(E'(Q))\n-------------------------------------------------------\n(c,d)  =(-3,4)\n(c',d')=(6,-7)\nThis component of the rank is 0\n-------------------------------------------------------\n2. E'(Q)/phi'(E(Q))\n-------------------------------------------------------\nThis component of the rank is 0\n\n-------------------------------------------------------\nSummary of results:\n-------------------------------------------------------\n        rank(E) = 0\n        #E(Q)/2E(Q) = 2\n\nInformation on III(E/Q):\n        #III(E/Q)[phi']    = 1\n        #III(E/Q)[2]       = 1\n\nInformation on III(E'/Q):\n        #phi'(III(E/Q)[2]) = 1\n        #III(E'/Q)[phi]    = 1\n        #III(E'/Q)[2]      = 1\n\n\nUsed descent via 2-isogeny with isogenous curve E' = [0,0,0,-19,30]\nRank = 0\nRank of S^2(E)  = 1\nRank of S^2(E') = 2\nRank of S^phi(E') = 1\nRank of S^phi'(E) = 1\n\nSearching for points (bound = 8)...done:\n  found points of rank 0\n  and regulator 1\nProcessing points found during 2-descent...done:\n  now regulator = 1\nSaturating (bound = 100)...done:\n  points were already saturated.\n\n\nRegulator = 1\n\nThe rank and full Mordell-Weil basis have been determined unconditionally.\n (0.055625 seconds)"

(It would also be nice if those \n's actually created a new line, as I expect they are supposed to do, but that's another issue entirely.)

Again, I don't feel able to review the Python.

Changed 12 years ago by Mike Hansen

Attachment: trac_10108-mwrank.2.patch added

comment:5 Changed 12 years ago by Mike Hansen

Reviewers: Mike Hansen
Status: needs_reviewpositive_review

Looks good to me. I added a patch which fixes the indentation of the options blocks.

comment:6 Changed 12 years ago by Jeroen Demeyer

Status: positive_reviewneeds_work

Please fix the ticket number (10108, NOT 10105) in the patch

Changed 12 years ago by John Cremona

Attachment: trac_10105-mwrank.patch added

renamed version of previous -- applies to 4.6.rc0

Changed 12 years ago by John Cremona

Attachment: trac_10108-mwrank.3.patch added

comment:7 Changed 12 years ago by John Cremona

Status: needs_workneeds_review

Apply only trac_10108-mwrank.3.patch (and sorry for the mess -- previous ones can be deleted).

Changed 12 years ago by Jeroen Demeyer

Attachment: trac_10108-mwrank.4.patch added

Ticket number fixed, apply only this patch

comment:8 Changed 12 years ago by Jeroen Demeyer

Status: needs_reviewpositive_review

John, I seem to have confused you :-) Never mind, I made the fix myself.

comment:9 in reply to:  8 Changed 12 years ago by John Cremona

Replying to jdemeyer:

John, I seem to have confused you :-) Never mind, I made the fix myself.

Very sorry - -first I thought it was the patch's name, then the comment in the doctest... but at least the bugfix works!

comment:10 Changed 12 years ago by Jeroen Demeyer

Status: positive_reviewneeds_work

This patch gives trouble for me when merging it as part of a potential sage-4.6.1.alpha0. For some reason I cannot explain, I get the following error when running sage -t devel/sage/sage/interfaces/mwrank.py:

sage -t  "devel/sage/sage/interfaces/mwrank.py"
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/sage-4.6.1.alpha0-x86_64-Linux/devel/sage/sage/interfaces/mwrank.py", line 111:
    sage: mwrank([0,-1,1,0,0])
Exception raised:
    Traceback (most recent call last):
      File "/mnt/usb1/scratch/jdemeyer/sage-4.6.1.alpha0-x86_64-Linux/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/mnt/usb1/scratch/jdemeyer/sage-4.6.1.alpha0-x86_64-Linux/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/mnt/usb1/scratch/jdemeyer/sage-4.6.1.alpha0-x86_64-Linux/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_4[3]>", line 1, in <module>
        mwrank([Integer(0),-Integer(1),Integer(1),Integer(0),Integer(0)])###line 111:
    sage: mwrank([0,-1,1,0,0])
      File "/mnt/usb1/scratch/jdemeyer/sage-4.6.1.alpha0-x86_64-Linux/local/lib/python/site-packages/sage/interfaces/mwrank.py", line 139, in __call__
        raise ValueError, 'Invalid input (%s) to mwrank'%cmd
    ValueError: Invalid input ([0, -1, 1, 0, 0]) to mwrank
**********************************************************************

What is strange is that simply doing

sage: mwrank([0,-1,1,0,0])

in a "real" Sage session works. So it works in Sage, but not in a doctest. I will need to investigate further.

comment:11 Changed 12 years ago by John Cremona

I think I can explain this. The problem to be solved for this ticket was that if mwrank is given incomplete but otherwise correct input, it just waits for the rest of the input, making Sage appear to hang. To fix this I made sure that the input provided by Sage always has some other stuff appended to it, so mwrank never has insufficient input. But then, the *next* time input is sent to mwrank, there is likely to be still some of that extra stuff in its input buffer. To get around that (I thought) I made sure that mwrank was restarted at every call.

Clearly what I did was insufficient, but this does explain who the order of executing commands does matter.

comment:12 Changed 9 years ago by Jeroen Demeyer

Milestone: sage-5.11sage-5.12

comment:13 Changed 9 years ago by John Cremona

Branch: u/cremona/ticket/10108
Modified: Aug 13, 2013, 3:35:53 PMAug 13, 2013, 3:35:53 PM

comment:14 Changed 9 years ago by John Cremona

Commit: 5b664d97bd33efcdc415b1e0342f8e3922658f26
Status: needs_workneeds_review

The git commit does a better jpb than the old patch: I implemented a new function validate_mwrank_input which accepts (and to a small degree standardises) valid mwrank inputs using some regular expression analysis. This means that mwrank will only get sent a valid string.

This is now ready for review.


Last 10 new commits:

520cfcaMerge branch 'master' of git://github.com/sagemath/sage into build_system
38d22b7Merge branch 'master' of ssh://trac.sagemath.org:2222/sage into build_system
139dcf5Merge branch 'build_system' of git://github.com/sagemath/sage into build_system
17e17ddMerge branch 'master' of ssh://trac.sagemath.org:2222/sage into build_system
b06bd7cMerge branch 'master' of git://github.com/sagemath/sage
858bb95Merge branch 'master' of git://github.com/sagemath/sage
0523e0dMerge branch 'master' of git://github.com/sagemath/sage
88ffd55Merge branch 'master' of git://github.com/sagemath/sage
68d0a5dMerge branch 'master' of git://github.com/sagemath/sage
057b3cdMerge branch 'master' of git://github.com/sagemath/sage

comment:15 Changed 9 years ago by wuthrich

Reviewers: Mike HansenMike Hansen, Chris Wuthrich
Status: needs_reviewneeds_work

I have two tests that do not pass. (I have rebased the branch to 6.1.rc0; so maybe mwrank changed in the meantime.) I looks like

**********************************************************************
File "mwrank.py", line 233, in sage.interfaces.mwrank.Mwrank_class.__call__
Failed example:
    mwrank('0 -1 1 0 0')
Expected:
    'Curve [0,-1,1,0,0] :\tBasic pair: I=16, J=-304\ndisc=-76032\n2-adic index bound = 2\nBy Lemma 5.1(a), 2-adic index = 1\n2-adic index = 1\nOne (I,J) pair\nLooking for quartics with I = 16, J = -304\nLooking for Type 3 quartics:\nTrying positive a from 1 up to 1 (square a first...)\n(1,0,-4,4,0)\t--trivial\n(1,0,2,4,1)\t--trivial\nTrying positive a from 1 up to 1 (...then non-square a)\nFinished looking for Type 3 quartics.\nMordell rank contribution from B=im(eps) = 0\nSelmer  rank contribution from B=im(eps) = 0\nSha     rank contribution from B=im(eps) = 0\nMordell rank contribution from A=ker(eps) = 0\nSelmer  rank contribution from A=ker(eps) = 0\nSha     rank contribution from A=ker(eps) = 0\n\nUsed full 2-descent via multiplication-by-2 map\nRank = 0\nRank of S^2(E)  = 0\n\nProcessing points found during 2-descent...done:\n  now regulator = 1\n\n\nRegulator = 1\n\nThe rank has been determined unconditionally.\n\n...'
Got:
    'Curve [0,-1,1,0,0] :\tBasic pair: I=16, J=-304\ndisc=-76032\n2-adic index bound = 2\nBy Lemma 5.1(a), 2-adic index = 1\n2-adic index = 1\nOne (I,J) pair\nLooking for quartics with I = 16, J = -304\nLooking for Type 3 quartics:\nTrying positive a from 1 up to 1 (square a first...)\n(1,0,-4,4,0)\t--trivial\n(1,0,2,4,1)\t--trivial\nTrying positive a from 1 up to 1 (...then non-square a)\nFinished looking for Type 3 quartics.\nMordell rank contribution from B=im(eps) = 0\nSelmer  rank contribution from B=im(eps) = 0\nSha     rank contribution from B=im(eps) = 0\nMordell rank contribution from A=ker(eps) = 0\nSelmer  rank contribution from A=ker(eps) = 0\nSha     rank contribution from A=ker(eps) = 0\n\nUsed full 2-descent via multiplication-by-2 map\nRank = 0\nRank of S^2(E)  = 0\n\nProcessing points found during 2-descent...done:\n  now regulator = 1\n\n\nRegulator = 1\n\nThe rank and full Mordell-Weil basis have been determined unconditionally.\n (0.006 seconds)'
**********************************************************************
File "mwrank.py", line 239, in sage.interfaces.mwrank.Mwrank_class.__call__
Failed example:
    "Rank = 0" in s and "The rank has been determined unconditionally" in s
Expected:
    True
Got:
    False
**********************************************************************

comment:16 Changed 9 years ago by wuthrich

Branch: u/cremona/ticket/10108u/wuthrich/ticket/10108
Commit: 5b664d97bd33efcdc415b1e0342f8e3922658f26e4f365ae32a8804072b839205566fede75066431

comment:17 Changed 9 years ago by John Cremona

Thanks. Since you did a rebase I can't see what you changed additionally, but I seem to have slipped up in testing (in one example) that the long-winded mwrank output is good where because of the time output one cannot just do a literal comparison. Testing...

comment:18 Changed 9 years ago by John Cremona

Status: needs_workneeds_review

OK, works for me (though I think my earlier branch did too!). I have set this back to "needs review" and Chris you can set it to positive review.

comment:19 Changed 9 years ago by wuthrich

Status: needs_reviewneeds_work

Ah interesting.

I did not change anything. I litterally took your mwrank.py and copied it into a branch based at develop, checking that this file was not touch on since then.

So I get the above errors and you do not get them. So it seems that mwrank does not give back the same string for you than for me. The issue (in both failures) is the final sentence. I get

"The rank and full Mordell-Weil basis have been determined unconditionally."

while we test for

"The rank has been determined unconditionally."

Is there a change in mwrank that I have missed?

(I revert back to needs_work).

comment:20 Changed 9 years ago by John Cremona

That is weird; I misunderstood. No changes at all in mwrank. But when I switch branches there is more recompilation than I would have expected (mpir rebuilds) for this. Very odd! I'll look into it further.

comment:21 Changed 9 years ago by wuthrich

From my develop to this branch u/wuthrich/..., it only compiles mwrank.py (as I would expect).

comment:22 Changed 9 years ago by John Cremona

I think there was some conflict between the state of the original branch of mine called ticket/10108 and the branch I had after checking out yours. So I switched back to develop, deleted the branch ticket/10108 altogether and re-pulled it. Now my git log has the right look to it:

commit e4f365ae32a8804072b839205566fede75066431
Author: Chris Wuthrich <christian.wuthrich@gmail.com>
Date:   Sat Jan 25 20:33:23 2014 +0000

    Trac #10108: more robust interface to mwrank

commit 1bd331978c99681b70e4877fa3149b0c9adf47ce
Author: Volker Braun <vbraun.name@gmail.com>
Date:   Sat Jan 25 01:41:12 2014 +0000

    Updated Sage version to 6.1.rc0

so I rebuild (i.e. "make"). And sage/interfaces/mwrank.py passes its tests. And specifically when in Sage I run

sage: mwrank('0 -1 1 0 0')

the output string is

'Curve [0,-1,1,0,0] :\tBasic pair: I=16, J=-304\ndisc=-76032\n2-adic index bound = 2\nBy Lemma 5.1(a), 2-adic index = 1\n2-adic index = 1\nOne (I,J) pair\nLooking for quartics with I = 16, J = -304\nLooking for Type 3 quartics:\nTrying positive a from 1 up to 1 (square a first...)\n(1,0,-4,4,0)\t--trivial\n(1,0,2,4,1)\t--trivial\nTrying positive a from 1 up to 1 (...then non-square a)\nFinished looking for Type 3 quartics.\nMordell rank contribution from B=im(eps) = 0\nSelmer  rank contribution from B=im(eps) = 0\nSha     rank contribution from B=im(eps) = 0\nMordell rank contribution from A=ker(eps) = 0\nSelmer  rank contribution from A=ker(eps) = 0\nSha     rank contribution from A=ker(eps) = 0\n\nUsed full 2-descent via multiplication-by-2 map\nRank = 0\nRank of S^2(E)  = 0\n\nProcessing points found during 2-descent...done:\n  now regulator = 1\n\n\nRegulator = 1\n\nThe rank has been determined unconditionally.\n\n (0.004001 seconds)'

Now I see what is happening! The curve has rank 0; so mwrank does not do the usual saturation step of making sure that we have the full MW group and not a subgroup of finite index; there is a flag (in my C++ code) called sat_ok which is set to 1 if saturation suceeds, 0 if it fails -- and is uninitialized otherwise! So it will be random for a rank 0 curve where one sees the additional string "The rank and full Mordell-Weil basis have been determined" or "The rank and full Mordell-Weil basis have been determined".

Obviously I will correct this in eclib, which is timely since I was planning tp update Sage's version sson anyway. Meanwhile we'll have to sidestep this by changing that doctest sneakily. I suggest first deleting the variable sentence, effectively moving the "..." forward; and in the next line just test for "Rank = 0" in s.

Shall I do that or will you?

comment:23 Changed 9 years ago by wuthrich

I can do it.

Do you want to keep the lengthy output to be tested ? Or would not 'Curve [0,-1,1,0,0] :\tBasic pair: I=16, J=-304 ... determined unconditionally ...' be enough ?

comment:24 in reply to:  23 Changed 9 years ago by John Cremona

Replying to wuthrich:

I can do it.

Thanks.

Do you want to keep the lengthy output to be tested ? Or would not 'Curve [0,-1,1,0,0] :\tBasic pair: I=16, J=-304 ... determined unconditionally ...' be enough ?

That would be enough, certainly as we also check that "Rank = 0" is in there.

comment:25 Changed 9 years ago by git

Commit: e4f365ae32a8804072b839205566fede750664310fb4c7dadbe5b82ffccff51cccfc03b33ca895f4

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

0fb4c7dTrac 10108: Change and shorten one doctest

comment:26 Changed 9 years ago by wuthrich

I run the tests now.

comment:27 in reply to:  22 Changed 9 years ago by John Cremona

Replying to cremona:

Obviously I will correct this in eclib, which is timely since I was planning to update Sage's version soon anyway.

The eclib patch is visible here:

https://github.com/JohnCremona/eclib/commit/d1ab6a59103fb86730f1e668e70ecf010ee37b2d

and the new version (with a lot more than just this change) is in a new spkg at #15738. But this ticket does not need that.

comment:28 Changed 9 years ago by wuthrich

Status: needs_workpositive_review

comment:29 Changed 9 years ago by For batch modifications

Milestone: sage-6.1sage-6.2

comment:30 Changed 9 years ago by Volker Braun

Resolution: fixed
Status: positive_reviewclosed

comment:31 Changed 9 years ago by Volker Braun

See #15798 for a followup ticket

Note: See TracTickets for help on using tickets.