2022-07-27 –, Red
Depending on the applications, the requirement for a multivariate polynomial library may be efficient computation of product, division, substitution, evaluation, gcd or even Gröbner bases. It is well understood that the concrete representation to use for these polynomials depends on whether they are sparse or not. In this talk, we show that in Julia, the choice of representation also depends on whether to specialize the compilation on the variables.
Multivariate polynomials appear in various applications such as computer algebra systems, homotopy continuation or Sum-of-Squares programming. Different applications have varied requirements for a multivariate polynomial library making it challenging to choose a representation that would be the most efficient for all use cases. It is well understood for instance that the concrete representation to use for these polynomials depends on whether they are sparse or not. Having an abstract interface allows both the application to be independent on the actual representation used but also some lower level operations such as the computation of polynomial division or gcd.
In fact, this abstraction is even more important in Julia than other languages because Julia allows yet another aspect to enter into the design of multivariate polynomials. We show in this talk that for basic operations, the Julia compiler can either compile a generic method working for any set of variables or a method specialized to a specific one. This can be achieved in Julia by moving some part of the polynomial description from field values to type parameters, hence also reducing the memory footprint of polynomials. These 2 aspects: sparsity and specialization make up for 4 different representations that all have specific use cases where they are most appropriate. Packages relying on multivariate polynomial computation for which more than one use case can occur should therefore be implemented on an abstract multivariate polynomial interface and require the user to choose the implementation via the type of polynomials given as input.
We illustrate this with actual Julia packages implementing these representations: DynamicPolynomials.jl (sparse, non-specialised), TypedPolynomials.jl (sparse, specialized), SIMDPolynomials.jl (sparse, specialized) and TaylorSeries.jl (dense, specialized). We analyze the impact of the choice of representation for these representations in a benchmark for gcd computation. The gcd implementation is written generically thanks to the abstract MultivariatePolynomials.jl interface.
Chris Elrod is a frequent commenter on the Julia Discourse, Slack, and Zulip, as well as a contributor to the ecosystem, known in particular for LoopVectorization.jl and JuliaSIMD.
Benoît Legat is a postdoc at MIT with Prof. Pablo Parrilo in the Laboratory for Information and Decision Systems (LIDS).