Opened 6 years ago
Closed 5 years ago
#22066 closed enhancement (fixed)
implement MacMahon's Omega operator
Reported by: | dkrenn | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-7.6 |
Component: | algebra | Keywords: | |
Cc: | cheuberg | Merged in: | |
Authors: | Daniel Krenn | Reviewers: | Clemens Heuberger |
Report Upstream: | N/A | Work issues: | |
Branch: | 482ab70 (Commits, GitHub, GitLab) | Commit: | 482ab70907bb11a8f55cff4860870b3af4ac3b31 |
Dependencies: | #21832, #21833, #21966, #21968, #21976, #21999, #22064 | Stopgaps: |
Description (last modified by )
MacMahon's Omega operator takes a quotient of laurent polynomials and removes all negative exponents in the corresponding power series.
The aim of this ticket is to implement it.
Change History (43)
comment:1 Changed 6 years ago by
- Branch set to u/dkrenn/omega
comment:2 Changed 6 years ago by
- Commit set to 004d61d40fa1ca52be7980ab59188b5da411ecf9
comment:3 Changed 6 years ago by
- Dependencies set to #21832, #21833, #21833, #21966, #21968, #21976, #21999, #22064
comment:4 Changed 6 years ago by
comment:5 Changed 6 years ago by
- Commit changed from 004d61d40fa1ca52be7980ab59188b5da411ecf9 to 4b1c37e34c2c5fa6264fd489e56e9e20cec3237d
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
41b1dcd | lazy import Omega
|
58943d6 | rename Omega_higher --> Omega_ge
|
49e75f4 | fix imports in doctests
|
b122d0f | rename to homogenous_symmetric_function
|
0b6dba8 | name Omega_numerator_P private
|
907d12e | docstring and tests for _Omega_numerator_P_
|
91ee1d0 | add "helper function" comment to some docstrings
|
c97bac4 | fix doc output
|
b085ca6 | module description
|
4b1c37e | references
|
comment:6 Changed 6 years ago by
- Status changed from new to needs_review
comment:7 Changed 6 years ago by
- Cc cheuberg added
comment:8 follow-up: ↓ 10 Changed 6 years ago by
see also #10669
comment:9 Changed 6 years ago by
- Commit changed from 4b1c37e34c2c5fa6264fd489e56e9e20cec3237d to 79fe3b36ea31ccc8a836a88e9d09c280942172bf
Branch pushed to git repo; I updated commit sha1. New commits:
79fe3b3 | extend docstring at top of file
|
comment:10 in reply to: ↑ 8 Changed 6 years ago by
comment:11 Changed 6 years ago by
- Dependencies changed from #21832, #21833, #21833, #21966, #21968, #21976, #21999, #22064 to #21832, #21833, #21966, #21968, #21976, #21999, #22064
Removed duplicate dependency #21833
comment:12 follow-up: ↓ 13 Changed 6 years ago by
- Commit changed from 79fe3b36ea31ccc8a836a88e9d09c280942172bf to 82327c883958a503e6291605e814ae36e7a35085
comment:13 in reply to: ↑ 12 Changed 6 years ago by
Merged in changed dependencies.
comment:14 Changed 6 years ago by
- Commit changed from 82327c883958a503e6291605e814ae36e7a35085 to fceb3e170e79f1390eee97d003d3f894954e901f
Branch pushed to git repo; I updated commit sha1. New commits:
f046132 | Python3 iteritems
|
0db5399 | MPolynomial: correct coefficient ring when dict as input
|
a20fb8a | revert 0f88065556 quick-fix in normalize
|
397301a | doctest example of ticket 21999
|
fceb3e1 | Merge branch 't/21999/laurent-floor-hash' into t/22066/omega
|
comment:15 follow-up: ↓ 23 Changed 6 years ago by
- Description modified (diff)
- Status changed from needs_review to needs_work
This is a review of this ticket modulo its dependencies.
General:
- I am not happy to have
Omega
in the global name space. There might be other uses of the upper case greek letter Omega which might as well live in the global name space, e.g., in context with asymptotics. Thus I suggest to have it asMacMahonOmega
or something like that, perhaps with an alias in the docstring.
- Is there a reason why some of the auxiliary functions are visible and some others are hidden (e.g., for #22067?). In that case, I suggest to have one example in the module documentation which demonstrates how to use
Omega
and perhaps one other example there which demonstrates how to use the other functions efficiently.
- I think that "laurent" should be capitalized throughout, cf. the Wikipedia article.
- Nowadays, the developers guide wants us to store all bibliographical references in
SAGE_ROOT/src/doc/en/reference/references/index.rst
.
- Long descriptions in docstrings: The developer guide does not give clear indications; nevertheless, I suggest to use the same command form as in the short description block above. Otherwise, it seems to be strange to have "Return ..." ... "this calculates".
Function Omega
:
expression
is allowed to be aFactorization
(as per the Tests), but this is not documented.
- Add examples demonstrating all allowed input variants (
expression
only, without denominator;denominator
as a non-factorized Polynomial); perhaps use a simple example to demonstrate all useful variations.
- There are two consecutive lines of imports from
sage.rings.polynomial.laurent_polynomial_ring
which could be done in one import; the second line is too long anyway
- Document and test
NotImplementedError
forop != operator.ge
.
- Test
ValueError
fornot denominator.is_integral()
.
- The line
numerator *= denominator.unit()
seems to be suspicious. Shouldn't it be/=
?
- Test
ValueError
"... is not a variable".
- Test
ZeroDivisionError
- Test
NotImplementedError
"... is not normalized"
- Test
NotImplementedError
"Cannot handle factor"
Function _Omega_
:
- Although main testing is done in
Omega
, it would be nice to have one non-trivial example to see how the input and output looks like.
Function Omega_ge
:
- State in docstring that
z_1
, ...,z_n
do not appear in the input, but do appear in the output.
- State the parent of the output in the docstring (The function
_Omega_
uses the fact that the parent does not depend ona
and uses a specific order of the variables)
- Is there a reason not to use
CyclotomicField
?
- Is there a reason to actually give the number of variables in
LaurentPolynomialRing
?
subs_power
: this is never called withvalue != None
but is only documented withvalue != None
. Thus remove the parametervalue
and adapt documentation.
subs_power
: The linep = tuple(var.dict().popitem()[0]).index(1)
is rather hard to understand, document that this actually just means thatvar
is thep
th generator of the parent.
subs_power
: also state that it is assumed thatvar
only occurs with exponents divisible byexponent
Function Omega_numerator
:
- Document that the numerator is normalized in such a way that the corresponding denominator has constant term 1.
- In
Omega_numerator
it is not clear why the input is not assumed to be flattened beforehand. Add a pointer toOmega_denumerator
.
Function _Omega_numerator_P
:
- When reading [APR2001] one would assume that
_Omega_numerator_P_
should be a cached function. I assume that performance tuning showed that this does not help. Document this.
- Add a meaningful description; currently, one must find out that these are the polynomials
P
in [APR2001].
- The last component of the input
x
is never used;t
is used instead. Consider removing the last component ofx
. Explain the situation.
Function Omega_factors_denominator
:
- Document that the denominator is normalized such that it has constant term 1 (cf. 24)
- The implicit assumption is that the
x
andy
are collected in such a way that one entry ofx
corresponds to the orbit of somex_j
under multiplication byd
th roots of unity and that the output is collected in a corresponding way.
Function partition
:
- Perhaps use an "ALGORITHM" block for the link to the source code.
Function homogeneous_symmetric_function
:
- Give definition (or a link to a definition) of homogeneous symmetric polynomials
- "whose type is determined by the input
x
": what does this mean?
comment:16 Changed 6 years ago by
- Reviewers set to Clemens Heuberger
comment:17 Changed 6 years ago by
- Commit changed from fceb3e170e79f1390eee97d003d3f894954e901f to 8ede01a667f9da18e43669e5e368323eaeeb0ff4
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
d9514a4 | Trac #22066.14: test non-normalized input
|
10900a9 | Trac #22066.15: test non-binom input
|
c0bf0b5 | Trac #22066.16: add non-trivial doctest in _Omega_
|
e60311a | Trac #22066.17: document z_i in Omega_ge
|
80125f8 | Trac #22066.18: state parent of output in Omega_ge
|
2a0f48e | Trac #22066.19: use CyclotomicField instead of QQ.extension(...)
|
8f6ec42 | Trac #22066.21: remove parameter value of subs_power as not needed
|
d874fd3 | Trac #22066.22: comment hard to read line
|
001dccf | Trac #22066.23: make a note in docstring on assumptions in subs_power
|
8ede01a | Trac #22066.24: note in Omega_numerator on normalization
|
comment:18 Changed 6 years ago by
- Commit changed from 8ede01a667f9da18e43669e5e368323eaeeb0ff4 to 0408bce6c72df493b369548e2f478698107db8d8
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
7034154 | Trac #22066.28: remove last component of x in _Omega_Numerator_P_
|
7f41896 | Trac #22066.27: reference P of [APR2001]
|
0331867 | Trac #22066.29: document normalized output of denominator
|
da4c210 | Trac #22066.30: write down implicit assumptions on x and y in _Omega_Numerator_P_
|
61a7ad8 | Trac #22066.31: use ALGORITHM-block
|
09fe59f | Trac #22066.32: provide link to definition of c.h.s. polynomials
|
278014d | Trac #22066.33: specify output-type more clearly
|
6da446e | Trac #22066.6: document Factorization-input
|
f55b39f | Trac #22066.7: test all input variants
|
0408bce | Trac #22066.11: correct handling of unit of denominator
|
comment:19 Changed 6 years ago by
- Commit changed from 0408bce6c72df493b369548e2f478698107db8d8 to 776800f36ee2ceb248b5df86b6053d08f0ed8de8
Branch pushed to git repo; I updated commit sha1. New commits:
776800f | Merge tag '7.5.rc1' into t/22066/omega-7.5.rc1
|
comment:20 Changed 6 years ago by
- Commit changed from 776800f36ee2ceb248b5df86b6053d08f0ed8de8 to 0408bce6c72df493b369548e2f478698107db8d8
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
comment:21 Changed 6 years ago by
- Branch changed from u/dkrenn/omega to u/dkrenn/omega-7.5.rc1
- Commit changed from 0408bce6c72df493b369548e2f478698107db8d8 to 776800f36ee2ceb248b5df86b6053d08f0ed8de8
Last 10 new commits:
7f41896 | Trac #22066.27: reference P of [APR2001]
|
0331867 | Trac #22066.29: document normalized output of denominator
|
da4c210 | Trac #22066.30: write down implicit assumptions on x and y in _Omega_Numerator_P_
|
61a7ad8 | Trac #22066.31: use ALGORITHM-block
|
09fe59f | Trac #22066.32: provide link to definition of c.h.s. polynomials
|
278014d | Trac #22066.33: specify output-type more clearly
|
6da446e | Trac #22066.6: document Factorization-input
|
f55b39f | Trac #22066.7: test all input variants
|
0408bce | Trac #22066.11: correct handling of unit of denominator
|
776800f | Merge tag '7.5.rc1' into t/22066/omega-7.5.rc1
|
comment:22 Changed 6 years ago by
- Commit changed from 776800f36ee2ceb248b5df86b6053d08f0ed8de8 to 13f2fdd726fe6e9719edcb6628e9485f62c0a2a5
comment:23 in reply to: ↑ 15 ; follow-up: ↓ 25 Changed 6 years ago by
I've addressed all issues mentioned earlier; comments below.
Replying to cheuberg:
- I am not happy to have
Omega
in the global name space. There might be other uses of the upper case greek letter Omega which might as well live in the global name space, e.g., in context with asymptotics. Thus I suggest to have it asMacMahonOmega
or something like that, perhaps with an alias in the docstring.
Changed to MacMahonOmega? everywhere.
- Is there a reason why some of the auxiliary functions are visible and some others are hidden (e.g., for #22067?). In that case, I suggest to have one example in the module documentation which demonstrates how to use
Omega
and perhaps one other example there which demonstrates how to use the other functions efficiently.
I am not sure here, what should be hidden and what not. The idea was, hide everything that for sure is a helper function. But I guess in some sense everything except for the main function is a helper somehow. Any suggestions how to proceed?
- Nowadays, the developers guide wants us to store all bibliographical references in
SAGE_ROOT/src/doc/en/reference/references/index.rst
.
Done, but my docs are still compiling (had to do make doc-clean
as the references were not recognized...). I comment when I have a pass.
- Is there a reason to actually give the number of variables in
LaurentPolynomialRing
?
Yes, so that the univariate polynomial ring is represented as multi-variate ring as well.
comment:24 Changed 6 years ago by
- Commit changed from 13f2fdd726fe6e9719edcb6628e9485f62c0a2a5 to 6cff79afc7776388567ba8982f99e238ba6c2054
Branch pushed to git repo; I updated commit sha1. New commits:
4a20e21 | Trac #22066: remove periods when not full sentence (INPUT/OUTPUT blocks)
|
5250cd0 | Trac #22066: extend title (insert "partition analysis")
|
9354988 | Trac 22066: repair broken links
|
2124040 | Trac #22066: insert example at top
|
6cff79a | Merge remote-tracking branch 'trac/u/dkrenn/omega' into t/22066/omega-7.5.rc1
|
comment:25 in reply to: ↑ 23 Changed 6 years ago by
- Status changed from needs_work to needs_review
Replying to dkrenn:
- Is there a reason why some of the auxiliary functions are visible and some others are hidden (e.g., for #22067?). In that case, I suggest to have one example in the module documentation which demonstrates how to use
Omega
and perhaps one other example there which demonstrates how to use the other functions efficiently.I am not sure here, what should be hidden and what not. The idea was, hide everything that for sure is a helper function. But I guess in some sense everything except for the main function is a helper somehow. Any suggestions how to proceed?
Now I've added an example at the top to show what MacMahon?'s Omega does and how it is applied.
- Nowadays, the developers guide wants us to store all bibliographical references in
SAGE_ROOT/src/doc/en/reference/references/index.rst
.Done, but my docs are still compiling (had to do
make doc-clean
as the references were not recognized...). I comment when I have a pass.
Passed.
comment:26 follow-up: ↓ 32 Changed 6 years ago by
- Branch changed from u/dkrenn/omega-7.5.rc1 to u/cheuberg/omega-7.5.rc1
comment:27 Changed 6 years ago by
- Commit changed from 6cff79afc7776388567ba8982f99e238ba6c2054 to 2ce3ab16ce8f41a9961d95a440dd832a138202eb
comment:28 follow-up: ↓ 33 Changed 6 years ago by
Replying to cheuberg:
- Is there a reason why some of the auxiliary functions are visible and some others are hidden (e.g., for #22067?). In that case, I suggest to have one example in the module documentation which demonstrates how to use
Omega
and perhaps one other example there which demonstrates how to use the other functions efficiently.
are we sure that the interface for the low level functions will remain stable?
Function
Omega
:
- Add examples demonstrating all allowed input variants (
expression
only, without denominator;denominator
as a non-factorized Polynomial); perhaps use a simple example to demonstrate all useful variations.
sage: MacMahonOmega(mu, mu^2, (1 - x*mu)*(1 - y/mu)) Traceback (most recent call last): ... TypeError: unable to factor n
seems to be a strange error message (What is "n"?)
- Test
NotImplementedError
"... is not normalized"
I think that the documentation should clearly state how the denominator must be factored.
- I am not happy that
MacMahonOmega(mu, mu^2 / ((1 - x*mu)*(1 - y/mu)))
does not work. This implies that the input method "expression – an element of the quotient field of some Laurent polynomials" only works in trivial cases. After all, just entering a rational function would be the most natural input format.
- What happens if the input is formulated in terms of polynomial rings instead of Laurent polynomial rings?
comment:29 Changed 6 years ago by
- Status changed from needs_review to needs_work
comment:30 Changed 6 years ago by
- Branch changed from u/cheuberg/omega-7.5.rc1 to u/dkrenn/omega-7.5.rc1
comment:31 Changed 6 years ago by
- Commit changed from 2ce3ab16ce8f41a9961d95a440dd832a138202eb to 4b1bb1d008fc6baf0b0c042cb5e54f228ed36364
comment:32 in reply to: ↑ 26 Changed 6 years ago by
Replying to cheuberg:
Branch changed from u/dkrenn/omega-7.5.rc1 to u/cheuberg/omega-7.5.rc1
Cross-reviewed (LGTM)
comment:33 in reply to: ↑ 28 Changed 6 years ago by
Replying to cheuberg:
Replying to cheuberg: are we sure that the interface for the low level functions will remain stable?
Omega_numerator
and Omega_factors_denominator
are now private.
sage: MacMahonOmega(mu, mu^2, (1 - x*mu)*(1 - y/mu)) Traceback (most recent call last): ... TypeError: unable to factor nseems to be a strange error message (What is "n"?)
This is hardcoded in factor
and appears as Laurent polynomials have not method factor
.
- Test
NotImplementedError
"... is not normalized"I think that the documentation should clearly state how the denominator must be factored.
- I am not happy that
MacMahonOmega(mu, mu^2 / ((1 - x*mu)*(1 - y/mu)))
does not work. This implies that the input method "expression – an element of the quotient field of some Laurent polynomials" only works in trivial cases. After all, just entering a rational function would be the most natural input format.
- What happens if the input is formulated in terms of polynomial rings instead of Laurent polynomial rings?
I've removed inputing a quotient from the docs as it is not functioning correctly in some cases. (Refactoring one of the factors in the denominator is not trivial and may change the result. To come around this, one has to know something on the coefficients of a factor; this should all go to a follow-up ticket.)
comment:34 Changed 6 years ago by
- Status changed from needs_work to needs_review
comment:35 Changed 6 years ago by
- Status changed from needs_review to positive_review
ok. Dependencies are rather orthogonal to this ticket, so I set this one to positive. At some stage, it might be good to implement other algorithms (cf. #10669) and to compare speed.
comment:36 Changed 6 years ago by
- Commit changed from 4b1bb1d008fc6baf0b0c042cb5e54f228ed36364 to f1e2fcd1060fc380f31f6e4ae14087c50a27f187
- Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
fded046 | Merge branch 'u/dkrenn/laurent-uni-convert' in 7.5.1
|
c75d370 | trac 21855 some details
|
11707ed | trac 21855 more details
|
65e2fc5 | Merge tag '7.6.beta2' into t/21855/public/21855
|
80eea43 | Merge branch 'public/21855' of git://trac.sagemath.org/sage into t/21976/laurent-efficient-construction
|
f1e2fcd | Merge branch 'u/dkrenn/laurent-efficient-construction' of git://trac.sagemath.org/sage into t/22066/omega-7.5.rc1
|
comment:37 Changed 6 years ago by
Merged in #21976 (and thus 7.6.beta2) to make this patch work again.
comment:38 Changed 6 years ago by
- Status changed from needs_review to positive_review
comment:39 follow-up: ↓ 41 Changed 5 years ago by
- Milestone changed from sage-7.5 to sage-7.6
- Status changed from positive_review to needs_work
Needs another rebasing.
comment:40 Changed 5 years ago by
- Commit changed from f1e2fcd1060fc380f31f6e4ae14087c50a27f187 to 482ab70907bb11a8f55cff4860870b3af4ac3b31
Branch pushed to git repo; I updated commit sha1. New commits:
cf22ee8 | Merge branch 'u/dkrenn/laurent-efficient-construction' of git://trac.sagemath.org/sage into public/polynomials/multivariable_laurent_poly_constructor-21976
|
c58559d | Some reviewer changes.
|
1b7377c | Merge branch 'develop' into public/polynomials/laurent_mpoly_constructor-21976
|
482ab70 | Merge branch 'public/polynomials/laurent_mpoly_constructor-21976' of git://trac.sagemath.org/sage into t/22066/omega-7.5.rc1
|
comment:41 in reply to: ↑ 39 Changed 5 years ago by
- Status changed from needs_work to needs_review
comment:42 Changed 5 years ago by
- Status changed from needs_review to positive_review
comment:43 Changed 5 years ago by
- Branch changed from u/dkrenn/omega-7.5.rc1 to 482ab70907bb11a8f55cff4860870b3af4ac3b31
- Resolution set to fixed
- Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
minor rewrite to increase readability
allow passing mon in _element_constructor_
fix pickling bug
determine parent at top of _element_constructor_
rewrite to detect more specialized situations
Merge branch 'u/dkrenn/laurent-efficient-construction' of trac.sagemath.org:sage into u/dakrenn/omega
quick-fix in normalize
Merge branch 'u/dkrenn/laurent-floor-hash' of trac.sagemath.org:sage into u/dakrenn/omega
use __call__ in subs to be more efficient
Merge branch 'u/dkrenn/laurent-subs' of trac.sagemath.org:sage into u/dakrenn/omega