# Multiplying two bivariate polynomials using FFT for univariate polynomials multiplication

Let $$f(x,y)=\sum_{0\le i\le n , 0 \le j \le d}a_{i,j}x^iy^j$$ $$g(x,y)=\sum_{0\le i\le n , 0 \le j \le d}b_{i,j}x^iy^j$$

We want to multiply $$f g$$.

I did the following: $$f(x,x^{2n+1})=\sum_{0\le i\le n , 0 \le j \le d}a_{i,j}x^ix^{j(2n+1)}$$

Thus we can define $$F(z)=\sum_{0\le i\le n , 0 \le j \le d}a_{i,j}z^{i+j(2n+1)}$$ $$G(z)=\sum_{0\le i\le n , 0 \le j \le d}b_{i,j}z^{i+j(2n+1)}$$

So obviously we can calculate the product $$F G$$ in $$O(nd \log(nd))$$ using FFT for univariate polynomial multiplication.

The only part I miss in my proof is how to infer $$(f g)(x,y)$$ from $$F G$$.

• Thank you for the fix! I recommend you use standard notation for multiplication, rather than inventing new notation. What is your question? We are a question-and-answer site, so we require you to articulate a specific question.
– D.W.
Commented May 26 at 5:57
• @D.W. Got it, thanks! If anyone can help I will appreciate it Commented May 31 at 6:27