Opened 9 years ago

Closed 7 years ago

#13525 closed enhancement (fixed)

PALP Normal Form

Reported by: sjg10 Owned by: mhampton
Priority: major Milestone: sage-6.3
Component: geometry Keywords:
Cc: novoselt, tomc, trehn, jkeitel Merged in:
Authors: Samuel Gonshaw, Jan Keitel Reviewers: Volker Braun
Report Upstream: N/A Work issues:
Branch: 1262262 (Commits, GitHub, GitLab) Commit: 126226211d29ee285f25285d980a12e0419ea609
Dependencies: #14319 Stopgaps:

Status badges

Description (last modified by sjg10)

This patch adds the PALP normal form algorithm natively into the lattice_polytope class, as well as a modified algorithm that is more efficient for some polytopes. This is then also used directly to calculate a normal form for Laurent polynomials.

These algorithms require abilities to permute rows and columns of matrices, as well as find automorphisms of matrices under these operations, and lattice polytopes under GL(n,Z) transformations. These are also implemented here.

Apply the latest patch only.

Attachments (1)

trac13525_palplaurentnormalform2.patch (59.1 KB) - added by sjg10 9 years ago.
Issues in comments addressed

Download all attachments as: .zip

Change History (36)

comment:1 Changed 9 years ago by sjg10

  • Status changed from new to needs_review

comment:2 Changed 9 years ago by vbraun

Very nice! Thanks for tackling this, I always wanted this implemented!

Some minor nitpicks: Whenever you return a list of stuff, its better to return a tuple (which is immutable).

def matrix_transformation(self,NewPolytope): 

CamelCase should only be used for class names, not parameters. Also, space after comma. Thats just the standard Python code style.

def lexicographical_order(self,certify=False): 

The name is a bit confusing, how about permutation_normal_form() or something like that?

def is_isomorphic(self,N,certify=False): 

The linear algebra people will probably object to that kind of isomorphism check of matrices. How about is_permutation_of()?

By default, in general one can't mix matrices and permutations

Should be just "in general, ...".

comment:3 follow-up: Changed 9 years ago by dimpase

The reference you give in the code does not define the normal form you are computing. Is this published anywhere? If yes, please give a proper reference. If not, it would be great if you give a definition in the docstrings.

PS. Well, I am very curious to find out what it is. That's one of the reasons I ask :–)

comment:4 Changed 9 years ago by novoselt

  • Cc novoselt added

comment:5 in reply to: ↑ 3 Changed 9 years ago by dimpase

Replying to dimpase:

The reference you give in the code does not define the normal form you are computing. Is this published anywhere? If yes, please give a proper reference. If not, it would be great if you give a definition in the docstrings.

PS. Well, I am very curious to find out what it is. That's one of the reasons I ask :–)

Volker kindly wrote: See Section 3.4 of http://arxiv.org/pdf/hep-th/9805190.pdf for the definition of the PALP normal form. So this would be a reference to add.

comment:6 follow-up: Changed 9 years ago by trehn

  • Cc trehn added

I have one brief remark about the method automorphisms(). If I see this correctly, you build the complete face lattice, compute its automorphism group (i.e. the combinatorial automorphism group of the polytope) and filter those permutations that correspond to GL(n,ZZ)-transformations.

There seems to be already a method of Polyhedron that computes the combinatorial automorphism group, so you could use this method. For the combinatorial automorphisms of the polytope you don't need the whole face lattice, but the bipartite vertex-facet-incidence graph is enough.

comment:7 in reply to: ↑ 6 ; follow-up: Changed 9 years ago by sjg10

Thanks all, fixing up the small issues now. Regarding what trehn said, firstly, LatticePolytope does not inherit at all from Polyhedron and there does not seem to be an easy way to cast between the two, though as an aside, maybe this should be rectified?

