> < ^ Date: Wed, 19 Jul 2000 11:09:24 -0500
> < ^ From: Markus Pueschel <pueschel@earthlink.net >
^ Subject: Fourier transforms

Dear Igor Markov,

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

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

  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.

  AUTHOR =  {Rockmore, D.},
  TITLE =   {{Some applications of generalized FFT's}},
  BOOKTITLE = {Proceedings of DIMACS Workshop in Groups and
  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:


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

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


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:


Best regards, Markus

Markus Pueschel
Dept. of ECE
Carnegie Mellon University

Miles-Receive-Header: reply

> < [top]