#10669: Implement MacMahon's partition analysis Omega operator
-----------------------------+----------------------------------------------
Reporter: nthiery | Owner: sage-combinat
Type: enhancement | Status: new
Priority: major | Milestone: sage-wishlist
Component: combinatorics | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------------+----------------------------------------------
Description changed by nthiery:
Old description:
> 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.
>
> - [[Maple
> implementation|http://www.combinatorics.net.cn/homepage/xin/maple/Ell.rar]]
> 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.
>
> - MuPAD crude implementation of Xin's algorithm by Thiéry:
>
> http://mupad-combinat.svn.sourceforge.net/viewvc/mupad-combinat/trunk
> /MuPAD-Combinat/experimental/2006-06-27-Omega.mu
>
> 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.
>
> - 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
New description:
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
}}}
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10669#comment:1>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
