生成交换群的DFT的一个算法

Generating Discrete Fourier Transform of Abel Groups

令G一个阶为n的有限群,复数域上的群代数同构于准对角矩阵代数.每一个这种同构叫作复数域上一个离散的傅立叶变换DFT,它是由两两不同构的不可约表示组成.计算一个群的常表示是一个相当困难的问题,1994年Baum和Clausen给出了计算超可解群DFT的算法,它的复杂度为O(|G|log|G|),2003年Clausen和Muller给出了可解群的一个算法,它的复杂度为O(p|G|2log|G|).主要对有限交换群来进行讨论,首先给出计算交换群的不可约表示的算法,并对算法进行分析,接下来计算这个算法的复杂度,计算的结果为O(|G|).

Let G be a finite group of order n. The group algebra G is isomorphic to matrix algebra i. e CG≌ k=1^h C^dk×dk.. Every such isomorphism is called a DFT of G. It consist of pairwise ineqivalent irreducible representation Dk. It＇s difficult to compute the ordinary irreducible representation of a given finite group. In 1994 Baum and Clausen gave the algorithm for supersolvable Groups DFT. Its complexity is O（│G│log│G│）.In 2003 Clausen and Muller gave an algorithm about solvable groups. In this paper we thought about Abel groups.