Opened 21 months ago
Closed 12 months ago
#25301 closed defect (fixed)
sparse_2term_quotient_only_pm1 gives different results depending on set iteration order
Reported by:  embray  Owned by:  

Priority:  major  Milestone:  sage8.7 
Component:  python3  Keywords:  
Cc:  cremona, was, davidloeffler, klui, mderickx, pbruin  Merged in:  
Authors:  John Cremona, Frédéric Chapoton  Reviewers:  John Cremona, Erik Bray, Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  19af688 (Commits)  Commit:  19af6889ef08455e4c560d56e382d8921f9ed3f4 
Dependencies:  Stopgaps: 
Description
This function in the sage.modular.modsym.relation_matrix_pyx
takes a set as input, and gives different results depending on the iteration order of the set (which is arbitrary, and often different on Python 2 vs Python 3).
While this in itself is not at all a bug, but a feature of the algorithm, this has far reaching effect on the results of other computations, resulting in tests that fail on Python 3 since the set ordering is definitely not the same (but the same tests could just as easily fail on Python 2 in principle).
Not sure yet what the best approach is to this.
Change History (41)
comment:1 Changed 19 months ago by
 Milestone changed from sage8.3 to sagewishlist
comment:2 Changed 16 months ago by
 Branch set to u/chapoton/25301
 Commit set to 92ce67cc8d88b4b1ff6281a09b85834df3c9c94a
comment:3 Changed 16 months ago by
 Commit changed from 92ce67cc8d88b4b1ff6281a09b85834df3c9c94a to edf3ee9a40e82b11a38f6caab8938a18d9c3a3e6
Branch pushed to git repo; I updated commit sha1. New commits:
edf3ee9  trying to sort

comment:4 Changed 16 months ago by
 Commit changed from edf3ee9a40e82b11a38f6caab8938a18d9c3a3e6 to 415800d1512cce9eb8f9b703b66976c7dc24d75b
Branch pushed to git repo; I updated commit sha1. New commits:
415800d  fix doctests in /modsym/heilbronn

comment:5 Changed 16 months ago by
 Cc cremona was added
So the question is :
should we just change the doctests or try to make them more robust ?
The opinion of some experts in modular symbols and Hecke operators is required..
comment:6 Changed 16 months ago by
 Commit changed from 415800d1512cce9eb8f9b703b66976c7dc24d75b to 60a22e502300f00bf16e750aa721055f241f0167
Branch pushed to git repo; I updated commit sha1. New commits:
60a22e5  another more robust test

comment:7 Changed 16 months ago by
 Commit changed from 60a22e502300f00bf16e750aa721055f241f0167 to 36f6be1dfd5bfd7fdbfd03d795ff53a97d090269
comment:8 Changed 15 months ago by
 Branch u/chapoton/25301 deleted
 Commit 36f6be1dfd5bfd7fdbfd03d795ff53a97d090269 deleted
a branch making some doctests more robust was moved to #26673
comment:9 Changed 13 months ago by
 Branch set to public/ticket/25301
 Commit set to 12820008a39ed91b90196d43ab5401113ddcede3
comment:10 Changed 13 months ago by
 Cc davidloeffler klui mderickx pbruin added
PLEASE, opinion from experts of modular symbols is required on the failing doctests!
Tell us if either
(1) the current change only modifies the bases of modular symbols and is harmless. We just need to change the doctests.
or
(2) at least some of the failing doctests are real failures, with bad and wrong answers
comment:11 Changed 13 months ago by
 Milestone changed from sagewishlist to sage8.6
 Status changed from new to needs_info
comment:12 Changed 13 months ago by
I'll look at it. (http://homepages.warwick.ac.uk/staff/J.E.Cremona/theses/index.html should qualify me)
comment:13 Changed 13 months ago by
I have started working through these, so far have done 3 out of 5 files in sage/modular and all are OK (i.e. the new output is equally valid). It will take a while to do the rest and I may not get back to it before the middle of next week for obvious reasons.
comment:14 Changed 13 months ago by
In several places the difference is that a different basis is being used for some vector space, so the matrices of Hecke operators look different. One plan might be to tag the matrix display as #random but to include the characteristic polynomial in the output. I am not currently doing this.
comment:15 Changed 13 months ago by
I'm having trouble with the test in line 217 of modular/modform/modular added for #8018 in 2010, authored by R Beezer and reviewed by AlexGhitza?.
comment:16 followup: ↓ 17 Changed 13 months ago by
Concerning the idea of tagging with # random
, this should not be necessary: instead one will change the doctests to their new values. The new values will hopefuly work in both python2 and python3 without problem. The only issue is to be sure that nothing got broken by all these changes of bases. This is exactly what you have started to do, thanks a lot.
In comment:15, you mean line 217 of modular/modform/numerical
, right ?
comment:17 in reply to: ↑ 16 Changed 13 months ago by
Replying to chapoton:
Concerning the idea of tagging with
# random
, this should not be necessary: instead one will change the doctests to their new values. The new values will hopefuly work in both python2 and python3 without problem. The only issue is to be sure that nothing got broken by all these changes of bases. This is exactly what you have started to do, thanks a lot.
OK
In comment:15, you mean line 217 of
modular/modform/numerical
, right ?
yes
I am getting back to this now.
comment:18 Changed 13 months ago by
 Commit changed from 12820008a39ed91b90196d43ab5401113ddcede3 to c65b74696ceff7067e81c0ef607c9778957d8502
