FLINT3.7.0-dev
/
Overview

Ball arithmetic

This section describes the algorithms behind FLINT's ball arithmetic: the modules mag, arf, arb and acb, and the polynomial, matrix and calculus modules built on them (arb_poly, acb_poly, arb_mat, acb_mat, arb_calc, acb_calc and arb_fmpz_poly). Each page gives the algorithm, the argument that its result is an enclosure, and the functions that implement it. Start with the overview, which explains the design and lists the pages by topic. Special functions have their own group, Special functions, and the other floating-point types of FLINT are compared in Floating-point arithmetic in FLINT.

OverviewBall arithmeticHow FLINT represents real and complex numbers as midpoint-radius balls, how each operation computes a midpoint and a bound for the propagated and rounding errors, why the radius has its own fast 30-bit type, and which pages describe the algorithms.

In this section#

OverviewBall arithmeticHow FLINT represents real and complex numbers as midpoint-radius balls, how each operation computes a midpoint and a bound for the propagated and rounding errors, why the radius has its own fast 30-bit type, and which pages describe the algorithms.AlgorithmRepresentation of radii and midpointsThe formats of mag_t (30-bit mantissa, upper-bound rounding) and arf_t (variable-length mantissa, correct rounding), with proofs that the basic mag operations give upper bounds, and how a rounding error becomes part of the radius.AlgorithmError propagationBounds for the propagated error of arithmetic operations, roots and elementary functions on balls, with proofs, together with the tail bounds for series that are used throughout the special function code.AlgorithmDot products of ballsHow arb_dot sums many products of balls in one fixed-point accumulator with a single final rounding, bounds all radius contributions with 30-bit word arithmetic, and lowers the working precision to what the radii justify.AlgorithmMultiplying polynomials with ball coefficientsHow arb_poly and acb_poly multiply polynomials with ball coefficients by scaling, splitting into blocks of similar magnitude and exact integer polynomial products, with separate products of nonnegative polynomials for the radii; with proofs that the results are enclosures.AlgorithmPower series in ball arithmeticHow truncated power series with ball coefficients give rigorous Taylor expansions, why their correctness is automatic, and how the choice between recurrences and Newton iteration affects the width of the enclosures; with the algorithms used by arb_poly, acb_poly and the generic gr_poly code for inversion, exponentials, roots, logarithms, trigonometric functions and composition.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.AlgorithmIsolating and refining real rootsBisection with exclusion and monotonicity tests for isolating the simple real roots of an analytic function given by a ball evaluator, Newton iteration with a rigorous quadratic error bound, the interval Newton operator, and precision doubling, as used by arb_calc, arb_poly and arb_fmpz_poly.AlgorithmBall matrix multiplicationHow arb_mat_mul and acb_mat_mul multiply ball matrices by splitting the inner dimension into blocks of entries with similar exponents, multiplying the midpoints exactly as integer matrices, and bounding the radius product in double precision, with the resulting error bounds.AlgorithmVerified linear algebraHow arb_mat and acb_mat solve linear systems, invert matrices and compute determinants with rigorous enclosures, by interval Gaussian elimination, by preconditioning with an approximate inverse, and by certifying an approximate solution with a residual bound.AlgorithmEigenvalue enclosuresHow acb_mat computes rigorous enclosures of the eigenvalues and eigenvectors of complex matrices by certifying floating-point approximations from the QR algorithm, with a global perturbation bound, a Gershgorin test after an approximate diagonalisation, and Rump's fixed-point method for eigenvalue clusters.AlgorithmRigorous numerical integrationHow acb_calc_integrate computes enclosures of integrals of analytic functions along line segments in the complex plane, combining direct interval enclosures, Gauss–Legendre quadrature with error bounds from bounds of the integrand on Bernstein ellipses, and adaptive bisection; with the stopping rules and the role of the user's evaluation function.

Referenced from#

Cite this page

The FLINT team, “Ball arithmetic,” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/algorithms/ball-arithmetic/index.html (generated 2026-10-20).