Opened 5 years ago

Last modified 4 months ago

#22067 needs_work enhancement

generating function of integral points of polyhedra

Reported by: dkrenn Owned by:
Priority: major Milestone: sage-9.5
Component: geometry Keywords:
Cc: cheuberg, jipilab, gh-braunmath, slelievre Merged in:
Authors: Daniel Krenn Reviewers: Matthias Koeppe
Report Upstream: N/A Work issues:
Branch: u/dkrenn/gf-polyhedron (Commits, GitHub, GitLab) Commit: a43c6be5761e99bbcd544e7b94cadbad2037ad26
Dependencies: Stopgaps:

Status badges

Description (last modified by slelievre)

Implement this using MacMahon's Omega operator (#22066).

Change History (133)

comment:1 Changed 5 years ago by dkrenn

  • Branch set to u/dkrenn/gf-polyhedron

comment:2 Changed 5 years ago by dkrenn

  • Authors set to Daniel Krenn
  • Commit set to 5d4910210e8c7c75d44c8aaa34c03f1d28b62909
  • Component changed from PLEASE CHANGE to geometry
  • Description modified (diff)

Last 10 new commits:

5a5db0ballow passing mon in _element_constructor_
3a809a4fix pickling bug
be67f37determine parent at top of _element_constructor_
6137662rewrite to detect more specialized situations
0570355Merge branch 'u/dkrenn/laurent-efficient-construction' of trac.sagemath.org:sage into u/dakrenn/omega
0f88065quick-fix in normalize
c0fea6eMerge branch 'u/dkrenn/laurent-floor-hash' of trac.sagemath.org:sage into u/dakrenn/omega
9389e62use __call__ in subs to be more efficient
004d61dMerge branch 'u/dkrenn/laurent-subs' of trac.sagemath.org:sage into u/dakrenn/omega
5d49102Merge branch 'u/dakrenn/omega' into u/dakrenn/gf-polyhedron

comment:3 Changed 5 years ago by git

  • Commit changed from 5d4910210e8c7c75d44c8aaa34c03f1d28b62909 to 32c6eeb9432da70febc8fe7d073f86023f7a1811

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

4b1c37ereferences
79fe3b3extend docstring at top of file
f1ec72eMerge branch 'u/dkrenn/omega' of git://trac.sagemath.org/sage into t/22067/gf-polyhedron
ddbf737repr_pretty and _latex_ of Hrepresentation
54fc5b8repr_pretty_Hrepresentation for polyhedra
968a998Merge branch 'u/dkrenn/inequality-pretty' of git://trac.sagemath.org/sage into t/22067/gf-polyhedron
1e327c5add generating_function module to index
662195bmodule description
4a98951fix imports in doctests
32c6eebfix omega imports

comment:4 Changed 5 years ago by dkrenn

  • Cc cheuberg added

comment:5 Changed 5 years ago by git

  • Commit changed from 32c6eeb9432da70febc8fe7d073f86023f7a1811 to 7fcfe5ef1b679400b66fb6778473d692e20193e3

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

9ca1aebmove repr_pretty code outside class, so that it can be used elsewhere as well
73649f9Merge branch 'u/dkrenn/inequality-pretty' into t/22067/gf-polyhedron
6f59894use repr_pretty (and remove old pretty_inequality)
ae030famore logging cleanup
a2334a3make helper functions private
c4d01ecmake helper function private (part 2)
86f40cawrite missing docstrings/comments
24abfd4todo-cleanup
76801dbfix a doctest
7fcfe5efix code typo

comment:6 Changed 5 years ago by git

  • Commit changed from 7fcfe5ef1b679400b66fb6778473d692e20193e3 to adf4dad4769aa2bc6f090b56c6a22e8279233523

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

adf4dadremove Summandization

comment:7 Changed 5 years ago by git

  • Commit changed from adf4dad4769aa2bc6f090b56c6a22e8279233523 to 999140f0b18a0b8d9fc9695316d0a16f6fde6dfa

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

dd0679euse relative imports
50a2a7amethod generating_function for a polyhedron
9932d28fix docstrings
999140frephare OUTPUT-block

comment:8 Changed 5 years ago by dkrenn

  • Status changed from new to needs_review

comment:9 Changed 5 years ago by mkoeppe

Return the generating function of the integer points of
+    the polyhedron's orthant with only nonnegative coordinates.

Why only the integer points with nonnegative coordinates?

comment:10 Changed 5 years ago by git

  • Commit changed from 999140f0b18a0b8d9fc9695316d0a16f6fde6dfa to f85e038c380e0686d06f2fe413ac22dbc95622e7

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

f85e038add doctest to _generate_mod_

comment:11 Changed 5 years ago by git

  • Commit changed from f85e038c380e0686d06f2fe413ac22dbc95622e7 to fce0c71d9bf117c3bfe549be7381a6008f2a8c9b

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

f7e9540fix doctest (conversion to symbolic)
82327c8Merge branch 'u/dakrenn/laurent-subs' into t/22066/omega
16e515eMerge branch 't/22066/omega' into t/22067/gf-polyhedron
0049218remove periods at end of non-sentence in INPUT-block
91cab4aPython3 print syntax
fce0c71Merge branch 'u/dkrenn/inequality-pretty' into t/22067/gf-polyhedron

comment:12 Changed 5 years ago by dkrenn

Merged in changed dependencies.

comment:13 follow-up: Changed 5 years ago by vdelecroix

Hello,

This would be really useful.

1) The name is too generic: generating_function could be anything (e.g. the number of lattice points in dilates). It should be something like non_negative_lattice_points_generating_function.

