On the Complexity of Multiplication in the Iwahori--Hecke Algebra of the Symmetric Group

preprint2016arXivOpen access

Abstract

We present new efficient data structures for elements of Coxeter groups of type AmA_m and their associated Iwahori--Hecke algebras H(Am)H(A_m). Usually, elements of H(Am)H(A_m) 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(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(Am)H(A_m).

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.