4-8 juil. 2016 Vancouver, British Columbia (Canada)

Par auteur > Wolff Sarah

Lundi 4

Karen Yeats
› 17:30 - 19:00 (1h30)
› SFU Harbour Center - Segal Centre Conference Rooms 1400 - 1410
Separation of Variables and the Computation of Fourier Transforms on Finite Groups, II
David Maslan  1  , Daniel N. Rockmore  2  , Sarah Wolff  3  
1 : HBK Capital Management, New York, NY
2 : Department of Mathematics [Dartmouth]  -  Site web
Dartmouth CollegeHanover, NH 03755-3551, USA -  États-Unis
3 : Department of Mathematics and Computer Science [Granville]  -  Site web
Department of Math and Computer ScienceDenison UniversityGranvilleOH, 43023, USA -  États-Unis

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
Personnes connectées : 1