Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 0902.20005
Maslen, David K.
The efficient computation of Fourier transforms on the symmetric group.
(English)
[J] Math. Comput. 67, No.223, 1121-1147 (1998). ISSN 0025-5718; ISSN 1088-6842/e

The paper describes techniques for the computation of Fourier transforms on symmetric groups and their homogeneous spaces. In particular, the matrix multiplication of Clausen's algorithm is replaced by sums indexed by combinatorial objects that generalize Young tableaux, which are written in a form similar to Horner's rule. The resulting algorithm computes the Fourier transform of a function on $S_n$ by ${3\over 4}n(n-1)n!$ multiplications and the same number of additions. The corresponding results for the inverse transforms and transforms on homogeneous spaces are also included.
[K.-H.Zimmermann (Hamburg)]
MSC 2000:
*20C40 Computational methods (representations of groups)
20C30 Representations of finite symmetric groups
65T50 Discrete and fast Fourier transforms
05E10 Tableaux, etc.

Keywords: fast Fourier transform; representations of symmetric groups; homogeneous spaces; Clausen's algorithm; Young tableaux

Highlights
Master Server