Hi, I'm trying to write a fast way to multiply polynomials using Eigen. For a simple example, given the polynomials below, I want to find their product:

Poly 1: x^2 + 2x + 3
Poly 2: 4x^3 + 5x^2 + 6x + 7

I'm representing them using coefficients only where the exponent is based on the index into a vector. This means the example above becomes:

Poly 1: (1, 2, 3)
Poly 2: (4, 5, 6, 7)

Desired result: (4, 13, 28, 34, 32, 21)

The nice thing is that I know the degrees of the polynomials ahead of time as well as the maximum degree of the result, meaning that I'm able to use vectors whose size is known at compile-time. I'm going to be chaining multiple convolutions together and currently I'm doing a bunch of block operations for each convolution, e.g:

Code: Select all

// In this example vec1 is of size 3 and vec2 is of size 5
for (int index=0; index<5; index++)
{
  result.segment<3>(index) += vec1 * vec2[index];
}

I'm preallocating vectors of the maximum size and repeatedly writing into them in this way. Is there a better way to accomplish this via a library function that I'm missing? Or is my current method (repeated block operations) the way to go?

One thing I'm thinking is that if you transpose one of the vectors and then multiply them you get a matrix of coefficients. If you then sum along the diagonals (running from bottom left to top right) you get the coefficients of the final polynomial. However, I don't know if this would be worth it over the method with block operations since you have to allocate a larger matrix (even though, again, the size would be known at compile-time) as well as efficiently sum along a diagonal. Let me illustrate this using the numbers above:

Code: Select all

1                     4  5  6  7
2   *   4 5 6 7   =   8  10 12 14
3                     12 15 18 21

4 = 4
8 + 5 = 13
12 + 10 + 6 = 28
15 + 12 + 7 = 34
18 + 14 = 32
21 = 21

I don't see any obvious way to reuse efficient matrix operations for that task. Your code seems to be the right way to go. If your polynomial are quite small, you could write your own meta unroller, Have a look at the file Eigen/src/REdux.h, and search for redux_novec_unroller for an example.