LLL improvements

[Fredrik Johansson]

Hi all,

I have recently improved the multiprecision code in fmpz_lll, mainly by using nfloat instead of mpf and mpfr and in some cases using arb instead of fmpq.

As a result, factoring high-degree polynomials in Z[x] with many local factors is now often ~5x faster, and finding integer relations in high dimension is often ~10x faster (one example is 60x faster).

Here is a short writeup: https://fredrikj.net/blog/2025/optimizing-multiprecision-lll-in-flint/

Our LLL code can certainly be optimized a lot more (there are some ideas in the blog post), but it's a big project.

Fredrik

[Bill Hart]

This is really nice work! It's also written up very well too.

The original code probably represents nearly a year of work between
Andy and I (to say nothing of the original work of people whose work
we were building on). It's really fantastic to see it taken seriously
and live on with such impressive speedups!

Bill.

> --
>
> ---
> You received this message because you are subscribed to the Google Groups "flint-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to flint-devel...@googlegroups.com.
> To view this discussion, visit https://groups.google.com/d/msgid/flint-devel/CAJdUXTK53JA_89kreKzfwXub9Sa%3Drq7nPymHfpcpQ2X%3DEFSWmA%40mail.gmail.com.

[Jeffrey Sarnoff]

Well done!

Best,

Jeffrey

To view this discussion, visit https://groups.google.com/d/msgid/flint-devel/CAB0xFns_8zGVC2%3DApR1RRT7_JMCcn1pvusQoE4fQUufBNxHFxw%40mail.gmail.com.