Opened 11 years ago

Closed 11 years ago

#5080 closed defect (fixed)

[with new patch, with positive review] Bug in decomposing modular symbol subspace

Reported by: robertwb Owned by: davidloeffler
Priority: blocker Milestone: sage-4.1
Component: modular forms Keywords:
Cc: craigcitro Merged in: sage-4.1.alpha0
Authors: David Loeffler Reviewers: Craig Citro, Michael Abshoff, John Cremona
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

sage: E = EllipticCurve("128a") 
sage: E.congruence_number()
------------------------------------------------------------
Traceback (most recent call last):
  File "<ipython console>", line 1, in <module>
  File "/Users/robert/sage/sage-3.1.3/local/lib/python2.5/site-packages/sage/schemes/elliptic_curves/ell_rational_field.py", line 2618, in congruence_number
    self.__congruence_number = W.congruence_number(V)
  File "/Users/robert/sage/sage-3.1.3/local/lib/python2.5/site-packages/sage/modular/modsym/space.py", line 938, in congruence_number
    W = other.q_expansion_module(prec, ZZ)
  File "/Users/robert/sage/sage-3.1.3/local/lib/python2.5/site-packages/sage/modular/modsym/space.py", line 770, in q_expansion_module
    return self._q_expansion_module_integral(prec)
  File "/Users/robert/sage/sage-3.1.3/local/lib/python2.5/site-packages/sage/modular/modsym/space.py", line 910, in _q_expansion_module_integral
    V = self.q_expansion_module(prec, QQ)
  File "/Users/robert/sage/sage-3.1.3/local/lib/python2.5/site-packages/sage/modular/modsym/space.py", line 772, in q_expansion_module
    return self._q_expansion_module_rational(prec)
  File "/Users/robert/sage/sage-3.1.3/local/lib/python2.5/site-packages/sage/modular/modsym/space.py", line 861, in _q_expansion_module_rational
    return self._q_expansion_module(prec)
  File "/Users/robert/sage/sage-3.1.3/local/lib/python2.5/site-packages/sage/modular/modsym/space.py", line 820, in _q_expansion_module
    return A.span([f.padded_list(prec) for f in self.q_expansion_basis(prec, algorithm)])
  File "/Users/robert/sage/sage-3.1.3/local/lib/python2.5/site-packages/sage/modular/modsym/space.py", line 602, in q_expansion_basis
    return Sequence(self._q_expansion_basis_hecke_dual(prec), cr=True)
  File "/Users/robert/sage/sage-3.1.3/local/lib/python2.5/site-packages/sage/modular/modsym/space.py", line 1073, in _q_expansion_basis_hecke_dual
    v = [self.dual_hecke_matrix(n).column(i) for n in range(1,prec)]
  File "/Users/robert/sage/sage-3.1.3/local/lib/python2.5/site-packages/sage/modular/hecke/module.py", line 797, in dual_hecke_matrix
    T = self._compute_dual_hecke_matrix(n)
  File "/Users/robert/sage/current/local/lib/python2.5/site-packages/sage/modular/hecke/submodule.py", line 110, in _compute_dual_hecke_matrix
    return A.restrict(self.dual_free_module(), check=check)
  File "/Users/robert/sage/current/local/lib/python2.5/site-packages/sage/modular/hecke/submodule.py", line 320, in dual_free_module
    "(cut down to rank %s, but should have cut down to rank %s)."%(V.rank(), self.rank())
RuntimeError: Computation of embedded dual vector space failed (cut down to rank 9, but should have cut down to rank 8).

Attachments (5)

trac_5080.patch (10.3 KB) - added by davidloeffler 11 years ago.
apply after #5736, #4357 and #5787
trac_5080_doctest.patch (907 bytes) - added by davidloeffler 11 years ago.
apply after previous patch
trac_5080_new.patch (3.8 KB) - added by davidloeffler 11 years ago.
replaces all previous patches
trac_5080_cachefix.patch (4.3 KB) - added by davidloeffler 11 years ago.
apply over trac_5080_new.patch
trac_5080_repair.patch (11.7 KB) - added by davidloeffler 11 years ago.
Apply to 4.1.alpha2

Download all attachments as: .zip

Change History (32)

comment:1 Changed 11 years ago by AlexGhitza

for the record, here are all the optimal elliptic curves of conductor at most 250 that exhibit the same problem (listed with Cremona labels): 128a1, 128b1, 128c1, 128d1, 144b1, 192a1, 192b1, 192c1, 192d1, 225c1, 225d1, 225e1

comment:2 Changed 11 years ago by davidloeffler

I have had a careful look at this, and I think I know what's going on. The problem is that for each of these curves, if f is the corresponding newform, then there is a finite set of forms f_1 ... f_m (none of them equal to f) in the space such that for every p, a_p(f) = a_p(f_i) for some i. It was a bit of a surprise to me that this is possible, but it doesn't contradict multiplicity one, and in fact if you take any fixed form and consider its twists by chi1, chi2, and chi1 * chi2 for any two quadratic characters chi1, chi2 of coprime moduli then you get an example.

