Improving Performance by Transitioning from Symbolic to Numeric Computing

[aidevnn]

I have faced significant challenges when computing splitting fields and Galois groups of high-degree symbolic polynomials.

These calculations can be incredibly time-consuming, especially when dealing with polynomials of degree greater than 5.

One approach that I am considering is leveraging numerical techniques such as approximation and interpolation to speed up the calculations.

Let's try.

[aidevnn]

ChatGPT generated the title and the comment of this issue after a short description of the subject.

[aidevnn]

Starting implementing BReal struct for arbitrary floating decimal, remains implementing unittest. Crafting LLL lattice reduction for passing from numerics to symbolics.

Work in progress

[aidevnn]

To find polynomial expression between algebraic numbers $P(\alpha) = \beta$, the last column of the Lattice can be made real with transformation $Re(\alpha^i) + π Im(\alpha^i)$ and the last cell will be $Re(\beta) + π Im(\beta)$.

Method source code https://github.com/aidevnn/FastGoat/blob/b39321fb0b621cf9050c0d2b33fc3593f33ac2d0/FastGoat/Examples/AlgebraicIntegerRelationLLL.cs#L18-L48

Now the polynomial $P=X^4 + 8X +12$ with A4 Galois Group can be computed faster in less than 10seconds. The minimal polynomial of the primitive element for the splitting field has degree 12.

A4 example https://github.com/aidevnn/FastGoat/blob/b39321fb0b621cf9050c0d2b33fc3593f33ac2d0/FastGoat/Examples/AlgebraicIntegerRelationLLL.cs#L232-L253