Opened 6 years ago
Last modified 3 months ago
#22067 needs_work enhancement
generating function of integral points of polyhedra
Reported by:  Daniel Krenn  Owned by:  

Priority:  major  Milestone:  sage9.8 
Component:  geometry  Keywords:  
Cc:  Clemens Heuberger, JeanPhilippe Labbé, ghbraunmath, Samuel Lelièvre  Merged in:  
Authors:  Daniel Krenn  Reviewers:  Matthias Koeppe 
Report Upstream:  N/A  Work issues:  
Branch:  u/dkrenn/gfpolyhedron (Commits, GitHub, GitLab)  Commit:  a43c6be5761e99bbcd544e7b94cadbad2037ad26 
Dependencies:  Stopgaps: 
Description (last modified by )
Implement this using MacMahon's Omega operator (#22066).
Change History (136)
comment:1 Changed 6 years ago by
Branch:  → u/dkrenn/gfpolyhedron 

comment:2 Changed 6 years ago by
Authors:  → Daniel Krenn 

Commit:  → 5d4910210e8c7c75d44c8aaa34c03f1d28b62909 
Component:  PLEASE CHANGE → geometry 
Description:  modified (diff) 
comment:3 Changed 6 years ago by
Commit:  5d4910210e8c7c75d44c8aaa34c03f1d28b62909 → 32c6eeb9432da70febc8fe7d073f86023f7a1811 

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

79fe3b3  extend docstring at top of file

f1ec72e  Merge branch 'u/dkrenn/omega' of git://trac.sagemath.org/sage into t/22067/gfpolyhedron

ddbf737  repr_pretty and _latex_ of Hrepresentation

54fc5b8  repr_pretty_Hrepresentation for polyhedra

968a998  Merge branch 'u/dkrenn/inequalitypretty' of git://trac.sagemath.org/sage into t/22067/gfpolyhedron

1e327c5  add generating_function module to index

662195b  module description

4a98951  fix imports in doctests

32c6eeb  fix omega imports

comment:4 Changed 6 years ago by
Cc:  Clemens Heuberger added 

comment:5 Changed 6 years ago by
Commit:  32c6eeb9432da70febc8fe7d073f86023f7a1811 → 7fcfe5ef1b679400b66fb6778473d692e20193e3 

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
9ca1aeb  move repr_pretty code outside class, so that it can be used elsewhere as well

73649f9  Merge branch 'u/dkrenn/inequalitypretty' into t/22067/gfpolyhedron

6f59894  use repr_pretty (and remove old pretty_inequality)

ae030fa  more logging cleanup

a2334a3  make helper functions private

c4d01ec  make helper function private (part 2)

86f40ca  write missing docstrings/comments

24abfd4  todocleanup

76801db  fix a doctest

7fcfe5e  fix code typo

comment:6 Changed 6 years ago by
Commit:  7fcfe5ef1b679400b66fb6778473d692e20193e3 → adf4dad4769aa2bc6f090b56c6a22e8279233523 

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

comment:7 Changed 6 years ago by
Commit:  adf4dad4769aa2bc6f090b56c6a22e8279233523 → 999140f0b18a0b8d9fc9695316d0a16f6fde6dfa 

comment:8 Changed 6 years ago by
Status:  new → needs_review 

comment:9 Changed 6 years ago by
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 6 years ago by
Commit:  999140f0b18a0b8d9fc9695316d0a16f6fde6dfa → f85e038c380e0686d06f2fe413ac22dbc95622e7 

Branch pushed to git repo; I updated commit sha1. New commits:
f85e038  add doctest to _generate_mod_

comment:11 Changed 6 years ago by
Commit:  f85e038c380e0686d06f2fe413ac22dbc95622e7 → fce0c71d9bf117c3bfe549be7381a6008f2a8c9b 

Branch pushed to git repo; I updated commit sha1. New commits:
f7e9540  fix doctest (conversion to symbolic)

82327c8  Merge branch 'u/dakrenn/laurentsubs' into t/22066/omega

16e515e  Merge branch 't/22066/omega' into t/22067/gfpolyhedron

0049218  remove periods at end of nonsentence in INPUTblock

91cab4a  Python3 print syntax

fce0c71  Merge branch 'u/dkrenn/inequalitypretty' into t/22067/gfpolyhedron

comment:13 followup: 17 Changed 6 years ago by
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 followup: 15 Changed 6 years ago by
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 multivariategeneratingfunction
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 followup: 18 Changed 6 years ago by
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 2^{dim} orthants and applying symmetries)).
comment:16 Changed 6 years ago by
Commit:  fce0c71d9bf117c3bfe549be7381a6008f2a8c9b → 5d4018af485d1fdda08e9fb872a9a8a17579118f 

