implement MacMahon's Omega operator #22066

dkrenn · 2016-12-16T08:18:29Z

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.

Depends on #21832
Depends on #21833
Depends on #21966
Depends on #21968
Depends on #21976
Depends on #21999
Depends on #22064

CC: @cheuberg

Component: algebra

Author: Daniel Krenn

Branch/Commit: 482ab70

Reviewer: Clemens Heuberger

Issue created by migration from https://trac.sagemath.org/ticket/22066

The text was updated successfully, but these errors were encountered:

dkrenn · 2016-12-16T08:32:37Z

Branch: u/dkrenn/omega

sagetrac-git · 2016-12-16T08:38:40Z

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

`d33a595`	`minor rewrite to increase readability`
`5a5db0b`	`allow passing mon in _element_constructor_`
`3a809a4`	`fix pickling bug`
`be67f37`	`determine parent at top of _element_constructor_`
`6137662`	`rewrite to detect more specialized situations`
`0570355`	`Merge branch 'u/dkrenn/laurent-efficient-construction' of trac.sagemath.org:sage into u/dakrenn/omega`
`0f88065`	`quick-fix in normalize`
`c0fea6e`	`Merge branch 'u/dkrenn/laurent-floor-hash' of trac.sagemath.org:sage into u/dakrenn/omega`
`9389e62`	use `__call__` in subs to be more efficient
`004d61d`	`Merge branch 'u/dkrenn/laurent-subs' of trac.sagemath.org:sage into u/dakrenn/omega`

sagetrac-git · 2016-12-16T08:38:40Z

Commit: 004d61d

dkrenn · 2016-12-16T08:54:15Z

Dependencies: #21832, #21833, #21833, #21966, #21968, #21976, #21999, #22064

dkrenn · 2016-12-16T08:54:25Z

Author: Daniel Krenn

sagetrac-git · 2016-12-16T09:55:53Z

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`

sagetrac-git · 2016-12-16T09:55:53Z

Changed commit from 004d61d to 4b1c37e

fchapoton · 2016-12-16T09:59:51Z

comment:8

see also #10669

sagetrac-git · 2016-12-16T10:03:55Z

Branch pushed to git repo; I updated commit sha1. New commits:

`79fe3b3`	`extend docstring at top of file`

sagetrac-git · 2016-12-16T10:03:55Z

Changed commit from 4b1c37e to 79fe3b3

dkrenn · 2016-12-16T10:12:30Z

comment:10

Replying to @fchapoton:

see also #10669

Thank you for mentioning this. (I have never thought anyone already created a ticket for this.) ;)

cheuberg · 2016-12-19T13:57:20Z

Changed dependencies from #21832, #21833, #21833, #21966, #21968, #21976, #21999, #22064 to #21832, #21833, #21966, #21968, #21976, #21999, #22064

cheuberg · 2016-12-19T13:57:20Z

comment:11

Removed duplicate dependency #21833

sagetrac-git · 2016-12-22T08:25:01Z

Changed commit from 79fe3b3 to 82327c8

sagetrac-git · 2016-12-22T08:25:01Z

Branch pushed to git repo; I updated commit sha1. New commits:

`f7e9540`	`fix doctest (conversion to symbolic)`
`82327c8`	`Merge branch 'u/dakrenn/laurent-subs' into t/22066/omega`

dkrenn · 2016-12-22T08:28:48Z

comment:13

Merged in changed dependencies.

sagetrac-git · 2016-12-26T17:35:04Z

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`

sagetrac-git · 2016-12-26T17:35:04Z

Changed commit from 82327c8 to fceb3e1

cheuberg · 2017-01-02T19:19:46Z

comment:15

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 as MacMahonOmega 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 generating function of integral points of polyhedra #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 a Factorization (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 for op != operator.ge.
Test ValueError for not 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 on a 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 with value != None but is only documented with value != None. Thus remove the parameter value and adapt documentation.
subs_power: The line p = tuple(var.dict().popitem()[0]).index(1) is rather hard to understand, document that this actually just means that var is the pth generator of the parent.
subs_power: also state that it is assumed that var only occurs with exponents divisible by exponent

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 to Omega_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 of x. 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 and y are collected in such a way that one entry of x corresponds to the orbit of some x_j under multiplication by dth 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?

cheuberg · 2017-01-02T19:20:24Z

Reviewer: Clemens Heuberger

sagetrac-git · 2017-01-04T08:24:58Z

Changed commit from fceb3e1 to 8ede01a

sagetrac-git · 2017-01-04T08:24:58Z

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`

cheuberg · 2017-01-12T10:22:06Z

comment:35

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.

sagetrac-git · 2017-02-09T09:23:23Z

Changed commit from 4b1bb1d to f1e2fcd

sagetrac-git · 2017-02-09T09:23:23Z

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`

dkrenn · 2017-02-09T09:24:22Z

comment:37

Merged in #21976 (and thus 7.6.beta2) to make this patch work again.

tscrim · 2017-03-02T14:49:09Z

comment:39

Needs another rebasing.

