Opened 10 months ago

Closed 3 weeks 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: sage-8.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 7 months ago by embray

  • Milestone changed from sage-8.3 to sage-wishlist

comment:2 Changed 4 months ago by chapoton

  • Branch set to u/chapoton/25301
  • Commit set to 92ce67cc8d88b4b1ff6281a09b85834df3c9c94a

New commits:

92ce67ctrac 25301 first steps

comment:3 Changed 4 months ago by git

  • Commit changed from 92ce67cc8d88b4b1ff6281a09b85834df3c9c94a to edf3ee9a40e82b11a38f6caab8938a18d9c3a3e6

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

edf3ee9trying to sort

comment:4 Changed 4 months ago by git

  • Commit changed from edf3ee9a40e82b11a38f6caab8938a18d9c3a3e6 to 415800d1512cce9eb8f9b703b66976c7dc24d75b

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

415800dfix doctests in /modsym/heilbronn

comment:5 Changed 4 months ago by chapoton

  • 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 4 months ago by git

  • Commit changed from 415800d1512cce9eb8f9b703b66976c7dc24d75b to 60a22e502300f00bf16e750aa721055f241f0167

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

60a22e5another more robust test

comment:7 Changed 4 months ago by git

  • Commit changed from 60a22e502300f00bf16e750aa721055f241f0167 to 36f6be1dfd5bfd7fdbfd03d795ff53a97d090269

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

bab53bbMerge branch 'u/chapoton/25301' in 8.4.rc1
36f6be1making some doctests of modular symbols more robust

comment:8 Changed 3 months ago by chapoton

  • Branch u/chapoton/25301 deleted
  • Commit 36f6be1dfd5bfd7fdbfd03d795ff53a97d090269 deleted

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

comment:9 Changed 2 months ago by chapoton

  • Branch set to public/ticket/25301
  • Commit set to 12820008a39ed91b90196d43ab5401113ddcede3

New commits:

1282000trying to sort the relations in modular symbols

comment:10 Changed 2 months ago by chapoton

  • 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 2 months ago by chapoton

  • Milestone changed from sage-wishlist to sage-8.6
  • Status changed from new to needs_info

comment:13 Changed 2 months ago by 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.

comment:14 Changed 2 months ago by 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.

comment:15 Changed 2 months ago by 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?.

comment:16 follow-up: Changed 7 weeks ago by 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 ?

comment:17 in reply to: ↑ 16 Changed 7 weeks ago by 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.

comment:18 Changed 6 weeks ago by git

  • 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 6 weeks ago by 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.

comment:20 Changed 6 weeks ago by cremona

  • Reviewers set to John Cremona
  • Status changed from needs_info to needs_review

comment:21 Changed 6 weeks ago by git

  • 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 6 weeks ago by 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.

comment:23 Changed 6 weeks ago by git

  • 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 6 weeks ago by 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.

comment:25 Changed 6 weeks ago by chapoton

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

comment:26 Changed 6 weeks ago by chapoton

Good, the bot is fully green.

comment:27 Changed 6 weeks ago by chapoton

And this fixes all doctests in 14 files in python3.

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

comment:28 Changed 6 weeks ago by embray

  • 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): 
    496496        # Let rels = rels union I relations.
    497497        rels.update(modI_relations(syms, sign))
    498498
    499     rels = list(rels)
     499    rels = sorted(rels)
    500500    # should be sorted(rels), but this breaks many doctests
    501501
    502502    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...)

Last edited 6 weeks ago by embray (previous) (diff)

comment:29 Changed 6 weeks ago by git

  • Commit changed from 356403a6cd93c5e2db964b0f61f16a54f4422117 to a59f31865b0f8e1e777f4829537e7b284a4d3c52

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

8c11dd9Merge branch 'public/ticket/25301' in 8.6.rc0
a59f318trac 25301 change the message below the sorting line

comment:30 Changed 6 weeks ago by 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 ?

comment:31 follow-up: Changed 6 weeks ago by 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.

comment:32 in reply to: ↑ 31 Changed 6 weeks ago by 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.

comment:33 Changed 6 weeks ago by 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.

comment:34 Changed 6 weeks ago by embray

  • 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 6 weeks ago by chapoton

  • Authors set to John Cremona, Frédéric Chapoton
  • Reviewers changed from John Cremona, Erik Bray to John Cremona, Erik Bray, Frédéric Chapoton

comment:36 Changed 5 weeks ago by embray

  • Milestone changed from sage-8.6 to sage-8.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 sage-pending or sage-wishlist.

comment:37 Changed 4 weeks ago by vbraun

  • Status changed from positive_review to needs_work

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]

comment:38 Changed 4 weeks ago by git

  • Commit changed from a59f31865b0f8e1e777f4829537e7b284a4d3c52 to 19af6889ef08455e4c560d56e382d8921f9ed3f4

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

d198ed9Merge branch 'public/ticket/25301' in 8.6
19af688trac 25301 fix 32 bit doctests by lowering precision, plus pyflakes change

comment:39 Changed 4 weeks ago by chapoton

  • Status changed from needs_work to needs_review

I have lowered slightly the precision

comment:40 Changed 4 weeks ago by cremona

  • Status changed from needs_review to positive_review

comment:41 Changed 3 weeks ago by vbraun

  • Branch changed from public/ticket/25301 to 19af6889ef08455e4c560d56e382d8921f9ed3f4
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.