Dense bivariate polynomials: generic operations and resultants

[maelhos]

Following #2449, I've been working on a prototype to handle dense bivariate polynomials in FLINT. Would this feature be interesting ?
I know for a fact that a good backend implementation of bivariate resultants (over large finite fields, $\mathbb Q$ and $\mathbb Z$) is really a feature a lot of people miss in Sage.

Most of it would follow https://github.com/vneiger/pml/blob/main/ntl-extras/lzz_pXY/src/lzz_pXY.cpp; the primary goal is to have basic arithmetic operations and bivariate resultant (using the geometric multipoint).

I have no idea how to name it, nmod_biv_poly maybe ?

[fredrik-johansson]

We already have generic bivariate polynomials: just use gr_poly with any polynomial base ring. This is surely the best place to implement fast bivariate resultants over finite fields as it will work out of the box with all our finite field implementations (and future ones).

There is also n_bpoly in the undocumented n_poly module used internally by our multivariate polynomials. If you want to work specifically with nmod coefficients, one option would be to document and extend that code, though a generic approach really seems better to me.

There is maybe also a case to be made for having a version of bivariate polynomials with 1D storage, but this wouldn't be my first priority.

I know for a fact that a good backend implementation of bivariate resultants (over large finite fields, Q and Z ) is really a feature a lot of people miss in Sage.

Indeed, I think this is a great project.

[maelhos]

I agree that bivariate polynomials are in essence just generic polynomials over some base polynomial ring.
Currently, bivariate resultants seem to be supported by

flint/src/gr_poly/resultant.c

Line 42 in d612c08

int gr_poly_resultant(gr_ptr r, const gr_poly_t f, const gr_poly_t g, gr_ctx_t ctx)

I imagine, but the complexity is probably not ideal in the case where the base ring is a polynomial ring.

Also, the current geometric multipoint is only for small characteristic fields, though I can first implement it for big characteristics as well. I have no idea if a generic ring geometric multipoint is possible / is a good idea, though.

Also, the case of Z and Q is a bit unclear; we talked about it a bit with @vneiger, and we're not quite sure how to deal with the potential coefficient blowup... Considering the "basis" algorithm of PML for bivariate resultant uses geometric multipoint and efficient univariate resultant, maybe we can implement the resultant for big and small characteristics and use CRT for Q and Z ?

[fredrik-johansson]

I imagine, but the complexity is probably not ideal in the case where the base ring is a polynomial ring.

"Not ideal" is an understatement, as the current fallback is to construct the Sylvester matrix and compute the determinant. The subresultant algorithm ought to be used instead when possible. (Currently this is implemented in https://github.com/flintlib/flint/blob/main/src/mpoly/univar.c for the internal mpoly generics, but wants porting to gr generics.)

I have no idea if a generic ring geometric multipoint is possible / is a good idea, though.

It should be possible.

Also, the case of Z and Q is a bit unclear;

Doing it by CRT sounds natural, unless the coefficient bounds available are extremely pessimistic. (Or is there a fast way to validate a resultant without bounds?)

[maelhos]

Understood,

What I suggest I can do right now is :

• Implement a specialization of gr_resultant in the case where the base ring is nmod_poly (basically and extra if statement) in a draft PR and test perf
• generalize that using CRT + big characteristic polynomials ring
• Try a more generic approach with generic geometric multipoint and compare it to more specialized approaches.

Also, I don't really know what the interesting target base ring is apart from F_p, Z, Q, and maybe real rings are also possible (rings with bounded size elements or CRTable).

[vneiger]

Try a more generic approach with generic geometric multipoint and compare it to more specialized approaches.

A first version (requiring fewer additions) could also make use of general (not geometric sequence) multipoint evaluation, which is implemented for more coefficient types than just nmod (at least, it is for fmpz_mod), and has a gr_poly_evaluate_vec*.