# 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

Since these are very short vector lengths, a "conventional" fast transform is not going to give you any gains.

Your best bet is probably to hand code each possible transform length indivdiually, unrolling all the loops and taking advantage of all "trivial " coefficients manually.

Another option could be to reduce the dimonsionality of the data but that depends how much codec gain you get in each dimension. If there is one dimension that has most of the codec gain, you can keep this and just linearize the other ones.

• I don't think I've understood what you meant by "linearize the other ones". Could you expand on that coment? – Cristian Maruan Bosin Sep 23 at 17:39
• You can just "pack" an n-dimensional matrix into a single one -dimensional vector – Hilmar Sep 24 at 14:56