id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
21388 Optimize Psi2() embray "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." defect closed minor sage-7.4 elliptic curves fixed Erik Bray, Jeroen Demeyer Jeroen Demeyer, Erik Bray N/A bdce5dced1e9f811616836253c4e7cd45b71fcf3 bdce5dced1e9f811616836253c4e7cd45b71fcf3