# Multivariate Polynomial Multiplication using Fast Fourier Transform (FFT)

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?

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.