Opened 9 years ago
Last modified 8 years ago
#15280 needs_work enhancement
Extensions of PALP normal form, affine normal form and isomorphisms
Reported by:  Jan Keitel  Owned by:  

Priority:  major  Milestone:  sage6.4 
Component:  geometry  Keywords:  toric 
Cc:  Volker Braun, Andrey Novoseltsev  Merged in:  
Authors:  Jan Keitel  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/jkeitel/normal_form_codimension (Commits, GitHub, GitLab)  Commit:  4e8dace1658e2565a2f391e1528083d0c277235c 
Dependencies:  #13525  Stopgaps: 
Description (last modified by )
Currently computing the normal form of a lattice polytope of nonzero codimension throws an exception since PALP doesn't cover it. However, the PALP algorithm can easily be extended to cover these cases, as suggested for example in Section 3.2 of http://magma.maths.usyd.edu.au/~kasprzyk/research/pdf/normal_form.pdf . The idea is to simply restrict to the sublattice spanned by vertices of the polytope, compute the normal form there and embed it back into the original ambient space.
In addition I've included affine_normal_form and find_isomorphism, which compute the affine normal form of a lattice polytope and isomorphisms between lattice polytopes, respectively.
Change History (30)
comment:1 Changed 9 years ago by
Commit:  → 8d4c11735db3de7833cb4ba7230890afe0dc620c 

comment:2 Changed 9 years ago by
Status:  new → needs_review 

I'm setting this to needs review. By the way, I'm still a bit confused about which branch to base my patches on. Right now I'm using public/sagegit/master  should I go back to simply the master branch on trac?
comment:4 Changed 9 years ago by
Commit:  8d4c11735db3de7833cb4ba7230890afe0dc620c → 4b42b4a909c83f675a0bd2e2e674e0795bef93f3 

comment:5 Changed 9 years ago by
Okay, I just made another patch based on the new master branch. I then pushed it here and used f in order to ignore the previously pushed commits, i.e. I executed git push f setupstream trac HEAD:u/jkeitel/normal_form_codimension
The branch seems to be pushed, that's fine, but there was in error in the trac hooks:
X11 forwarding request failed on channel 0 Counting objects: 16, done. Delta compression using up to 8 threads. Compressing objects: 100% (8/8), done. Writing objects: 100% (8/8), 2.35 KiB, done. Total 8 (delta 6), reused 0 (delta 0) remote: Trac #15280: Commit changed to 4b42b4. remote: Traceback (most recent call last): remote: File "./hooks/postreceive.d/01trac_branch", line 152, in <module> remote: trac.update_commit(number, ticket, branch, oldref, newref) remote: File "./hooks/postreceive.d/01trac_branch", line 139, in update_commit remote: commit += '\n'.join(self.log_table(newref, limit=FORCED_COMMITS)) remote: UnboundLocalError: local variable 'commit' referenced before assignment To ssh://git@trac.sagemath.org:2222/sage.git + 8d4c117...4b42b4a HEAD > u/jkeitel/normal_form_codimension (forced update) Branch normal_form_codimension set up to track remote branch u/jkeitel/normal_form_codimension from trac.
Afterwards I had to set the commit by hand. That's clearly not part of this ticket, but it might still be something to fix.
Cheers, Jan
comment:6 Changed 9 years ago by
You should never merge another branch in unless you absolutely have to. Just because there is a newer master is not a reason. The only valid reasons are 1) there is a conflict with the new master or 2) you need a feature from the new master.
comment:7 Changed 9 years ago by
Commit:  4b42b4a909c83f675a0bd2e2e674e0795bef93f3 → b2372408a86d4f7bd34caad6c7f5451aed2dc242 

Branch pushed to git repo; I updated commit sha1. New commits:
[changeset:b237240]  Fixed normal form of origin. 
[changeset:3f7996e]  Improved isomorphim check. 
[changeset:f64a7ee]  Merge branch 'normal_form_codimension' into maximal_polytopes 
[changeset:bbb1bc7]  Caching for affine normal form. 
[changeset:7bf8ebb]  Merged affine normal transform. 
[changeset:22828ce]  Affine normal form 
[changeset:604ad66]  Treat case with single vertex at origin. 
[changeset:4a62c1d]  Made subpolytopes a bit faster. 
[changeset:e667148]  Subpolytopes for PPL 
comment:8 Changed 9 years ago by
Commit:  b2372408a86d4f7bd34caad6c7f5451aed2dc242 → 10f060281d24af0e79eb7c0be3de40f6ea4b1b3d 

