> < ^ From:

^ Subject:

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

> < [top]