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: sage-6.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:

Status badges

Description (last modified by Jan Keitel)

Currently computing the normal form of a lattice polytope of non-zero 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 . 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 git

Commit: 8d4c11735db3de7833cb4ba7230890afe0dc620c

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

[changeset:8d4c117]Small change for affine case.
[changeset:d890cb6]Normal form for lattice polytopes of non-zero codimension.
[changeset:07152d8]Merge important bugfix for dev scripts
[changeset:8237337]Merging Sage-5.12.rc0 and sage-git fixes
[changeset:1ccb8e5]Ignoring selection of temporary files taken from
[changeset:383c35a]Makefile target to download upstream sources.
[changeset:3b15578]Merging Sage-5.12.beta5, newest dev scripts, and the doctest fixes.
[changeset:1456c52]Merge branch 'ticket/14482' into public/sage-git/master
[changeset:b890215]Merge branch 'ticket/14482' into public/sage-git/master
[changeset:d8713eb]Merge remote-tracking branch 'origin/build_system' into public/sage-git/master

comment:2 Changed 9 years ago by Jan Keitel

Status: newneeds_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/sage-git/master - should I go back to simply the master branch on trac?

comment:3 Changed 9 years ago by Volker Braun

You should use just master for any new branches.

comment:4 Changed 9 years ago by Jan Keitel

Commit: 8d4c11735db3de7833cb4ba7230890afe0dc620c4b42b4a909c83f675a0bd2e2e674e0795bef93f3

comment:5 Changed 9 years ago by Jan Keitel

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 --set-upstream 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/post-receive.d/01-trac_branch", line 152, in <module> 
remote:     trac.update_commit(number, ticket, branch, oldref, newref)
remote:   File "./hooks/post-receive.d/01-trac_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://

  + 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 Volker Braun

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 git

Commit: 4b42b4a909c83f675a0bd2e2e674e0795bef93f3b2372408a86d4f7bd34caad6c7f5451aed2dc242

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 Jan Keitel

Commit: b2372408a86d4f7bd34caad6c7f5451aed2dc24210f060281d24af0e79eb7c0be3de40f6ea4b1b3d

comment:9 Changed 9 years ago by Jan Keitel

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 git

Commit: 10f060281d24af0e79eb7c0be3de40f6ea4b1b3dcbb323290e0f89433abd3467f91c8f0dbfd7fcc4

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 Jan Keitel

Dependencies: #13525
Status: needs_reviewneeds_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 git

Commit: cbb323290e0f89433abd3467f91c8f0dbfd7fcc40828630f23bb7a8f285264f4e5a91f89e3ab6a17

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 Changed 9 years ago by Jan Keitel

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 Jan Keitel

Description: modified (diff)
Summary: Normal form for polytopes of non-zero codimensionExtensions of PALP normal form, affine normal form and isomorphisms

comment:15 Changed 9 years ago by For batch modifications

Milestone: sage-6.0sage-6.1

comment:16 Changed 9 years ago by For batch modifications

Milestone: sage-6.1sage-6.2

comment:17 Changed 9 years ago by For batch modifications

Milestone: sage-6.2sage-6.3

comment:18 Changed 9 years ago by git

Commit: 0828630f23bb7a8f285264f4e5a91f89e3ab6a1761b0d264008bc64948d8aab6509e0cccf4c0f991

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

eefea2dMerge branch 'develop' into t/13525/PALP_normal_form
6b7b32cminor fixes
a5428afFixes to normal_form_pc to work with point collections properly.
1262262Use point collections more directly.
fddc0dbFirst attempt at merging affine normal form with normal form.
d6d03a3Changing to point collections.
61b0d26Isomorphisms and cosmetic changes.

comment:19 Changed 9 years ago by Jan Keitel

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 Andrey Novoseltsev

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 another return
  • _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 one-liner.

comment:21 in reply to:  13 Changed 9 years ago by Andrey Novoseltsev

Volker, any thoughts on 13?

comment:22 Changed 9 years ago by Andrey Novoseltsev

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 Jan Keitel

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 git

Commit: 61b0d264008bc64948d8aab6509e0cccf4c0f9914e8dace1658e2565a2f391e1528083d0c277235c

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

4e8daceRemove merge relicts and first clean up.

comment:25 Changed 9 years ago by Andrey Novoseltsev

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


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 default-algorithm 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 Jan Keitel

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 Andrey Novoseltsev

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 Jan Keitel

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
 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 {}
   796103    2.135    0.000    8.395    0.000
   796103    1.921    0.000    1.921    0.000 {}
   171376    1.513    0.000    1.513    0.000 {posix.write}
        1    1.383    1.383   39.131   39.131
    85688    1.050    0.000   26.405    0.000
    22916    1.049    0.000   18.948    0.001
   796103    0.919    0.000    1.819    0.000
  1592206    0.900    0.000    0.900    0.000 {posix.waitpid}
    19818    0.833    0.000   14.553    0.001
    42815    0.476    0.000   11.385    0.000
    85688    0.428    0.000   26.977    0.000
    42942    0.382    0.000    1.034    0.000
    99725    0.346    0.000    0.472    0.000
    46719    0.317    0.000    0.412    0.000
   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
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
   128426    0.202    0.000    0.222    0.000
    22917    0.194    0.000    0.429    0.000
   171376    0.177    0.000    0.177    0.000 {time.sleep}
    42815    0.160    0.000   12.065    0.000
    42873    0.151    0.000   16.769    0.000
   978573    0.150    0.000    0.196    0.000 {len}
    42815    0.148    0.000    0.148    0.000
    99709    0.144    0.000    0.144    0.000
   839045    0.131    0.000    0.131    0.000 {method 'lower' of 'str' objects}
   405591    0.123    0.000    0.157    0.000
    42873    0.120    0.000   16.926    0.000
    46719    0.116    0.000    0.116    0.000
    42865    0.113    0.000    0.228    0.000
    85688    0.111    0.000    2.005    0.000
   207596    0.100    0.000    0.100    0.000 {range}
    42942    0.096    0.000    0.314    0.000
    42873    0.094    0.000   16.473    0.000
    46719    0.085    0.000    0.498    0.000
   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
    42815    0.072    0.000   11.788    0.000
   602437    0.068    0.000    0.068    0.000 {method 'append' of 'list' objects}
    42873    0.062    0.000   16.600    0.000

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 Andrey Novoseltsev

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 For batch modifications

Milestone: sage-6.3sage-6.4
Note: See TracTickets for help on using tickets.