Convolution on symmetric group Sn - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T22:18:37Z http://mathoverflow.net/feeds/question/57276 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/57276/convolution-on-symmetric-group-sn Convolution on symmetric group Sn Deepti Pachauri 2011-03-03T18:43:19Z 2011-07-31T08:53:59Z <p>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).</p> <p>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.</p> <p>Now the question I have is - How does the convolution of two functions (g &amp; 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.</p> <p>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</p> <p>I would appreciate if anyone can direct me to some papers/books which talk about these concepts.</p> <p>DP</p> http://mathoverflow.net/questions/57276/convolution-on-symmetric-group-sn/57293#57293 Answer by Klim Efremenko for Convolution on symmetric group Sn Klim Efremenko 2011-03-03T22:29:08Z 2011-03-03T22:44:36Z <p>It is not an answer to your question, but I hope it will help:</p> <p>In general arithmetic complexity of convolution in non-anelian groups "equivalent" to the complexity of matrix multiplication. Here is the reason why:</p> <p>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.</p> http://mathoverflow.net/questions/57276/convolution-on-symmetric-group-sn/71717#71717 Answer by openID for Convolution on symmetric group Sn openID 2011-07-31T08:53:59Z 2011-07-31T08:53:59Z <p><a href="http://www.cbse.ucsc.edu/sites/default/files/convolutions.pdf" rel="nofollow">http://www.cbse.ucsc.edu/sites/default/files/convolutions.pdf</a> http://www.mpi-hd.mpg.de/astrophysik/HEA/internal/Numerical_Recipes/f13-1.pdf</p> <p>might help you </p>