Abstract Polynomial Interface for high performance implementations.

[jjgarzella]

My research group (mostly @alexp616) has been working on implementing polynomial multiplication and polynomial powering on the GPU using CUDA.jl hardware. Our motivation is for applications in Birational Geometry and Number Theory, where polynomial powering over the integers is a fundamental operation. The current implementation uses a multi-modular parallel FFT that noticeably outperforms FLINT. The implementation isn't complete, for example there are many basic operations that still aren't implemented on the GPU.

I think it would be really cool to have this implementation used by Oscar. The use cases I would be interested in are

• Some Oscar algorithms are bottlenecked by polynomial multiplication, perhaps those could use a heuristic to decide whether to use a GPU-based algorithm. I've been told that Gromov-Witten invariants might fall into this category?
• If I'm writing my own algorithm (assuming I already have a Nvidia GPU, etc), I'd like to be able to use a GPU-based polynomial type as a drop-in replacement for ZZMPolyRing / ZZMPolyRingElem. It would be especially nice if this could "trickle down" to other polynomial-based operations (for one research direction, we need to do this with Laurent polynomials).

Julia has well-documented interfaces such as AbstractArray and AbstractDict, which packages can implement to make drop-in replacements for Array and Dict. What I'd really like is to have an AbstractPolynomial or AbstractMPolyRing for which one can implement various types and then mix and match them.

Given that context, I have a few (hopefully not to vague) questions:

• Are the methods in the docs, plus the basic ring operations, enough to guarantee that polynomial functionality works? Are there some things that depend on the implementation details of FLINT?
• Does the Laurent polynomial functionality here depend only on the multivariable polynomial operations?
• Should a type like our CuZZMPolyRingElem have the same parent ZZMPolyRing? Or would its implementation require a new parent type?

I'd appreciate any feedback or advice, I'm still a newcomer to Oscar.

[thofma]

Hi Jack! (sorry for the late response)

I'll try to answer some of the questions (and add some more questions).

My research group (mostly @alexp616) has been working on implementing polynomial multiplication and polynomial powering on the GPU using CUDA.jl hardware. Our motivation is for applications in Birational Geometry and Number Theory, where polynomial powering over the integers is a fundamental operation. The current implementation uses a multi-modular parallel FFT that noticeably outperforms FLINT. The implementation isn't complete, for example there are many basic operations that still aren't implemented on the GPU.

I think it would be really cool to have this implementation used by Oscar.

I can imagine that something like this could be useful.

• If I'm writing my own algorithm (assuming I already have a Nvidia GPU, etc), I'd like to be able to use a GPU-based polynomial type as a drop-in replacement for ZZMPolyRing / ZZMPolyRingElem. It would be especially nice if this could "trickle down" to other polynomial-based operations (for one research direction, we need to do this with Laurent polynomials).

This can probably made work.

Given that context, I have a few (hopefully not to vague) questions:

• Are the methods in the docs, plus the basic ring operations, enough to guarantee that polynomial functionality works? Are there some things that depend on the implementation details of FLINT?

To be honest, for the multivariate polynomials, it is not too clear what the "interface" is. Also, there is actually only very little code that is provided for multivariate polynomials implementing the interface.

Is there some specific "polynomial functionality", that you would like to work?

• Does the Laurent polynomial functionality here depend only on the multivariable polynomial operations?

Yes, one can build this laurent polynomials using any multivariate polynomial ring; see here.

• Should a type like our CuZZMPolyRingElem have the same parent ZZMPolyRing? Or would its implementation require a new parent type?

Yes, they need to be different.

I'd appreciate any feedback or advice, I'm still a newcomer to Oscar.

Keep the questions coming. We try to be a bit quicker with our response in the future.