Handling Polynomials

[roccaa]

Representing polynomials

Currently we do not have any data structure to represent polynomials. We can only encode monomials (multivariate or univariate).
Considering the variables (x_1,x_2,x_3,x_4), let M = (x_1^2)*(x_2^2)*(x_3^0)*(x_4^1) be a multivariate monomial, then its encoding is given by the Array{Int64} = [2,2,0,1].

A polynomials can be encode in multiple way:

1. By the algebraic formula. Ex: M' = 4*x_1^3x_3 + 5*(x_1^2)*(x_2^2)*(x_3^0)*(x_4^1) (we need the expanded form to apply our algorithms).
   1.. In expanded form the parsing is doable, but the conversion into expanded form can be costly and hard to code.
   2.. If we need to perform symbolic operation on the polynomials, this will be mandatory.
   ex:
   ⋅⋅⋅ F(y) = 4*y_1^3y_3 + 5*(y_1^2)*(y_2^2)*(y_3^0)*(y_4^1)
   ⋅⋅⋅ G(x) = ({y_1 = 4x_1+2*x_2}), ({y_2 = ...}), ...
   ⋅⋅⋅ Bernstein expansion of F(G(x)) ?
   3.. Its user friendly
   4.. This package was mentioned: DynamicPolynomials.jl

2. Expanded matrix form.
   1.. It is given by: columns are monomials degrees (except the last value), lines are variables degrees is the various monomials, with the exception of the last line that is the parameter associated to the multivariate monomial.
   For example using M' from the 1st item:

   1st monomial	....	ith monomial	....
   3	...	2	...
   0	...	2	...
   1	...	0	...
   0	...	1	...
   4	...	5	...

2.. This is the classical input format for toolbox such as Yalmip for example (I think Yalmip use the transpose of the above matrix...?I will check later.).
3.. If there is no satisfiable way to handle polynomial symbolically, at least this format is kind of standard.

3. Internal encoding: Array{(AbstractType,Array{Int64})}
   1.. Note that I refer to the coefficient as an AbstractType to allow symbolic Bernstein expansion.

[roccaa]

By the way, this internal encoding is good only if we continue with the kron() based code, and implicit representation (see the issue on bounding polynomials when I write it). For other Bernstein expansion computation methods, this may no be the best encoding.

[mforets]

4.. This package was mentioned: DynamicPolynomials.jl

Yes, i don't know the internals, but see also the Ecosystem section in the MultivariatePolynomials.jl docs, which gives a complete account of the different packages for handling polynomials and how they are related.

[mforets]

I was a bit confused in my previous comment -- what is more interesting for us is to implement functionality using MultivariatePolynomials. Then, the Bernstein expansions can be used with any representation that implements the API.