comment:9 Changed 9 years ago by
Sorry for the previous post by git, apparently I'm still struggling  must have done something bad to my local copy. Now everything should be fine. In any case, I've added a 'affine normal form' that is invariant under affine transformations of the polytope.
comment:10 Changed 9 years ago by
Commit:  10f060281d24af0e79eb7c0be3de40f6ea4b1b3d → cbb323290e0f89433abd3467f91c8f0dbfd7fcc4 

Branch pushed to git repo; I updated commit sha1. New commits:
[changeset:cbb3232]  Caching for affine normal form. 
comment:11 Changed 9 years ago by
Dependencies:  → #13525 

Status:  needs_review → needs_work 
I'm putting this to needs_work because #13525 is changing the same methods and one of the two will need to be a dependency of the other.
comment:12 Changed 9 years ago by
Commit:  cbb323290e0f89433abd3467f91c8f0dbfd7fcc4 → 0828630f23bb7a8f285264f4e5a91f89e3ab6a17 

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
[changeset:0828630]  Merge with updates from PALP normal form and clean up. 
[changeset:7b85f7e]  Added more doctests and longer descriptions. 
[changeset:a0ca816]  Inverse and affine transformations for normal forms. 
[changeset:f77942a]  Working on linear transformations for normal form. 
[changeset:9a18837]  Attempt at merging PALP normal form. 
[changeset:6938bac]  Added normal form permutation read out from PALP. 
[changeset:00dcc4a]  Embedding matrix must be over ZZ. 
[changeset:21dc3ec]  Direct call to PALP for affine normal form. 
[changeset:0f328ca]  Removed normal form for Laurent polynomials. 
[changeset:1051207]  Removed auto and isomorphism code for the time being. 
comment:13 followup: 21 Changed 9 years ago by
LatticePolytope? now has methods affine_normal_form and find_isomorphism that allows finding isomorphisms between polytopes that are related to each other by an affine transformation, even if the embedding spaces are different. At the moment I'm using LatticeEuclideanGroupElement?, a class that seemed only to be intended for LatticePolytope_PPL for the affine maps. Is there a better alternative? I need affine maps between different dimensional vector spaces. Also, the maps may be over QQ and while I've written a short hack to extend LatticeEuclideanGroupElement? to do that, that's probably not the best solution.
Suggestions? Volker? :)
comment:14 Changed 9 years ago by
Description:  modified (diff) 

Summary:  Normal form for polytopes of nonzero codimension → Extensions of PALP normal form, affine normal form and isomorphisms 
comment:15 Changed 9 years ago by
Milestone:  sage6.0 → sage6.1 

comment:16 Changed 9 years ago by
Milestone:  sage6.1 → sage6.2 

comment:17 Changed 9 years ago by
Milestone:  sage6.2 → sage6.3 

comment:18 Changed 9 years ago by
Commit:  0828630f23bb7a8f285264f4e5a91f89e3ab6a17 → 61b0d264008bc64948d8aab6509e0cccf4c0f991 

Branch pushed to git repo; I updated commit sha1. New commits:
eefea2d  Merge branch 'develop' into t/13525/PALP_normal_form

6b7b32c  minor fixes

a5428af  Fixes to normal_form_pc to work with point collections properly.

1262262  Use point collections more directly.

fddc0db  First attempt at merging affine normal form with normal form.

d6d03a3  Changing to point collections.

61b0d26  Isomorphisms and cosmetic changes.

comment:19 Changed 9 years ago by
I've done my best to merge in the changes in the lattice polytope class and the new commits from #13525. Doctests still need to be adjusted to point collections, but at least things seem to be working.
comment:20 Changed 9 years ago by
This definitely needs some close attention while rebasing, as I am looking at the first four differences and they are
 Format of the constructor call which is not really used anywhere in Sage, so why should it be here???
return
after anotherreturn
_desc
popping which should not be there since there is no more_desc
 Resurrection of old convoluted code for the number of facets instead of the new oneliner.
