多元多项式乘积的FPT算法

The FPT Algorithm of Multi-variable Polynomial Multiplication

本文详细讨论了多元多项式乘积的多项式变换(FPT)算法。首先给出了二元的情况,然后推广到了一般多元多项式,最后给出了这种算法在计算二维循环卷积中的应用,由此可见,这种算法在计算多维卷积和多维DFT 时是很有效的。

In this paper,we discussed the FPT algorithm of multi—variable polynomial multiplicationin detail.Firstly,we give the case of two—variable.Secondary,we generalize it to multi—vari-able polynomial.At last,we apply it to the computation of the two dimensional cyclic convolu-tion.As a result,this kind of algorithm is efficient in computation of M—D DFTs and M—D con-volutions.