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

DOI10.1016/J.JSC.2016.09.001MaRDI QIDQ1711997zbMATH OpenOpenAlexWikidataFDO

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)

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

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)

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)$.

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

Cites work

• scientific article; zbMATH DE number 1516227 (Why is no real title available?)
• scientific article; zbMATH DE number 1361790 (Why is no real title available?)
• CHEVIE -- A system for computing and processing generic character tables
• \(\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

Describes a project that uses

Uses Software

• PyCox
• CHEVIE
• GAP

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)