Expansion of a polynomial (Best way)

Hi, I have a polynomial of the form : (1+x^a1)*(1+x^a2)*...*(1+x^an), and I want to expand it (compute its coefficients). Which is the best way (low computational complexity) of doing this in Matlab?

I hope it is clear. Thanks for your help.

Best regards. H.

[Walter Roberson]

When you say "low computational complexity", do you mean "the lowest theoretical Big-O measure", or "the simplest instruction" or "the fastest executing" or "relatively simple code and executes decently fast" ?

[Iain]

If you go to a sensible order in the polynomial (i.e. less than about 10), the code will likely be too fast to worry about.

[Hadjer]

@Walter Roberson: it doesn't matter if the solution is complicated or involves other concepts, I am looking for "the lowest theoretical Big-O measure" and the faster way of achieving my goal. I intend using it as a subroutine in another algorithm.

PS @lain: the sum of ai (i=1..n) "order of the polynomial" can be large (>50) but I only need to extract a subset of the coefficients (precisely the half).

Thanks.

Answer 1

[Roger Stafford]

Let a be a row vector consisting of your exponents, a1, a2, ..., an. Then try this:

 A = cumsum([0,a])+1;
 a1 = a + 1;
 C = [1,zeros(1,A(size(A,2))-1)];
 for k = 1:size(a,2)
   C(a1(k):A(k+1)) = C(a1(k):A(k+1)) + C(1:A(k));
 end

The C row vector will have the coefficients of the powers of x for your product:

 C(1)+C(2)*x+C(3)*x^2+C(4)*x^3+C(5)*x^4+...

[Hadjer]

Brilliant, that's what I was looking for, correct me if I am wrong, it a dynamic program, with computational complexity O(n*P), where P=sum(a). I don't think that there exists another way of expanding this polynomial better than this one.

Thank you guys. Hadjer.

[Roger Stafford]

Yes, O(length(a)*sum(a)), is the complexity of that algorithm.

Answer 2

[Walter Roberson]

I am not sure of the best way to express this at the moment. The elements are

(-1)^(k) * sum( x^(sum(a[p], p element of Q), Q is the set of distinct combinations of n objects taken k at a time)

so for example, for n = 4,

+ (+1) * (x^(a[1]+a[2]+a[3]+a[4]))
+ (-1) * (x^(a[1]+a[2]+a[3]) + x^(a[1]+a[2]+a[4]) + x^(a[1]+a[3]+a[4]) + x^(a[2]+a[3]+a[4]))
+ (+1) * (x^(a[1]+a[2]) + x^(a[1]+a[3]) + x^(a[1]+a[4]) + x^(a[2]+a[3]) + x^(a[2]+a[4]) + x^(a[3]+a[4])
+ (-1) * (x^a[1] + x^a[2] + x^a[3] + x^a[4])
+ (+1) * 1

and so the computational complexity would be that of producing all of the combinations. Some of the methods are noted at http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n

But if I were doing it myself, unless I had good reason otherwise, I would probably just toss it into a symbolic toolbox. For example in Maple,

sort(combine(expand(product(1-x^a[n], n = 1 .. 4))))

[Hadjer]

Thank you for the answer, I'll take a close look at these methods. But, I am sure that producing all possible combinations have an exponential complexity O(2^n).

[Walter Roberson]

2^n seems plausible to me, but perhaps someone found a better way.

You can see with a small amount of experimentation that this is what the elements do come out as. If it takes O(2^n) to calculate them all out, then it takes O(2^n), and any algorithm we might put forth as having lower complexity would, if valid, also be a way to lower the complexity of finding all combinations.

[Hadjer]

I have found that if we enumerate all roots (it is easy given the form of this polynomial), we can compute the coefficients of this polynomial using matlab' poly function. But I can't figure out its complexity, it uses a matrix to find the coefficients. Please could someone explain to me how this function computes these coeff in order to estimate its computational complexity?