Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. Linear time fourier transforms of Snkinvariant functions on the symmetric group Sn
 Association for Computing Machinery ACM: 42nd ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2017. Proceedings : Kaiserslautern, Germany, July 23  28, 2017 New York: ACM, 2017 ISBN: 9781450350648 pp.101108 
 International Symposium on Symbolic and Algebraic Computation (ISSAC) <42, 2017, Kaiserslautern> 

 English 
 Conference Paper 
 Fraunhofer FKIE () 
Abstract
This paper introduces new techniques for the efficient computation of discrete Fourier transforms (DFTs) of Snkinvariant functions on the symmetric group Sn. We uncover diamond and leafrakelike structures in Young's seminormal and orthogonal representations. Combining this with both a multiresolution scheme and an anticipation technique for saving scalar multiplications leads to linear time partial FFTs. Following the inductive version of Young's branching rule we obtain a global FFT that computes a DFT of Snkinvariant functions on Sn in at most ck...[Sn : Snk] scalar multiplications and additions, where ck denotes a positive constant depending only on k. This runtime, which is linear in [Sn : Snk], is order optimal and improves Maslen's algorithm. For example, it takes less than one second on a standard notebook to run our FFT algorithm for an Sn2invariant realvalued function on Sn, n=5000.