comment:22 Changed 9 years ago by
Jan, it would be better also to try to take advantage of the switch rather than just making things work:
vertices = matrix(QQ, self.vertices_pc().column_matrix().transpose())
can be written more naturally as
vertices = matrix(QQ, self.vertices_pc().matrix())
which is shorter and does not require double transposition of a cached matrix. Or perhaps as
vertices = self.vertices_pc().matrix().change_ring(QQ)
Sorry for annoying rebasing, but in the long run it should be nice to have uniform behaviour for polytopes and cones/fans.
comment:23 Changed 9 years ago by
Sorry, the first differences must have crept back in in the merge. Don't know how that happened, but now that #13525 is merged that's easier to see and I'll get rid of them. You're also absolutely right about the code you quote above and I had planned to do so. The code does still need to be cleaned up and there might well be a couple of other places that can be simplified. I'll try to do that in the next commits.
comment:24 Changed 9 years ago by
Commit:  61b0d264008bc64948d8aab6509e0cccf4c0f991 → 4e8dace1658e2565a2f391e1528083d0c277235c 

Branch pushed to git repo; I updated commit sha1. New commits:
4e8dace  Remove merge relicts and first clean up.

comment:25 Changed 9 years ago by
Inspired by Nathan / Volker arguments about filters for cached functions: I didn't quite liked how normal_form
was changed in #13525 to accept parameters that make it return different output types. It used to be straightforward
@cached_method normal_form(self)
and with this ticket it gets more and more complicated, which makes it unclear how (and whether) it should be cached. I also found it annoying that this conditional output propagates down to helper functions.
So how about this:
 Drop arguments to helper functions so that their output is stable and if something has to be done to it, the caller does not have to parse argument to decompose and recompose the output appropriately. Am I right that permutation/transformation don't cost much time to compute in addition to normal form? Certainly permutations are trivial when read from the PALP output.
 Perhaps only the defaultalgorithm normal form has to be cached: with all the associated data, but only once and during each call