2) What do you mean by "generating function"? Is it weighted by the sum of the vector?

3) You should at least check that the number of integer partitions is correctly computed by your function with the polyhedron

x1 >= x2 >= x3 >= x4 >= x5 >= 1

versus

sage: [Partitions(k, length=5).cardinality() for k in range(5,20)]
[1, 1, 2, 3, 5, 7, 10, 13, 18, 23, 30, 37, 47, 57, 70]

comment:14 follow-up: Changed 5 years ago by mkoeppe

I agree with Vincent that the name is too generic. This seems to compute what, for example, LattE would call the multivariate generating function (which can be computed by count --multivariate-generating-function after installing package latte_int) -- but not of the integer points of the given polyhedron but of its intersection with the positive orthant. This "positive orthant" business, I think, is just a peculiarity of the Omega approach but I don't think it's makes sense to expose it to the user. Maybe raise a NotImplementedError instead if the given polytope is not contained in the positive orthant?

comment:15 in reply to: ↑ 14 ; follow-up: Changed 5 years ago by vdelecroix

Replying to mkoeppe:

This "positive orthant" business, I think, is just a peculiarity of the Omega approach but I don't think it's makes sense to expose it to the user. Maybe raise a NotImplementedError instead if the given polytope is not contained in the positive orthant?

+1. The API would be much better (and allows extension in the future to count all points (that can already be done intersecting with the 2dim orthants and applying symmetries)).

comment:16 Changed 5 years ago by git

  • Commit changed from fce0c71d9bf117c3bfe549be7381a6008f2a8c9b to 5d4018af485d1fdda08e9fb872a9a8a17579118f

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

5c22d7frename methods (to make it more precise)
68e3fc7check if polyhedron is in nonnegative orthant
d001a8edoctests for polyhedra with negative coordinates
4ee76c4fix existing doctests
7a96155document nonnegative-orthant-changes
0afac56minor rewrite (integer points --> integral points)
871aea4write down formula to make resulting GF precise
aa208eaminor rewrite in SEEALSO blocks
594d9e5example integer partitions
5d4018afix docs (ReST syntax)

comment:17 in reply to: ↑ 13 Changed 5 years ago by dkrenn

Replying to vdelecroix:

This would be really useful.

Good :)

Thank you for your comments. Code updated.

1) The name is too generic: generating_function could be anything (e.g. the number of lattice points in dilates). It should be something like non_negative_lattice_points_generating_function.

