Changes between Initial Version and Version 2 of Ticket #22967


Ignore:
Timestamp:
05/22/17 23:13:17 (2 years ago)
Author:
klui
Comment:

New commits:

af8fbd2added code for optimizing

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #22967

    • Property Status changed from new to needs_review
    • Property Authors changed from to Kevin Lui
    • Property Priority changed from major to minor
    • Property Branch changed from to u/klui/image_of_hecke_algebra_does_not_do_what_the_docstring_and_function_arguments_suggests
    • Property Keywords modular abelian variety hecke algebra added
    • Property Commit changed from to af8fbd28a263f4015b6e9907d05c1f29c8f4897e
    • Property Type changed from defect to enhancement
  • Ticket #22967 – Description

    initial v2  
     1The method image_of_hecke_algebra computes the image by starting with the zero subspace and adding hecke operators until the sturm bound.
     2
     3This 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.
     4
     5The speedup should be evident in most modular abelian varieties of dimension greater than 1.
     6
     7Without the break condition:
     8{{{
     9sage: %time J1(18).endomorphism_ring().image_of_hecke_algebra(check_every=0)
     10CPU times: user 1.12 s, sys: 60 ms, total: 1.18 s
     11Wall time: 1.17 s
     12Subring of endomorphism ring of Abelian variety J1(18) of dimension 2
     13sage: %time J0(23).endomorphism_ring().image_of_hecke_algebra(check_every=0)
     14CPU times: user 164 ms, sys: 8 ms, total: 172 ms
     15Wall time: 161 ms
     16Subring of endomorphism ring of Abelian variety J0(23) of dimension 2
     17sage: %time J1(23).endomorphism_ring().image_of_hecke_algebra(check_every=0)
     18CPU times: user 3min 42s, sys: 8.91 s, total: 3min 51s
     19Wall time: 3min 51s
     20Subring of endomorphism ring of Abelian variety J1(23) of dimension 12
     21}}}
     22
     23With the break condition:
     24{{{
     25sage: %time J1(18).endomorphism_ring().image_of_hecke_algebra(check_every=1)
     26CPU times: user 204 ms, sys: 40 ms, total: 244 ms
     27Wall time: 236 ms
     28Subring of endomorphism ring of Abelian variety J1(18) of dimension 2
     29sage: %time J0(23).endomorphism_ring().image_of_hecke_algebra(check_every=1)
     30CPU times: user 92 ms, sys: 16 ms, total: 108 ms
     31Wall time: 99.1 ms
     32Subring of endomorphism ring of Abelian variety J0(23) of dimension 2
     33sage: %time J1(23).endomorphism_ring().image_of_hecke_algebra(check_every=1)
     34CPU times: user 28.5 s, sys: 1.26 s, total: 29.8 s
     35Wall time: 29.8 s
     36Subring of endomorphism ring of Abelian variety J1(23) of dimension 12
     37}}}
     38
     39
     40I 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.
     41{{{
     42from sage.all import *
     43from itertools import product
     44 
     45 
     46@parallel(40)
     47def test_at_level(N, j):
     48    if j == 0:
     49        J = J0(N)
     50    else:
     51        J = J1(N)
     52 
     53    R = J.endomorphism_ring()
     54    A = R.image_of_hecke_algebra(check_every=0)
     55    B = R.image_of_hecke_algebra(check_every=1)
     56 
     57    return [x.matrix() for x in A.gens()] == \
     58            [x.matrix() for x in B.gens()]
     59 
     60Ns = range(1,26)
     61js = [0,1]
     62tests = list(product(Ns,js))
     63 
     64test_results = list(test_at_level(tests))
     65print("Number of tests: {}".format(len(test_results)))
     66if all([x[1] for x in test_results]):
     67    print("Passed")
     68else:
     69    print("Failed")
     70}}}