Improved formulations for fast polynomial transform
Albert Ming Loh, Wan-Chi Siu · 1993 IEEE International Symposium on Circuits and Systems · 2002
The fast polynomial transform (FPT) can be used to efficiently compute 2D convolutions. The formulations for the realization of a powers-of-two length fast polynomial transform mainly include either (i) the decomposition of one-variable polynomials using the Chinese remainder theorem (CRT) on one of the two dimensions or (ii) the decomposition of two-variable polynomials using the CRT, also on one of the 2-dimensions. New formulations are given which involve two-variable polynomials using the CRT decomposition on both of the two dimensions for the realization of the FPT. This approach substantially reduces the number of operations for the realization of two-dimensional convolutions, especially in terms of the numbers of multiplications.>