Branch pushed to git repo; I updated commit sha1. New commits:
c65b746  #25301: fix all but one doctest in sage.modular

comment:19 Changed 13 months ago by
The latest commit fixes all but one doctest in sage/modular, the last one being the one I mentioned above in the numerical section. It is hard to get a new example which works since the code finds a random linear combination of a few Tp for small p, which is different every time  yet one needs to find one such which has eigenvalues quite close together. I will come back to this.
I mostly just replaced the expected output with what the actual output now is, after doing some tests to check that the new output is reasonable. In a few places I adapted the doctest to be just as useful but more canonical. In one place I reworded a docstring (when the output of some modular symbol operation is not literally a monomial modular symbol but a linear combination of these).
I'm adding David Loeffler to the notification list since some of the files I touched are (I think) written and/or worked on by him. Meanwhile I am looking to see if there are any failing doctests outside sage/modular.
comment:20 Changed 13 months ago by
 Reviewers set to John Cremona
 Status changed from needs_info to needs_review
comment:21 Changed 13 months ago by
 Commit changed from c65b74696ceff7067e81c0ef607c9778957d8502 to 00f5218bfe205beccf73102a2e5df07a7c172eda
Branch pushed to git repo; I updated commit sha1. New commits:
00f5218  #25301: fix doctests outside sage.modular

comment:22 Changed 13 months ago by
There were 6 files outside sage/modular with doctests which needed changing: done.
That just leaves the numerical one which I will look at again now.
comment:23 Changed 13 months ago by
 Commit changed from 00f5218bfe205beccf73102a2e5df07a7c172eda to 356403a6cd93c5e2db964b0f61f16a54f4422117
Branch pushed to git repo; I updated commit sha1. New commits:
356403a  #25301: fix last doctest

comment:24 Changed 13 months ago by
OK all done.
I put myself down as a reviewer but we need further review: I only tested with default python, and also it would be good for another pair of eyes to look at all the doctests I changed.
comment:25 Changed 13 months ago by
Thanks John for your hard work on this ticket, which is of major importance in our progress towards python3.
comment:26 Changed 13 months ago by
Good, the bot is fully green.
comment:27 Changed 13 months ago by
And this fixes all doctests in 14 files in python3.
So I am extremely tempted to give it a positive review...
comment:28 Changed 13 months ago by

src/sage/modular/modsym/relation_matrix.py
diff git a/src/sage/modular/modsym/relation_matrix.py b/src/sage/modular/modsym/relation_matrix.py index 5e968c3..8e92a7c 100644
a b def relation_matrix_wtk_g0(syms, sign, field, sparse): 496 496 # Let rels = rels union I relations. 497 497 rels.update(modI_relations(syms, sign)) 498 498 499 rels = list(rels)499 rels = sorted(rels) 500 500 # should be sorted(rels), but this breaks many doctests 501 501 502 502 if syms._apply_S_only_0pm1() and is_RationalField(field):
There's a still a comment saying "should be sorted(rels)" when now it is that.
+1 from me unless there's any good reason not to sort (is this a major performance regression anywhere? We haven't really gotten anywhere with performance testing so who knows...)
comment:29 Changed 13 months ago by
 Commit changed from 356403a6cd93c5e2db964b0f61f16a54f4422117 to a59f31865b0f8e1e777f4829537e7b284a4d3c52
