FLINT3.7.0-dev
/
Module · 20 functions

arb_fmpz_poly.h

#include <flint/arb_fmpz_poly.h>

This module contains functions for integer polynomials (fmpz_poly_t) that use ball arithmetic, either to produce real or complex numbers or internally to produce an exact result. The central functions are arb_fmpz_poly_real_roots and arb_fmpz_poly_complex_roots, which compute disjoint enclosures of all real or complex roots of a squarefree integer polynomial to a requested accuracy, combining exact real root isolation in fmpz_poly.h (Counting and isolating real roots over Z), refinement by interval Newton iteration and bisection, and the certified numerical root finder of acb_poly.h; see Isolating the roots of integer polynomials and the tutorial Certified roots of polynomials. Conversions between integer polynomials and ball polynomials are in arb_poly.h and acb_poly.h (arb_poly_set_fmpz_poly, arb_poly_get_unique_fmpz_poly, ...).

The header declares its functions with the types from acb_types.h but does not include arb.h or acb.h; programs that create balls must include those headers too.

AlgorithmCertified roots of polynomialsHow acb_poly_find_roots computes all complex roots of a polynomial by the Weierstrass–Durand–Kerner iteration from Newton polygon starting values and certifies them with inclusion disks; how real roots are recognised; root bounds; and how arb_fmpz_poly combines this with exact real root isolation.

Evaluation#

void _arb_fmpz_poly_evaluate_arb_horner(arb_t res, const fmpz * poly, slong len, const arb_t x, slong prec)
void arb_fmpz_poly_evaluate_arb_horner(arb_t res, const fmpz_poly_t poly, const arb_t x, slong prec)
void _arb_fmpz_poly_evaluate_arb_rectangular(arb_t res, const fmpz * poly, slong len, const arb_t x, slong prec)
void _arb_fmpz_poly_evaluate_arb(arb_t res, const fmpz * poly, slong len, const arb_t x, slong prec)
void arb_fmpz_poly_evaluate_arb(arb_t res, const fmpz_poly_t poly, const arb_t x, slong prec)

Set res to the value of the integer polynomial (given as a polynomial or as len coefficients) at the real ball x, using Horner's rule, rectangular splitting [PS1973] (which multiplies the integer coefficients by precomputed powers of x in dot products), or an automatic choice.

More
void _arb_fmpz_poly_evaluate_acb_horner(acb_t res, const fmpz * poly, slong len, const acb_t x, slong prec)
void arb_fmpz_poly_evaluate_acb_horner(acb_t res, const fmpz_poly_t poly, const acb_t x, slong prec)
void _arb_fmpz_poly_evaluate_acb_rectangular(acb_t res, const fmpz * poly, slong len, const acb_t x, slong prec)
void _arb_fmpz_poly_evaluate_acb(acb_t res, const fmpz * poly, slong len, const acb_t x, slong prec)
void arb_fmpz_poly_evaluate_acb(acb_t res, const fmpz_poly_t poly, const acb_t x, slong prec)

Set res to the value of the integer polynomial at the complex ball x, using Horner's rule, rectangular splitting, or an automatic choice (the real evaluation if x is real, rectangular splitting otherwise).

Deflation#

Returns the largest d such that \mathit{poly}(x) = g(x^d) for an integer polynomial g, that is, the GCD of the exponents of the nonconstant terms. For a constant polynomial the result is 1, and for the zero polynomial 0.

void arb_fmpz_poly_deflate(fmpz_poly_t res, const fmpz_poly_t poly, ulong deflation)

Sets res to g where \mathit{poly}(x) = g(x^d) with d = deflation, which must divide the exponent of every nonzero term of poly.

Polynomial roots#

The functions in this section assume that the polynomial is squarefree; this is not checked. For a general polynomial, isolate the roots of the factors of a squarefree factorisation, which also gives the multiplicities:

fmpz_poly_factor_t fac;
fmpz_poly_factor_init(fac);
fmpz_poly_factor_squarefree(fac, poly);

for (i = 0; i < fac->num; i++)
{
    deg = fmpz_poly_degree(fac->p + i);
    flint_printf("%wd roots of multiplicity %wd\n", deg, fac->exp[i]);
    roots = _acb_vec_init(deg);
    arb_fmpz_poly_complex_roots(roots, fac->p + i, 0, prec);
    _acb_vec_clear(roots, deg);
}

fmpz_poly_factor_clear(fac);

Flags for the root isolation functions (values 1 and 2): print information about the progress of the computation, and (only for arb_fmpz_poly_real_roots) compute the rational roots exactly first.

void arb_fmpz_poly_refine_root_arb(arb_t res, const fmpz_poly_t poly, const arb_t initial, slong prec)

Given a ball initial that contains exactly one root of the squarefree polynomial poly, in its interior unless initial is exact, sets res to an enclosure of that root with a relative accuracy of at least prec bits that is contained in initial. If the root is an endpoint of initial, the function may fail to terminate.

Full documentation
slong arb_fmpz_poly_real_roots(arb_ptr roots, const fmpz_poly_t poly, int flags, slong prec)
void arb_fmpz_poly_complex_roots(acb_ptr roots, const fmpz_poly_t poly, int flags, slong prec)

Write to roots disjoint enclosures of all real roots, or of all complex roots, of the squarefree polynomial poly, each with a relative accuracy of at least prec bits. arb_fmpz_poly_real_roots returns the number of real roots and writes them in increasing order; arb_fmpz_poly_complex_roots writes \deg(\mathit{poly}) roots: first the real roots in increasing order (with imaginary parts exactly zero), then the nonreal roots in conjugate pairs, the root in the upper half-plane first. The output array must have room for the degree of poly entries. A polynomial of degree less than 1 has no roots.

Full documentation

Special polynomials#

Sets res to the minimal polynomial of the Gaussian periods \sum_{a \in H} \zeta^a, where \zeta = e^{2 \pi i / q} and H runs over the cosets of the subgroup of order d = (q-1)/n of (\mathbb{Z} / q\mathbb{Z})^{\times}. The result has degree n; for d = 1 it is the cyclotomic polynomial \Phi_q. Requires q prime, n \mid q - 1 and \gcd(n, d) = 1; otherwise res is set to zero.

More

References#

  • [PS1973] M. S. Paterson and L. J. Stockmeyer, "On the number of nonscalar multiplications necessary to evaluate polynomials", SIAM J. Comput (1973)
Cite this page

The FLINT team, “arb_fmpz_poly.h (module overview),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/arb_fmpz_poly/index.html (generated 2026-10-20).