Branch pushed to git repo; I updated commit sha1. New commits:
5c22d7f  rename methods (to make it more precise)

68e3fc7  check if polyhedron is in nonnegative orthant

d001a8e  doctests for polyhedra with negative coordinates

4ee76c4  fix existing doctests

7a96155  document nonnegativeorthantchanges

0afac56  minor rewrite (integer points > integral points)

871aea4  write down formula to make resulting GF precise

aa208ea  minor rewrite in SEEALSO blocks

594d9e5  example integer partitions

5d4018a  fix docs (ReST syntax)

comment:17 Changed 6 years ago by
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 likenon_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 >= 1versus
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 Changed 6 years ago by
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 2^{dim} 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.)
comment:19 Changed 6 years ago by
Summary:  generating function of integervalued polyhedra → generating function of integral points of polyhedra 

comment:20 Changed 6 years ago by
Commit:  5d4018af485d1fdda08e9fb872a9a8a17579118f → fe77eec64d6d7ac53decb703977a1464c5d09bfa 

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 quickfix in normalize

397301a  doctest example of ticket 21999

fceb3e1  Merge branch 't/21999/laurentfloorhash' into t/22066/omega

fe77eec  Merge branch 't/22066/omega' into t/22067/gfpolyhedron

comment:21 followup: 23 Changed 6 years ago by
Status:  needs_review → 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 6 years ago by
Commit:  fe77eec64d6d7ac53decb703977a1464c5d09bfa → 35cf3a2c59178cb55df897b9eaf3d4a6d7beafe1 

Branch pushed to git repo; I updated commit sha1. New commits:
35cf3a2  fix 1dimensial case (creation of univariate laurent polynomial ring)

comment:23 Changed 6 years ago by
Status:  needs_work → 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 followup: 29 Changed 6 years ago by
I think the name of the variables used in the generating function should be a user option
comment:25 followup: 30 Changed 6 years ago by
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 followups: 31 32 33 Changed 6 years ago by
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 6 years ago by
Reviewers:  → Matthias Koeppe 

Status:  needs_review → needs_work 
comment:28 Changed 6 years ago by
Commit:  35cf3a2c59178cb55df897b9eaf3d4a6d7beafe1 → 401c4988cf876724d7d3d6079c11f35c37c06fa6 

Branch pushed to git repo; I updated commit sha1. New commits:
98d46b6  new option: specify the prefix of the output variables

fb2f8f6  test and document prefix_variable_name

7bbae4b  extend documentation of parameter result_as_tuple

3d9bb3f  extend documentation of parameter sort_factors

401c498  check base ring of the polyhedron (if it is ZZ or QQ)

comment:29 Changed 6 years ago by
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 Changed 6 years ago by
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)^1I had hoped for an error
Now the base ring of the polyhedron is inspected.
comment:31 followup: 35 Changed 6 years ago by
Replying to mkoeppe:
Various algorithms options such as
result_as_tuple
are not sufficiently documented.
Docs extended.
comment:32 Changed 6 years ago by
Replying to mkoeppe:
Also I think the method
generating_function_of_integral_points
should have analgorithm
keyword. For polytopes, could provide a naive algorithm that just collects the monomials corresponding tointegral_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 followup enhancement ticket #22111.
comment:33 Changed 6 years ago by
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 6 years ago by
Status:  needs_work → needs_review 

comment:35 followup: 36 Changed 6 years ago by
comment:36 Changed 6 years ago by
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 6 years ago by
Cc:  JeanPhilippe Labbé added 

comment:38 Changed 6 years ago by
Commit:  401c4988cf876724d7d3d6079c11f35c37c06fa6 → 22bd0c4c8e5cb0a2829867e9c069561872b39879 

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
b8314a3  Trac #22066: Format Mac1915

2ce3ab1  Trac #22066: minor rewording

4b1bb1d  Merge remotetracking branch 'trac/u/cheuberg/omega7.5.rc1' into t/22066/omega7.5.rc1

fded046  Merge branch 'u/dkrenn/laurentuniconvert' 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/laurentefficientconstruction

f1e2fcd  Merge branch 'u/dkrenn/laurentefficientconstruction' of git://trac.sagemath.org/sage into t/22066/omega7.5.rc1

22bd0c4  Merge branch 'u/dkrenn/omega7.5.rc1' of git://trac.sagemath.org/sage into t/22067/gfpolyhedron

