Applications & benchmarks
Here we illustrate FLINT's capabilities on various benchmark problems and give examples of research problems that were solved with FLINT's help.
Arithmetic with huge numbers
FLINT uses GMP and MPFR under the hood but notably also provides its own arbitrary-size integer and floating-point code which can be 2-10 times faster in many typical applications.
Digits of pi
A basic benchmark problem is to compute $\pi$ to 100 million digits using the builtin pi function (for GMP we use the GMP-chudnovsky program provided on the GMP website):
| Implementation | Time |
|---|---|
| GMP-chudnovsky | 62.1 s |
| MPFR | 172.9 s |
| FLINT | 31.6 s |
| FLINT (8 threads) | 9.34 s |
Benchmark machine: 8-core AMD Ryzen 7 PRO 5850U CPU (Zen 3).
FLINT is about twice as fast as GMP and five times faster than MPFR on this benchmark. When allowed to use multiple threads, FLINT is 6.6x faster than GMP (which is single-threaded only) and 18x faster than MPFR. Note that due to the nature of the algorithm used to compute $\pi$, this benchmark heavily exercises numbers of all sizes, not just 100-million-digit numbers.
We mention that FLINT is about half as fast as the special-purpose, closed-source pi computing program y-cruncher (which does this in 18.3 s on a single core and in 4.45 s on 8 cores); however, FLINT can compute far more general mathematical objects.
Exact linear algebra
Integer matrix multiplication
| Language, integer type | Algorithm | $b = 10$ | $b = 100$ | $b = 1000$ |
|---|---|---|---|---|
| Julia, BigInt | Naive (built-in * for Array) | 0.224 | 0.356 | 0.542 |
| Python, int | Naive (@ for numpy.array) | 0.0375 | 0.0731 | 0.890 |
| Python, gmpy2.mpz | Naive (@ for numpy.array) | 0.0479 | 0.0537 | 0.192 |
| Pari/GP, t_INT | Naive ($n^3 \times$ (c += a * b)) | 0.211 | 0.219 | 0.369 |
| Pari/GP, t_INT | Optimized (built-in * for t_MAT) | 0.00147 | 0.00920 | 0.102 |
| GMP (C++ wrapper), mpz_class | Naive ($n^3 \times$ (c += a * b)) | 0.0287 | 0.0294 | 0.169 |
| GMP, mpz_t | Naive ($n^3 \times$ (mpz_addmul)) | 0.0122 | 0.0172 | 0.159 |
| FLINT, fmpz_t | Naive ($n^3 \times$ (fmpz_addmul)) | 0.00395 | 0.0213 | 0.163 |
| FLINT, fmpz_t | Optimized (fmpz_mat_mul), | 0.0000678 | 0.00235 | 0.0456 |
| FLINT, fmpz_t | Optimized (fmpz_mat_mul), 8 threads | 0.0000675 | 0.000800 | 0.0142 |
Timing results are given in seconds. Benchmark machine: 8-core AMD Ryzen 7 PRO 5850U CPU (Zen 3). Note: for this benchmark, we configured FLINT to use the BLAS backend for modular matrix multiplications.
Matrix multiplication is a common kernel for other operations. Here we compare timings to multiply two 100 × 100 matrices with b-bit integer entries.
The main takeway is that an optimized integer matrix multiplication algorithm such as that provided by FLINT's fmpz_mat_mul is much faster (sometimes by more than a factor 1000) than a naive loop doing $n^3$ big-integer multiplications and additions. For the matrices in this benchmark, FLINT's fmpz_mat_mul is using a multimodular algorithm. (Pari/GP also uses a similar algorithm, but it is somewhat slower than FLINT.)
If one implements the naive algorithm, FLINT's fmpz_t is about 3× faster than GMP's mpz_t with small entries (and at worst 20% slower for medium-size entries) due to using an inline representation for word-size integers.
Multivariate polynomial arithmetic
FLINT includes fast, multithreaded code for multivariate polynomials over $\mathbb{Z}$, $\mathbb{Q}$ and $\mathbb{Z}/n\mathbb{Z}$ and other coefficient rings. Some older (2019) benchmarks results are available (part 1, part 2) demonstrating favorable performance compared to Maple, Trip and Giac on both sparse and dense problems.
Handling algebraic and exact numbers
Equality of two large expressions
Computer algebra systems often struggle to manipulate exact numbers like $\sqrt{2 + \sqrt{3}}$ when the expressions become large. FLINT can sometimes handle such problems more easily. In 2020 a SageMath user reported that SageMath did not finish in six hours when asked to check the equality $A = B$ of two algebraic numbers which arose in a matrix computation. The expressions for the numbers involve nested square roots and have about 7000 terms. The current version of FLINT proves this equality in four seconds.
Cutting squares into similar rectangles
Ian Henderson has a nice writeup about enumerating all ways to cut a square into $n$ similar rectangles. This problem was solved up to $n = 8$ with an exhaustive computer search using the exact real numbers in FLINT/Calcium to represent roots of polynomials.
Numerical computation
The ball arithmetic in FLINT (formerly the separate Arb library) is used in diverse applications (physics, biology, engineering, number theory, etc.) requiring extremely precise and reliable numerical computation.
Accurate Gaunt factors for quadrupole radiation
Josef Pradler and Lukas Semmelrock write in the The Astrophysical Journal (2021) about computing accurate Gaunt factors for nonrelativistic quadrupole bremsstrahlung:
The calculation of hypergeometric functions of large imaginary arguments is a difficult task [...]. A particular strength of [Arb] is the rigorous computation of hypergeometric functions [...]; common software frameworks such as Mathematica appear not able to yield results for $|\nu_i| \gtrsim 100$ for all required function values in a reasonable amount of time
We use Arb to calculate the hypergeometric functions, Sommerfeld factors, and all coefficients; in short, the entire expression This is required, because, first, products such as $S_i S_f \times |{}_2F_1(i \nu_f, i \nu_i; 1; z)|^2$ can be of the form $huge \times tiny$, and second, because of the occurrence of cancellations in the final linear combination of these terms. Because of factors $\exp(\pm \nu_{i,f})$ contained in $S_{i,f}$, it turns out that the required precision is approximately $|\nu_{i,f}|$. In our tabulation we therefore evaluate the ingredients with up to $10^4$ digits of precision.
The ternary Goldbach conjecture
FLINT/Arb has been used for certain computations in Harald Helfgott's solution of the ternary Goldbach problem, for instance to establish precise bounds for integrals involving the Riemann zeta function in the complex plane. The computations are described in more detail in Helfgott's book; source code is available on his website.
Figure: a short subsegment of one of Helfgott's integrals: $\int_{-\tfrac{1}{4}+8i}^{-\tfrac{1}{4}+40000i} \left|\frac{F_{19}(s+\tfrac{1}{2}) F_{19}(s+1)}{s^2}\right| |ds|$, where $F_N(s) = \zeta(s) \prod_{p\leq N} (1 - p^{-s})$.
The Riemann hypothesis
The highest verification of the Riemann hypothesis to date was done in 2020 by Dave Platt and Trim Trudgian, reaching height $3 \cdot 10^{12}$. Parts of their computations used FLINT/Arb ball arithmetic
[...] in place of full interval arithmetic whence there is a space saving of roughly 50%, which make applications more cache friendly.
The de Bruijn-Newman constant
FLINT/Arb was used in a large distributed computation as part of the "polymath" project to bound the de Bruijn-Newman constant. A contributor to that effort wrote:
Very impressed by the robustness of your software as well as by the tremendous speed gains that it has brought us (up till a factor 20-30 faster than Pari/GP). So far we haven't encountered a single bug in the software. Well done!
Burgers-Hilbert equation
Joel Dahne and Javier Gómez-Serrano have proved the existence of a periodic highest, cusped, traveling wave solution for the Burgers-Hilbert equation, and more recently also for the fractional KdV equation. The interval computations in the proofs took 10,000 CPU hours to run on a 384-core cluster, employing power series arithmetic and special functions provided by FLINT/Arb. The authors write:
These bounds are highly non-trivial, in particular $\delta_{0}$ is given by the supremum of a function on the interval $[0, \pi]$ which attains its maximum around $10^{-5000}$. [...] Note that these numbers are extremely small, too small to be represented even in standard quadruple precision binary128, though Arb has no problem handling them.