fredrikj.net / blog /

Optimizing multiprecision LLL in FLINT

August 21, 2025

This post describes some recent improvements to the multiprecision arithmetic in FLINT's LLL lattice basis reduction. LLL has many important applications, including two key tasks where it is used internally by FLINT:

• Factoring in $\mathbb{Z}[x]$ using van Hoeij's algorithm.
• Integer relation searches as part of equality proving and symbolic simplification in the Calcium implementation of $\overline{\mathbb{Q}}$ and $\mathbb{C}$.

As we shall see, these two applications have gotten significantly faster in the current development version of FLINT in large dimensions, with speedups up to 6x and 60x observed on benchmarks for factoring and integer relations respectively.

Overview of FLINT's LLL

FLINT's LLL incorporates ideas from the following articles:

• Damien Stehlé, Floating-Point LLL: Theoretical and Practical Aspects
• Gilles Villard, Certification of the QR factor R and of lattice basis reducedness

The idea is essentially the following: we first do an heuristic LLL reduction using floating-point arithmetic and then rigorously certify its correctness using posteriori analysis of an approximate QR factorization. The certification itself can use floating-point arithmetic if we make judicious use of directed rounding. This strategy is significantly faster than executing the original LLL algorithm in exact rational arithmetic.

Both the heuristic LLL reduction and the certification come in two versions: a fast machine precision implementation, and a slower multiprecision implementation used as a fallback when machine precision fails. This typically becomes necessary in large enough dimensions. Finally, there is an exact certification (using $\mathbb{Q}$ arithmetic and the naive definition of LLL-reducedness) used as an ultimate fallback when even the multiprecision floating-point QR certification is inconclusive.

(Also worth noting is that for lattices with large bit size, FLINT reduces to smaller bit sizes using "ULLL" an unpublished algorithm by Andrew Novocin but inspired by the $\tilde L^1$ algorithm from Andrew Novocin, Damien Stehlé, Gilles Villard, An LLL-reduction algorithm with quasi-linear time complexity. However, this high-level wrapper is largely independent of the underlying floating-point LLLs.)

Changes

Over the last month, I made the following improvements to FLINT's LLL code:

• The heuristic multiprecision LLL previously used GMP's mpf type. I changed it to use FLINT's faster nfloat instead.
• The multiprecision floating-point certification previously used MPFR's mpfr type with directed rounding. I changed it to use nfloat. This required adding directed rounding support for nfloat as a new feature.
• The heuristic multiprecision LLL previously attempted to detect cancellations in dot products in order to fall back to a more precise calculation when too many accurate digits are lost. This cancellation check was implemented by computing norms of the input vectors, which is about as expensive as actually computing the dot product. It would be possible to optimize the cancellation check, but I decided to just remove this trick entirely as it does not seem to actually help much in practice. (Before removing this trick, I was reassurred to find that Stehlé's article also discusses the fact that it might be a net slowdown, confirming my own limited tests.)
• When the multiprecision floating-point QR certification fails, FLINT would previously jump to naively checking LLL-reducedness using exact fmpq arithmetic as noted above. This suffers from horrendous coefficient blowup. I thus inserted another naive LLL-reducedness check with high precision arb ball arithmetic before the fmpq test. (This should make the fmpq fallback extremely rare.)

Polynomial factoring benchmark

Here are the results on FLINT's benchmark suite for factoring in $\mathbb{Z}[x]$ (running build/fmpz_poly_factor/profile/p-factor_hard -hard).

Quick explanation: each input polynomial has the specified degree and coefficients smaller than $\pm 2^{\text{Bits}}$. "Factors" is the number of factors over $\mathbb{Z}[x]$ and "Local factors" is the number of factors over $\mathbb{Z}_p[x]$ (usually larger than the number of global factors; it is smaller in some entries in the table below due to a deflation hack). A large number of local factors is what necessitates running LLL to find the correct recombination; the dimension of the lattice is roughly that of the number of local factors.

We observe some very nice speedups on all examples with more than 100 local factors where the multiprecision code in the LLL typically really starts to kick in, and on some smaller examples too. For the largest examples there seems to be a pretty consistent 4x to 6x speedup, with the time for the adversarial Swinnerton-Dyer polynomial S10 dropping all the way from eight hours to less than two hours!

Actually, S9 (and presumably also S10) is still slower than in FLINT 1.6 of ten years ago (Bill Hart reported this example taking 21 seconds with FLINT 1.6 in 2016) due to some missing heuristics in the FLINT 2 (and FLINT 3) factoring code. These heuristics presumably result in easier lattice problems. Nevertheless, it is interesting that we partly seem to catch up just by improving LLL performance for "hard" lattices.

Integer relation benchmark

I added a new profile program (build/fmpz_lll/profile/p-lindep) to test performance on integer relation lattices. This program generates a vector of $n$ uniformly random real numbers, inserts $\log(2)$, $\log(3)$, $\log(6)$ at positions $0.25n$, $0.5$ and $0.75n$, and runs _qqbar_acb_lindep with precision 64, 128, 256, ... bits until the relation $(\ldots, 0, \pm 1, 0, \ldots, 0, \pm 1, 0, \ldots, 0, \mp 1, 0, \ldots)$ is recovered. The "Precision" column in the table shows at what input precision (= bit size of lattice) this occurs.

One can think of more interesting integer relation problems (this one would be solvable by brute force), but this one seemed appropriate for a simple benchmark.

One notices significant improvements for $n$ larger than about 200, with a consistent order-of-magnitude speedup for $n$ larger than 250 and a 60x speedup in one case ($n = 290$). It is worth noting that the running time for the new LLL code increases much more smoothly with $n$: the FLINT 3.3 LLL would randomly take 5-10 times longer for some $n$ compared to adjacent one due to hitting the slow fmpq fallback, which is now avoided.

Future

There is much more to optimize about FLINT's LLL.

• The high-level algorithm was originally designed specifically for knapsack lattices (which occur in van Hoeij's algorithm), so various parameters could presumably be tuned differently for for other kinds of lattices.
• The machine precision and integer arithmetic could be optimized.
• Certification could use ball arithmetic instead of floating-point arithmetic with directed rounding.
• Multithreading is not completely straightforward, but should be doable.
• Recently, new lattice reduction algorithms have been published that perform much better than the "classical" floating-point LLL at least in some applications, more effectively reducing the work to block linear algebra (QR factorization and matrix multiplication). See FLATTER by Keegan Ryan and Nadia Heninger, and BLASTER by Léo Ducas, Ludo Pulles and Marc Stevens. It would be interesting to implement these algorithms using FLINT's multiprecision nfloat linear algebra.

fredrikj.net  |  Blog index  |  RSS feed  |  Follow me on Mastodon  |  Become a sponsor