New fast algorithm for multidimensional type-IV DCT

The authors first propose an index mapping such that the type-IV m-dimensional discrete cosine transform (m-D DCT-IV) is turned into a sum involving a number of (m-1)-dimensional discrete cosine transforms ((m-1)-D DCTs). Then a polynomial transform is used for implementing the sum. Based on symmetrical properties, a refined fast polynomial transform algorithm is proposed for computing the polynomial transform. Compared to the row-column m-D DCT-IV algorithm, the proposed algorithm achieves remarkable savings in arithmetic operations. More precisely, the numbers of multiplications and additions for m-dimensional DCT-IV are nearly 1/m and (2m+1)/3m times those of the row-column method, respectively.