extract coefficients of a group of polynomials under the same basis of monomials

[Hank Yang]

Hi, I have a question about manipulating polynomials.

Suppose I have a group of polynomials, p1, p2, ... pN, and each polynomial pi is a function of x = [x1,x2,...,xn] in n variables, and each polynomial has degree less or equal to d.

Now I want to extract the coefficients of each polynomial pi, such that pi = coeff_i' * [x]_d, where [x]_d is the standard monomial basis of degree less or equal to d. 

So essentially, I want to extract the big coefficient matrix such that:

[p1, p2, ..., pN]' =[coeff_1, coeff_2, ... coeff_N]' * [x]_d,

are written in the same basis [x]_d

I know that the function "coefficients" in YALMIP can extract the coefficients of each polynomial pi, but it does not return zeros for terms that are not in pi. So it would be messy to extract coefficients for each pi and then arrange them in the order of [x]_d with zero padding.

Is there an easy way of performing this? (the mutipoly package in SOSTOOLS can do this easily.)

[Johan Löfberg]

Doesn't seem to be supported at the moment (as the error message reveals) but it is easily done with a loop

sdpvar x y t

p = [1 + 2*x^4;3+4*x+5*y+6*(x*y)^2 + 7*x*y*t]

monoms = monolist([x y],4);

c = fullcoefficients(p,[x y],monoms);

sdisplay(c(1,:))

sdisplay(c(2,:))

sdisplay(monoms)

function c = fullcoefficients(p,x,v)

c = [];

for i = 1:length(p)

    [ci,vi] = coefficients(p(i),x,v);

    c = [c;ci(:)'];

end

[Johan Löfberg]

it's supported in the develop branch now, if you write [c,v] = coefficients(p,x) for vector p

[Hank Yang]

Thanks Johan for the quick response.

It works well when the dimension of p is small.

However, I am dealing with the case when p is a vector of ~100k polynomials, and the monomial basis is [x]_d, where dimension of x is around 10 and degree d = 4.

Any chance that the extraction of the coefficients can be done fast? (I guess this would require some design of data structure...)

[Johan Löfberg]

No, for that you will have to hack using much lower level operators to get things fast, inspired by functions such as getexponentbase (or rewrite coefficients to do it efficiently also in the matri case, as it is now, it simply recursively calls coefficients for every element, which is very inefficient

Basically, everything is based on this

sdpvar x y t

p = [1 + 2*x^2;3+4*x*y*t]
monom_table = yalmip('monomtable');
full(getbase(p))
getvariables(p)
full(monom_table)

ans =

     1     2     0

     3     0     4

ans =

     4     6

ans =

     1     0     0     0     0     0

     0     1     0     0     0     0

     0     0     1     0     0     0

     2     0     0     0     0     0

     1     1     0     0     0     0

     1     1     1     0     0     0

[Hank Yang]

Understood, thanks!

[Johan Löfberg]

A quick fix appears to be to change line 142 etc in coefficients from

 for i = 1:length(vin)

            if isa(vin(i),'double')

                vi(i) = 0;

            else

                vi(i) = getvariables(vin(i));

            end

        end

to

if isequal(getbase(vin), [1 spalloc(1,length(vin)-1,0);spalloc(length(vin)-1,1,0) speye(length(vin)-1)])

        vi = [0 getvariables(vin)];

    else

        for i = 1:length(vin)

            if isa(vin(i),'double')

                vi(i) = 0;

            else

                vi(i) = getvariables(vin(i));

            end

        end

    end