Opened 2 years ago

Closed 2 years ago

#22967 closed enhancement (fixed)

image_of_hecke_algebra does not do what the docstring and function arguments suggests

Reported by: klui Owned by:
Priority: minor Milestone: sage-8.0
Component: modular forms Keywords: modular abelian variety, hecke algebra, sd87
Cc: Merged in:
Authors: Kevin Lui Reviewers: Gerardo Zelaya
Report Upstream: N/A Work issues:
Branch: af8fbd2 (Commits) Commit: af8fbd28a263f4015b6e9907d05c1f29c8f4897e
Dependencies: Stopgaps:

Description (last modified by klui)

The method image_of_hecke_algebra computes the image by starting with the zero subspace and adding hecke operators until the sturm bound.

This patch speeds up this method significantly by checking at each step whether the current module is the full endomorphism ring by checking to see if it is of maximal rank and is saturated. This method is already referenced in the current code but was never actually implemented.

The speedup should be evident in most modular abelian varieties of dimension greater than 1.

Without the break condition:

sage: %time J1(18).endomorphism_ring().image_of_hecke_algebra(check_every=0)
CPU times: user 1.12 s, sys: 60 ms, total: 1.18 s
Wall time: 1.17 s
Subring of endomorphism ring of Abelian variety J1(18) of dimension 2
sage: %time J0(23).endomorphism_ring().image_of_hecke_algebra(check_every=0)
CPU times: user 164 ms, sys: 8 ms, total: 172 ms
Wall time: 161 ms
Subring of endomorphism ring of Abelian variety J0(23) of dimension 2
sage: %time J1(23).endomorphism_ring().image_of_hecke_algebra(check_every=0)
CPU times: user 3min 42s, sys: 8.91 s, total: 3min 51s
Wall time: 3min 51s
Subring of endomorphism ring of Abelian variety J1(23) of dimension 12

With the break condition:

sage: %time J1(18).endomorphism_ring().image_of_hecke_algebra(check_every=1)
CPU times: user 204 ms, sys: 40 ms, total: 244 ms
Wall time: 236 ms
Subring of endomorphism ring of Abelian variety J1(18) of dimension 2
sage: %time J0(23).endomorphism_ring().image_of_hecke_algebra(check_every=1)
CPU times: user 92 ms, sys: 16 ms, total: 108 ms
Wall time: 99.1 ms
Subring of endomorphism ring of Abelian variety J0(23) of dimension 2
sage: %time J1(23).endomorphism_ring().image_of_hecke_algebra(check_every=1)
CPU times: user 28.5 s, sys: 1.26 s, total: 29.8 s
Wall time: 29.8 s
Subring of endomorphism ring of Abelian variety J1(23) of dimension 12

I also checked this is against the old code. I broke the caching by commenting out lines 956-959 and then ran this code on a big computer.

from sage.all import *
from itertools import product
 
 
@parallel(40)
def test_at_level(N, j):
    if j == 0:
        J = J0(N)
    else:
        J = J1(N)
 
    R = J.endomorphism_ring()
    A = R.image_of_hecke_algebra(check_every=0)
    B = R.image_of_hecke_algebra(check_every=1)
 
    return [x.matrix() for x in A.gens()] == \
            [x.matrix() for x in B.gens()]
 
Ns = range(1,26)
js = [0,1]
tests = list(product(Ns,js))
 
test_results = list(test_at_level(tests))
print("Number of tests: {}".format(len(test_results)))
if all([x[1] for x in test_results]):
    print("Passed")
else:
    print("Failed")

Change History (5)

comment:1 Changed 2 years ago by klui

  • Branch set to u/klui/image_of_hecke_algebra_does_not_do_what_the_docstring_and_function_arguments_suggests

comment:2 Changed 2 years ago by klui

  • Authors set to Kevin Lui
  • Commit set to af8fbd28a263f4015b6e9907d05c1f29c8f4897e
  • Description modified (diff)
  • Keywords modular abelian variety hecke algebra added
  • Priority changed from major to minor
  • Status changed from new to needs_review
  • Type changed from defect to enhancement

New commits:

af8fbd2added code for optimizing

comment:3 Changed 2 years ago by geze

  • Keywords sd87 added

comment:4 Changed 2 years ago by geze

  • Reviewers set to Gerardo Zelaya
  • Status changed from needs_review to positive_review

The new input describes accurately the change. The change reflects the use of "check_every" until it achieves the sturm bound.

comment:5 Changed 2 years ago by vbraun

  • Branch changed from u/klui/image_of_hecke_algebra_does_not_do_what_the_docstring_and_function_arguments_suggests to af8fbd28a263f4015b6e9907d05c1f29c8f4897e
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.