Important regression in polynomial arithmetic since 1st World COVID19 containment

Skip to first unread message

Grégory Vanuxem

Dec 27, 2022, 5:31:07 AM12/27/22
to, Nemo-Devel

Just to let you know. I was discussing yesterday the use of FLINT 2
for different operations on polynomials over different rings. And as a
matter of fact I gave a bench that I ran at the beginning of the first
COVID 19 containment (around march 2020). But I was surprised by the
regression in terms of performance.
This is with nested univariate polynomials, the R.Fateman benchmark,
if memory does not deserve me multivariate polynomial operations were
not implemented/finalized in FLINT. Here FLINT routines are called via
Nemo on top of Julia.

March 2020:
R, x = PolynomialRing(ZZ, "x");
S, y = PolynomialRing(R, "y");
T, z = PolynomialRing(S, "z");
U, t = PolynomialRing(T, "t");
f = x + y + z + t + 1
p = f^30;
@time q = p*(p+1);
20.099625 seconds (2.32 M allocations: 102.120 MiB, 0.78% gc time)

And today on the same laptop (almost the same configuration):
julia> R, x = PolynomialRing(ZZ, "x");
julia> S, y = PolynomialRing(R, "y");
julia> T, z = PolynomialRing(S, "z");
julia> U, t = PolynomialRing(T, "t");
julia> f = x + y + z + t + 1
t + z + y + x + 1
julia> p = f^30;
julia> @time q = p*(p+1);
32.071521 seconds (8.32 M allocations: 335.585 MiB, 0.96% gc time,
0.02% compilation time).
julia> @time q = p*(p+1);
31.502950 seconds (8.31 M allocations: 335.553 MiB, 1.28% gc time,
0.01% compilation time)
julia> @time q = p*(p+1);
31.069855 seconds (5.59 M allocations: 265.802 MiB, 0.23% gc time)

It could be because of Julia upgrades but I would be surprised.


Dec 27, 2022, 5:59:40 AM12/27/22
to nemo-devel
Multivariate polynomials were added in 2016 in Nemo, see We ran the Bateman benchmark always with nested univariate polynomials, so this looks like a regression. I assume this is the same machine?


Grégory Vanuxem

Dec 27, 2022, 6:36:55 AM12/27/22
to, Nemo-Devel
My fault, multivariate polynomials were implemented in FLINT in 2020.
The same bench was ~13 sec in 2020 and ~11.5 as of today for
multivariate polynomials.

Dec 27, 2022, 4:06:41 PM12/27/22
to nemo-devel
I believe I found the regression. A possible fix is proposed at Thanks for the report!


Reply all
Reply to author
0 new messages