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$.

  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented May 26 at 5:57
  • $\begingroup$ @D.W. Got it, thanks! If anyone can help I will appreciate it $\endgroup$
    – AlgoMan
    Commented May 31 at 6:27


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.