# Fast algorithm for n-dimensional DCT

I need to implement an encoder which compresses a 5-dimensional structure of 10 bits values. Each dimension has between 4 and 12 elements. If a dimension ever has more than 12 elements, it is partitioned in half. So far, I have been using a separable DCT to do that, but my implementation is very slow: I have implemented a naive DCT transform, which has complexity of $$O(N^2)$$. I have tried some fast algorithms, but they seem to be slower than the naive approach: a naive DCT for 6 elements is faster the Fast version, but for $$N = 4$$ and $$8$$, the fast approach is definitely faster. Also, I cannot force the friendly power-of-2 sizes.

I remember the Cooley–Tukey FFT algorithm decomposes a sequence of size $$N$$ into their factors $$N_1$$ and $$N_2$$ such that $$N = N_1N_2$$. I also know that there are specialized algorithms for 2D DCT due to their use in video and image codecs.

My question is: Is there any reference about a fast multidimensional DCT or even a "reversed" Cooley-Tukey for DCT of which I could transform my 5D array into 1D and use a fast DCT?

Exrta bits: We are researching not only the DCT-II but the whole family of trigonometric transforms., insights about any of the DST and DCT are welcome!

Edited 9/23

Just as an extra comment, this solution is being implemented in C++.

• I don't really understand the sentence on $2^{15}$ and $7^5$ – Laurent Duval Sep 22 at 21:20
• Hey, I removed this particular part, but what I meant was that if I zero-pad to the next power of 2, Id introduce unnecessary data; At the end of the day, I want to represent each 5D structure with the least amount of bits possible. – Cristian Maruan Bosin Sep 23 at 0:12
• Hmm... I had massive speed issue in certain taper implementation (based on for-loop) ... replacing the loops by just dot-products and sums turned 60 minute task to less than one second task. Proper matrix algebra could be even faster... . This was situation with Octave (/Matlab) ... . – Juha P Sep 23 at 6:29
• As it's C++ implementation in question, you sure use advantage of SSE / AVX where possible? – Juha P Sep 23 at 19:56
• @JuhaP I must say I didnt even think of using something more closely related to the CPU itself. The most work I went through was being the most cache-friendly possible. I had a quick search here and actually they might be very useful. I really appreciate for that comment! =) – Cristian Maruan Bosin Sep 23 at 20:57