#20693: Sage crashes when computing newforms
-------------------------------------+-------------------------------------
Reporter: ehlen | Owner:
Type: defect | Status: new
Priority: critical | Milestone: sage-7.3
Component: modular forms | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/ehlen/sage_crashes_when_computing_newforms|
9218fb3214dbc776e1f914bd68f8fb4df1dd437e
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by ehlen):
OK, so I really tried a lot of things and I came to the conclusion that
what is currently done in {{{_invert_c_}}} of
{{{number_field_element.pyx}}} is too much work, "causes" the NTLError in
the cases at hand and inversion can be made much much faster with a
minimal change.
The main point is this: Currently, given a number field element of the
form x/d, where (if I understood it correctly), x is a polynomial with
integer coeffs and d is an integer, modulo a polynomial M/D, where again M
is a poly with integer coeffs and M an integer, the code sets
{{{
a = x*D
b = M*d
}}}
and computes {{{r, s, t}}}, such that
{{{
r = s*a + t*b.
}}}
Thus, {{{s/r}}} is the inverse of {{{a=x*D}}} modulo {{{b=M*d}}} (with
rational coefficients, in Q[X]/(dM)).
Now, I don't really now why this is done and maybe I misunderstand
something but I think taking {{{dM}}} here is unnecessary and slows
everything down. Anyway, the result is that
{{{
1 = s/r*D*d*x/d + t*D/(r*d)*d*M/D
}}}
And so the code returns {{{s/r*D*d}}} as the inverse.
What I did was to instead set
{{{
a = x*D
b = M
}}}
and then again compute {{{r,s,t}}} as above so that now {{{s/r}}} is the
inverse of {{{a}}} modulo {{{M}}} with rational coefficients, i.e.
in Q[X]/(M). This means that we get
{{{
1 = s/r*D*d*x/d + t*D/r*M/D
}}}
which shows that modulo M/D, we get that {{{s/r*D*d}}} is the inverse.
Now, after I wrote this down, it also seems that multiplying {{{x}}} by
{{{D}}} is not needed.
I will try this out and push the changes immediately.
Btw, all doctests pass.
I also added some doctests to make sure we always test that this issue
here is resolved.
However, since the example I had at hand is so large, it adds a lot of
junk to the source code which I don't like very much.
Is there any way to add an external test, that's not necessary in the
dotstring in sage (no nosetests at all???)?
--
Ticket URL: <http://trac.sagemath.org/ticket/20693#comment:30>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