normal_form
will drop unnecessary pieces?
Another option is to make normal_form
always return everything, but given the name I think normal_form()
should return just the normal form and nothing else or it gets confusing. Besides, while I agree that it is nice to have extra data, I used normal form a lot by itself, so it is useful on its own.
comment:26 Changed 9 years ago by
Yes, I actually wondered about the same thing when I read that discussion. I'd say I'll just make a few timings in order to see whether there's a significant advantage to not calculating the permutation / transformation. Surely, always calculating the permutation shouldn't hurt, so we can probably drop the permutation
flag from the helper functions.
After that, we can still check whether there should be a separate function for computing the transformation that sends something to normal form and one that only outputs the normal form.
comment:27 Changed 9 years ago by
If the transformation is computed in the same way no matter what algorithm has been used, then probably it can be computed directly in normal_form
if necessary.
On the bright side, since these details do not affect user interface, there is no worry about deprecations and waiting.
comment:28 Changed 9 years ago by
Here are some timings, showing that the effect of computing the permutations can in fact be largely neglected:
sage: o = lattice_polytope.cross_polytope(2) sage: %timeit o._palp_native_normal_form(permutation=False) 10 loops, best of 3: 43.8 ms per loop sage: %timeit o._palp_native_normal_form(permutation=True) 10 loops, best of 3: 43.9 ms per loop sage: %timeit o._palp_modified_normal_form(permutation=False) 10 loops, best of 3: 36 ms per loop sage: %timeit o._palp_modified_normal_form(permutation=True) 10 loops, best of 3: 36.1 ms per loop sage: %timeit o._normal_form_full_dimensional(permutation=False) 10 loops, best of 3: 8.91 ms per loop sage: %timeit o._normal_form_full_dimensional(permutation=True) 10 loops, best of 3: 9.12 ms per loop
However, the same tests show (again) that our python implementations from #13525 are really, really slow:
sage: o = lattice_polytope.cross_polytope(4) sage: %timeit o._palp_native_normal_form(permutation=False) 1 loops, best of 3: 33.7 s per loop sage: %timeit o._palp_native_normal_form(permutation=True) 1 loops, best of 3: 33.6 s per loop sage: %timeit o._palp_modified_normal_form(permutation=False) 1 loops, best of 3: 1.4 s per loop sage: %timeit o._palp_modified_normal_form(permutation=True) 1 loops, best of 3: 1.38 s per loop sage: %timeit o._normal_form_full_dimensional(permutation=False) 10 loops, best of 3: 11.2 ms per loop sage: %timeit o._normal_form_full_dimensional(permutation=True) 10 loops, best of 3: 11.5 ms per loop
The following isn't really relevant for this ticket, but the reason that they are so slow are the calls to GAP:
%prun o._palp_native_normal_form(permutation=True) 38627975 function calls (38584943 primitive calls) in 39.390 seconds Ordered by: internal time ncalls tottime percall cumtime percall filename:lineno(function) 428940 9.260 0.000 23.171 0.000 pexpect.py:918(expect_list) 19600688 4.943 0.000 4.943 0.000 {method 'search' of '_sre.SRE_Pattern' objects} 98854 3.581 0.000 3.655 0.000 {method 'with_permuted_rows_and_columns' of 'sage.matrix.matrix0.Matrix' objects} 796103 2.139 0.000 2.139 0.000 {select.select} 796103 2.135 0.000 8.395 0.000 pexpect.py:502(read_nonblocking) 796103 1.921 0.000 1.921 0.000 {posix.read} 171376 1.513 0.000 1.513 0.000 {posix.write} 1 1.383 1.383 39.131 39.131 lattice_polytope.py:3109(_palp_PM_max) 85688 1.050 0.000 26.405 0.000 gap.py:576(_execute_line) 22916 1.049 0.000 18.948 0.001 lattice_polytope.py:3169(PGE) 796103 0.919 0.000 1.819 0.000 pexpect.py:743(isalive) 1592206 0.900 0.000 0.900 0.000 {posix.waitpid} 19818 0.833 0.000 14.553 0.001 permgroup.py:594(__call__) 42815 0.476 0.000 11.385 0.000 expect.py:1154(eval) 85688 0.428 0.000 26.977 0.000 gap.py:664(_eval_line) 42942 0.382 0.000 1.034 0.000 permutation.py:5608(from_cycles) 99725 0.346 0.000 0.472 0.000 free_module.py:899(__call__) 46719 0.317 0.000 0.412 0.000 permutation.py:542(__init__) 639678 0.286 0.000 0.286 0.000 {isinstance} 838918 0.270 0.000 0.270 0.000 {method 'find' of 'str' objects} 615296 0.267 0.000 0.267 0.000 {method 'index' of 'list' objects} 42815 0.247 0.000 11.715 0.000 gap.py:510(eval) 85884/42942 0.222 0.000 0.441 0.000 {repr} 2328491 0.221 0.000 0.221 0.000 {method 'start' of '_sre.SRE_Match' objects} 171376 0.205 0.000 1.894 0.000 pexpect.py:660(send) 128426 0.202 0.000 0.222 0.000 expect.py:1310(_check_valid) 22917 0.194 0.000 0.429 0.000 permgroup_named.py:158(__classcall__) 171376 0.177 0.000 0.177 0.000 {time.sleep} 42815 0.160 0.000 12.065 0.000 interface.py:675(__contains__) 42873 0.151 0.000 16.769 0.000 expect.py:1276(__init__) 978573 0.150 0.000 0.196 0.000 {len} 42815 0.148 0.000 0.148 0.000 interface.py:508(__getattr__) 99709 0.144 0.000 0.144 0.000 free_module.py:330(create_key) 839045 0.131 0.000 0.131 0.000 {method 'lower' of 'str' objects} 405591 0.123 0.000 0.157 0.000 combinat.py:1086(__getitem__) 42873 0.120 0.000 16.926 0.000 interface.py:162(__call__) 46719 0.116 0.000 0.116 0.000 permutation.py:4476(__classcall_private__) 42865 0.113 0.000 0.228 0.000 expect.py:1326(__del__) 85688 0.111 0.000 2.005 0.000 pexpect.py:672(sendline) 207596 0.100 0.000 0.100 0.000 {range} 42942 0.096 0.000 0.314 0.000 permutation.py:675(_repr_) 42873 0.094 0.000 16.473 0.000 gap.py:1294(set) 46719 0.085 0.000 0.498 0.000 sets_cat.py:310(_element_constructor_from_element_class) 857880 0.085 0.000 0.085 0.000 {method 'end' of '_sre.SRE_Match' objects} 42942 0.074 0.000 0.118 0.000 global_options.py:664(__getitem__) 42815 0.072 0.000 11.788 0.000 gap.py:797(_contains) 602437 0.068 0.000 0.068 0.000 {method 'append' of 'list' objects} 42873 0.062 0.000 16.600 0.000 interface.py:387(_create) ...
Maybe that could be improved at some point. In any case, I'll now remove the permutation flag.
comment:29 Changed 9 years ago by
Thanks for looking into this! Of course, the diamond is very simple and it may be different for other polytopes, but then again you usually want to do something beyond normal form computation and that something is likely to take much more time. Any timings or ideas for computing actual transformations? My guess is that it is faster that normal form itself, but slower than keeping track of permutations. But with 10% difference or so I am for simpler readable code.
comment:30 Changed 8 years ago by
Milestone:  sage6.3 → sage6.4 

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