comment:39 followup: 40 Changed 6 years ago by
Commit:  22bd0c4c8e5cb0a2829867e9c069561872b39879 → 35507829141ae344a84be1ce67d557c99087db0a 

comment:40 Changed 6 years ago by
comment:41 Changed 6 years ago by
Commit:  35507829141ae344a84be1ce67d557c99087db0a → 4d2ccb6f12eb183daebe9c4e046ecb0be7ac6f74 

Branch pushed to git repo; I updated commit sha1. New commits:
4d2ccb6  unify INPUT/OUTPUT blocks

comment:43 Changed 6 years ago by
Milestone:  sage7.5 → sage7.6 

Status:  needs_review → needs_work 
comment:44 Changed 6 years ago by
Commit:  4d2ccb6f12eb183daebe9c4e046ecb0be7ac6f74 → 3a3aec5122c35e5fc9291b69895f6e185a54cc41 

Branch pushed to git repo; I updated commit sha1. New commits:
cf22ee8  Merge branch 'u/dkrenn/laurentefficientconstruction' of git://trac.sagemath.org/sage into public/polynomials/multivariable_laurent_poly_constructor21976

c58559d  Some reviewer changes.

1b7377c  Merge branch 'develop' into public/polynomials/laurent_mpoly_constructor21976

3a3aec5  Merge branch 'public/polynomials/laurent_mpoly_constructor21976' of git://trac.sagemath.org/sage into t/22067/gfpolyhedron

comment:45 Changed 6 years ago by
Status:  needs_work → 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 6 years ago by
Commit:  3a3aec5122c35e5fc9291b69895f6e185a54cc41 → b09d1622689b7c7c35a3413698f222177e9e6876 

Branch pushed to git repo; I updated commit sha1. New commits:
b09d162  Trac #22067: minor modification of logging output

comment:47 Changed 6 years ago by
Commit:  b09d1622689b7c7c35a3413698f222177e9e6876 → 423096c71bac2a2aa4c75311baca4c0a4c929bf9 

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
24a861f  rename _generate_mods_ to generate_mods

7bb6fef  adapt to previous code movement

fd117ff  factor out callingOmegacode

f137fba  small cleanup

aaf0fa0  restrict splitting off inequality to constants <= 0

802c523  use _simplify_ to cancel terms

2d94245  update doctests

b4082d2  function _simplify_ for cancelling factors in intermediate result (quotient)

b02b7f1  use and test new feature in _Omega_function

423096c  Merge branch 'u/dakrenn/omegasimplify' into t/22067/gfpolyhedron

comment:48 Changed 6 years ago by
Dependencies:  #22065, #22066 → #22065, #22066, #22803 

Status:  needs_review → 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 6 years ago by
Commit:  423096c71bac2a2aa4c75311baca4c0a4c929bf9 → 3cfd809279a92f1259e01381125afa0e8965e97d 

comment:50 Changed 6 years ago by
Status:  needs_work → needs_review 

comment:52 followup: 54 Changed 6 years ago by
Status:  needs_review → needs_work 

ping ? just 2 imports need to be changed..
comment:53 Changed 6 years ago by
Commit:  3cfd809279a92f1259e01381125afa0e8965e97d → c91baa5d0ba1d7febd8cd5afe9c92b724c52efc2 

Branch pushed to git repo; I updated commit sha1. New commits:
c91baa5  Trac #22067: correct import of lcm

comment:54 Changed 6 years ago by
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 6 years ago by
Status:  needs_work → needs_review 

comment:56 followup: 60 Changed 6 years ago by
Trivial remark: some "laurent" are missing their capitals.
comment:57 followup: 61 Changed 5 years ago by
Status:  needs_review → needs_work 

and one failing doctest
comment:58 Changed 4 years ago by
Commit:  c91baa5d0ba1d7febd8cd5afe9c92b724c52efc2 → 1b922e779cf2e4e32a0257ed39f63fdcc5c09bdb 

comment:59 Changed 4 years ago by
Commit:  1b922e779cf2e4e32a0257ed39f63fdcc5c09bdb → 0f2d193c0a27c2073c9f149c47a9422c680ded66 

Branch pushed to git repo; I updated commit sha1. New commits:
0f2d193  doc: laurent > Laurent

comment:60 Changed 4 years ago by
comment:62 Changed 4 years ago by
Dependencies:  #22065, #22066, #22803 → #22065, #22066, #22803, #24837 

