FLINT3.7.0-dev
/

_gr_poly_revert_series, gr_poly_revert_series, _gr_poly_revert_series_lagrange, gr_poly_revert_series_lagrange, _gr_poly_revert_series_lagrange_fast, gr_poly_revert_series_lagrange_fast, _gr_poly_revert_series_newton, gr_poly_revert_series_newton

Synopsis#include <flint/gr_poly.h>
int _gr_poly_revert_series(gr_ptr res, gr_srcptr f, slong flen, slong n, gr_ctx_t ctx)source
int gr_poly_revert_series(gr_poly_t res, const gr_poly_t f, slong n, gr_ctx_t ctx)source
int _gr_poly_revert_series_lagrange(gr_ptr res, gr_srcptr f, slong flen, slong n, gr_ctx_t ctx)source
int gr_poly_revert_series_lagrange(gr_poly_t res, const gr_poly_t f, slong n, gr_ctx_t ctx)source
int _gr_poly_revert_series_lagrange_fast(gr_ptr res, gr_srcptr f, slong flen, slong n, gr_ctx_t ctx)source
int gr_poly_revert_series_lagrange_fast(gr_poly_t res, const gr_poly_t f, slong n, gr_ctx_t ctx)source
int _gr_poly_revert_series_newton(gr_ptr res, gr_srcptr f, slong flen, slong n, gr_ctx_t ctx)source
int gr_poly_revert_series_newton(gr_poly_t res, const gr_poly_t f, slong n, gr_ctx_t ctx)source

Set res to the compositional inverse f^{-1}, with f^{-1}(f(x)) = f(f^{-1}(x)) = x \bmod x^n. The reversion exists when f(0) = 0 and f'(0) is invertible; GR_DOMAIN is returned otherwise (GR_UNABLE if f(0) is not provably zero).

The lagrange version uses the Lagrange inversion formula, the lagrange_fast version the baby-step giant-step form of it from [Joh2015b], and the newton version Newton iteration on f(h) = x with power series compositions [BrentKung1978]. The Lagrange versions divide by 2, \ldots, n - 1 and return GR_UNABLE in too small characteristic. The default version uses Newton iteration from five times the composition cutoff of _gr_poly_compose_series on (when Kinoshita-Li composition makes it faster), and lagrange_fast otherwise, falling back to Newton iteration when the latter fails with GR_UNABLE. The underscore versions do not allow aliasing.

References#

  • [Joh2015b] F. Johansson, "A fast algorithm for reversion of power series", Math. Comp. 84 (2015), 475-484, http://doi.org/10.1090/S0025-5718-2014-02857-3
  • [BrentKung1978] Brent, R. P. and Kung, H. T. : Fast Algorithms for Manipulating Formal Power Series, J. ACM 25:4 (1978) 581–595
Cite this page

The FLINT team, “_gr_poly_revert_series, gr_poly_revert_series, _gr_poly_revert_series_lagrange, gr_poly_revert_series_lagrange, _gr_poly_revert_series_lagrange_fast, gr_poly_revert_series_lagrange_fast, _gr_poly_revert_series_newton, gr_poly_revert_series_newton (gr_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/gr_poly/_gr_poly_revert_series.html (generated 2026-10-20).