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)?
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?
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.
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.
diff --git a/src/sage/libs/flint/nmod_poly.pxd b/src/sage/libs/flint/nmod_poly.pxd
index e99a228..3926a6c 100644
--- a/src/sage/libs/flint/nmod_poly.pxd
+++ b/src/sage/libs/flint/nmod_poly.pxd
@@ -68,6 +68,8 @@ cdef extern from "flint/nmod_poly.h":
cdef void nmod_poly_one(nmod_poly_t res)
cdef void nmod_poly_truncate(nmod_poly_t poly, long len)
cdef void nmod_poly_reverse(nmod_poly_t output, nmod_poly_t input, long m)
+ cdef void nmod_poly_revert_series(nmod_poly_t output, nmod_poly_t intput, long m)
+
cdef int nmod_poly_equal(nmod_poly_t a, nmod_poly_t b)
# Powering
diff --git a/src/sage/rings/polynomial/polynomial_zmod_flint.pyx b/src/sage/rings/polynomial/polynomial_zmod_flint.pyx
index 1856be1..254501c 100644
--- a/src/sage/rings/polynomial/polynomial_zmod_flint.pyx
+++ b/src/sage/rings/polynomial/polynomial_zmod_flint.pyx
@@ -767,3 +767,39 @@ cdef class Polynomial_zmod_flint(Polynomial_template):
else:
nmod_poly_reverse(&res.x, &self.x, nmod_poly_length(&self.x))
return res
+
+ def revert_series(self, n):
+ r"""
+ Return a polynomial `f` such that `f(self(x)) = self(f(x)) = x mod x^n`.
+
+ EXAMPLES::
+
+ sage: R.<t> = GF(5)[]
+ sage: f = t - t^3 + t^5
+ sage: f.revert_series(5) # todo: this fails (needs to be fixed)!
+ t + t^3 + 2*t^5
+
+ sage: f.revert_series(-1)
+ Traceback (most recent call last):
+ ...
+ ValueError: argument n must be a non-negative integer, got -1
+
+ sage: g = - t^3 + t^5
+ sage: g.revert_series(6)
+ Traceback (most recent call last):
+ ...
+ ValueError: self must have constant coefficient 0 and a unit for coefficient 1
+ """
+ cdef Polynomial_zmod_flint res = self._new()
+ cdef unsigned long m
+ if n < 0:
+ raise ValueError("argument n must be a non-negative integer, got %s" % n)
+ m = n
+ if not self[0].is_zero() or not self[1].is_unit():
+ raise ValueError("self must have constant coefficient 0 and a unit for coefficient 1")
+
+ sig_on()
+ nmod_poly_revert_series(&res.x, &self.x, m)
+ sig_off()
+
+ return res