sagetrac-git · 2017-03-02T14:58:21Z

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`

sagetrac-git · 2017-03-02T14:58:21Z

Changed commit from f1e2fcd to 482ab70

dkrenn · 2017-03-02T14:59:41Z

comment:41

Replying to @tscrim:

Needs another rebasing.

Merged in dependency #21976. Once the patchbot is happy, this can be positive again.

vbraun · 2017-03-05T15:13:50Z

Changed branch from u/dkrenn/omega-7.5.rc1 to 482ab70

Implement this using !MacMahon's Omega operator (sagemath#22066). URL: https://trac.sagemath.org/22067 Reported by: dkrenn Ticket author(s): Daniel Krenn Reviewer(s): Matthias Koeppe

dkrenn added this to the sage-7.5 milestone Dec 16, 2016

dkrenn added c: algebra labels Dec 16, 2016

dkrenn added the s: needs review label Dec 16, 2016

This comment has been minimized.

Sign in to view

cheuberg added s: needs work and removed s: needs review labels Jan 2, 2017

dkrenn added s: needs review and removed s: needs work labels Jan 5, 2017

cheuberg added s: positive review and removed s: needs review labels Jan 12, 2017

sagetrac-git mannequin added s: needs review and removed s: positive review labels Feb 9, 2017

dkrenn added s: positive review and removed s: needs review labels Feb 9, 2017

tscrim added s: needs work and removed s: positive review labels Mar 2, 2017

tscrim modified the milestones: sage-7.5, sage-7.6 Mar 2, 2017

dkrenn added s: needs review and removed s: needs work labels Mar 2, 2017

vbraun removed the s: positive review label Mar 5, 2017

vbraun closed this as completed in 4ca33ea Mar 5, 2017

This was referenced Jan 18, 2023

generating function of integral points of polyhedra #22067

Closed

MacMahon's Omega: cancel some common factors in intermediate result #22803

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

implement MacMahon's Omega operator #22066

implement MacMahon's Omega operator #22066

dkrenn commented Dec 16, 2016

dkrenn commented Dec 16, 2016

sagetrac-git mannequin commented Dec 16, 2016

sagetrac-git mannequin commented Dec 16, 2016

dkrenn commented Dec 16, 2016

dkrenn commented Dec 16, 2016

sagetrac-git mannequin commented Dec 16, 2016

sagetrac-git mannequin commented Dec 16, 2016

fchapoton commented Dec 16, 2016

sagetrac-git mannequin commented Dec 16, 2016

sagetrac-git mannequin commented Dec 16, 2016

dkrenn commented Dec 16, 2016

cheuberg commented Dec 19, 2016

cheuberg commented Dec 19, 2016

sagetrac-git mannequin commented Dec 22, 2016

sagetrac-git mannequin commented Dec 22, 2016

dkrenn commented Dec 22, 2016

sagetrac-git mannequin commented Dec 26, 2016

sagetrac-git mannequin commented Dec 26, 2016

This comment has been minimized.

cheuberg commented Jan 2, 2017

cheuberg commented Jan 2, 2017

sagetrac-git mannequin commented Jan 4, 2017

sagetrac-git mannequin commented Jan 4, 2017

cheuberg commented Jan 12, 2017

sagetrac-git mannequin commented Feb 9, 2017

sagetrac-git mannequin commented Feb 9, 2017

dkrenn commented Feb 9, 2017

tscrim commented Mar 2, 2017

sagetrac-git mannequin commented Mar 2, 2017

sagetrac-git mannequin commented Mar 2, 2017

dkrenn commented Mar 2, 2017

vbraun commented Mar 5, 2017

implement MacMahon's Omega operator #22066

implement MacMahon's Omega operator #22066

Comments

dkrenn commented Dec 16, 2016

dkrenn commented Dec 16, 2016

sagetrac-git mannequin commented Dec 16, 2016

sagetrac-git mannequin commented Dec 16, 2016

dkrenn commented Dec 16, 2016

dkrenn commented Dec 16, 2016

sagetrac-git mannequin commented Dec 16, 2016

sagetrac-git mannequin commented Dec 16, 2016

fchapoton commented Dec 16, 2016

sagetrac-git mannequin commented Dec 16, 2016

sagetrac-git mannequin commented Dec 16, 2016

dkrenn commented Dec 16, 2016

cheuberg commented Dec 19, 2016

cheuberg commented Dec 19, 2016

sagetrac-git mannequin commented Dec 22, 2016

sagetrac-git mannequin commented Dec 22, 2016

dkrenn commented Dec 22, 2016

sagetrac-git mannequin commented Dec 26, 2016

sagetrac-git mannequin commented Dec 26, 2016

This comment has been minimized.

cheuberg commented Jan 2, 2017

cheuberg commented Jan 2, 2017

sagetrac-git mannequin commented Jan 4, 2017

sagetrac-git mannequin commented Jan 4, 2017

cheuberg commented Jan 12, 2017

sagetrac-git mannequin commented Feb 9, 2017

sagetrac-git mannequin commented Feb 9, 2017

dkrenn commented Feb 9, 2017

tscrim commented Mar 2, 2017

sagetrac-git mannequin commented Mar 2, 2017

sagetrac-git mannequin commented Mar 2, 2017

dkrenn commented Mar 2, 2017

vbraun commented Mar 5, 2017