> < ^ From:

< ^ Subject:

Dear GAP Forum,

Igor Markov asked about computing Fourier transforms on groups. For those who

haven't met this concept, given a function f from a group G to a field k of

characteristic coprime to G, then the Fourier transform of f is a function F

from

the k-linear representations of G to k, defined by

F(p) = Sum(g in G : f(g)p(g))

where p: G -> GL_n(k) is a representation.

Normally, one thinks of p running over the irreducible representations of G,

in which case, the Fourier transform can be regarded as a change of basis in

the group algebra from the basis of group elements to the basis of matrix

entries in irreducible representations.

The case of G = C* (the multiplicative group of the complex numbers) is

essentially

the standard Fourier transform, while G = C_{2^n} (cyclic order 2^n) is the

discrete Fourier transform.

Anyway, this offers a natural naive implementation in GAP:

FourierTransform := function(f, G)

return rho -> Sum(G, g->Image(rho,g)*f(g));

end;

this returns a function which accepts a homomorphism from G to a matrix group

and returns the value of the Fourier transform there. off the top of my head,

I'm less sure about how to do the inverse Fourier transform effectively.

There is a lot of work by Michael Clausen and Ulrich Baum on computing

non-abelian Fourier transforms efficiently. I include a few BiBTeX entries

culled from a very cursory search of MathSciNet. The basis of their approach

is the observation that, if H < G and T is a transversal of the cosets of H,

then:

F(p) = Sum(g in G: f(g)p(g)) = Sum( t in T: p(t) * Sum( h in H: f(th)p(h) ) )

On the face of it, this offers no gain, but if p decomposes over H, then one

can

choose a basis of p such that p(h) is block diagonal for all h, and then there

are fewer matrix entries to consider in the inner sum.

This is applied along a chain of subgroups, and further work is done to choose

a transversal and basis in such a way that all the matrices p(t) are highly

sparse, giving further improvements.

Steve Linton

@book {MR96i:68001, AUTHOR = {Clausen, Michael and Baum, Ulrich}, TITLE = {Fast {F}ourier transforms}, PUBLISHER = {Bibliographisches Institut}, ADDRESS = {Mannheim}, YEAR = {1993}, PAGES = {ii+181}, ISBN = {3-411-16361-5}, MRCLASS = {68-02 (11Y16 20F16 65T20 68Q25)}, MRNUMBER = {96i:68001}, MRREVR = {V{\'\i}t{\u{e}}zslav Vesel{\'y}}, } @article {MR94f:65129, AUTHOR = {Baum, Ulrich and Clausen, Michael and Tietz, Benno}, TITLE = {Improved upper complexity bounds for the discrete {F}ourier transform}, JOURNAL = {Appl. Algebra Engrg. Comm. Comput.}, FJOURNAL = {Applicable Algebra in Engineering, Communication and Computing}, VOLUME = {2}, YEAR = {1991}, NUMBER = {1}, PAGES = {35--43}, ISSN = {0938-1279}, CODEN = {AAECEW}, MRCLASS = {65T10 (20D60 65Y20)}, MRNUMBER = {94f:65129}, } @article {MR94a:20028, AUTHOR = {Clausen, Michael and Baum, Ulrich}, TITLE = {Fast {F}ourier transforms for symmetric groups: theory and implementation}, JOURNAL = {Math. Comp.}, FJOURNAL = {Mathematics of Computation}, VOLUME = {61}, YEAR = {1993}, NUMBER = {204}, PAGES = {833--847}, ISSN = {0025-5718}, CODEN = {MCMPAF}, MRCLASS = {20C40 (20C30 68Q40)}, MRNUMBER = {94a:20028}, MRREVR = {Stephen A. Linton}, } @article {MR93d:20031, AUTHOR = {Baum, Ulrich}, TITLE = {Existence and efficient construction of fast {F}ourier transforms on supersolvable groups}, JOURNAL = {Comput. Complexity}, FJOURNAL = {Computational Complexity}, VOLUME = {1}, YEAR = {1991}, NUMBER = {3}, PAGES = {235--256}, ISSN = {1016-3328}, MRCLASS = {20C40 (20C15 68Q40)}, MRNUMBER = {93d:20031}, } @article {MR91m:68100, AUTHOR = {Baum, Ulrich and Clausen, Michael}, TITLE = {Some lower and upper complexity bounds for generalized {F}ourier transforms and their inverses}, JOURNAL = {SIAM J. Comput.}, FJOURNAL = {SIAM Journal on Computing}, VOLUME = {20}, YEAR = {1991}, NUMBER = {3}, PAGES = {451--459}, ISSN = {0097-5397}, CODEN = {SMJCAT}, MRCLASS = {68Q40 (20C15)}, MRNUMBER = {91m:68100}, } @incollection {MR1235793, AUTHOR = {Clausen, Michael and Baum, Ulrich}, TITLE = {Fast {F}ourier transforms for symmetric groups}, BOOKTITLE = {Groups and computation (New Brunswick, NJ, 1991)}, PAGES = {27--39}, PUBLISHER = {Amer. Math. Soc.}, ADDRESS = {Providence, RI}, YEAR = {1993}, MRCLASS = {20C40 (68Q40 68R05)}, MRNUMBER = {1 235 793}, }

> < [top]