Hi Frederik
On 20.07.2014 15:20, Fredrik Johansson wrote:
There is also an nmod_poly_revert_series in flint for polynomials over
Z/nZ for word-size n. It would not hurt to wrap that function in the
same patch.
I agree, but somehow the "flint import" details are slightly different.
I also saw a different name somewhere, "reverse_series". So I was not
sure how to exactly import it for nmod. I would appreciate if someone
familiar with flint could do that (or leave it out for now).
Another idea (perhaps for a separate update) would be to add a sage
implementation of flint's algorithm for reversion over generic base
ring. This is Algorithm 1: "Fast Lagrange inversion" in
http://www.ams.org/journals/mcom/0000-000-00/S0025-5718-2014-02857-3/
(if you can't access it, http://arxiv.org/abs/1108.4772). The generic
code would be a little slower than flint's implementations over Z, Q and
Z/nZ, so you definitely want to special-case those. But in general, this
should be much faster than sage's current implementation for polynomials
of high degree.
I am not familiar with the details but I assume that the algorithm
heavily depends on the performance of power series operations like
multiplication or inversion. See e.g. fredrikj.net/math/rev.pdf
Flint is quite fast for all of those and I think sage's power series
implementation is not optimized at all (does it even support fast
multiplication?).
The ideal solution would be to directly improve sage's power series
implementation (e.g. using flint's code, which probably requires quite
a lot of work). In any case if you can implement the mentioned
improvement above that would be great of course. :-)
I simply suggested a small, non-intrusive patch in the meantime which
allows one to use flint. Also, the patch could be applied independent of
the suggested improvement above.
Best
Jonas
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