This mightily confuses two functions for submodules of Hecke modules: "complement" and "dual_free_module". The former has a workaround, in that if it can't find a complement using only one Hecke operator at a time, it falls back on calling "decomposition" (which is slower, but is immune to this problem) and works out the complement using that. The latter doesn't. But anyway, the two are basically doing the same thing, since the embedded dual free module of a submodule V is by definition the annihilator of the Hecke-stable complement of V (when this exists). So the fix is to get rid of the existing "dual_free_module" routine and replace it with a simpler routine that calls "complement" and then does some trivial linear algebra.

I will post a patch when I get a chance to code it up.

Changed 11 years ago by davidloeffler

apply after #5736, #4357 and #5787

comment:3 Changed 11 years ago by davidloeffler

  • Summary changed from Bug in decomposing modular symbol subspace to [with patch, needs review] Bug in decomposing modular symbol subspace

Here's a patch.

comment:4 follow-up: Changed 11 years ago by cremona

I'm about to try this out. Is there a doctest showing that

sage: E = EllipticCurve("128a") 
sage: E.congruence_number()

now works?

comment:5 in reply to: ↑ 4 Changed 11 years ago by cremona

Replying to cremona:

I'm about to try this out. Is there a doctest showing that

sage: E = EllipticCurve("128a") 
sage: E.congruence_number()

now works?

Which it does:

sage: sage: E = EllipticCurve("128a")
sage: sage: E.congruence_number()
32

comment:6 Changed 11 years ago by cremona

  • Summary changed from [with patch, needs review] Bug in decomposing modular symbol subspace to [with patch, positive review but extra doctest needed] Bug in decomposing modular symbol subspace

Patch looks good, applies fine to 4.0.alpha0 and fixes the bug. My only quibble is that there is no new doctest to show that the reported bug is fixed.

Changed 11 years ago by davidloeffler

apply after previous patch

comment:7 Changed 11 years ago by davidloeffler

  • Summary changed from [with patch, positive review but extra doctest needed] Bug in decomposing modular symbol subspace to [with patch, positive review] Bug in decomposing modular symbol subspace

Sorry, that was very sloppy of me. Here is a patchlet that adds the missing doctest.

comment:8 Changed 11 years ago by cremona

Brilliant. And I forgot to say (on one of these tickets) -- we do now have 100% coverage on all sage/modular/modsym, and all tests pass.

comment:9 Changed 11 years ago by mabshoff

  • Summary changed from [with patch, positive review] Bug in decomposing modular symbol subspace to [with patch, needs work] Bug in decomposing modular symbol subspace

Unfortunately this patch causes a massive speed regression:

sage: time EllipticCurve('858k2').sha().an_padic(Integer(7))
CPU times: user 8.90 s, sys: 0.33 s, total: 9.23 s
Wall time: 9.52 s
7^2 + O(7^3)

With both patches from this ticket this one alone takes minutes, so sorry, but "needs work".

Cheers,

Michael

comment:10 Changed 11 years ago by davidloeffler

Groan, I suppose that going via complement to get dual free module is probably slower when the Hecke matrices are very sparse, as they are here. I generally worry first about getting a mathematically correct answer, and only then about efficiency issues. Can't look at this right now, sorry -- I've already spent far too much time on Sage stuff in the last week or two -- might get around to it sometime next week.

comment:11 Changed 11 years ago by craigcitro

Hey David,

It's definitely the right choice to go for correctness over speed first. I'll look into speeding this up in the next few days, if you don't beat me to it. As the simplest possible attempt, though, couldn't we just drop your new code in where the RuntimeError is raised? Obviously this isn't the classiest fix, but it wouldn't be bad as a first approximation.

comment:12 Changed 11 years ago by davidloeffler

Hi Craig,

It's a delicate thing. There are two potential first-approximation algorithms for computing complements, or (equivalently) embedded duals: either work on the dual side (cutting down to the smallest space on which Hecke acts like it does on self) or work on the ambient side (cutting down to the smallest space on which Hecke acts like it does on the quotient ambient/self).

What we had before was one algorithm in complement and the other in dual_free_module, never exploiting the fact that the two problems are essentially equivalent. I standardised on the algorithm that complement was using, largely because the code to handle the pathological case (for which neither algorithm works) was already there in the complement routine.

The classy fix is to heuristically choose which algorithm to use, because (in non-pathological cases) the dual-side version is much quicker when the given submodule is much smaller than the ambient space, and the ambient-side version is much quicker when the given submodule is most of the ambient space. This is (roughly) what is meant by the comment in submodule.py saying:

# TODO: optimize in some cases by computing image of
# complementary factor instead of kernel...?

David

Changed 11 years ago by davidloeffler

replaces all previous patches

comment:13 Changed 11 years ago by davidloeffler

  • Summary changed from [with patch, needs work] Bug in decomposing modular symbol subspace to [with new patch, needs review] Bug in decomposing modular symbol subspace

Here's a new patch, which causes no speed regression at all in the p-adic analytic sha for 858k1, and still solves the original 128a congruence number problem.

comment:14 Changed 11 years ago by cremona

