New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
PALP Normal Form #13525
Comments
comment:2
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).
CamelCase should only be used for class names, not parameters. Also, space after comma. Thats just the standard Python code style.
The name is a bit confusing, how about
The linear algebra people will probably object to that kind of isomorphism check of matrices. How about
Should be just "in general, ...". |
comment:3
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:5
Replying to @dimpase:
Volker kindly wrote: |
comment:6
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
Thanks all, fixing up the small issues now. Regarding what trehn said, firstly, 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
Replying to @sagetrac-sjg10:
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
Replying to @sagetrac-trehn:
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. |
Attachment: trac13525_palplaurentnormalform2.patch.gz Issues in comments addressed |
This comment has been minimized.
This comment has been minimized.
Changed author from sjg10 to Samuel Gonshaw |
Dependencies: #14319 |
comment:12
#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:
Also, docstring should be imperative: "Return foobar". Not: "Returns foobar" or "We return foobar". |
Branch: u/jkeitel/PALP_normal_form |
Commit: |
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
|
comment:17
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. |
Branch pushed to git repo; I updated commit sha1. New commits:
|
comment:20
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. |
Branch pushed to git repo; I updated commit sha1. New commits:
|
Work Issues: rebase |
Changed branch from u/jkeitel/PALP_normal_form to u/vbraun/PALP_normal_form |
Branch pushed to git repo; I updated commit sha1. New commits:
|
Reviewer: Volker Braun |
comment:30
I've fixed the merge conflict and some minor nitpicks (unnused |
Changed work issues from rebase to none |
comment:31
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. |
Changed branch from u/vbraun/PALP_normal_form to u/novoselt/PALP_normal_form |
Changed branch from u/novoselt/PALP_normal_form to |
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.
Depends on #14319
CC: @novoselt @sagetrac-tomc @sagetrac-trehn @sagetrac-jkeitel
Component: geometry
Author: Samuel Gonshaw, Jan Keitel
Branch/Commit:
1262262
Reviewer: Volker Braun
Issue created by migration from https://trac.sagemath.org/ticket/13525
The text was updated successfully, but these errors were encountered: