Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Linear time fourier transforms of Sn-k-invariant functions on the symmetric group Sn

 
: Clausen, M.; Hühne, P.

:

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: 978-1-4503-5064-8
pp.101-108
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 Sn-k-invariant functions on the symmetric group Sn. We uncover diamond- and leaf-rake-like 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 Sn-k-invariant functions on Sn in at most ck...[Sn : Sn-k] scalar multiplications and additions, where ck denotes a positive constant depending only on k. This run-time, which is linear in [Sn : Sn-k], 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 Sn-2-invariant real-valued function on Sn, n=5000.

: http://publica.fraunhofer.de/documents/N-464493.html