Two BSP algorithms for Bruhat decomposition achieve O(n^3/p) computation, O(n^2/p^(2/3)) communication, and a tunable synchronization cost, with the strip-recursive variant matching the best known trade-off for LU decomposition.
Demazure product of permutations and hopping
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
The Demazure product (also goes by the name of 0-Hecke product or the greedy product) is an associative operation on Coxeter groups with interesting properties and important applications. In this note, we study permutations and present an efficient way to compute the Demazure product of two permutations starting from their usual product and then applying a new operator we call a hopping operator. We also give an analogous result for the group of signed permutations.
fields
cs.DS 1years
2026 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Communication-efficient parallel Bruhat decomposition
Two BSP algorithms for Bruhat decomposition achieve O(n^3/p) computation, O(n^2/p^(2/3)) communication, and a tunable synchronization cost, with the strip-recursive variant matching the best known trade-off for LU decomposition.