Dear Igor Markov,

you asked about Fourier transforms for groups and Steve Linton gave a
short
overview including some references to work by Clausen and Baum.

I find the best literature to get into this topic are
the book

@BOOK{Clausen:93,
  AUTHOR =       {Clausen, M. and Baum, U.},
  TITLE =        {Fast Fourier Transforms},
  PUBLISHER =    {BI-Verlag},
  YEAR =         1993
}

(you can only order it by contacting Michael Clausen directly,
University of Bonn, Germany)

and the overview article by Dan Rockmore (Dartmouth, USA),
which includes a large list of references.

@INPROCEEDINGS{Rockmore:95,
  AUTHOR =  {Rockmore, D.},
  TITLE =   {{Some applications of generalized FFT's}},
  BOOKTITLE = {Proceedings of DIMACS Workshop in Groups and
Computation},
  YEAR =    1995,
  VOLUME =  28,
  PAGES =   {329--370} 
}

Dan Rockmore has done a lot of very important work in this field
and you might want to check his website.

If you want to work with Fourier transforms in gap, and you are running
GAP 3.4.4, you can use the share package AREP:

http://avalon.ira.uka.de/home/pueschel/arep/arep.html

AREP is able to construct FFTs for arbitrary solvable groups given
as a product of sparse matrices (the computational cost
makes it feasible up to sizes of around 1000).

If you are interested in FFTs on Qunatum Computers you might want to
check

@Unpublished{Hoyer:97,
  author =       "H{\o}yer, P.",
  title =        "{Efficient Quantum Transforms}",
  note =         "LANL preprint quant--ph/9702028",
  year =         "1997",
  month =        feb,
  kopie =        "Kopie vorhanden"
}

or

Markus Püschel, Martin Rötteler, and Thomas Beth
Fast Quantum Fourier Transforms for a Class of Non-abelian Groups
Proc. AAECC 99, pages 148-159, LNCS 1719, Springer

For the hidden subgroup problem check the publications of
Martin Rötteler:

http://avalon.ira.uka.de/home/roetteler/index.html

Best regards, Markus

--
Markus Pueschel
Dept. of ECE
Carnegie Mellon University
http://www.ece.cmu.edu/~pueschel

Miles-Receive-Header: reply