Opened 12 years ago
Closed 5 years ago
#10669 closed enhancement (wontfix)
Implement MacMahon's partition analysis Omega operator
Reported by: | Nicolas M. Thiéry | Owned by: | Sage Combinat CC user |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | combinatorics | Keywords: | |
Cc: | Sage Combinat CC user, Jason Bandlow, musiker, Zafeirakis Zafeirakopoulos | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Consider a multivariate fraction F, mixing parameters and variables (or possibly just an Eliot fraction, where the denonimators are binomials). The Omega operator applied on F returns the constant term of F, under the form of a fraction in the parameters.
A typical application of this tool is to build the generating function for all the solutions to a system of Diophantine linear equation. It has also been used in many papers to build closed form formula for generating series.
Implementations and algorithms:
- http://www.risc.jku.at/research/combinat/software/Omega/ Mathematica implementation by Andrews/Paule/Riese?: Non-Free. Sources available upon request.
- http://www.combinatorics.net.cn/homepage/xin/maple/Ell.rar Maple implementation by Guoce Xin who realized that Laurent series were the appropriate setup for this problem, both conceptually and to derive efficient algorithms using explicit partial fraction decomposition, together with subtle heuristics for controlling the number of terms ([2]; see also Zeilberger opinion [3]).
- http://www-irma.u-strasbg.fr/~guoniu/software/ Maple implementation by Guo-Niu Han, who generalized Xin's algorithm from Eliot fractions to any rational fraction [3]
- http://www.risc.jku.at/research/combinat/software/GenOmega/index.php Mathematica implementation by Wiesinger of Han's algorithm The link also point to Wiesinger's master thesis on the topic.
- http://mupad-combinat.svn.sourceforge.net/viewvc/mupad-combinat/trunk/MuPAD-Combinat/experimental/2006-06-27-Omega.mu MuPAD crude implementation of Xin's algorithm by Thiéry:
The only reason to mention it here is for the attempts at using proper data structures and object orientation; it is my bet that those could eventually yield not only much more readable code, but also eventually faster. However at this point the heuristics are improperly fine tuned, and the code darn slow.
- Links with Schur functions, by Fu and Lascoux [4]
- Sage prototype (Bandlow/Musiker?) written at Sage Days 7: ...
[1] http://arxiv.org/abs/math.CO/0408377 [2] http://www.math.rutgers.edu/~zeilberg/Opinion74.html [3] http://www-irma.u-strasbg.fr/~guoniu/papers/p36omega.pdf [4] http://arxiv.org/abs/math/0404064
Change History (6)
comment:1 Changed 12 years ago by
Description: | modified (diff) |
---|
comment:2 Changed 11 years ago by
Cc: | Zafeirakis Zafeirakopoulos added |
---|
comment:4 Changed 5 years ago by
Milestone: | sage-wishlist → sage-duplicate/invalid/wontfix |
---|---|
Status: | new → needs_review |
comment:5 Changed 5 years ago by
Status: | needs_review → positive_review |
---|
comment:6 Changed 5 years ago by
Resolution: | → wontfix |
---|---|
Status: | positive_review → closed |
closing positively reviewed duplicates
I have a Sage implementation of the Omega operator, mainly based on the Andrews/Paule/Riese? papers. (I haven't seen the MMA implementation). Maybe Zaf is interested in working on it so it can be included in Sage.