0

I want to compute all d-dimensional monomials of degree less than k and put them into a cell array - Pbase - in an ordered way (I use Matlab but this ploblem applies for other languages too). k and d are provided by the user but arbitrary.

What I have done so far,(the array called degreeindex show the location of monomials of a certain degree in Pbase):

n=nchoosek(d+k,k);%i know there are n over k possibilities for such monomials
Pbase=cell(1,n);
degreeindex=zeros(k+1,3);%showing [degree, start, end]
x=sym('x',[d,1]);

%the polynomials of degree 0
Pbase{1}=1;
degreeindex(1,1:3)=[0,1,1];%initialized for degree 0

%degree 1 monomials
degree=2;
degreeindex(degree,:)=[degree-1,degreeindex(degree-1,3)+1,degreeindex(degree-1,3)+1];
for i=1:d
    Pbase{degreeindex(degree,2)+i-1}=x(i);
    degreeindex(degree,3)=degreeindex(degree,3)+1;
end

%degree2 monomials
degree=3;
degreeindex(degree,:)=[degree-1,degreeindex(degree-1,3),degreeindex(degree-1,3)+1];
for i=1:d
    for j=i:d
        Pbase{degreeindex(degree,3)-1}=x(i).*x(j);
        degreeindex(degree,3)=degreeindex(degree,3)+1;
    end
end

%degree3 monomials
degree=4;
degreeindex(degree,:)=[degree-1,degreeindex(degree-1,3),degreeindex(degree-1,3)+1];
for i1=1:d
    for i2=i1:d
        for i3=i2:d
        Pbase{degreeindex(degree,3)-1}=x(i1).*x(i2)*x(i3);
        degreeindex(degree,3)=degreeindex(degree,3)+1;
        end
    end
end
...

The problem is that I don't find a way to do this for an arbitrary degree k. In the solution above I would have to include a new (and deeper) nested loop for every degree.

I know this seems like a faily trivial problem but I can't get my head around it. I appreciate all advice.

0

2 Answers 2

0

You are trying to do a type of partitioning, specifically you want to find all integer partitions of k into m or fewer parts (where order matters).

Using nchoosek you can easily achive this (adapted from the Matlab File Exchange,here):

d = 3; % num dims
k = 4; % degree
x=sym('x',[d,1]);
m = nchoosek(k+d-1,d-1); 
dividers = [zeros(m,1),nchoosek((1:(k+d-1))',d-1),ones(m,1)*(k+d)]; 
a = diff(dividers,1,2)-1;
PBase = cell(1, size(a,1));
for i = 1:size(a,1)
    PBase{i} = prod(x.' .^ a(i,:));
end

Loop over whatever values of k you need.

1
  • Thank you, Tokkot! This is a really nice and easy solution.
    – Vincent.W.
    Nov 11, 2016 at 8:29
0

Check my FileExchange submission for Multivariate Polynomial Regression. Inside, for a given degree, I compute all monomials of a basis polynomial with an arbitrary degree. It is lightning fast, but at the cost of some memory.

MultiPolyRegress

This is the relevant section:

% Function Parameters
NData = size(Data,1);
NVars = size(Data,2);
RowMultiB = '1';
RowMultiC = '1';
Lim = max(PV);

% Initialize
A=zeros(Lim^NVars,NVars);

% Create Colums Corresponding to Mathematical Base
for ii=1:NVars
    A(:,ii)=mod(floor((1:Lim^NVars)/Lim^(ii-1)),Lim);
end

% Flip - Reduce - Augment
A=fliplr(A); A=A(sum(A,2)<=Lim,:); Ab=diag(repmat(Lim,[1,NVars])); A=[A;Ab];

% Degree Conditionals
for ii=1:NVars
    A=A(A(:,ii)<=PV(ii),:);
end

Notice that there are no explicit for loops that depend on power, only on number of variables in the polynomial. Also notice the potentially gigantic matrix A. Let me know if you need any further help after giving this a look.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.