On Tue, Jul 22, 2014 at 9:05 PM, Jonas Jermann <jjerma...@gmail.com> wrote: > Hi > > > On 21.07.2014 13:10, Fredrik Johansson wrote: >> >> 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. > > > 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)?
The reversion of t - t^3 + O(t^5) to length n = 5 should be t + t^3 + O(t^5). This is what I get when I call flint directly from a C program. Are you getting something different? Note that the current implementation requires that 1, 2, ..., n-1 are invertible (this restriction is documented in the flint manual). So for polynomials over GF(5), n = 6 would be invalid input. You could insert some code that checks this and either raises an exception or computes over Z or Q and converts back. >>>> 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? Sure. > I still feel the best long-term solution would be to use > flint for power series. That would give a huge performance boost. > But again, that's an independent question: The ticket could be applied even > if flint was already used for power series. True. 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.