Craig, are you going to review David's new patch here? Or shall I?

comment:15 Changed 11 years ago by craigcitro

Hi John -- I'm planning on looking at it somewhat soon, but feel free to beat me to it! :)

comment:16 Changed 11 years ago by davidloeffler

  • Owner changed from craigcitro to davidloeffler
  • Status changed from new to assigned

comment:17 Changed 11 years ago by craigcitro

  • Cc craigcitro added

comment:18 Changed 11 years ago by craigcitro

  • Summary changed from [with new patch, needs review] Bug in decomposing modular symbol subspace to [with new patch, needs work (minor)] Bug in decomposing modular symbol subspace

Sorry I've been so slow about getting to this.

The patch looks great, but I have one gripe. I hate the fact that we're working around Python's "private" obfuscation (the _HeckeSubmodule__attr thing). It's brittle, because if the class name changes, or if certain methods get overridden, it'll break. Worse, it's ugly. :) I think we should fix it, though I'm not sure I know the "right" way. Some options:

  • change these to attributes with a single underscore
  • set these attributes to None in the constructor, and check if they're not None
  • I know the combinat branch has a cached_method decorator -- I don't know if it has a system for checking if the attribute is set, but it might.

I guess I'd lean towards the third if it works, and if not, the second (and filing a trac ticket asking for the enhancement to cached_method). One option I don't like: adding flags for each attribute to see if it's set.

comment:19 Changed 11 years ago by davidloeffler

Good point. I've become rather fond of @cached_function and @cached_method -- I have a patch which I haven't uploaded yet which removes about 100 lines of caching code from sage/modular/modform by systematically using @cached_method -- but it hadn't occurred to me to use it in this way. It seems that cached methods have a method "is_in_cache"; and if the method takes no arguments, you can call "is_in_cache" with no arguments either, and it works fine.

I will do a new patch, but in 28 hours I will be catching a plane to Barcelona for SD16, so it might not get done before next weekend. David

Changed 11 years ago by davidloeffler

apply over trac_5080_new.patch

comment:20 Changed 11 years ago by davidloeffler

  • Summary changed from [with new patch, needs work (minor)] Bug in decomposing modular symbol subspace to [with new patch, needs review] Bug in decomposing modular symbol subspace

For the first time I can remember, I wrote a fix and it worked first time. Here is a patch which removes all instances of "hasattr".

(There is potential for cleaning up elsewhere in sage/modular/hecke/submodule.py using cached_method -- the is_new, is_old, new_submodule, old_submodule calls have their own caching code which we can now get rid of -- but that is for another ticket.)

David

comment:21 Changed 11 years ago by craigcitro

  • Authors set to David Loeffler
  • Reviewers set to Craig Citro, Michael Abshoff
  • Summary changed from [with new patch, needs review] Bug in decomposing modular symbol subspace to [with new patch, with positive review] Bug in decomposing modular symbol subspace

Looks good, and I'm very happy with the changes.

comment:22 Changed 11 years ago by rlm

  • Merged in set to sage-4.1.alpha0
  • Resolution set to fixed
  • Status changed from assigned to closed

comment:23 Changed 11 years ago by was

  • Resolution fixed deleted
  • Status changed from closed to reopened
On Jun 27, 11:54 pm, davidloeffler <dave.loeff...@gmail.com> wrote:
> On SuSE, 32-bit, sage -testall -long passes except for errors in the
> same three files Jaap reported above (and a harmless timeout in
> elliptic curves).

I spoke too soon. Something rather harmful has in fact happened: the
wrong patches have been merged for track #5080. My first attempt at
fixing this problem caused a catastrophic slowdown in elliptic curve
Sha routines, so I started again from scratch and did a new patch that
worked differently. It seems that the old patch has been merged, with
the result that

sage: EllipticCurve("858k1").sha().an_padic(7)

has been slowed down by *several orders of magnitude*. That was why I
was seeing timeouts in that file.

To reiterate: the patch "trac_5080.patch" on that ticket is evil, bad
and wrong, should not have been merged, and must be removed from Sage
ASAP.

David

comment:24 Changed 11 years ago by was

  • Priority changed from major to blocker

Changed 11 years ago by davidloeffler

Apply to 4.1.alpha2

comment:25 Changed 11 years ago by davidloeffler

I've just uploaded the patch trac_5080_repair.patch. Apply this patch (only) to 4.1.alpha2 gets hecke/submodule.py into the intended state. I've checked that this passes doctests in sage/modular/hecke, and that mabshoff's 858k2 example computes within a reasonable time limit.

David

comment:26 Changed 11 years ago by cremona

I checked that the new patch applies cleanly to 4.1.alpha2, all tests in modular/hecke pass, and the function mabshoff highlighted runs fine in about 10s.

The tag still said "positive review", but now it deserves it again.

comment:27 Changed 11 years ago by rlm

  • Resolution set to fixed
  • Reviewers changed from Craig Citro, Michael Abshoff to Craig Citro, Michael Abshoff, John Cremona
  • Status changed from reopened to closed

Merged the fix patch into sage-4.1.alpha3.

Note: See TracTickets for help on using tickets.