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: |
Description (last modified by )
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
Attachments (1)
Change History (18)
comment:1 Changed 13 years ago by
- Component changed from algebra to combinatorics
- Owner changed from AlexGhitza to bump
comment:2 Changed 13 years ago by
comment:3 Changed 13 years ago by
- 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
- Cc sage-combinat added
comment:5 Changed 13 years ago by
Rebased to Sage 4.3.1.
comment:6 Changed 13 years ago by
- 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
- typo in your e-mail address.
- the method of determining KL._base_ring_type seems a little strange. Why not use is_Polynomial and isinstance(q, LaurentPolynomial?)?
- KazhdanLusztigPolynomial? should inherit from SageObject?. That allows pickling, etc.
sage/combinat/root_system/weyl_group.py
*InWeylGroup_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...
- Can you include a doctest in
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
- 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
- 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
- Reviewers changed from roed to roed, Brant Jones
comment:10 Changed 13 years ago by
- 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:12 Changed 13 years ago by
comment:13 Changed 13 years ago by
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
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
Correction: the line self._prefix = prefix should be somewhere in the init method of WeylGroup_gens
(not WeylGroup
).
Changed 13 years ago by
Kazhdan-Lusztig polynomials, Bruhat order, improved __repr__
for WeylGroups?.
comment:16 Changed 13 years ago by
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
- 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.
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.