Hi all
Could someone familiar with flint/sage enable flint's
revert_series (for rational/integer polynomials)?
(Sorry if it was already implemented somewhere and I missed it).
Attached is a small, non-intrusive patch (done with help from IRC)
in that direction which simply adds series reversion for
integer and rational flint polynomials.
For those polynomials (resp. power series) flint is _much_
faster than the current implementation of power series reversion
(which is a big bottleneck for the modular forms code I currently
work on -> "u/jj/hecke_mf").
In my opinion this offers an acceptable and small compromise which
in particular doesn't (yet) require to implement power series using
flint. For someone interested in using it for power series, simply
convert the series to a (flint) polynomial, apply flint's revert_series
and convert the result back to a power series.
It could of course also be used to replace the current power series
reversion over integers/rationals.
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/fmpq_poly.pxd b/src/sage/libs/flint/fmpq_poly.pxd
index 78c9581..10dbca6 100644
--- a/src/sage/libs/flint/fmpq_poly.pxd
+++ b/src/sage/libs/flint/fmpq_poly.pxd
@@ -92,6 +92,7 @@ cdef extern from "flint/fmpq_poly.h":
void fmpq_poly_get_slice(fmpq_poly_t, fmpq_poly_t, long, long)
void fmpq_poly_truncate(fmpq_poly_t, unsigned long)
void fmpq_poly_reverse(fmpq_poly_t, fmpq_poly_t, unsigned long)
+ void fmpq_poly_revert_series(fmpq_poly_t, fmpq_poly_t, unsigned long)
void fmpq_poly_set_array_mpq(fmpq_poly_t, mpq_t *, unsigned long)
void fmpq_poly_from_string(fmpq_poly_t, char *)
diff --git a/src/sage/libs/flint/fmpz_poly.pxd b/src/sage/libs/flint/fmpz_poly.pxd
index 40cc231..9ff7b28 100644
--- a/src/sage/libs/flint/fmpz_poly.pxd
+++ b/src/sage/libs/flint/fmpz_poly.pxd
@@ -11,3 +11,5 @@ cdef class Fmpz_poly(SageObject):
cdef extern from "flint/fmpz_poly.h":
cdef void fmpz_poly_reverse(fmpz_poly_t output, fmpz_poly_t input,
unsigned long length)
+ cdef void fmpz_poly_revert_series(fmpz_poly_t output, fmpz_poly_t input,
+ unsigned long length)
diff --git a/src/sage/rings/polynomial/polynomial_integer_dense_flint.pyx b/src/sage/rings/polynomial/polynomial_integer_dense_flint.pyx
index 34b1380..aef1e40 100644
--- a/src/sage/rings/polynomial/polynomial_integer_dense_flint.pyx
+++ b/src/sage/rings/polynomial/polynomial_integer_dense_flint.pyx
@@ -41,7 +41,8 @@ from sage.structure.factorization import Factorization
from sage.rings.fraction_field_element import FractionFieldElement
from sage.rings.arith import lcm
-from sage.libs.flint.fmpz_poly cimport fmpz_poly_reverse
+from sage.libs.flint.fmpz_poly cimport fmpz_poly_reverse, fmpz_poly_revert_series
+
from sage.libs.flint.ntl_interface cimport fmpz_poly_set_ZZX, fmpz_poly_get_ZZX
from sage.libs.ntl.ntl_ZZX_decl cimport *, vec_pair_ZZX_long_c
@@ -1406,3 +1407,19 @@ cdef class Polynomial_integer_dense_flint(Polynomial):
fmpz_poly_reverse(res.__poly, self.__poly,
fmpz_poly_length(self.__poly))
return res
+
+ def revert_series(self, n):
+ """
+ Return a polynomial f such that f(self(x)) = f(self(x)) = x mod x^n.
+ """
+
+ cdef Polynomial_integer_dense_flint res = self._new()
+ cdef unsigned long m
+ m = n
+ if m != n:
+ raise ValueError, "argument n must be a non-negative integer, got %s"%(n)
+ if not self[0].is_zero() or not self[1].is_unit():
+ raise ValueError, "self must have constant coefficient 0 and +1 or -1 as the coefficient for x^1"
+
+ fmpz_poly_revert_series(res.__poly, self.__poly, m)
+ return res
diff --git a/src/sage/rings/polynomial/polynomial_rational_flint.pyx b/src/sage/rings/polynomial/polynomial_rational_flint.pyx
index 0c13ffe..f287aa0 100644
--- a/src/sage/rings/polynomial/polynomial_rational_flint.pyx
+++ b/src/sage/rings/polynomial/polynomial_rational_flint.pyx
@@ -614,6 +614,23 @@ cdef class Polynomial_rational_flint(Polynomial):
if do_sig: sig_off()
return res
+ def revert_series(self, n):
+ """
+ Return a polynomial f such that f(self(x)) = f(self(x)) = x mod x^n.
+ """
+
+ cdef Polynomial_rational_flint res = self._new()
+ cdef unsigned long m
+ m = n
+ if m != n:
+ raise ValueError, "argument n must be a non-negative integer, got %s"%(n)
+ if not self[0].is_zero() or not self[1].is_unit():
+ raise ValueError, "self must have constant coefficient 0 and +1 or -1 as the coefficient for x^1"
+
+ fmpq_poly_revert_series(res.__poly, self.__poly, m)
+ return res
+
+
###########################################################################
# Comparisons #
###########################################################################
