Converting fmpz_mod_mpoly_t to fmpz_mod_poly_t

[Håvard Raddum]

Hi,

I have a program that works on multivariate polynomials over F_p, so using the type fmpz_mod_mpoly.  At a point I end up with a polynomial in only one variable (i.e. really a univariate polynomial) that I want to factor.  The method in fmpz_mod_mpoly_factor.h is quite slow, and I wonder if it might be faster if my polynomial was treated as the univariate polynomial it really is.  So, is there an easy way to convert an fmpz_mod_mpoly_t that only depends on a single variable to fmpz_mod_poly_t?

[Albin Ahlbäck]

Hello Håvard,

I believe you can use the undocumented functions
`fmpz_mod_mpoly_is_fmpz_mod_poly' and
`fmpz_mod_mpoly_get_fmpz_mod_poly'. Please see conversions in
`fmpz_mod_mpoly.h', at around line 333 in the current HEAD.

Best,
Albin

> --
>
> ---
> You received this message because you are subscribed to the Google
> Groups "flint-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to flint-devel...@googlegroups.com <mailto:flint-
> devel+un...@googlegroups.com>.
> To view this discussion, visit https://groups.google.com/d/msgid/flint-
> devel/3fe9c802-3020-4606-89d2-5f04c2083789n%40googlegroups.com <https://
> groups.google.com/d/msgid/flint-
> devel/3fe9c802-3020-4606-89d2-5f04c2083789n%40googlegroups.com?
> utm_medium=email&utm_source=footer>.

[Fredrik Johansson]

Indeed, we should document these. The interfaces are exactly the same as the documented fmpz_mpoly functions.

Håvard, please let us know if converting to fmpz_mod_poly makes a difference. In that case, we should add a univariate heuristic to fmpz_mpoly_factor.

Fredrik

To unsubscribe from this group and stop receiving emails from it, send an email to flint-devel...@googlegroups.com.
To view this discussion, visit https://groups.google.com/d/msgid/flint-devel/fbdad1ce-bdb7-4f4f-9c1f-2a7fd45fa069%40gmail.com.

[Håvard Raddum]

And for completeness, I also tried the univariate factoring method (fmpz_mod_poly_factor) instead of the root-finding method, but factoring in the univariate case actually took longer (35.594 sec) on the polynomial of degree 9261 than factoring as a multivariate polynomial.  Don't see any reason why that should be the case, though. 

[Håvard Raddum]

Thanks a lot for your tips!  Indeed, fmpz_mod_mpoly_get_fmpz_mod_poly was what I was looking for.  Actually, I am interested in finding the roots in F_p of my univariate polynomial, and see that fmpz_mod_poly_factor has a method called fmpz_mod_poly_roots that does exactly that.

For comparison, for a polynomial of degree 9261 and using the built-in root-finding method, it took 0.313 seconds to find the root on my computer.  Factoring as a multivariate polynomial indeed finds a linear factor giving the same root, but took 22.335 seconds to run.  So a big time difference.

Cheers,

Håvard

On Friday, 6 December 2024 at 11:35:20 UTC+1 Fredrik Johansson wrote: