Opened 8 years ago

Last modified 7 years ago

#15280 needs_work enhancement

Extensions of PALP normal form, affine normal form and isomorphisms

Reported by: jkeitel Owned by:
Priority: major Milestone: sage-6.4
Component: geometry Keywords: toric
Cc: vbraun, novoselt 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 jkeitel)

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 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 8 years ago by git

  • Commit set to 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 https://github.com/github/gitignore/tree/master/Global
[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 8 years ago by jkeitel

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

comment:3 Changed 8 years ago by vbraun

You should use just master for any new branches.

comment:4 Changed 8 years ago by jkeitel

  • Commit changed from 8d4c11735db3de7833cb4ba7230890afe0dc620c to 4b42b4a909c83f675a0bd2e2e674e0795bef93f3

comment:5 Changed 8 years ago by jkeitel

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://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 8 years ago by vbraun

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 8 years ago by git

  • Commit changed from 4b42b4a909c83f675a0bd2e2e674e0795bef93f3 to 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 8 years ago by jkeitel

  • Commit changed from b2372408a86d4f7bd34caad6c7f5451aed2dc242 to 10f060281d24af0e79eb7c0be3de40f6ea4b1b3d

comment:9 Changed 8 years ago by jkeitel

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 8 years ago by git

  • Commit changed from 10f060281d24af0e79eb7c0be3de40f6ea4b1b3d to cbb323290e0f89433abd3467f91c8f0dbfd7fcc4

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

[changeset:cbb3232]Caching for affine normal form.

comment:11 Changed 8 years ago by jkeitel

  • Dependencies set to #13525
  • Status changed from needs_review to 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 8 years ago by git

  • Commit changed from cbb323290e0f89433abd3467f91c8f0dbfd7fcc4 to 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 follow-up: Changed 8 years ago by jkeitel

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 8 years ago by jkeitel

  • Description modified (diff)
  • Summary changed from Normal form for polytopes of non-zero codimension to Extensions of PALP normal form, affine normal form and isomorphisms

comment:15 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.0 to sage-6.1

comment:16 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:17 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:18 Changed 7 years ago by git

  • Commit changed from 0828630f23bb7a8f285264f4e5a91f89e3ab6a17 to 61b0d264008bc64948d8aab6509e0cccf4c0f991

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 7 years ago by jkeitel

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 7 years ago by novoselt

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 7 years ago by novoselt

Volker, any thoughts on 13?

comment:22 Changed 7 years ago by novoselt

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 7 years ago by jkeitel

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 7 years ago by git

  • Commit changed from 61b0d264008bc64948d8aab6509e0cccf4c0f991 to 4e8dace1658e2565a2f391e1528083d0c277235c

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

4e8daceRemove merge relicts and first clean up.

comment:25 Changed 7 years ago by novoselt

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 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 7 years ago by jkeitel

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 7 years ago by novoselt

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 7 years ago by jkeitel

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 7 years ago by novoselt

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 7 years ago by vbraun_spam

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