Status:  needs_work → needs_review 
comment:63 Changed 4 years ago by
you can just remove the dependencies (empty this field), once closed
comment:64 Changed 4 years ago by
Commit:  0f2d193c0a27c2073c9f149c47a9422c680ded66 → 372da68378a9fce88ff20f1308bd243bad28c396 

Branch pushed to git repo; I updated commit sha1. New commits:
372da68  cleanup pyflakes warnings

comment:65 Changed 4 years ago by
Commit:  372da68378a9fce88ff20f1308bd243bad28c396 → 1583e91e3f207b0ce47369cd00083c963889dba7 

Branch pushed to git repo; I updated commit sha1. New commits:
1583e91  fixup: forgotten ** left of kwds

comment:66 Changed 4 years ago by
Commit:  1583e91e3f207b0ce47369cd00083c963889dba7 → 05108969d429ca7c6299f7b6d999f12e807ab224 

Branch pushed to git repo; I updated commit sha1. New commits:
0510896  uniquify sorting in SplitOffSimpleInequalities

comment:67 Changed 4 years ago by
Cc:  ghbraunmath added 

comment:68 Changed 4 years ago by
Cc:  Samuel Lelièvre added 

Description:  modified (diff) 
Milestone:  sage7.6 → sage8.8 
comment:69 Changed 3 years ago by
Milestone:  sage8.8 → sage8.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:71 Changed 3 years ago by
Milestone:  sage8.9 → sage9.1 

Ticket retargeted after milestone closed
comment:74 Changed 2 years ago by
Milestone:  sage9.2 → sage9.3 

comment:75 Changed 22 months ago by
Milestone:  sage9.3 → sage9.4 

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.
comment:76 Changed 17 months ago by
Dependencies:  #22065, #22066, #22803, #24837 

Work issues:  → py3 
comment:77 Changed 17 months ago by
Commit:  05108969d429ca7c6299f7b6d999f12e807ab224 → 066ba21fe05d8b3ebd36cf3f7df12883067e3ac1 

comment:78 Changed 17 months ago by
Status:  needs_work → needs_review 

Work issues:  py3 
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 followup: 80 Changed 17 months ago by
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 Changed 17 months ago by
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 17 months ago by
I think prefix_variable_name
should be replaced by handling name
and names
arguments, like for example the PolynomialRing
constructor does.
comment:82 Changed 17 months ago by
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 17 months ago by
Commit:  066ba21fe05d8b3ebd36cf3f7df12883067e3ac1 → 8fcebd1d25ac4e4af7de360692a19d226922417e 

comment:84 Changed 17 months ago by
Thank you for your fast replies. I've addressed both ticket:22067#comment:81 and ticket:22067#comment:82, need review.
comment:85 followup: 87 Changed 17 months ago by
There is still a prefix_variable_name
in a docstring
comment:86 Changed 17 months ago by
Commit:  8fcebd1d25ac4e4af7de360692a19d226922417e → f04075f41cd06ed1a085ee60749285f5a6f3eddc 

Branch pushed to git repo; I updated commit sha1. New commits:
f04075f  Trac #22067 comment:85: fix docstring (forgotten prefix_variable_name)

comment:87 followup: 123 Changed 17 months ago by
comment:88 followups: 95 96 97 Changed 17 months ago by
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 followup: 94 Changed 17 months ago by
+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 followup: 98 Changed 17 months ago by
+ 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 followup: 99 Changed 17 months ago by
+ 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 followup: 101 Changed 17 months ago by
Also
+ def _transform_(self):
... I think standard naming for internal functions would be _transform
comment:93 Changed 17 months ago by
Commit:  f04075f41cd06ed1a085ee60749285f5a6f3eddc → 015883b37bf24f7289959699bce3504969b97f45 

Branch pushed to git repo; I updated commit sha1. New commits:
223517f  Trac #22067 comment:89: refactor recursively called code

ad0444a  Trac #22067 comment:88(2): use "yield from"

c75e86d  Trac #22067 comment:88(1): describe outout of composition_mod more detailed

fbf3b4e  Trac #22067 comment:90: remove obsolete iter statements

015883b  Trac #22067 comment:91: fix wrong modulus

