On the complexity of multiplication in the Iwahori-Hecke algebra of the symmetric group

详细信息    查看全文

• 作者：Alice C. Niemeyer^a ; ^{alice.niemeyer@mathb.rwth-aachen.de} ; Gö ; tz Pfeiffer^b ; ^{goetz.pfeiffer@nuigalway.ie} ; Cheryl E. Praeger^c ; ^{cheryl.praeger@uwa.edu.au}
• 关键词：20C08 ; 20F55 ; 20B40
• 刊名：Journal of Symbolic Computation
• 出版年：2017
• 出版时间：May-June 2017
• 年：2017
• 卷：80
• 期：part_P3
• 页码：817-832
• 全文大小：373 K
• 卷排序：80

文摘

We present new efficient data structures for elements of Coxeter groups of type AmAm and their associated Iwahori–Hecke algebras H(Am)H(Am). Usually, elements of H(Am)H(Am) are represented as simple coefficient list of length M=(m+1)!M=(m+1)! with respect to the standard basis, indexed by the elements of the Coxeter group. In the new data structure, elements of H(Am)H(Am) are represented as nested coefficient lists. While the cost of addition is the same in both data structures, the new data structure leads to a huge improvement in the cost of multiplication in H(Am)H(Am).