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

DOI10.1016/J.JSC.2016.09.001zbMATH Open1486.68258arXiv1512.05319OpenAlexW2216761078WikidataQ56987321 ScholiaQ56987321MaRDI QIDQ1711997FDOQ1711997

Authors: Alice C. Niemeyer, Götz Pfeiffer, Cheryl E. Praeger 

Publication date: 21 January 2019

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Abstract: We present new efficient data structures for elements of Coxeter groups of type $A_m$ and their associated Iwahori--Hecke algebras $H(A_m)$. Usually, elements of $H(A_m)$ are represented as simple coefficient list of length $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(A_m)$ 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(A_m)$.

Full work available at URL: https://arxiv.org/abs/1512.05319

Recommendations

• Computation in Coxeter groups. I: Multiplication
• On the computation of Kazhdan-Lusztig polynomials and representations of Hecke algebras
• Multiplicative bases for the centres of the group algebra and Iwahori-Hecke algebra of the symmetric group.
• The Hecke group algebra of a Coxeter group and its representation theory.
• scientific article; zbMATH DE number 1516227

zbMATH Keywords

complexitysymmetric groupIwahori-Hecke algebrafinite Coxeter group

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Data structures (68P05) Symmetric groups (20B30) Reflection and Coxeter groups (group-theoretic aspects) (20F55) Hecke algebras and their representations (20C08)

Cites Work

• CHEVIE -- A system for computing and processing generic character tables
• Title not available (Why is that?)
• Title not available (Why is that?)
• \(\mathsf{PyCox}\): computing with (finite) Coxeter groups and Iwahori-Hecke algebras.

Cited In (3)

• Computation in Coxeter groups. I: Multiplication
• Concrete Multiplicative Complexity of Symmetric Functions
• Complexity of multiplication in commutative group algebras over fields of prime characteristic

Uses Software

• GAP
• CHEVIE
• PyCox

This page was built for publication: On the complexity of multiplication in the Iwahori-Hecke algebra of the symmetric group

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1711997)