Help understanding the relationship between generic and specific types in Flint3

[GiacomoPope]

This is a very broad question, but I will pick something specific just to help make this clear.

In gr_poly.h there are methods for evaluation, and in particular, fast multipoint evaluation using product trees is available for the generic type.

Looking at then specific types, fmpz_mod_poly has both the naive iterative Horner method, but also a faster method building a product tree, which i assume is similar to the above for the generic type. However, this same method seems to be missing for fq_poly, which has no multipoint evaluation at all?

For the cases where it is not implemented for the specific type, can we fall back to the generic type? In the cases where it's implemented for both what happens? What's the relationship between generic_X and specific_X.

My thinking for python-flint, the answer for the above then filters through to how we structure out code.

If we can inherit generic methods on specific types, should we then build from flint_base and implement the generic_types first, and then do things like cdef class fmpz_poly(generic_poly), if we can inherit the available methods?

[oscarbenjamin]

Making the question broader I wonder if we should use the generic types for all polynomials and matrices.

At a base level the scalar types like fmpz, fmpq, fmpz_mod, and fq cannot really be implemented in a purely generic way. We need to have Python types that correspond to each Flint scalar type and they need to have methods, operators etc that are specific to those types.

It should be possible though to use gr_poly or gr_mat rather than having e.g. fmpz_poly, fmpq_poly etc. That way we can have e.g. a single python-flint class that encompasses all the different Flint _poly types and uses Flint's generics for most of the basic methods.

There are some functions in Flint that are specific to one type though e.g. fmpz_mat_snf for computing the Smith Normal Form of a matrix of integers. For these perhaps instead of having methods like M.snf() there could be a function like snf(M) where the function converts the matrix to fmpz_mat internally. This would not require python-flint to expose an fmpz_mat type but just the Cython code in the snf function would need to be able to convert to a C-level fmpz_mat (which I think just means casting the pointer).

[oscarbenjamin]

I have a bit of a better understanding of how the gr stuff works now and so some of what I said above does not make sense any more...

I think that we want to add the gr_ stuff and that will provide duplicate implementations for all existing types but can also be used to construct types that don't yet exist in python-flint. The gr_types will all be separate though and not connected by inheritance in a way that is different from how the existing types are connected in inheritance. Effectively then gr is just another ground type like fmpz etc. Conversions should be implemented for all non-generic types to gr and back. Someone using the gr type directly will need to construct the appropriate context somehow and can then have somewhat direct access to the gr functions.

In a higher-level interface we can abstract over this so that the user does something like:

F, z = GF(p, d)
R, [x, y] = F.mpoly_ring(["x", "y"])
p = x*y + z
p.factor()

The internal implementation of R would then be gr_mpoly because we don't have another implementation of mpoly for finite fields. If the base ring had been Z then the internal implementation would have been fmpz_mpoly. A user at this level should not need to think about whether the generic or non-generic types are being used and the high-level wrapper should choose implicitly based on what is available.

There are then two cases where we might want to convert between gr and non-gr types internally for an operation:

1. If we have gr_mpoly say over GF(p, d) then it does not define gr_mpoly_factor but in some cases we could use a non-generic type to compute the factorisation. So we convert, compute the operation and convert back.

2. We have a non-generic type that is missing some method such as e.g. fq_default_poly_integral or something but a generic implementation exists. Then we convert from non-generic type to gr and back to compute the operation. (This particular example maybe does not make sense because it is probably more efficient to have a simple implementation of computing the integral but in other cases it might make sense.)

Those conversions should all be transparent to the user though and ideally with a high-level interface they wouldn't need to think about these things.