Separation of Variables and the Computation of Fourier Transforms on Finite Groups, II

1 : HBK Capital Management, New York, NY

2 : Departments of Mathematics and Computer Science, Dartmouth College, Hanover, NH

3 : Department of Mathematics and Computer Science, Denison University, Granville, OH

We present a general diagrammatic approach to the construction of efficient algorithms for computing

the Fourier transform of a function on a finite group. By extending work which connects Bratteli diagrams to the

construction of Fast Fourier Transform algorithms we make explicit use of the path algebra connection and work in

the setting of quivers. In this setting the complexity of an algorithm for computing a Fourier transform reduces to path

counting in the Bratelli diagram, and we generalize Stanley's work on differential posets to provide such counts. Our

methods give improved upper bounds for computing the Fourier transform for the general linear groups over finite

fields, the classical Weyl groups, and homogeneous spaces of finite groups.

- Poster