Secondly it is possible, and such was the intent (though I haven't personally checked this out, but have been told) that checking if a permutation corresponds to a GL(n,ZZ) transformation is a more hefty computation than constructing the face lattice. Doing so (especially as it is decorated with some lattice polytope invariants) and reducing the number of permutations to check, over just finding the combinatorial automorphisms and checking all of these may be quicker.

comment:8 in reply to: ↑ 7 ; follow-up: Changed 9 years ago by trehn

Replying to sjg10:

Secondly it is possible, and such was the intent (though I haven't personally checked this out, but have been told) that checking if a permutation corresponds to a GL(n,ZZ) transformation is a more hefty computation than constructing the face lattice. Doing so (especially as it is decorated with some lattice polytope invariants) and reducing the number of permutations to check, over just finding the combinatorial automorphisms and checking all of these may be quicker.

Sorry, I didn't see the lattice index invariants at first. Of course, my comment is not relevant if your input is "easy". Because you check all permutations whether they correspond to GL(n,ZZ)-transformations, trying to keep this number small seems reasonable.

I think that, depending on the polytope, either the size of the face lattice or the number of group elements will cause problems if you go to dimensions beyond the PALP limit.

comment:9 in reply to: ↑ 8 Changed 9 years ago by sjg10

Replying to trehn:

I think that, depending on the polytope, either the size of the face lattice or the number of group elements will cause problems if you go to dimensions beyond the PALP limit.

This is one of the main reasons of having implemented the PALP algorithm natively, the overflow errors that PALP is susceptible to in higher dimensions is removed when running the algorithm through python.

Changed 9 years ago by sjg10

Issues in comments addressed

comment:10 Changed 9 years ago by sjg10

  • Description modified (diff)

comment:11 Changed 9 years ago by jdemeyer

  • Authors changed from sjg10 to Samuel Gonshaw

comment:12 Changed 8 years ago by vbraun

  • Dependencies set to #14319

#14319 improves the graph automorphisms so you don't have to track the relabeling any more. This would simplify the code here, too.

As a minor nitpick, pep8 would be nice:

def palp_modified_normal_form(L,affine_transform=False,certify=False):    # no
def palp_modified_normal_form(L, affine_transform=False, certify=False):  # yes

Also, docstring should be imperative: "Return foobar". Not: "Returns foobar" or "We return foobar".

comment:13 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:14 Changed 8 years ago by jkeitel

  • Cc jkeitel added

comment:15 Changed 8 years ago by jkeitel

  • Branch set to u/jkeitel/PALP_normal_form

comment:16 Changed 8 years ago by git

  • Commit set to e4db787135b8bd21e55dac8784f34257a2c4af98

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

[changeset:e4db787]First pass over lattice_polytope, still errors.
[changeset:a497d27]First sweep of matrix0.pyx
[changeset:3dbd2dc]First sweep of matrix2.pyx and permgroup_element.pyx
[changeset:efd80b4]Working on matrix permutations.
[changeset:4aa0318]Natively implement PALP Normal Form
[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
[changeset:970090d]Merge branch 'u/ohanar/build_system'

comment:17 Changed 8 years ago by jkeitel

I have tried to rebase the patch and, in particular, tried to adapt to the changes from #14319. However, automorphisms of LatticePolytopes? do not work yet and there is probably much code that could be rewritten.

As far as the code in lattice_polytope.py is concerned, I've only reformated and not checked what the code actually does. The same is true for all other normal_form methods.

comment:18 Changed 8 years ago by jkeitel

  • Status changed from needs_review to needs_work

comment:19 Changed 8 years ago by git

  • Commit changed from e4db787135b8bd21e55dac8784f34257a2c4af98 to 10512078772ae6fdd6fb6b68016e64df2a934568

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

[changeset:1051207]Removed auto- and isomorphism code for the time being.
[changeset:a11b390]Fixing doctests.
[changeset:1b1f739]Rearranging and regrouping palp_* methods.
[changeset:e31daec]Fixed errors in palp_*-methods.
[changeset:37ea582]Working on permutation normal form.
[changeset:e4cdd6d]Cosmetic changes.

comment:20 Changed 8 years ago by jkeitel

This is now almost at a point where things are working. For now I have removed the attempts at a method finding isomorphisms between two given polytopes. The plan is to write a proper method for general affine transformations in #15280.

comment:21 Changed 8 years ago by git

  • Commit changed from 10512078772ae6fdd6fb6b68016e64df2a934568 to 6938bac48e41ded016430e2399493aeb9ef9e00e

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

[changeset:6938bac]Added normal form permutation read out from PALP.
[changeset:0f328ca]Removed normal form for Laurent polynomials.

comment:22 Changed 8 years ago by git

  • Commit changed from 6938bac48e41ded016430e2399493aeb9ef9e00e to 7b85f7ea7ef33e0f69c266b36f7e9c2c00ca0a38

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

[changeset:7b85f7e]Added more doctests and longer descriptions.

comment:23 Changed 8 years ago by jkeitel

  • Authors changed from Samuel Gonshaw to Samuel Gonshaw, Jan Keitel
  • Summary changed from PALP/Laurent Normal Form to PALP Normal Form

Alright, I think I am more or less done rewriting the patch. I have

  • removed functionality for Laurent normal form and finding isomorphisms between LatticePolytopes?. These were broken and at least the latter will be reintroduced (in more general form) in #15280
  • restructured the _palp* methods for computing normal forms in lattice_polytope.py
  • rebased and partially rewritten the code and tried to use the common formatting conventions
  • included permutation read-out directly from PALP
  • extended docstrings and tests

There are some issues: Two key functions, namely LatticePolytopeClass?._palp_normal_form_native and Matrix.permutation_normal_form, both of which calculate the maximal form of a matrix under permutations of columns and rows have fairly tense bits of code and I did not understand everything. While I verified that after fixing a couple of small errors they now give the correct results for several thousand examples, there may additional bugs. There might also be potential for optimization.

What should be done in this case?

comment:24 Changed 8 years ago by jkeitel

  • Status changed from needs_work to needs_review

comment:25 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:26 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:27 Changed 7 years ago by rws

  • Status changed from needs_review to needs_work
  • Work issues set to rebase

comment:28 Changed 7 years ago by vbraun

  • Branch changed from u/jkeitel/PALP_normal_form to u/vbraun/PALP_normal_form

comment:29 Changed 7 years ago by git

  • Commit changed from 7b85f7ea7ef33e0f69c266b36f7e9c2c00ca0a38 to 6b7b32c006be4a11025c656ebb2c1306324195a5

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

6b7b32cminor fixes

comment:30 Changed 7 years ago by vbraun

  • Reviewers set to Volker Braun
  • Status changed from needs_work to positive_review
  • Work issues rebase deleted

I've fixed the merge conflict and some minor nitpicks (unnused _normal_form, doc build). Functionality looks good to me.

comment:31 Changed 7 years ago by novoselt

  • Status changed from positive_review to needs_work

This branch "undoes" some of the deprecation-related changes from #15240, let me try to go over it too, will have a version in a few hours.

comment:32 Changed 7 years ago by novoselt

  • Branch changed from u/vbraun/PALP_normal_form to u/novoselt/PALP_normal_form

comment:33 Changed 7 years ago by novoselt

  • Commit changed from 6b7b32c006be4a11025c656ebb2c1306324195a5 to 126226211d29ee285f25285d980a12e0419ea609
  • Status changed from needs_work to needs_review

Done!


New commits:

a5428afFixes to normal_form_pc to work with point collections properly.
1262262Use point collections more directly.

comment:34 Changed 7 years ago by vbraun

  • Status changed from needs_review to positive_review

comment:35 Changed 7 years ago by vbraun

  • Branch changed from u/novoselt/PALP_normal_form to 126226211d29ee285f25285d980a12e0419ea609
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.