Computations over `AbsSimpleNumberField` are very slow

[HechtiDerLachs]

Here's some code to play around with a current example of ours (CC: @simonbrandhorst):

h0 = load("equation.txt")

R = parent(h0)
x, y = gens(R)
h0 = evaluate(h0, [y, x])

E0 = elliptic_curve(h0, x, y)

kkt = coefficient_ring(R)
P = base_ring(kkt)
kk = coefficient_ring(P)

kk2, iso = absolute_simple_field(kk)
iso_inv = pseudo_inv(iso)

kk2T, T = kk2[:T]
Fkk2T = fraction_field(kk2T)
Fkk2Txy, (x, y) = Fkk2T[:x, :y]

iso_ffs = f->map_coefficients(iso_inv, numerator(f))//map_coefficients(iso_inv, denominator(f))

h0_simp = map_coefficients(iso_ffs, h0)
R = parent(h0_simp)
x, y = gens(R)

E0_simp = elliptic_curve(h0_simp, x, y)

Q, T = QQ[:T]
FQ = fraction_field(Q)
FQxy, (x, y) = FQ[:x, :y]

h1 = y^2 -(x^3 - (T^8 + 1)*x)

E1 = elliptic_curve(h1, x, y)

kk2T, T = kk2[:T]
Fkk2T = fraction_field(kk2T)
Fkk2Txy, (x, y) = Fkk2T[:x, :y]

h1_ext = y^2 -(x^3 - (T^8 + 1)*x)

E1_ext = elliptic_curve(h1_ext, x, y)

kkT, T = kk[:T]
FkkT = fraction_field(kkT)
FkkTxy, (x, y) = FkkT[:x, :y]

h1_tower = y^2 -(x^3 - (T^8 + 1)*x)

E1_tower = elliptic_curve(h1_tower, x, y)

S1 = elliptic_surface(E1, 2)
S1_tower = elliptic_surface(E1_tower, 2)
S1_ext = elliptic_surface(E1_ext, 2)

@time weierstrass_chart(S1);
@time weierstrass_chart(S1_ext);
@time weierstrass_chart(S1_tower);

@profview weierstrass_chart(S1);
@profview weierstrass_chart(S1_ext);
@profview weierstrass_chart(S1_tower);

and here's the associated file.

The timings for the second last set of commands for me is:

julia> @time weierstrass_chart(S1);
  0.049070 seconds (581.03 k allocations: 24.731 MiB)

julia> @time weierstrass_chart(S1_ext);
 23.779963 seconds (110.45 M allocations: 6.985 GiB, 3.09% gc time, 0.13% compilation time)

julia> @time weierstrass_chart(S1_tower);
  0.449551 seconds (4.29 M allocations: 303.480 MiB, 28.88% gc time)

So computing over kk2 which is of type AbsSimpleNumberField is slower by a factor of ~500 compared to QQ. Why?

I will write a follow-up with my estimations from usage of the profiler.

[HechtiDerLachs]

My estimation is that most of the time is spent on the arithmetic of fractions of multivariate polynomials, i.e. elements of FracField. For these cancellation of fractions via gcd is implemented and can not be switched off.

From the stacktrace it now seems that gcd computation in polynomial rings over AbsSimpleNumberField proceed via some kind of factorization and that all together really has an impact on performance.

Unfortunately, we can not simply kick out the use of FracFields in the localizations. Using them was requested by @simonbrandhorst , @afkafkafk13 , and @jankoboehm years ago and now it's deeply built in.

Any ideas how things can be sped up nevertheless? @fieker ? @thofma ?

[simonbrandhorst]

I don't remember "requesting" that. But it is biting us all the time. The FractionFields just don't seem to be right for accommodating localisations.

[HechtiDerLachs]

But the problem stays. Here's a followup for analysis:

julia> x, y, t = gens(load("R1.txt"));

julia> @time gcd(x^100 - 7*y^2 + y*t^7, y^4 - y^2 + 1);
  0.000272 seconds (150 allocations: 7.367 KiB)

julia> x, y, t = gens(load("R1_ext.txt"));

julia> @time gcd(x^100 - 7*y^2 + y*t^7, y^4 - y^2 + 1);
  0.027662 seconds (15.77 k allocations: 1.019 MiB)

julia> x, y, t = gens(load("R1_tower.txt"));

julia> @time gcd(x^100 - 7*y^2 + y*t^7, y^4 - y^2 + 1);
  0.000395 seconds (311 allocations: 22.586 KiB)

The three polynomial rings used are serialized in these files: R1.txt R1_ext.txt R1_tower.txt

I think everyone wants faster arithmetic in the fraction fields of these rings, right?

[lgoettgens]

@fieker wants to look into this

[afkafkafk13]

I don't remember "requesting" that. But it is biting us all the time. The FractionFields just don't seem to be right for accommodating localisations.

I don't think, Simon or I ever requested that explicitly. It was more a decision to do it 'properly' using the Oscar-framework and not spend manpower on building something separate using the additional knowledge of our context. On the other hand, I can confirm the observations that it is slow.

[thofma]

The example errors with

julia> R = parent(h)
ERROR: UndefVarError: `h` not defined
Stacktrace:
 [1] top-level scope
   @ REPL[5]:1

[HechtiDerLachs]

Yes, sorry. I hadn't run the whole script at once in the end. It's updated now.

[thofma]

I think we can make the gcd faster, see https://github.com/thofma/Hecke.jl/pull/1505. It still needs a bit of tweaking.

[HechtiDerLachs]

Another instance where I'm having trouble:

nums = load("numerators.txt")
dens = load("denominators.txt")
U = powers_of_element(prod(dens));
L, _ = localization(U);
imggens = [a//b for (a, b) in zip(nums, dens)]
R = base_ring(L)
v = gens(R)
g = L.(imggens)
phi = hom(R, L, g)
w1 = phi(v[1])
w1^2 # computes
b = v[1]^2
phi(b) # Fails!

Here are the files: numerators.txt denominators.txt

For a short version you may just compare

nums = load("numerators.txt")
dens = load("denominators.txt")
f = nums[1]//dens[1]
f^2 # computes
nums[1]^2 // dens[1]^2 # fails

[HechtiDerLachs]

I think we can make the gcd faster

That's actually great news! Thanks a lot!

Do you think, the example I just gave should be off limits for gcd computation in terms of size?

[thofma]

Still under construction, so cannot give a definite answer yet.

[thofma]

Yes, we can make your last example work. It is quite the opposite of the original issue, since this is about multivariate polynomials over towers of fields, as opposed to AbsSimpleNumField.

[HechtiDerLachs]

Great news again! Thanks a lot! Let me know when your patch is ready to be tried out.

Yes, it is the opposite. Since working over AbsSimpleNumField was not very pleasing for the moment, I changed back to my tower and continued there until I hit a wall. That was eventually the one above. So if this also works, I'm very happy!

[thofma]

Should be faster with #3750