Opened 13 years ago

Closed 13 years ago

#7751 closed enhancement (fixed)

Kazhdan-Lusztig polynomials, Bruhat order, and related features

Reported by: bump Owned by:
Priority: major Milestone: sage-4.3.3
Component: combinatorics Keywords: Kazhdan-Lusztig, Bruhat order
Cc: sage-combinat Merged in: sage-4.3.3.alpha1
Authors: Daniel Bump Reviewers: David Roe, Brant Jones
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by bump)

This patch includes algorithms for the Bruhat order, Kazhdan-Lusztig polynomials, improvements to the __repr__ method of WeylGroup? elements, and other enhancements.

Mike Hansen is working on an interface to coxeter3, which is be able to compute Kazhdan-Lusztig polynomials rather faster. However I think this patch still contains things that are needed.

For discussion see this thread:

http://groups.google.com/group/sage-combinat-devel/browse_thread/thread/d324f6fcb6d2a436?hl=en

This patch depends on #7753 and #7754.

Attachments (1)

kazhdan_lusztig.patch (18.5 KB) - added by bump 13 years ago.
Kazhdan-Lusztig polynomials, Bruhat order, improved __repr__ for WeylGroups?.

Download all attachments as: .zip

Change History (18)

comment:1 Changed 13 years ago by bump

  • Component changed from algebra to combinatorics
  • Owner changed from AlexGhitza to bump

comment:2 Changed 13 years ago by bump

I made a minor change so that the Kazhdan-Lusztig computation doesn't hang in the affine case. I've only done much testing for finite Weyl groups but I suppose it is correct in the affine case.

comment:3 Changed 13 years ago by bump

  • Description modified (diff)
  • Status changed from new to needs_review

I have revised the patch. It now depends on #7753 and #7754. The revised patch makes use of the Bruhat order as implemented in #7753 and makes the Kazhdan-Lusztig polynomials using @cached_method. Other changes allow the base ring to be a LaurentPolynomialRing.

The patch is much faster now, something like 50% faster.

comment:4 Changed 13 years ago by bump

  • Cc sage-combinat added

comment:5 Changed 13 years ago by bump

Rebased to Sage 4.3.1.

comment:6 Changed 13 years ago by roed

  • Reviewers set to roed
  • Status changed from needs_review to needs_work

Looks good. Here are a few comments. After these are addressed, I'll be happy to give this a positive review.

  • sage/combinat/kazhdan_lusztig.py
  • sage/combinat/root_system/weyl_group.py *In WeylGroup_gens, __classcall_ needs another trailing underscore. Include a doctest to make sure that this feature works!
    • Can you include a doctest in WeylGroupElement.__repr__? I know it's tested elsewhere, but...

In general, do you have a reason to use __call__ explicitly, rather than parentheses? Similarly, you don't need to explicitly call repr: using %s in a string will do that for you automatically.

comment:7 Changed 13 years ago by bump

  • Status changed from needs_work to needs_review

I addressed most of David Roe's comments.

But the email address is not a typo.

Brant Jones is also looking at the patch.

comment:8 Changed 13 years ago by brant.c.jones

  • Status changed from needs_review to positive_review

Patch review: trac_7751

This patch implements Kazhdan--Lusztig polynomials and R-polynomials associated to pairs of Weyl group elements in arbitrary type using standard recursive formulas. I have verified the results of this code against the Kazhdan--Lusztig polynomials produced by GAP/Chevie for all pairs of elements in finite type A_4. I also verified this code against GAP/Chevie for all pairs in affine type A_2 (having 3 generators) for all pairs of elements with Coxeter length less than or equal to 5. This patch correctly implements useful mathematics and the documentation includes references to relevant mathematical literature.

-- Brant Jones

comment:9 Changed 13 years ago by bump

  • Reviewers changed from roed to roed, Brant Jones

comment:10 Changed 13 years ago by bump

  • Summary changed from Kazhdan-Lusztig polynomials, Bruhat order, and related features [with patch, needs review] to Kazhdan-Lusztig polynomials, Bruhat order, and related features

comment:11 Changed 13 years ago by roed

  • Owner changed from bump to (none)

I agree. Positive review.

comment:12 Changed 13 years ago by roed

  • Authors set to bump

comment:13 Changed 13 years ago by mpatel

Applying the patch to this hierarchy (minus #8232), I get

patching file sage/combinat/root_system/weyl_group.py
Hunk #5 FAILED at 145
1 out of 13 hunks FAILED -- saving rejects to file sage/combinat/root_system/weyl_group.py.rej

The reject:

--- weyl_group.py
+++ weyl_group.py
@@ -138,6 +146,7 @@
         self.n = lattice.dimension() # Really needed?
         # MatrixGroup_gens takes plain matrices as input. So we can't do:
         #MatrixGroup_gens.__init__(self, list(self.simple_reflections()))
+        self._prefix = prefix
         MatrixGroup_gens.__init__(self, [self.morphism_matrix(self.lattice().si
mple_reflection(i)) for i in self.index_set()])
 
     @cached_method

comment:14 Changed 13 years ago by bump

If this conflict occurs, you may resolve just making sure the line self._prefix = prefix occurs somewhere in the init method of WeylGroup?.

comment:15 Changed 13 years ago by bump

Correction: the line self._prefix = prefix should be somewhere in the init method of WeylGroup_gens (not WeylGroup).

Changed 13 years ago by bump

Kazhdan-Lusztig polynomials, Bruhat order, improved __repr__ for WeylGroups?.

comment:16 Changed 13 years ago by bump

Patch rebased to sage-4.3.3.alpha0. This fixes the conflict reported by mpatel with no other changes.

comment:17 Changed 13 years ago by mvngu

  • Authors changed from bump to Daniel Bump
  • Merged in set to sage-4.3.3.alpha1
  • Resolution set to fixed
  • Reviewers changed from roed, Brant Jones to David Roe, Brant Jones
  • Status changed from positive_review to closed

Daniel, I have committed the attachment kazhdan_lusztig.patch in your name, since the patch doesn't contain your full name.

Note: See TracTickets for help on using tickets.