image_of_hecke_algebra does not do what the docstring and function arguments suggests

[kevinywlui]

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")

Component: modular forms

Keywords: modular abelian variety, hecke algebra, sd87

Author: Kevin Lui

Branch/Commit: af8fbd2

Reviewer: Gerardo Zelaya

Issue created by migration from https://trac.sagemath.org/ticket/22967

[kevinywlui]

Branch: u/klui/image_of_hecke_algebra_does_not_do_what_the_docstring_and_function_arguments_suggests

[kevinywlui]

New commits:

af8fbd2

added code for optimizing

[kevinywlui]

Changed keywords from none to modular abelian variety, hecke algebra

[kevinywlui]

Author: Kevin Lui

[kevinywlui]

Commit: af8fbd2

[sagetrac-geze]

Changed keywords from modular abelian variety, hecke algebra to modular abelian variety, hecke algebra, sd87

[sagetrac-geze]

Reviewer: Gerardo Zelaya

[sagetrac-geze]

comment:4

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

[vbraun]

Changed branch from u/klui/image_of_hecke_algebra_does_not_do_what_the_docstring_and_function_arguments_suggests to af8fbd2