2015/12/08 by David K. Maslen, Maslen, David, Daniel N. Rockmore +3
Computer Science · Mathematics · #16-04 #16Gxx #20-04 #20Cxx #43-04 #65Txx #Advanced Algebra and Geometry #Algebraic structures and combinatorial models #F.2.1 #FOS: Mathematics #Group Theory (math.GR) #Numerical Analysis (math.NA) #Representation Theory (math.RT) #Rings and Algebras (math.RA) #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1512.02445
openalex publication_date 2015/12/08 · openalex created_date 2022/10/07 · openalex updated_date 2026/07/28
We present a general diagrammatic approach to the construction of efficient\nalgorithms for computing the Fourier transform of a function on a finite group.\nBy extending work which connects Bratteli diagrams to the construction of Fast\nFourier Transform algorithms % citesovi, we make explicit use of the path\nalgebra connection to the construction of Gel'fand-Tsetlin bases and work in\nthe setting of quivers. We relate this framework to the construction of a em\nconfiguration space derived from a Bratteli diagram. In this setting the\ncomplexity of an algorithm for computing a Fourier transform reduces to the\ncalculation of the dimension of the associated configuration space. Our methods\ngive improved upper bounds for computing the Fourier transform for the general\nlinear groups over finite fields, the classical Weyl groups, and homogeneous\nspaces of finite groups, while also recovering the best known algorithms for\nthe symmetric group and compact Lie groups.\n