Cooley-Tukey FFT like algorithm for the discrete triangle transform

The discrete triangle transform (DTT) was recently introduced (Püschel, M. and Rötteler, M., Proc. ICASSP, 2004) 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² log(n)) for an input of size n×n.