On Mon, Jul 21, 2014 at 7:37 AM, Jonas Jermann <jjerma...@gmail.com> wrote: > 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).
You could use some other method in polynomial_zmod_flint.pyx as a template; reverse() for example. I guess you saw "reverse_series" in nmod_poly.pxd. This file is just out of date and should be updated to match the nmod_poly.h in the latest flint. > >> 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 The fast reversion algorithm basically does fewer polynomial multiplications than the naive algorithm (O(n^0.5) instead of O(n)), so it's an improvement regardless of whether polynomial multiplication is slow or fast. Fredrik -- 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.
