sparse_2term_quotient_only_pm1 gives different results depending on set iteration order

[embray]

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.

[chapoton]

New commits:

​92ce67c

trac 25301 first steps

[git]

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

​edf3ee9

trying to sort

[git]

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

​415800d

fix doctests in /modsym/heilbronn

[chapoton]

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

[git]

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

​60a22e5

another more robust test

[git]

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

​bab53bb	Merge branch 'u/chapoton/25301' in 8.4.rc1
​36f6be1	making some doctests of modular symbols more robust

[chapoton]

a branch making some doctests more robust was moved to #26673

[chapoton]

---

New commits:

​1282000

trying to sort the relations in modular symbols

[chapoton]

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

[cremona]

I'll look at it. (​http://homepages.warwick.ac.uk/staff/J.E.Cremona/theses/index.html should qualify me)

[cremona]

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.

[cremona]

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.

[cremona]

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

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

In comment:15, you mean line 217 of modular/modform/numerical, right ?

[cremona]

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.

[git]

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

​c65b746

#25301: fix all but one doctest in sage.modular

[cremona]

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.

[git]

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

​00f5218

#25301: fix doctests outside sage.modular

[cremona]

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.

[git]

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

​356403a

#25301: fix last doctest

[cremona]

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.

[chapoton]

Thanks John for your hard work on this ticket, which is of major importance in our progress towards python3.

[chapoton]

Good, the bot is fully green.

[chapoton]

And this fixes all doctests in 14 files in python3.

So I am extremely tempted to give it a positive review...

[embray]

src/sage/modular/modsym/relation_matrix.py

@@ -496 +496 @@
         # Let rels = rels union I relations.
         rels.update(modI_relations(syms, sign))
 
-    rels = list(rels)
+    rels = sorted(rels)
     # should be sorted(rels), but this breaks many doctests
 
     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...)

[git]

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

​8c11dd9	Merge branch 'public/ticket/25301' in 8.6.rc0
​a59f318	trac 25301 change the message below the sorting line

[chapoton]

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 ?

[chapoton]

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.

[cremona]

Replying to chapoton:

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.

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.

[chapoton]

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.

[embray]

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.

[embray]

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 sage-pending or sage-wishlist.

[vbraun]

On 32-bit:

**********************************************************************
File "src/sage/modular/modform/numerical.py", line 75, in sage.modular.modform.numerical.NumericalEigenforms
Failed example:
    n.ap(2)  # rel tol 2e-15
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 4e-15 > 2e-15
**********************************************************************
File "src/sage/modular/modform/numerical.py", line 77, in sage.modular.modform.numerical.NumericalEigenforms
Failed example:
    n.systems_of_eigenvalues(7)  # rel tol 2e-15
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 4e-15 > 2e-15
    1.2360679774997936 vs 1.2360679774997887, tolerance 4e-15 > 2e-15
**********************************************************************
File "src/sage/modular/modform/numerical.py", line 89, in sage.modular.modform.numerical.NumericalEigenforms
Failed example:
    n.eigenvalues([2,3,5])  # rel tol 2e-15
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 4e-15 > 2e-15
    1.2360679774997936 vs 1.2360679774997887, tolerance 4e-15 > 2e-15
**********************************************************************
1 item had failures:
   3 of   7 in sage.modular.modform.numerical.NumericalEigenforms
    [46 tests, 3 failures, 0.46 s]

[git]

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

​d198ed9	Merge branch 'public/ticket/25301' in 8.6
​19af688	trac 25301 fix 32 bit doctests by lowering precision, plus pyflakes change

[chapoton]

I have lowered slightly the precision