summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorRelease Manager <release@sagemath.org>2016-09-03 17:10:40 +0200
committerVolker Braun <vbraun.name@gmail.com>2016-09-04 10:55:07 +0200
commitd76461f71b077622424cf47fe0f7c0d2f4bb3b01 (patch)
tree965e86135e3e8185746fb61f654b5e1f376276d2
parentTrac #21401: py3 get rid of some xrange outside combinat (diff)
parentOptimize Psi2() (diff)
Trac #21388: Optimize Psi2()
We greatly optimize the `Psi2()` function. Before: {{{ sage: from sage.schemes.elliptic_curves.isogeny_small_degree import Psi2 sage: timeit('Psi2.f(71)') 5 loops, best of 3: 9.36 s per loop }}} After: {{{ sage: from sage.schemes.elliptic_curves.isogeny_small_degree import Psi2 sage: timeit('Psi2.f(71)') 5 loops, best of 3: 875 ms per loop }}} (note the use of `Psi2.f()` to bypass caching) -------- This also provides a workaround to a test that caused the Python interpreter to segfault on Windows. The specific call that caused the segfault is: `Psi2(71)` But in brief, the crash occurs because we have (in the original code) a large element of `Univariate Quotient Polynomial Ring in v over Multivariate Polynomial Ring in x, u over Rational Field with modulus v^2 - u^4 + 10*u^3 + 3*u^2 - 4*u + 8`. This is then being cast simply to a multivariate rational polynomial over x, u, v. Because there is no direct coercion between these types this involves `eval()`-ing the polynomial as a Python expression. The problem is that this expression can become too large for the stack-- specifically in Python's symbol visibility analysis, a step it performs just before compiling an expression to bytecode. The implementation of that recurses into binary expressions, leading to a stack overflow for such a large expression. This issue has come up once before in #16014 where it was worked around by a rewrite of the code. This particular test worked on Linux where the default stack size is 8MB, but it crashed on Windows where the typical stack is just 1MB. The optimization gives smaller expressions to eval. A more general fix to this problem would be nice though--I'm writing up some thoughts I have on it in a separate post. URL: https://trac.sagemath.org/21388 Reported by: embray Ticket author(s): Erik Bray, Jeroen Demeyer Reviewer(s): Jeroen Demeyer, Erik Bray
-rw-r--r--src/sage/schemes/elliptic_curves/isogeny_small_degree.py46
1 files changed, 27 insertions, 19 deletions
diff --git a/src/sage/schemes/elliptic_curves/isogeny_small_degree.py b/src/sage/schemes/elliptic_curves/isogeny_small_degree.py
index 63e6ef7..3840dea 100644
--- a/src/sage/schemes/elliptic_curves/isogeny_small_degree.py
+++ b/src/sage/schemes/elliptic_curves/isogeny_small_degree.py
@@ -1455,23 +1455,30 @@ def Psi2(l):
The generic `l`-kernel polynomial.
- TESTS::
+ EXAMPLES::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import Psi2
sage: Psi2(11)
x^5 - 55*x^4*u + 994*x^3*u^2 - 8774*x^2*u^3 + 41453*x*u^4 - 928945/11*u^5 + 33*x^4 + 276*x^3*u - 7794*x^2*u^2 + 4452*x*u^3 + 1319331/11*u^4 + 216*x^3*v - 4536*x^2*u*v + 31752*x*u^2*v - 842616/11*u^3*v + 162*x^3 + 38718*x^2*u - 610578*x*u^2 + 33434694/11*u^3 - 4536*x^2*v + 73872*x*u*v - 2745576/11*u^2*v - 16470*x^2 + 580068*x*u - 67821354/11*u^2 - 185976*x*v + 14143896/11*u*v + 7533*x - 20437029/11*u - 12389112/11*v + 19964151/11
+ sage: Psi2(71) # long time (1 second)
+ -2209380711722505179506258739515288584116147237393815266468076436521/71*u^210 + ... - 14790739586438315394567393301990769678157425619440464678252277649/71
- """
- if not l in hyperelliptic_primes:
- raise ValueError("%s must be one of %s."%(l,hyperelliptic_primes))
+ TESTS::
+ sage: Psi2(13)
+ Traceback (most recent call last):
+ ...
+ ValueError: 13 must be one of [11, 17, 19, 23, 29, 31, 41, 47, 59, 71].
+ """
data = _hyperelliptic_isogeny_data(l)
- R = PolynomialRing(QQ,['x','u'])
- x, u = R.gens()
- L = PolynomialRing(R,'y')
- y = L.gen()
- K = R.extension(y**2-R(data['hyper_poly']),name = 'v')
+
+ R = PolynomialRing(QQ, 'u')
+ u = R.gen()
+ L = PolynomialRing(R, 'v')
+ v = L.gen()
+ K = R.extension(v*v - R(data['hyper_poly']), 'v')
v = K.gen()
+
from sage.categories.homset import Hom
h = Hom(K,K)(-v)
@@ -1482,20 +1489,21 @@ def Psi2(l):
s1 = K(data['A2'])
d = (l-1)//2
- s = [1]
- t = [d,s1,((1-10*d)*A - Abar)*(1/QQ(30))]
- t += [((1-28*d)*B - 42*t[1]*A - Bbar)*(1/QQ(70))]
- c = [0,6*t[2] + 2*A*t[0],10*t[3] + 6*A*t[1] + 4*B*t[0]]
+ s = [K(1)]
+ t = [d, s1, ((1-10*d)*A - Abar) * QQ((1,30))]
+ t.append(((1-28*d)*B - 42*t[1]*A - Bbar) * QQ((1,70)))
+ c = [0, 6*t[2] + 2*A*t[0], 10*t[3] + 6*A*t[1] + 4*B*t[0]]
for n in range(2,d):
k = sum(c[i]*c[n-i] for i in range(1,n))
- c += [(3*k-(2*n-1)*(n-1)*A*c[n-1]-(2*n-2)*(n-2)*B*c[n-2])*(1/QQ((n-1)*(2*n+5)))]
+ c.append((3*k-(2*n-1)*(n-1)*A*c[n-1]-(2*n-2)*(n-2)*B*c[n-2]) * QQ((1,(2*n+5)*(n-1))))
for n in range(3,d):
- t += [(c[n]-(4*n-2)*A*t[n-1]-(4*n-4)*B*t[n-2])*(1/QQ(4*n+2))]
+ t.append((c[n]-(4*n-2)*A*t[n-1]-(4*n-4)*B*t[n-2]) * QQ((1,4*n+2)))
for n in range(1,d+1):
- s += [(-1/QQ(n))*sum((-1)**i*t[i]*s[n-i] for i in range(1,n+1))]
- psi = sum((-1)**i*s[i]*x**(d-i) for i in range(0,d+1))
- R = PolynomialRing(QQ,['x','u','v'])
- return R(psi)
+ s.append(QQ((-1,n)) * sum((-1)**i*t[i]*s[n-i] for i in range(1,n+1)))
+
+ R = PolynomialRing(QQ, ('x', 'u', 'v'))
+ x = R.gen(0)
+ return sum((-1)**i * x**(d-i) * R(s[i].lift()) for i in range(0,d+1))
def isogenies_prime_degree_genus_plus_0(E, l=None):