3

I am trying to find the coefficients of multiplications of 2 $N$-variate polynomials using $N$-dimensional fast Fourier transform (FFT) on MATLAB.

My approach so far is as follows: Based on this post, I learned to do it for the multiplication of 2 1-dimensional polynomials. It is simply

y1 = [1 0 0 0];
y2 = [0 2 0 0];

ifft(fft(y1).*fft(y2));

for $y_1=1$ and $y_2=2x$, whereby $x$ is the input.

How about when it is multivariate, say $y_1=1+2x_1$ and $y_2=x_1+4{x_1}^2x_2$, whereby $x_1$ and $x_2$ are the inputs? How can I make use of the MATLAB function fftn?

Community
  • 1
arvindrajan92
  • 625

1 Answers1

2

I actually managed to find the answer to the question and would like to share it here. First we construct the polynomial in $2$-dimensional matrix - because 2 variables are involved.

y1 = zeros(4,2)
y1(1,1) = 1;
y1(2,1) = 2;

y2 = zeros(4,2)
y2(2,1) = 1;
y2(3,2) = 4;

Then we use the functions fftn() and ifftn() to find the coefficients

ifftn(fftn(y1).*fftn(y2))

This will give you the following results:

0     0
1     0
2     4
0     8

which resembles $x_1 + 4{x_1}^2x_2 + 8{x_1}^3x_2 + 2{x_1}^2$ in matrix.

arvindrajan92
  • 625