any_root(ring=F_ext) is underperforming

[GiacomoPope]

Steps To Reproduce

In my refactoring of any_root() #37170 I accidentally introduced a performance regression when finding roots over extension fields.

Sage 10.2

sage: %time _ = f.any_root()
CPU times: user 6.89 ms, sys: 321 µs, total: 7.21 ms
Wall time: 6.91 ms
sage: %time _ = f.any_root(L)
CPU times: user 7.34 ms, sys: 316 µs, total: 7.66 ms
Wall time: 7.42 ms
sage: %time _ = f.change_ring(L).any_root()
CPU times: user 3.13 s, sys: 9.92 ms, total: 3.14 s
Wall time: 3.15 s

SageMath version 10.3.beta8

sage: %time _ = f.any_root()
CPU times: user 6.68 ms, sys: 116 µs, total: 6.8 ms
Wall time: 6.75 ms
sage: %time _ = f.any_root(L)
CPU times: user 844 ms, sys: 4.69 ms, total: 849 ms
Wall time: 849 ms
sage: %time _ = f.change_ring(L).any_root()
CPU times: user 819 ms, sys: 3.62 ms, total: 823 ms
Wall time: 823 ms

Expected Behavior

When I refactor code, it should not have worse performance

Actual Behavior

I have refactored code and introduced poor performance

Additional Information

The fix will be to go back to any_root() and complicate the implementation to look for a root in the smallest extension before casting the root to F_ext. Currently, the implementation finds a root in f.change_ring(F_ext).any_root() which is very slow for very large extensions.

The new version should look for some degree degree distinct degree factorisation over various extensions working with the smallest one possible.

Environment

N/A

Checklist

• I have searched the existing issues for a bug report that matches the one I want to file, without success.
• I have read the documentation and troubleshoot guide

[GiacomoPope]

Looking a little more carefully the real culprit is the "cheating" any_root() did before.

In the original code, if degree > 1 or ring was supplied which needed a degree > 1 irreducible factor, the algorithm worked in the minimal extension by finding an irreducible polynomial of degree d then called f.roots(ring)[0] on this irreducible. This in many cases is much faster that using any_root() and f.roots() uses NTL/Flint calls.

The new code always uses any_root(), which seems... like the right thing to do, but because this is python code it's slower for very large extensions or very large characteristic.

I started working on a fix in #37443, but I have an issue that if I do

f = self.any_irreducible_factor(degree=d)
F_ext = self.base_ring().extension(d)
r = f.roots(F_ext)
return ring(r)

SageMath cannot always coerce the root in F_ext to the ring ring.

This coercion is a serious problem and even dumb examples lead to errors

sage: R.<x> = GF(11)[]
....: F_ext = GF(11^6, modulus=x^6+3*x^4+4*x^3+6*x^2+7*x+2,names="a")
....: ring = GF(11^6, modulus=x^6+3*x^4+4*x^3+6*x^2+7*x+2,names="b")
....: F_ext(ring.random_element())
# Error

I think maybe this needs a separate issue?

[grhkm21]

Yes, let’s open a separate issue for the finite field issue(sss), and probably get people on sage-devel? I think maybe the whole design should be reconsidered.

[GiacomoPope]

I agree. Are you happy to make the finite field issue? For now we could patch this function to call roots when the degree of the base field goes over a threshold or when the characteristic goes over a threshold?

This seems ugly but I don't know what else to do

[grhkm21]

Yes and yes. I'll collect some more data / potential fixes first before creating the issue

[GiacomoPope]

This should now be fixed by #37443

┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 10.2, Release Date: 2023-12-03                    │
│ Using Python 3.11.4. Type "help()" for help.                       │
└────────────────────────────────────────────────────────────────────┘
sage: set_random_seed(0)
....: K.<x> = GF((29, 3), names="a")[]
....: f = K.random_element(15).monic()
....: L.<a> = f.splitting_field()
....: %time _ = f.roots(L)
....: %time _ = f.any_root(L)
CPU times: user 90.3 ms, sys: 399 µs, total: 90.7 ms
Wall time: 90.7 ms
CPU times: user 11.1 ms, sys: 615 µs, total: 11.7 ms
Wall time: 12.8 ms

┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 10.3.beta8, Release Date: 2024-02-13              │
│ Using Python 3.11.4. Type "help()" for help.                       │
└────────────────────────────────────────────────────────────────────┘
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Warning: this is a prerelease version, and it may be unstable.     ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
sage: set_random_seed(0)
....: K.<x> = GF((29, 3), names="a")[]
....: f = K.random_element(15).monic()
....: L.<a> = f.splitting_field()
....: %time _ = f.roots(L)
....: %time _ = f.any_root(L)
CPU times: user 81 ms, sys: 347 µs, total: 81.3 ms
Wall time: 81.4 ms
CPU times: user 7.63 ms, sys: 407 µs, total: 8.04 ms
Wall time: 8.92 ms