Cooley-Tukey FFT like Algorithm for the Discrete Triangle Transform

The discrete triangle transform (DTT) was recently introduced in the paper “The discrete triangle transform” (Proceedings of ICASSP’04) 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, as the DCT, type III, 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.