comment:30 Changed 13 months ago by
In my idea, this change should not impact the performance at all. We are just sorting a bunch of pairs of integers, no big deal.
@cremona: do you have some worries on this question of performance regression, John ? What would be a good test to run to make sure that no speed is lost ?
comment:31 followup: ↓ 32 Changed 13 months ago by
Before
sage: %timeit ModularSymbols(4691).basis() 1 loop, best of 3: 1.28 s per loop
After
sage: %timeit ModularSymbols(4691).basis() 1 loop, best of 3: 1.27 s per loop
So I do not see any significant difference here.
comment:32 in reply to: ↑ 31 Changed 13 months ago by
Replying to chapoton:
Before
sage: %timeit ModularSymbols(4691).basis() 1 loop, best of 3: 1.28 s per loopAfter
sage: %timeit ModularSymbols(4691).basis() 1 loop, best of 3: 1.27 s per loopSo I do not see any significant difference here.
That is just the sort of test I was going to suggest, but 4691 is prime and that is a very special case, so I suggest (as you have the new and old code up and running I think it is easier for you than for me right now) that you also try the following levels: N with several prime factors (e.g. 2310), larger prime powers, and a combination of the above such as 1680.
comment:33 Changed 13 months ago by
before:
sage: %timeit ModularSymbols(2310).basis() 1 loop, best of 3: 6.53 s per loop sage: %timeit ModularSymbols(1680).basis() 1 loop, best of 3: 2.06 s per loop sage: %timeit ModularSymbols(5**5).basis() 1 loop, best of 3: 8.59 s per loop (fluctuates between 8.59 and 8.65)
after:
sage: %timeit ModularSymbols(2310).basis() 1 loop, best of 3: 6.52 s per loop (or 6.53) sage: %timeit ModularSymbols(1680).basis() 1 loop, best of 3: 2.07 s per loop sage: %timeit ModularSymbols(5**5).basis() 1 loop, best of 3: 8.68 s per loop (fluctuates between 8.66 and 8.73)
So there is no meaningful difference in the first two cases, I think. The last one for 5**5
fluctuates more than the others, but seems to be consistently slightly slower.
comment:34 Changed 13 months ago by
 Reviewers changed from John Cremona to John Cremona, Erik Bray
 Status changed from needs_review to positive_review
Okay, thank you for checking. I did not think it would likely make a significant difference, but I wasn't exactly sure how best to benchmark that.
comment:35 Changed 13 months ago by
 Reviewers changed from John Cremona, Erik Bray to John Cremona, Erik Bray, Frédéric Chapoton
comment:36 Changed 12 months ago by
 Milestone changed from sage8.6 to sage8.7
Retarging tickets optimistically to the next milestone. If you are responsible for this ticket (either its reporter or owner) and don't believe you are likely to complete this ticket before the next release (8.7) please retarget this ticket's milestone to sagepending or sagewishlist.
comment:37 Changed 12 months ago by
 Status changed from positive_review to needs_work
On 32bit:
********************************************************************** File "src/sage/modular/modform/numerical.py", line 75, in sage.modular.modform.numerical.NumericalEigenforms Failed example: n.ap(2) # rel tol 2e15 Expected: [3.0, 1.6180339887498947, 0.6180339887498968] Got: [3.0, 1.6180339887498965, 0.6180339887498943] Tolerance exceeded in 1 of 3: 0.6180339887498968 vs 0.6180339887498943, tolerance 4e15 > 2e15 ********************************************************************** File "src/sage/modular/modform/numerical.py", line 77, in sage.modular.modform.numerical.NumericalEigenforms Failed example: n.systems_of_eigenvalues(7) # rel tol 2e15 Expected: [ [1.6180339887498947, 2.2360679774997894, 3.2360679774997894], [0.6180339887498968, 2.236067977499788, 1.2360679774997936], [3.0, 4.0, 6.0] ] Got: [ [1.6180339887498965, 2.2360679774997894, 3.236067977499793], [0.6180339887498943, 2.2360679774997894, 1.2360679774997887], [3.0, 4.0, 6.0] ] Tolerance exceeded in 2 of 9: 0.6180339887498968 vs 0.6180339887498943, tolerance 4e15 > 2e15 1.2360679774997936 vs 1.2360679774997887, tolerance 4e15 > 2e15 ********************************************************************** File "src/sage/modular/modform/numerical.py", line 89, in sage.modular.modform.numerical.NumericalEigenforms Failed example: n.eigenvalues([2,3,5]) # rel tol 2e15 Expected: [[3.0, 1.6180339887498947, 0.6180339887498968], [4.0, 2.2360679774997894, 2.236067977499788], [6.0, 3.2360679774997894, 1.2360679774997936]] Got: [[3.0, 1.6180339887498965, 0.6180339887498943], [4.0, 2.2360679774997894, 2.2360679774997894], [6.0, 3.236067977499793, 1.2360679774997887]] Tolerance exceeded in 2 of 9: 0.6180339887498968 vs 0.6180339887498943, tolerance 4e15 > 2e15 1.2360679774997936 vs 1.2360679774997887, tolerance 4e15 > 2e15 ********************************************************************** 1 item had failures: 3 of 7 in sage.modular.modform.numerical.NumericalEigenforms [46 tests, 3 failures, 0.46 s]
comment:38 Changed 12 months ago by
 Commit changed from a59f31865b0f8e1e777f4829537e7b284a4d3c52 to 19af6889ef08455e4c560d56e382d8921f9ed3f4
comment:39 Changed 12 months ago by
 Status changed from needs_work to needs_review
I have lowered slightly the precision
comment:40 Changed 12 months ago by
 Status changed from needs_review to positive_review
comment:41 Changed 12 months ago by
 Branch changed from public/ticket/25301 to 19af6889ef08455e4c560d56e382d8921f9ed3f4
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
trac 25301 first steps