comment:94 Changed 17 months ago by
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 Changed 17 months ago by
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 ofZmod(m)
.
Docstrings extended to state precisely what the items are.
comment:96 Changed 17 months ago by
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 followup: 105 Changed 17 months ago by
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 forloop 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 Changed 17 months ago by
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 Changed 17 months ago by
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 followup: 102 Changed 17 months ago by
it would be good to add a doctest in which lcm is different from max.
comment:101 followup: 103 Changed 17 months ago by
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 _[azAZ09][_azAZ09]*[azAZ09]("  wc l 5899 dakrenn@nops:/opt/sage/9.3$ ./sage grep "def _[azAZ09][_azAZ09]*[azAZ09]_("  wc l 5908
Also, _..._
is used in methods like _repr_
, therefore I'm in favor of keeping it.
comment:102 followup: 104 Changed 17 months ago by
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 followup: 106 Changed 17 months ago by
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 Changed 17 months ago by
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 followup: 107 Changed 17 months ago by
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 forloop 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 usingyield 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 Changed 17 months ago by
comment:107 Changed 17 months ago by
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 followup: 112 Changed 17 months ago by
+ 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(b1) + 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 followup: 111 Changed 17 months ago by
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 17 months ago by
Commit:  015883b37bf24f7289959699bce3504969b97f45 → 1636422c6a770b8d204184a1d4737e159d19f24c 

comment:111 followup: 114 Changed 17 months ago by
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 followup ticket.
comment:112 followup: 117 Changed 17 months ago by
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:114 Changed 17 months ago by
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 classTransformMod
. I suggest to do this "upgrade" of the function on a followup ticket.
Thanks for the changes you made. I agree, this part is sufficiently clear now
comment:115 Changed 17 months ago by
Commit:  1636422c6a770b8d204184a1d4737e159d19f24c → d24a4ca39c88265e052a79d743baecbe4fe8088d 

Branch pushed to git repo; I updated commit sha1. New commits:
d24a4ca  Trac #226067 comment:112: fix typo

comment:117 followup: 127 Changed 17 months ago by
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 17 months ago by
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 followup: 128 Changed 17 months ago by
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 followup: 129 Changed 17 months ago by
Likewise for compositions_mod
 it shouldn't be a public interface
comment:121 followup: 130 Changed 17 months ago by
+ 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 followup: 132 Changed 17 months ago by
There is a nontrivial algorithm in SplitOffSimpleInequalities._transform_
, which probably needs some explanation
comment:123 followup: 131 Changed 17 months ago by
Replying to dkrenn:
Replying to mkoeppe:
There is still a
prefix_variable_name
in a docstringIndeed, 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 17 months ago by
@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 17 months ago by
Status:  needs_review → needs_work 

comment:126 Changed 16 months ago by
Commit:  d24a4ca39c88265e052a79d743baecbe4fe8088d → a43c6be5761e99bbcd544e7b94cadbad2037ad26 

Branch pushed to git repo; I updated commit sha1. New commits:
cb021aa  Trac #22067: update fileheader (year, support)

0a40e08  Trac #22067 comment:119: make transformhelper classes internal

122d080  Trac #22067 comment:120: make compositions_mod internal

b086f94  Trac #22067 comment:117 and comment:121: make code for split=True more transparent

e6f9513  Trac #22067 comment:117: document ``split`` better

a43c6be  Trac #22067 comment:123: NotImplemented error when more than one variable names are provided

comment:127 Changed 16 months ago by
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 thehyperplane_arrangements.braid
.
Rephrased now anyways. (Not sure if bringing in two more concepts ("braid" and "complement of") would makes things more clear.)
comment:128 Changed 16 months ago by
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 Changed 16 months ago by
comment:130 Changed 16 months ago by
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 Changed 16 months ago by
Replying to mkoeppe:
Replying to dkrenn:
Replying to mkoeppe:
There is still a
prefix_variable_name
in a docstringIndeed, 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 providedI 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 Changed 16 months ago by
Replying to mkoeppe:
There is a nontrivial algorithm in
SplitOffSimpleInequalities._transform_
, which probably needs some explanation
This is still open.
comment:133 Changed 16 months ago by
Milestone:  sage9.4 → sage9.5 

comment:134 Changed 12 months ago by
Milestone:  sage9.5 → sage9.6 

comment:135 Changed 8 months ago by
Milestone:  sage9.6 → sage9.7 

comment:136 Changed 3 months ago by
Milestone:  sage9.7 → sage9.8 

Last 10 new commits:
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/laurentefficientconstruction' of trac.sagemath.org:sage into u/dakrenn/omega
quickfix in normalize
Merge branch 'u/dkrenn/laurentfloorhash' of trac.sagemath.org:sage into u/dakrenn/omega
use __call__ in subs to be more efficient
Merge branch 'u/dkrenn/laurentsubs' of trac.sagemath.org:sage into u/dakrenn/omega
Merge branch 'u/dakrenn/omega' into u/dakrenn/gfpolyhedron