Advanced Search

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

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]