Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have question regarding convolution of functions (say g and h) defined on Sn. In Fourier space this is equivalent to IFT(G.H), where G = FT(g) and H = FT(h).

Fast Fourier transforms (Clausen's FFT) proceeds by recursively breaking down Fourier transformation over Sn into smaller transforms over S_(n-1), S_(n-2)... and computing each S_(k)-transform from the k independent S_(k-1) transforms.

Now the question I have is - How does the convolution of two functions (g & h, each defined on Sn) translate to S_(n-1)? In other words, is their any defining expression involving G' and H' to provide the n-1 independent S_(n-1) transforms to get final the convolution.

G': descendant Fourier transform of G on S_(n-1) H': descendant Fourier transform of H on S_(n-1) FT: Fourier transform IFT: Inverse Fourier transform

I would appreciate if anyone can direct me to some papers/books which talk about these concepts.


share|improve this question
add comment

2 Answers

It is not an answer to your question, but I hope it will help:

In general arithmetic complexity of convolution in non-anelian groups "equivalent" to the complexity of matrix multiplication. Here is the reason why:

The way of doing Fourier Transform in abelian group $A$ can be described in the is the following way: Let $f,g \in F[A]$ We know that $F[A]$ is isomorphic to the space $F^A$ with pointwise multiplication. Let $T$(which is acctually Fourier Transform) be this isomorphism. If we want calculate $f*g$ then calculate $T^{-1}(T(f)\cdot T(g))$. In case of non abelian group like $S_n$ It holds that $F[G]$ is isomorphic to the direct sum of matrix algebras that is $F[G]\simeq\oplus M_{n_i}$. Thus using the same formula you can calculate convolution in $S_n$, but now you will need to multiply matrixes.

share|improve this answer
I guess you described convolution on Sn using matrix multiplication. My question is slightly different. Thanks for the response though. Deepti Pachauri –  Deepti Pachauri Mar 7 '11 at 19:05
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.