Missing special case for factoring polynomials

[BhuvaneshBhatt]

Is your feature request related to a problem? Please describe.

I came across a missing special case for factoring polynomials in FLINT while using it in Mathematica, which causes such factoring to take a long time (well over 10 seconds for each of the examples below, which should take less than 0.02 seconds):

poly = x^103 + x^2 y^3 + x^101 y^103 + y^106 expected_factorization = (x^101 + y^3) (x^2 + y^103)

poly = x^162 y^127 + x^156 y^13 + x^6 y^114 + 1 expected_factorization = (1 + x^12 y) (1 - x^12 y + x^24 y^2 - x^36 y^3 + x^48 y^4 - x^60 y^5 + x^72 y^6 - x^84 y^7 + x^96 y^8 - x^108 y^9 + x^120 y^10 - x^132 y^11 + x^144 y^12) (1 + x^2 y^38) (1 - x^2 y^38 + x^4 y^76)

poly = x^174 + y^16 + x^240 y^168 + x^66 y^184 expected_factorization = (x^174 + y^16) (1 + x^22 y^56) (1 - x^22 y^56 + x^44 y^112)

poly = 453192 x^128 y^27 - 652695 x^170 y^89 - 61824 x^130 y^115 + 89040 x^172 y^177 expected_factorization = 3 x^128 y^27 (-184 + 265 x^42 y^62) (-821 + 112 x^2 y^88)

Notice that each example factors into two pairs of binomials.

Describe the solution you'd like

It would be great if this special case could be added to the FLINT polynomial factorization code.

[albinahlback]

Can you add an MWE for the issue?

[fredrik-johansson]

$ time build/examples/factor_polynomial "x^103 + x^2*y^3 + x^101*y^103 + y^106"
x^103+x^101*y^103+x^2*y^3+y^106 =
1*(x^2+y^103)^1*(x^101+y^3)^1

real	0m14,624s
user	0m12,254s
sys	0m2,368s

@tthsqe12 Any idea why these are so slow? I guess we could try to add some special case, but I'd rather improve the general-purpose factoring algorithm if possible.

[fredrik-johansson]

I guess this is it: fmpz_mpoly_factor has the following special case for bivariate polynomials:

    else if (ctx->minfo->nvars == 2)
    {
        ...
        fmpz_mpoly_get_bpoly(b, A, 0, 1, ctx);
        fmpz_bpoly_factor(u, bf, b);
    }

Commenting out this branch, the first example takes 0.01 seconds as expected.

So we should figure out why fmpz_bpoly_factor is slow, and fix it.

If it can't be fixed, change the heuristic in fmpz_mpoly_factor to call fmpz_bpoly_factor for bivariates only when it's worth it.

[fredrik-johansson]

In the first example, the bottleneck is fmpz_bpoly_divides. One can get it down to 0.2 seconds by adding a mod p heuristic (https://github.com/fredrik-johansson/flint/commit/e3e8f0238c09130744cb0581e4a7ef791cb31504).

However, the other examples are dominated by lifting.

I think fmpz_bpoly_factor just has poor asymptotics, and I'm not sure if that can be fixed easily. Unfortunately, the fix is not as simple as commenting out the nvars == 2 branch either, because the generic code currently crashes for some bivariates.