On Tuesday, July 22, 2014 2:05:30 PM UTC+2, Jonas Jermann wrote: > > Hi > > On 21.07.2014 13:10, Fredrik Johansson wrote: > > On Mon, Jul 21, 2014 at 7:37 AM, Jonas Jermann <jjer...@gmail.com > <javascript:>> 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. > > I added the zmod revert_series but somehow the result is wrong(?), even > if I increase the precision. Attached is a patch against the current > ticket with the failing doctest. Maybe revert_series does not exactly do > what we/I expect for finite fields, it seems to drop the t^5 term over > GF(5)? > > >>> 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. > > That's very nice and only positive change. :) > It's an independent modification of the current ticket though, right? > > My point of view is "let's make one step at a time" or we'll just never include anything in Sage. So I think the little wrapper you submitted is a good inclusion. For sure we should also implement all that Fredrik and you suggested, but let's already include what you already did.
-- 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.
