Copyrights to these papers may be held by the publishers. The download files are preprints. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
Markus Püschel and Martin Rötteler (Proc. IEEE Digital Signal Processing Workshop, pp. 158-162, 2004)
Cooley-Tukey FFT Like Algorithm for the Discrete Triangle Transform
Published paper (link to publisher)
Bibtex
The discrete triangle transform (DTT) was recently introduced as an example of a non-separable transform for signal processing on a two-dimensional triangular grid. The DTT is built from Chebyshev polynomials in two variables in the same way as the DCT, type III, is built from Chebyshev polynomials in one variable. We show that, as a consequence, the DTT has, like the type III DCT, a Cooley-Tukey FFT type fast algorithm. We derive this algorithm and an upper bound for the number of complex operations it requires. Similar to most separable two-dimensional transforms, the operations count of this algorithm is O(n^2 log(n)) for an input of size n x n.
Keywords: (No keyword)More information: