#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:  sage6.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: 
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 sagedevel, 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)
Change History (36)
comment:1 followup: 2 Changed 12 years ago by
Component:  PLEASE CHANGE → elliptic curves 

Keywords:  mwrank added 
Owner:  changed from tbd to John Cremona 
comment:2 Changed 12 years ago by
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.
comment:3 followup: 4 Changed 12 years ago by
Authors:  → John Cremona 

Status:  new → needs_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 Changed 12 years ago by
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 2isogenous 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 2isogeny 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 2descent...done:\n now regulator = 1\nSaturating (bound = 100)...done:\n points were already saturated.\n\n\nRegulator = 1\n\nThe rank and full MordellWeil 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
Attachment:  trac_10108mwrank.2.patch added 

comment:5 Changed 12 years ago by
Reviewers:  → Mike Hansen 

Status:  needs_review → positive_review 
Looks good to me. I added a patch which fixes the indentation of the options blocks.
comment:6 Changed 12 years ago by
Status:  positive_review → needs_work 

Please fix the ticket number (10108, NOT 10105) in the patch
Changed 12 years ago by
Attachment:  trac_10105mwrank.patch added 

renamed version of previous  applies to 4.6.rc0
Changed 12 years ago by
Attachment:  trac_10108mwrank.3.patch added 

comment:7 Changed 12 years ago by
Status:  needs_work → needs_review 

Apply only trac_10108mwrank.3.patch (and sorry for the mess  previous ones can be deleted).
Changed 12 years ago by
Attachment:  trac_10108mwrank.4.patch added 

Ticket number fixed, apply only this patch
comment:8 followup: 9 Changed 12 years ago by
Status:  needs_review → positive_review 

John, I seem to have confused you :) Never mind, I made the fix myself.
comment:9 Changed 12 years ago by
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
Status:  positive_review → needs_work 

This patch gives trouble for me when merging it as part of a potential sage4.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/sage4.6.1.alpha0x86_64Linux/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/sage4.6.1.alpha0x86_64Linux/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/mnt/usb1/scratch/jdemeyer/sage4.6.1.alpha0x86_64Linux/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/mnt/usb1/scratch/jdemeyer/sage4.6.1.alpha0x86_64Linux/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/sage4.6.1.alpha0x86_64Linux/local/lib/python/sitepackages/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
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
Milestone:  sage5.11 → sage5.12 

comment:13 Changed 9 years ago by
Branch:  → u/cremona/ticket/10108 

Modified:  Aug 13, 2013, 3:35:53 PM → Aug 13, 2013, 3:35:53 PM 
comment:14 Changed 9 years ago by
Commit:  → 5b664d97bd33efcdc415b1e0342f8e3922658f26 

Status:  needs_work → needs_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:
520cfca  Merge branch 'master' of git://github.com/sagemath/sage into build_system

38d22b7  Merge branch 'master' of ssh://trac.sagemath.org:2222/sage into build_system

139dcf5  Merge branch 'build_system' of git://github.com/sagemath/sage into build_system

17e17dd  Merge branch 'master' of ssh://trac.sagemath.org:2222/sage into build_system

b06bd7c  Merge branch 'master' of git://github.com/sagemath/sage

858bb95  Merge branch 'master' of git://github.com/sagemath/sage

0523e0d  Merge branch 'master' of git://github.com/sagemath/sage

88ffd55  Merge branch 'master' of git://github.com/sagemath/sage

68d0a5d  Merge branch 'master' of git://github.com/sagemath/sage

057b3cd  Merge branch 'master' of git://github.com/sagemath/sage

comment:15 Changed 9 years ago by
Reviewers:  Mike Hansen → Mike Hansen, Chris Wuthrich 

Status:  needs_review → needs_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\n2adic index bound = 2\nBy Lemma 5.1(a), 2adic index = 1\n2adic 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)\ttrivial\n(1,0,2,4,1)\ttrivial\nTrying positive a from 1 up to 1 (...then nonsquare 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 2descent via multiplicationby2 map\nRank = 0\nRank of S^2(E) = 0\n\nProcessing points found during 2descent...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\n2adic index bound = 2\nBy Lemma 5.1(a), 2adic index = 1\n2adic 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)\ttrivial\n(1,0,2,4,1)\ttrivial\nTrying positive a from 1 up to 1 (...then nonsquare 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 2descent via multiplicationby2 map\nRank = 0\nRank of S^2(E) = 0\n\nProcessing points found during 2descent...done:\n now regulator = 1\n\n\nRegulator = 1\n\nThe rank and full MordellWeil 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
Branch:  u/cremona/ticket/10108 → u/wuthrich/ticket/10108 

Commit:  5b664d97bd33efcdc415b1e0342f8e3922658f26 → e4f365ae32a8804072b839205566fede75066431 
comment:17 Changed 9 years ago by
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 longwinded 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
Status:  needs_work → needs_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
Status:  needs_review → needs_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 MordellWeil 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
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
From my develop to this branch u/wuthrich/..., it only compiles mwrank.py (as I would expect).
comment:22 followup: 27 Changed 9 years ago by
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 repulled 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\n2adic index bound = 2\nBy Lemma 5.1(a), 2adic index = 1\n2adic 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)\ttrivial\n(1,0,2,4,1)\ttrivial\nTrying positive a from 1 up to 1 (...then nonsquare 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 2descent via multiplicationby2 map\nRank = 0\nRank of S^2(E) = 0\n\nProcessing points found during 2descent...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 MordellWeil basis have been determined" or "The rank and full MordellWeil 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 followup: 24 Changed 9 years ago by
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 Changed 9 years ago by
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
Commit:  e4f365ae32a8804072b839205566fede75066431 → 0fb4c7dadbe5b82ffccff51cccfc03b33ca895f4 

Branch pushed to git repo; I updated commit sha1. New commits:
0fb4c7d  Trac 10108: Change and shorten one doctest

comment:27 Changed 9 years ago by
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
Status:  needs_work → positive_review 

comment:29 Changed 9 years ago by
Milestone:  sage6.1 → sage6.2 

comment:30 Changed 9 years ago by
Resolution:  → fixed 

Status:  positive_review → closed 
I have a patch for this which I will post soon.