It seems that "integral points" is used in sage.geometry.polyhedron` a couple of times, thus, changed to generating_function_of_integral_points.

2) What do you mean by "generating function"? Is it weighted by the sum of the vector?

Inserted a formula to make this precise.

3) You should at least check that the number of integer partitions is correctly computed by your function with the polyhedron

x1 >= x2 >= x3 >= x4 >= x5 >= 1

versus

sage: [Partitions(k, length=5).cardinality() for k in range(5,20)]
[1, 1, 2, 3, 5, 7, 10, 13, 18, 23, 30, 37, 47, 57, 70]

Indeed; example added.

comment:18 in reply to: ↑ 15 Changed 5 years ago by dkrenn

Replying to vdelecroix:

Replying to mkoeppe:

This "positive orthant" business, I think, is just a peculiarity of the Omega approach but I don't think it's makes sense to expose it to the user. Maybe raise a NotImplementedError instead if the given polytope is not contained in the positive orthant?

+1. The API would be much better (and allows extension in the future to count all points (that can already be done intersecting with the 2dim orthants and applying symmetries)).

I agree. Changed to documentation and added a few lines to check if polyhedron is in the nonnegative orthant; otherwise raise NotImplementedError. (Created a follow up ticket #22099 for this.)

Version 0, edited 5 years ago by dkrenn (next)

comment:19 Changed 5 years ago by dkrenn

  • Summary changed from generating function of integer-valued polyhedra to generating function of integral points of polyhedra

comment:20 Changed 5 years ago by git

  • Commit changed from 5d4018af485d1fdda08e9fb872a9a8a17579118f to fe77eec64d6d7ac53decb703977a1464c5d09bfa

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

f046132Python3 iteritems
0db5399MPolynomial: correct coefficient ring when dict as input
a20fb8arevert 0f88065556 quick-fix in normalize
397301adoctest example of ticket 21999
fceb3e1Merge branch 't/21999/laurent-floor-hash' into t/22066/omega
fe77eecMerge branch 't/22066/omega' into t/22067/gf-polyhedron

comment:21 follow-up: Changed 5 years ago by mkoeppe

  • Status changed from needs_review to needs_work
sage: P = Polyhedron(vertices=[[1], [5]])
sage: P.generating_function_of_integral_points()
TypeError: unsupported operand type(s) for -: 'tuple' and 'tuple'

comment:22 Changed 5 years ago by git

  • Commit changed from fe77eec64d6d7ac53decb703977a1464c5d09bfa to 35cf3a2c59178cb55df897b9eaf3d4a6d7beafe1

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

35cf3a2fix 1-dimensial case (creation of univariate laurent polynomial ring)

comment:23 in reply to: ↑ 21 Changed 5 years ago by dkrenn

  • Status changed from needs_work to needs_review

Replying to mkoeppe:

sage: P = Polyhedron(vertices=[[1], [5]])
sage: P.generating_function_of_integral_points()
TypeError: unsupported operand type(s) for -: 'tuple' and 'tuple'

Fixed.

comment:24 follow-up: Changed 5 years ago by mkoeppe

I think the name of the variables used in the generating function should be a user option

comment:25 follow-up: Changed 5 years ago by mkoeppe

sage: P = Polyhedron(rays=[(1, sqrt(2)), (0, 1)])
sage: P.generating_function_of_integral_points()
1 * (-y0 + 1)^-1 * (-y1 + 1)^-1

I had hoped for an error

comment:26 follow-ups: Changed 5 years ago by mkoeppe

Also I think the method generating_function_of_integral_points should have an algorithm keyword. For polytopes, could provide a naive algorithm that just collects the monomials corresponding to integral_points. And another algorithm would be to just call LattE.

Various algorithms options such as result_as_tuple are not sufficiently documented.

For the LattE algorithm, the best output format would be a sum of Factorizations. Is this what result_as_tuple can represent?

comment:27 Changed 5 years ago by mkoeppe

  • Reviewers set to Matthias Koeppe
  • Status changed from needs_review to needs_work

comment:28 Changed 5 years ago by git

  • Commit changed from 35cf3a2c59178cb55df897b9eaf3d4a6d7beafe1 to 401c4988cf876724d7d3d6079c11f35c37c06fa6

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

98d46b6new option: specify the prefix of the output variables
fb2f8f6test and document prefix_variable_name
7bbae4bextend documentation of parameter result_as_tuple
3d9bb3fextend documentation of parameter sort_factors
401c498check base ring of the polyhedron (if it is ZZ or QQ)

comment:29 in reply to: ↑ 24 Changed 5 years ago by dkrenn

Replying to mkoeppe:

I think the name of the variables used in the generating function should be a user option

True; option is now available :)

comment:30 in reply to: ↑ 25 Changed 5 years ago by dkrenn

Replying to mkoeppe:

sage: P = Polyhedron(rays=[(1, sqrt(2)), (0, 1)])
sage: P.generating_function_of_integral_points()
1 * (-y0 + 1)^-1 * (-y1 + 1)^-1

I had hoped for an error

Now the base ring of the polyhedron is inspected.

comment:31 in reply to: ↑ 26 ; follow-up: Changed 5 years ago by dkrenn

Replying to mkoeppe:

Various algorithms options such as result_as_tuple are not sufficiently documented.

Docs extended.

comment:32 in reply to: ↑ 26 Changed 5 years ago by dkrenn

Replying to mkoeppe:

Also I think the method generating_function_of_integral_points should have an algorithm keyword. For polytopes, could provide a naive algorithm that just collects the monomials corresponding to integral_points. And another algorithm would be to just call LattE.

As this does not change the interface, only extends it, I have put this on the follow--up enhancement ticket #22111.

comment:33 in reply to: ↑ 26 Changed 5 years ago by dkrenn

Replying to mkoeppe:

For the LattE algorithm, the best output format would be a sum of Factorizations. Is this what result_as_tuple can represent?

Yes, correct. (As mentioned, I've extended the docstring of this option.)

comment:34 Changed 5 years ago by dkrenn

  • Status changed from needs_work to needs_review

comment:35 in reply to: ↑ 31 ; follow-up: Changed 5 years ago by mkoeppe

Replying to dkrenn:

Replying to mkoeppe:

Various algorithms options such as result_as_tuple are not sufficiently documented.

Docs extended.

Wouldn't it be nicer to have a class to represent such sums, much like Factorization represents products?

comment:36 in reply to: ↑ 35 Changed 5 years ago by dkrenn

Replying to mkoeppe:

Replying to dkrenn:

Replying to mkoeppe:

Various algorithms options such as result_as_tuple are not sufficiently documented.

Docs extended.

Wouldn't it be nicer to have a class to represent such sums, much like Factorization represents products?

Yes, indeed. I had this (a class Summandization in some draft, but as it is nowhere else in SageMath (e.g. partial_fraction_decomposition), I decided to keep it simple and consistent and use a tuple.

comment:37 Changed 5 years ago by jipilab

  • Cc jipilab added

comment:38 Changed 5 years ago by git

  • Commit changed from 401c4988cf876724d7d3d6079c11f35c37c06fa6 to 22bd0c4c8e5cb0a2829867e9c069561872b39879

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

b8314a3Trac #22066: Format Mac1915
2ce3ab1Trac #22066: minor rewording
4b1bb1dMerge remote-tracking branch 'trac/u/cheuberg/omega-7.5.rc1' into t/22066/omega-7.5.rc1
fded046Merge branch 'u/dkrenn/laurent-uni-convert' in 7.5.1
c75d370trac 21855 some details
11707edtrac 21855 more details
65e2fc5Merge tag '7.6.beta2' into t/21855/public/21855
80eea43Merge branch 'public/21855' of git://trac.sagemath.org/sage into t/21976/laurent-efficient-construction
f1e2fcdMerge branch 'u/dkrenn/laurent-efficient-construction' of git://trac.sagemath.org/sage into t/22066/omega-7.5.rc1
22bd0c4Merge branch 'u/dkrenn/omega-7.5.rc1' of git://trac.sagemath.org/sage into t/22067/gf-polyhedron

comment:39 follow-up: Changed 5 years ago by git

  • Commit changed from 22bd0c4c8e5cb0a2829867e9c069561872b39879 to 35507829141ae344a84be1ce67d557c99087db0a

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

78c8278precise description of input/output of helper functions
3550782unify error messages

comment:40 in reply to: ↑ 39 Changed 5 years ago by dkrenn

Replying to git:

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

78c8278precise description of input/output of helper functions

I've written a better description of the helper functions to make reviewing easier.

comment:41 Changed 5 years ago by git

  • Commit changed from 35507829141ae344a84be1ce67d557c99087db0a to 4d2ccb6f12eb183daebe9c4e046ecb0be7ac6f74

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

4d2ccb6unify INPUT/OUTPUT blocks

comment:42 follow-up: Changed 5 years ago by mkoeppe

needs rebasing

comment:43 Changed 5 years ago by mkoeppe

  • Milestone changed from sage-7.5 to sage-7.6
  • Status changed from needs_review to needs_work

comment:44 Changed 5 years ago by git

  • Commit changed from 4d2ccb6f12eb183daebe9c4e046ecb0be7ac6f74 to 3a3aec5122c35e5fc9291b69895f6e185a54cc41

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

cf22ee8Merge branch 'u/dkrenn/laurent-efficient-construction' of git://trac.sagemath.org/sage into public/polynomials/multivariable_laurent_poly_constructor-21976
c58559dSome reviewer changes.
1b7377cMerge branch 'develop' into public/polynomials/laurent_mpoly_constructor-21976
3a3aec5Merge branch 'public/polynomials/laurent_mpoly_constructor-21976' of git://trac.sagemath.org/sage into t/22067/gf-polyhedron

comment:45 in reply to: ↑ 42 Changed 5 years ago by dkrenn

  • Status changed from needs_work to needs_review

Replying to mkoeppe:

needs rebasing

This was because of a change in one of its dependencies. Merged in; should now work again.

comment:46 Changed 5 years ago by git

  • Commit changed from 3a3aec5122c35e5fc9291b69895f6e185a54cc41 to b09d1622689b7c7c35a3413698f222177e9e6876

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

b09d162Trac #22067: minor modification of logging output

comment:47 Changed 5 years ago by git

  • Commit changed from b09d1622689b7c7c35a3413698f222177e9e6876 to 423096c71bac2a2aa4c75311baca4c0a4c929bf9

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

24a861frename _generate_mods_ to generate_mods
7bb6fefadapt to previous code movement
fd117fffactor out calling-Omega-code
f137fbasmall cleanup
aaf0fa0restrict splitting off inequality to constants <= 0
802c523use _simplify_ to cancel terms
2d94245update doctests
b4082d2function _simplify_ for cancelling factors in intermediate result (quotient)
b02b7f1use and test new feature in _Omega_-function
423096cMerge branch 'u/dakrenn/omega-simplify' into t/22067/gf-polyhedron

comment:48 Changed 5 years ago by dkrenn

  • Dependencies changed from #22065, #22066 to #22065, #22066, #22803
  • Status changed from needs_review to needs_work
  • Merged in 7.6, as some error messages concerning polynomial rings have changed and thus doctests failed.
  • Merged in #22803, which simplifies the some generating functions due to cancellations
  • Fixed a small bug.
  • Restructured/refactored some code to make testing the overall result easier.
  • Extended the existing doctests to see the correctness of the results.

(Set it to needs work as some docstrings are not yet written.)

comment:49 Changed 5 years ago by git

  • Commit changed from 423096c71bac2a2aa4c75311baca4c0a4c929bf9 to 3cfd809279a92f1259e01381125afa0e8965e97d

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

53b5fb0correct link
3cfd809complete docstrings and doctests

comment:50 Changed 5 years ago by dkrenn

  • Status changed from needs_work to needs_review

comment:51 Changed 5 years ago by chapoton

2 failing doctests, see patchbot report (wrong import)

comment:52 follow-up: Changed 5 years ago by chapoton

  • Status changed from needs_review to needs_work

ping ? just 2 imports need to be changed..

comment:53 Changed 5 years ago by git

  • Commit changed from 3cfd809279a92f1259e01381125afa0e8965e97d to c91baa5d0ba1d7febd8cd5afe9c92b724c52efc2

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

c91baa5Trac #22067: correct import of lcm

comment:54 in reply to: ↑ 52 Changed 5 years ago by dkrenn

Replying to chapoton:

ping ? just 2 imports need to be changed..

Sorry, I am currently some kind of busy. However, changed the import. Let's see what the patchbot says now ;)

comment:55 Changed 5 years ago by dkrenn

  • Status changed from needs_work to needs_review

comment:56 follow-up: Changed 5 years ago by chapoton

Trivial remark: some "laurent" are missing their capitals.

comment:57 follow-up: Changed 4 years ago by chapoton

  • Status changed from needs_review to needs_work

and one failing doctest

comment:58 Changed 3 years ago by git

  • Commit changed from c91baa5d0ba1d7febd8cd5afe9c92b724c52efc2 to 1b922e779cf2e4e32a0257ed39f63fdcc5c09bdb

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

1bd336aMerge tag '8.3' into t/22067/gf-polyhedron
d5f551aMerge commit 'b1ae583' into t/22067/gf-polyhedron
acb0c64fix error message (change due to new SageMath version)
1b922e7fix call to deprecated method

comment:59 Changed 3 years ago by git

  • Commit changed from 1b922e779cf2e4e32a0257ed39f63fdcc5c09bdb to 0f2d193c0a27c2073c9f149c47a9422c680ded66

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

0f2d193doc: laurent --> Laurent

comment:60 in reply to: ↑ 56 Changed 3 years ago by dkrenn

Replying to chapoton:

Trivial remark: some "laurent" are missing their capitals.

Fixed in ​0f2d193

comment:61 in reply to: ↑ 57 Changed 3 years ago by dkrenn

Replying to chapoton:

and one failing doctest

Fixed.

comment:62 Changed 3 years ago by dkrenn

  • Dependencies changed from #22065, #22066, #22803 to #22065, #22066, #22803, #24837
  • Status changed from needs_work to needs_review

comment:63 Changed 3 years ago by chapoton

you can just remove the dependencies (empty this field), once closed

comment:64 Changed 3 years ago by git

  • Commit changed from 0f2d193c0a27c2073c9f149c47a9422c680ded66 to 372da68378a9fce88ff20f1308bd243bad28c396

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

372da68cleanup pyflakes warnings

comment:65 Changed 3 years ago by git

  • Commit changed from 372da68378a9fce88ff20f1308bd243bad28c396 to 1583e91e3f207b0ce47369cd00083c963889dba7

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

1583e91fixup: forgotten ** left of kwds

comment:66 Changed 3 years ago by git

  • Commit changed from 1583e91e3f207b0ce47369cd00083c963889dba7 to 05108969d429ca7c6299f7b6d999f12e807ab224

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

0510896uniquify sorting in SplitOffSimpleInequalities

comment:67 Changed 3 years ago by mkoeppe

  • Cc gh-braunmath added

comment:68 Changed 3 years ago by slelievre

  • Cc slelievre added
  • Description modified (diff)
  • Milestone changed from sage-7.6 to sage-8.8

comment:69 Changed 2 years ago by embray

  • Milestone changed from sage-8.8 to sage-8.9

Moving tickets from the Sage 8.8 milestone that have been actively worked on in the last six months to the next release milestone (optimistically).

comment:70 Changed 2 years ago by chapoton

  • Status changed from needs_review to needs_work

one failing doctest.

comment:71 Changed 2 years ago by embray

  • Milestone changed from sage-8.9 to sage-9.1

Ticket retargeted after milestone closed

comment:72 Changed 20 months ago by mkoeppe

  • Milestone changed from sage-9.1 to sage-9.2

pushing these forward to 9.2

comment:73 Changed 16 months ago by mkoeppe

Looks like some py3 issues need fixing

comment:74 Changed 14 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:75 Changed 10 months ago by mkoeppe

  • Milestone changed from sage-9.3 to sage-9.4

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

comment:76 Changed 5 months ago by mkoeppe

  • Dependencies #22065, #22066, #22803, #24837 deleted
  • Work issues set to py3

comment:77 Changed 5 months ago by git

  • Commit changed from 05108969d429ca7c6299f7b6d999f12e807ab224 to 066ba21fe05d8b3ebd36cf3f7df12883067e3ac1

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

50dd52bMerge tag '9.3' into t/22067/gf-polyhedron
d1987b9Trac #22067: fix py3 issues related to zip
c1792b7Trac #22067: fix doctests due to changed error message
066ba21Trac #22067: remove old py2/3 compatible code

comment:78 Changed 5 months ago by dkrenn

  • Status changed from needs_work to needs_review
  • Work issues py3 deleted

Actually, looked at this ticket just yesterday; now merged in 9.3, fixed the py3 issues and make it pass the tests again.

comment:79 follow-up: Changed 5 months ago by dkrenn

I've skim read all the comments here; AFAICS, 3 to 4 years ago, the review seems to have completed but it hasn't made the step to a positive review. Anything that I missed?

comment:80 in reply to: ↑ 79 Changed 5 months ago by dkrenn

Replying to dkrenn:

I've skim read all the comments here; AFAICS, 3 to 4 years ago, the review seems to have been completed but it hasn't made the step to a positive review. Anything that I missed?

comment:81 Changed 5 months ago by mkoeppe

I think prefix_variable_name should be replaced by handling name and names arguments, like for example the PolynomialRing constructor does.

comment:82 Changed 5 months ago by mkoeppe

Also, codespell from ./sage -tox -- src/sage/geometry/polyhedron/generating_function.py indicates the correction

sage/geometry/polyhedron/generating_function.py:110: handeled ==> handled, handheld

In the same line where this typo appears, there is another one: polyhedon->polyhedron

comment:83 Changed 5 months ago by git

  • Commit changed from 066ba21fe05d8b3ebd36cf3f7df12883067e3ac1 to 8fcebd1d25ac4e4af7de360692a19d226922417e

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

ab74b6eTrac #22067 comment:81: replace prefix_variable_name by the usual name and names parameters
8fcebd1Trac #22067 comment:82: fix typos in docstring

comment:84 Changed 5 months ago by dkrenn

Thank you for your fast replies. I've addressed both ticket:22067#comment:81 and ticket:22067#comment:82, need review.

comment:85 follow-up: Changed 5 months ago by mkoeppe

There is still a prefix_variable_name in a docstring

comment:86 Changed 5 months ago by git

  • Commit changed from 8fcebd1d25ac4e4af7de360692a19d226922417e to f04075f41cd06ed1a085ee60749285f5a6f3eddc

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

f04075fTrac #22067 comment:85: fix docstring (forgotten prefix_variable_name)

comment:87 in reply to: ↑ 85 ; follow-up: Changed 5 months ago by dkrenn

Replying to mkoeppe:

There is still a prefix_variable_name in a docstring

Indeed, thanks, fixed.

comment:88 follow-ups: Changed 5 months ago by mkoeppe

Also this docstring needs work

+def compositions_mod(u, m, r=0, multidimensional=False):
+    r"""
+    Return an iterable of tuples `a` such that `a u^T \equiv r \mod m`.

It should make clear that the items of a are elements of Zmod(m). Is there are reason why you don't make the results vectors over Zmod(m)?

Also this:

+
+    return _compositions_mod_(u, r)

I think should be using yield from.

comment:89 follow-up: Changed 5 months ago by mkoeppe

+def _compositions_mod_(u, r):
+    r"""
+    Helper function to :func:`compositions_mod`.

should still describe what it does and explain input and output

comment:90 follow-up: Changed 5 months ago by mkoeppe

+        split = iter((ph, ph.Hrepresentation_str(**Hrepresentation_str_options))
+                     for ph in split)

this is a "useless use of iter" -- the generator expression is already iterable. (similarly in several other places in the file)

comment:91 follow-up: Changed 5 months ago by mkoeppe

+    v = u[0]
+    m = max(vv.order() for vv in v)
+    Z = Zmod(m)
+    for j in srange(m):

I don't think max is correct here, shouldn't this be lcm?

comment:92 follow-up: Changed 5 months ago by mkoeppe

Also

+    def _transform_(self):

... I think standard naming for internal functions would be _transform

comment:93 Changed 5 months ago by git

  • Commit changed from f04075f41cd06ed1a085ee60749285f5a6f3eddc to 015883b37bf24f7289959699bce3504969b97f45

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

223517fTrac #22067 comment:89: refactor recursively called code
ad0444aTrac #22067 comment:88(2): use "yield from"
c75e86dTrac #22067 comment:88(1): describe outout of composition_mod more detailed
fbf3b4eTrac #22067 comment:90: remove obsolete iter statements
015883bTrac #22067 comment:91: fix wrong modulus

comment:94 in reply to: ↑ 89 Changed 5 months ago by dkrenn

Replying to mkoeppe:

+def _compositions_mod_(u, r):
+    r"""
+    Helper function to :func:`compositions_mod`.

should still describe what it does and explain input and output

Reading this again, I think, this is not a good style, as _composition_mod_ is basically needed/used as this function calles recursively itself. I've renamed it to recursively_build_compositions and moved it into the main function, so slightly refactored the code.

comment:95 in reply to: ↑ 88 Changed 5 months ago by dkrenn

Replying to mkoeppe:

Also this docstring needs work

+def compositions_mod(u, m, r=0, multidimensional=False):
+    r"""
+    Return an iterable of tuples `a` such that `a u^T \equiv r \mod m`.

It should make clear that the items of a are elements of Zmod(m).

Docstrings extended to state precisely what the items are.

comment:96 in reply to: ↑ 88 Changed 5 months ago by dkrenn

Replying to mkoeppe:

Is there are reason why you don't make the results vectors over Zmod(m)?

Yes. The elements do not have all neccessarily the same modulus; documented this now as well.

comment:97 in reply to: ↑ 88 ; follow-up: Changed 5 months ago by dkrenn

Replying to mkoeppe:

Also this:

+
+    return _compositions_mod_(u, r)

I think should be using yield from.

This does not change anything at all as _compositions_mod_ is already a generator expression (and FWIW no for-loop is used anyways). What is the reason for doing this? A semantic reason maybe? (I've done the change, but it can be reverted easily if there is no reason for using yield from.)

comment:98 in reply to: ↑ 90 Changed 5 months ago by dkrenn

Replying to mkoeppe:

+        split = iter((ph, ph.Hrepresentation_str(**Hrepresentation_str_options))
+                     for ph in split)

this is a "useless use of iter" -- the generator expression is already iterable. (similarly in several other places in the file)

Indeed; removed (all).

comment:99 in reply to: ↑ 91 Changed 5 months ago by dkrenn

Replying to mkoeppe:

+    v = u[0]
+    m = max(vv.order() for vv in v)
+    Z = Zmod(m)
+    for j in srange(m):

I don't think max is correct here, shouldn't this be lcm?

Ouch, yes, correct, it should definitely be lcm. How could I miss this? :) Changed.

comment:100 follow-up: Changed 5 months ago by mkoeppe

it would be good to add a doctest in which lcm is different from max.

comment:101 in reply to: ↑ 92 ; follow-up: Changed 5 months ago by dkrenn

Replying to mkoeppe:

Also

+    def _transform_(self):

... I think standard naming for internal functions would be _transform

I do think both conventions are used

dakrenn@nops:/opt/sage/9.3$ ./sage -grep "def _[a-zA-Z0-9][_a-zA-Z0-9]*[a-zA-Z0-9](" | wc -l
5899
dakrenn@nops:/opt/sage/9.3$ ./sage -grep "def _[a-zA-Z0-9][_a-zA-Z0-9]*[a-zA-Z0-9]_(" | wc -l
5908

Also, _..._ is used in methods like _repr_, therefore I'm in favor of keeping it.

comment:102 in reply to: ↑ 100 ; follow-up: Changed 5 months ago by dkrenn

Replying to mkoeppe:

it would be good to add a doctest in which lcm is different from max.

This is already the case in the existing

        sage: list(compositions_mod([(1, 2), (2, 2), (3, 2)], 6,
        ....:                       multidimensional=True))
        [(0, 0, 0), (1, 1, 1), (2, 2, 2), (3, 0, 3), (4, 1, 4), (5, 2, 5)]

(which changed after switching to lcm)

comment:103 in reply to: ↑ 101 ; follow-up: Changed 5 months ago by mkoeppe

Replying to dkrenn:

_..._ is used in methods like _repr_

Yes, but this specifically mimics the "dunder" method __repr__ to which it is connected.

comment:104 in reply to: ↑ 102 Changed 5 months ago by mkoeppe

Replying to dkrenn:

Replying to mkoeppe:

it would be good to add a doctest in which lcm is different from max.

This is already the case in the existing

        sage: list(compositions_mod([(1, 2), (2, 2), (3, 2)], 6,
        ....:                       multidimensional=True))
        [(0, 0, 0), (1, 1, 1), (2, 2, 2), (3, 0, 3), (4, 1, 4), (5, 2, 5)]

(which changed after switching to lcm)

OK, thanks, I hadn't noticed that

comment:105 in reply to: ↑ 97 ; follow-up: Changed 5 months ago by mkoeppe

Replying to dkrenn:

Replying to mkoeppe:

Also this:

+
+    return _compositions_mod_(u, r)

I think should be using yield from.

This does not change anything at all as _compositions_mod_ is already a generator expression (and FWIW no for-loop is used anyways). What is the reason for doing this? A semantic reason maybe? (I've done the change, but it can be reverted easily if there is no reason for using yield from.)

It makes of course no practical difference in this example. But it is the syntactic presence of yield in the body of a function that changes a function to a generator. Consider:

sage: def test():
....:     if False: yield 1
....: 
sage: test()
<generator object test at 0x105434970>

So it is good practice to use yield from to pass on another generator, instead of just returning the generator object.

comment:106 in reply to: ↑ 103 Changed 5 months ago by dkrenn

Replying to mkoeppe:

Replying to dkrenn:

_..._ is used in methods like _repr_

Yes, but this specifically mimics the "dunder" method __repr__ to which it is connected.

I see, thank you for this explanation. Anyways, the function discussed was renamed and refactored.

comment:107 in reply to: ↑ 105 Changed 5 months ago by dkrenn

Replying to mkoeppe:

But it is the syntactic presence of yield in the body of a function that changes a function to a generator. Consider:

sage: def test():
....:     if False: yield 1
....: 
sage: test()
<generator object test at 0x105434970>

So it is good practice to use yield from to pass on another generator, instead of just returning the generator object.

Ok, thank you. Yes, we then should keep the yields from.

comment:108 follow-up: Changed 5 months ago by mkoeppe

+    if split is True:
+        split = (
+            (Polyhedron(
+                ieqs=[tuple(1 if i==b else (-1 if i==a or i==0 and a > b else 0)
+                            for i in range(d+1))
+                      for a, b in zip(pi[:-1], pi[1:])]),
+             'b{}'.format(pi[0]-1) +
+             ''.join((' <= ' if a < b else ' < ') +
+                     'b{}'.format(b-1)
+                     for a, b in zip(pi[:-1], pi[1:])))
+            for pi in Permutations(d))
+

This part looks a bit magical, could you illustrate this with doctests somewhere?

comment:109 follow-up: Changed 5 months ago by mkoeppe

Also, the docstring of compositions_mod should probably use the word "all" somewhere. Are these ALL solutions to this modular equation? Is every solution returned exactly once? etc.

Also the examples should be revised because in the output the crucial choice of the modulus for each of the components is not visible.

Overall, I think I would be happier if this whole thing could be redone in the language of point lattices (sage.modules.free_module_integer) and their cosets --- but I have not looked at how you use the result.

comment:110 Changed 5 months ago by git

  • Commit changed from 015883b37bf24f7289959699bce3504969b97f45 to 1636422c6a770b8d204184a1d4737e159d19f24c

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

6dca949Trac #22067 comment:109(2): show moduli in doctests
811d0b9Trac #22067 comment:109(1): say that "all" tuples are returned in compositions_mod
1636422Trac #22067 comment:108: add a doctest to show split polyhedra

comment:111 in reply to: ↑ 109 ; follow-up: Changed 5 months ago by dkrenn

Replying to mkoeppe:

Also, the docstring of compositions_mod should probably use the word "all" somewhere. Are these ALL solutions to this modular equation? Is every solution returned exactly once? etc.

Done.

Also the examples should be revised because in the output the crucial choice of the modulus for each of the components is not visible.

Done.

Overall, I think I would be happier if this whole thing could be redone in the language of point lattices (sage.modules.free_module_integer) and their cosets --- but I have not looked at how you use the result.

The helper function compositions_mod returns the results exactly as needed in the class TransformMod. I suggest to do this "upgrade" of the function on a follow-up ticket.

comment:112 in reply to: ↑ 108 ; follow-up: Changed 5 months ago by dkrenn

Replying to mkoeppe:

This part looks a bit magical, could you illustrate this with doctests somewhere?

Not that easy, but I somehow managed to write a doctest showing some details of this specific part of the code.

comment:113 follow-up: Changed 5 months ago by mkoeppe

typo: "substitited"

comment:114 in reply to: ↑ 111 Changed 5 months ago by mkoeppe

Replying to dkrenn:

Overall, I think I would be happier if this whole thing could be redone in the language of point lattices (sage.modules.free_module_integer) and their cosets --- but I have not looked at how you use the result.

The helper function compositions_mod returns the results exactly as needed in the class TransformMod. I suggest to do this "upgrade" of the function on a follow-up ticket.

Thanks for the changes you made. I agree, this part is sufficiently clear now

comment:115 Changed 5 months ago by git

  • Commit changed from 1636422c6a770b8d204184a1d4737e159d19f24c to d24a4ca39c88265e052a79d743baecbe4fe8088d

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

d24a4caTrac #226067 comment:112: fix typo

comment:116 in reply to: ↑ 113 Changed 5 months ago by dkrenn

Replying to mkoeppe:

typo: "substitited"

Fixed.

comment:117 in reply to: ↑ 112 ; follow-up: Changed 5 months ago by mkoeppe

Replying to dkrenn:

Replying to mkoeppe:

This part looks a bit magical, could you illustrate this with doctests somewhere?

Not that easy, but I somehow managed to write a doctest showing some details of this specific part of the code.

Thanks, this is an improvement. Now I understand that the strings that are assembled in this part of the code are just used for logging.

I think both the description of the "splitting" in the documentation and the implementation can be made more transparent.

Perhaps it should at least be said that if split=True, it uses the complement of the hyperplane_arrangements.braid.

comment:118 Changed 5 months ago by mkoeppe

I was hoping to have something like TransformHrepresentation in more generality (related to #30198), but that's of course outside of the scope of this ticket

comment:119 follow-up: Changed 5 months ago by mkoeppe

Maybe all of the helper classes in this file should be marked as internal somehow (can we use leading underscores for class names too?) so that if this is reworked for more generality, we don't have to go through deprecation.

comment:120 follow-up: Changed 5 months ago by mkoeppe

Likewise for compositions_mod - it shouldn't be a public interface

comment:121 follow-up: Changed 5 months ago by mkoeppe

+                ieqs=[tuple(1 if i==b else (-1 if i==a or i==0 and a > b else 0)
+                            for i in range(d+1))

how about splitting out the 0th position of this tuple here to make this more transparent.

comment:122 follow-up: Changed 5 months ago by mkoeppe

There is a nontrivial algorithm in SplitOffSimpleInequalities._transform_, which probably needs some explanation

comment:123 in reply to: ↑ 87 ; follow-up: Changed 5 months ago by mkoeppe

Replying to dkrenn:

Replying to mkoeppe:

There is still a prefix_variable_name in a docstring

Indeed, thanks, fixed.

Following up on name/names:

+        sage: generating_function_of_integral_points(P2[0],
+        ....:     sort_factors=True, names=('a', 'b'))
+        Traceback (most recent call last):
+        ...
+        ValueError: exactly one variable name has to be provided

I don't understand this restriction. Why would the user not be allowed to provide all the names for the variables?

comment:124 Changed 5 months ago by dkrenn

@mkoeppe, thank you. I brievley looked over your comments and agree that these should be incorporated. I'll be off for some time now (maybe a week) and then continue to work on this.

comment:125 Changed 5 months ago by mkoeppe

  • Status changed from needs_review to needs_work

comment:126 Changed 5 months ago by git

  • Commit changed from d24a4ca39c88265e052a79d743baecbe4fe8088d to a43c6be5761e99bbcd544e7b94cadbad2037ad26

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

cb021aaTrac #22067: update file-header (year, support)
0a40e08Trac #22067 comment:119: make transform-helper classes internal
122d080Trac #22067 comment:120: make compositions_mod internal
b086f94Trac #22067 comment:117 and comment:121: make code for split=True more transparent
e6f9513Trac #22067 comment:117: document ``split`` better
a43c6beTrac #22067 comment:123: NotImplemented error when more than one variable names are provided

comment:127 in reply to: ↑ 117 Changed 5 months ago by dkrenn

Replying to mkoeppe:

Replying to dkrenn:

Replying to mkoeppe:

This part looks a bit magical, could you illustrate this with doctests somewhere?

Not that easy, but I somehow managed to write a doctest showing some details of this specific part of the code.

Thanks, this is an improvement. Now I understand that the strings that are assembled in this part of the code are just used for logging.

I think both the description of the "splitting" in the documentation and the implementation can be made more transparent.

Documentation rewritten and extended.

Perhaps it should at least be said that if split=True, it uses the complement of the hyperplane_arrangements.braid.

Rephrased now anyways. (Not sure if bringing in two more concepts ("braid" and "complement of") would makes things more clear.)

comment:128 in reply to: ↑ 119 Changed 5 months ago by dkrenn

Replying to mkoeppe:

Maybe all of the helper classes in this file should be marked as internal somehow (can we use leading underscores for class names too?) so that if this is reworked for more generality, we don't have to go through deprecation.

Now they are internal (IMO this should have been also without the fear of a deprecation).

comment:129 in reply to: ↑ 120 Changed 5 months ago by dkrenn

Replying to mkoeppe:

Likewise for compositions_mod - it shouldn't be a public interface

Done.

comment:130 in reply to: ↑ 121 Changed 5 months ago by dkrenn

Replying to mkoeppe:

+                ieqs=[tuple(1 if i==b else (-1 if i==a or i==0 and a > b else 0)
+                            for i in range(d+1))

how about splitting out the 0th position of this tuple here to make this more transparent.

Code majorly rewritten with the hope that it is clearer now.

comment:131 in reply to: ↑ 123 Changed 5 months ago by dkrenn

Replying to mkoeppe:

Replying to dkrenn:

Replying to mkoeppe:

There is still a prefix_variable_name in a docstring

Indeed, thanks, fixed.

Following up on name/names:

+        sage: generating_function_of_integral_points(P2[0],
+        ....:     sort_factors=True, names=('a', 'b'))
+        Traceback (most recent call last):
+        ...
+        ValueError: exactly one variable name has to be provided

I don't understand this restriction. Why would the user not be allowed to provide all the names for the variables?

Can be done on a follow up ticket; it raises a NotImplementedError now.

comment:132 in reply to: ↑ 122 Changed 5 months ago by dkrenn

Replying to mkoeppe:

There is a nontrivial algorithm in SplitOffSimpleInequalities._transform_, which probably needs some explanation

This is still open.

comment:133 Changed 4 months ago by mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5
Note: See TracTickets for help on using tickets.