Opened 7 months ago
Closed 7 months ago
#30531 closed defect (fixed)
Polyhedron_normaliz._triangulate_normaliz should not use NmzResult directly
Reported by:  mkoeppe  Owned by:  

Priority:  critical  Milestone:  sage9.2 
Component:  geometry  Keywords:  
Cc:  Winfried, jipilab, ghkliem  Merged in:  
Authors:  Jonathan Kliem  Reviewers:  Matthias Koeppe 
Report Upstream:  N/A  Work issues:  
Branch:  8d934b2 (Commits, GitHub, GitLab)  Commit:  8d934b248b5db0d1a2b69fbeccee91919f01a02e 
Dependencies:  Stopgaps: 
Description
_triangulate_normaliz
calls ._cone_generators
, which calls NmzResult
directly instead of going through ._nmz_result
.
This relies on the persistence of the rational and number field handlers in PyNormaliz
, which is subject to change in future PyNormaliz
versions.
Change History (34)
comment:1 Changed 7 months ago by
 Milestone changed from sage9.2 to sage9.3
comment:2 Changed 7 months ago by
comment:3 Changed 7 months ago by
I guess normaliz can handle this by now:
sage: P._nmz_result(P._normaliz_cone, "Triangulation") [[[0, 1, 2, 4], 16*a], [[1, 2, 4, 3], 16*a], [[1, 3, 4, 5], 16*a], [[3, 5, 6, 7], 16*a], [[6, 2, 4, 3], 16*a], [[6, 3, 4, 5], 16*a]]
This is exactly what we want.
comment:4 Changed 7 months ago by
 Priority changed from major to critical
comment:5 Changed 7 months ago by
 Milestone changed from sage9.3 to sage9.2
comment:6 Changed 7 months ago by
 Branch set to u/ghkliem/fix_normaliz_triangulation
 Commit set to bb90807ff268df14926e58a4741b49a66599eaac
 Status changed from new to needs_review
comment:7 Changed 7 months ago by
 Commit changed from bb90807ff268df14926e58a4741b49a66599eaac to 10b5312e1f9780b6b0e5021323b7058f028f644a
Branch pushed to git repo; I updated commit sha1. New commits:
10b5312  typo

comment:8 Changed 7 months ago by
Is homogenous
correct in any context?
git grep homogenous
reveals quite something. Could be on the list of common typos that are discovered by this tox
testing framework (and should of course be a typo ticket before that, but is annoying as one needs to deprecate at least one function).
comment:9 Changed 7 months ago by
I think the correct spelling is "homogeneous".
If there is any problem on the Normaliz/PyNormaliz? side, let me know.
comment:10 Changed 7 months ago by
Normaliz
works all right.
Is there a way to ignore the dehomogenization for Triangulation
of noncompact polyhedra? I currently recreate the cone from precomputed data without specifying the dehomogenization to achieve this.
comment:11 Changed 7 months ago by
I think you want to get a triangulation (of the homogenization) even if the input defines an unbounded polyhedron. At present forbidden. It would be no real problem to do do this computation, but it requires a change in the source code of Normaliz. I keep it in mind.
comment:12 Changed 7 months ago by
Is this ready for review? The method _cone_generators
of the ticket description is unchanged
comment:13 Changed 7 months ago by
I guess the static method _cone_generators
can just be removed. What do you think about it? It's not just anywhere else as much as I can see.
The correct way to do it anyway is by self._nmz_result(self._normaliz_cone, "Generators")
. I wasn't sure about how to resolve this issue for a static method.
comment:14 Changed 7 months ago by
If it's not used any more, yes, please remove it
comment:15 Changed 7 months ago by
 Commit changed from 10b5312e1f9780b6b0e5021323b7058f028f644a to b45d775016f2d6f20dc89f93b077de164a39966a
Branch pushed to git repo; I updated commit sha1. New commits:
b45d775  remove unused private method that incorrectly uses the API

comment:16 Changed 7 months ago by
 Reviewers set to Matthias Koeppe
 Status changed from needs_review to positive_review
comment:17 Changed 7 months ago by
I have changed the Normaliz code so that triangulations can be computed for arbitrary input (just pushed to GitHub/master; will be part of version 3.8.9). It is clear that this notion must be interpreted with care if the input defines an unbounded polyhedron. A corresponding remark has been added to Normaliz.pdf (p. 121 in the current version).
I am not sure whether the computation in which the triangulations come up, are genuinely inhomogeneous, or the inhomogeneity is due to the implementation of the Sage polyhedron class. As mentioned earlier, it would be really good if the Sage cone class could use Normaliz as a backend.
comment:18 followup: ↓ 20 Changed 7 months ago by
IMPORTANT: Triangulations are defined with respect to an ordered set of generators. The only reliable interactive way to connect the triangulation with the generators is to ask for them AFTER the computation of the triangulation since this computation may have changed the order (or even the set). Normaliz knows this problem and therefore stores the generators after the computation of the triangulation for future reference. So with disciplined use there is no problem.
But often generators are already defined before the computation of the triangulation, and if users ask for them too early, chaos can ensue. For this reason I will introduce the matrix TriangulationGenerators? that stores the ordered set of generators used in building the triangulation. The name should help to avoid confusion.
comment:19 Changed 7 months ago by
I've opened #30569 for the update to the upcoming version and left a note there regarding the triangulations
comment:20 in reply to: ↑ 18 Changed 7 months ago by
Replying to Winfried:
IMPORTANT: Triangulations are defined with respect to an ordered set of generators. The only reliable interactive way to connect the triangulation with the generators is to ask for them AFTER the computation of the triangulation since this computation may have changed the order (or even the set). Normaliz knows this problem and therefore stores the generators after the computation of the triangulation for future reference. So with disciplined use there is no problem.
But often generators are already defined before the computation of the triangulation, and if users ask for them too early, chaos can ensue. For this reason I will introduce the matrix TriangulationGenerators? that stores the ordered set of generators used in building the triangulation. The name should help to avoid confusion.
From my point of view, this means that this ticket should go back to needs work.
comment:21 Changed 7 months ago by
 Status changed from positive_review to needs_work
comment:22 Changed 7 months ago by
@Winfried: Could you maybe provide an example where the order changes or point me towards such a direction. (EDIT: If you know something, if the next point applies, don't worry about it.)
Or is it just in principal a wrong assumption for the API to make and this could go wrong at some point?
If I initialize with precomputed data and random order of vertices, calling Triangulation
doesn't change the order (at least for the examples I tried).
comment:23 Changed 7 months ago by
Look at
>>> import PyNormaliz >>> from PyNormaliz import * >>> vert = [[2, 1, 1, 2, 1], [2, 1, 0, 2, 1], [2, 1, 1, 2, 1], [2, 0, 1, 2, 1], [2, 0, 0, 2, 1], [2, 0, 1, 2, 1], [2, 1, 1, 2, 1], [2, 1, 0, 2, 1], [2, 1, 1, 2, 1]] >>> C= Cone(vertices = vert) >>> C.Generators() [[2, 1, 1, 2, 1], [2, 1, 0, 2, 1], [2, 1, 1, 2, 1], [2, 0, 1, 2, 1], [2, 0, 0, 2, 1], [2, 0, 1, 2, 1], [2, 1, 1, 2, 1], [2, 1, 0, 2, 1], [2, 1, 1, 2, 1]] >>> C.Triangulation() [[[0, 1, 2], 1], [[0, 1, 3], 1], [[0, 2, 4], 1], [[0, 3, 4], 1], [[1, 2, 5], 1], [[1, 3, 6], 1], [[2, 4, 7], 1], [[3, 4, 8], 1]] >>> C.Generators() [[2, 0, 0, 2, 1], [2, 1, 0, 2, 1], [2, 0, 1, 2, 1], [2, 0, 1, 2, 1], [2, 1, 0, 2, 1], [2, 1, 1, 2, 1], [2, 1, 1, 2, 1], [2, 1, 1, 2, 1], [2, 1, 1, 2, 1]] >>>
I would not bet that this impossible with precomputed generators. I stumbled on this problem when the last Travis run of PyNormaliz? failed because the triangulation had changed relative to the reference. In the Normaliz workflow the triangulation can be computed at two places, and this place has changed with the last commit in order to make triangulations available also for unbounded polyhedra.
If the triangulation is computed together with the Ehrhart series (==> old place), then we get a different result:
>>> D= Cone(vertices = vert) >>> D.Compute("EhrhartSeries", "Triangulation") True >>> D.Generators() [[2, 1, 1, 2, 1], [2, 1, 0, 2, 1], [2, 1, 1, 2, 1], [2, 0, 1, 2, 1], [2, 0, 0, 2, 1], [2, 0, 1, 2, 1], [2, 1, 1, 2, 1], [2, 1, 0, 2, 1], [2, 1, 1, 2, 1]] >>> D.Triangulation() [[[0, 1, 3], 1], [[1, 2, 3], 1], [[2, 3, 4], 1], [[2, 4, 5], 1], [[3, 4, 6], 1], [[4, 5, 6], 1], [[5, 6, 7], 1], [[5, 7, 8], 1]] >>> D.Generators() [[2, 1, 1, 2, 1], [2, 1, 0, 2, 1], [2, 1, 1, 2, 1], [2, 0, 1, 2, 1], [2, 0, 0, 2, 1], [2, 0, 1, 2, 1], [2, 1, 1, 2, 1], [2, 1, 0, 2, 1], [2, 1, 1, 2, 1]] >>>
In this case the order has not changed. Both results are correct  triangulations are not uniquely determined and there is no canonical order of the generators. The next days I will try to find out what is really going on. Nevertheless I think it is really better to introduce TriangulationGenereors? that are not defined before the triangulation has been computed.
comment:24 Changed 7 months ago by
Thanks. You were faster than me. I just wanted to post that I stumped upon this while trying to get a doctest for algebraic polyhedra (that finding the correct indices also works for them).
The current branch produces:
sage: C1 = Polyhedron(rays=[[0,0,1],[1,0,AA(2).sqrt()],[0,1,1],[1,1,1]], backend='normaliz') sage: C1.triangulate(engine='normaliz') (<0,1,2>, <0,2,3>) sage: list(a.ambient_Vrepresentation() for a in C1.face_generator()) [(A vertex at (0, 0, 0), A ray in the direction (0, 0, 1), A ray in the direction (0, 1, 1), A ray in the direction (0.7071067811865475?, 0, 1), A ray in the direction (1, 1, 1)), (), (A vertex at (0, 0, 0), A ray in the direction (0, 0, 1), A ray in the direction (0, 1, 1)), (A vertex at (0, 0, 0), A ray in the direction (0, 0, 1), A ray in the direction (0.7071067811865475?, 0, 1)), (A vertex at (0, 0, 0), A ray in the direction (0, 1, 1), A ray in the direction (1, 1, 1)), (A vertex at (0, 0, 0), A ray in the direction (0.7071067811865475?, 0, 1), A ray in the direction (1, 1, 1)), (A vertex at (0, 0, 0), A ray in the direction (0, 0, 1)), (A vertex at (0, 0, 0), A ray in the direction (0, 1, 1)), (A vertex at (0, 0, 0),), (A vertex at (0, 0, 0), A ray in the direction (0.7071067811865475?, 0, 1)), (A vertex at (0, 0, 0), A ray in the direction (1, 1, 1))] sage: C1.rays() (A ray in the direction (0, 0, 1), A ray in the direction (0, 1, 1), A ray in the direction (0.7071067811865475?, 0, 1), A ray in the direction (1, 1, 1))
This is wrong (this is why I printed all the extra stuff).
Checking the indices I get: (<0,1,3>, <0,2,3>)
.
So accidentally I stumbled upon an example myself.
comment:25 Changed 7 months ago by
 Commit changed from b45d775016f2d6f20dc89f93b077de164a39966a to 63f1b79d8eafab0dc88902a310f8d7a16ef6b6e5
Branch pushed to git repo; I updated commit sha1. New commits:
63f1b79  account for maybe changed order of the generators

comment:26 Changed 7 months ago by
 Status changed from needs_work to needs_review
It's not pretty, but it seems to work.
comment:27 Changed 7 months ago by
 Status changed from needs_review to positive_review
My guess is that this workaround might fail if this not full dimensional.
But I think this is good enough as a hot fix for Sage 9.2 while we wait for the new Normaliz.
comment:28 Changed 7 months ago by
To day I have changed the master branch of Normliz as follows:
 Generators are no longer accessible from the outside
 they are replaced by TriangulationGenerators?
 TriangulationGeneretors? are set immediately after a triangulation has been computed
It is possible to compute several triangulations successively, for example an ordinary one first and then a unimodular one. I think it is clear that one must pull the TriangulationGenerators? again after the second computation.
One could go a step further by bundling the Triangulation and the TriangulationGenerators? so that they are returned together. If you think this is necessary, please let me know.
PyNormaliz? has not yet been updated. I think only changes in the tests are necessary.
comment:29 Changed 7 months ago by
 Status changed from positive_review to needs_work
********************************************************************** File "src/sage/geometry/polyhedron/backend_normaliz.py", line 1574, in sage.geometry.polyhedron.backend_normaliz.Polyhedron_normaliz._triangulate_normaliz Failed example: C1 = Polyhedron(rays=[[0,0,1],[1,0,AA(2).sqrt()],[0,1,1],[1,1,1]], backend='normaliz') Exception raised: Traceback (most recent call last): File "/home/release/Sage/local/lib/python3.8/sitepackages/sage/doctest/forker.py", line 720, in _run self.compile_and_execute(example, compiler, test.globs) File "/home/release/Sage/local/lib/python3.8/sitepackages/sage/doctest/forker.py", line 1145, in compile_and_execute exec(compiled, globs) File "<doctest sage.geometry.polyhedron.backend_normaliz.Polyhedron_normaliz._triangulate_normaliz[0]>", line 1, in <module> C1 = Polyhedron(rays=[[Integer(0),Integer(0),Integer(1)],[Integer(1),Integer(0),AA(Integer(2)).sqrt()],[Integer(0),Integer(1),Integer(1)],[Integer(1),Integer(1),Integer(1)]], backend='normaliz') File "sage/misc/lazy_import.pyx", line 353, in sage.misc.lazy_import.LazyImport.__call__ (build/cythonized/sage/misc/lazy_import.c:3736) return self.get_object()(*args, **kwds) File "/home/release/Sage/local/lib/python3.8/sitepackages/sage/geometry/polyhedron/constructor.py", line 662, in Polyhedron return parent(Vrep, Hrep, convert=convert, verbose=verbose) File "sage/structure/parent.pyx", line 902, in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:9364) return mor._call_with_args(x, args, kwds) File "sage/structure/coerce_maps.pyx", line 180, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_with_args (build/cythonized/sage/structure/coerce_maps.c:5154) raise File "sage/structure/coerce_maps.pyx", line 175, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_with_args (build/cythonized/sage/structure/coerce_maps.c:5042) return C._element_constructor(x, *args, **kwds) File "/home/release/Sage/local/lib/python3.8/sitepackages/sage/geometry/polyhedron/parent.py", line 598, in _element_constructor_ return self.element_class(self, Vrep, Hrep, **kwds) File "/home/release/Sage/local/lib/python3.8/sitepackages/sage/geometry/polyhedron/backend_normaliz.py", line 238, in __init__ Polyhedron_base.__init__(self, parent, Vrep, Hrep, **kwds) File "/home/release/Sage/local/lib/python3.8/sitepackages/sage/geometry/polyhedron/base.py", line 249, in __init__ self._init_from_Vrepresentation(vertices, rays, lines, **kwds) File "/home/release/Sage/local/lib/python3.8/sitepackages/sage/geometry/polyhedron/backend_normaliz.py", line 565, in _init_from_Vrepresentation self._init_from_normaliz_data(data, normaliz_field=normaliz_field, verbose=verbose) File "/home/release/Sage/local/lib/python3.8/sitepackages/sage/geometry/polyhedron/backend_normaliz.py", line 387, in _init_from_normaliz_data cone = self._cone_from_normaliz_data(data, verbose) File "/home/release/Sage/local/lib/python3.8/sitepackages/sage/geometry/polyhedron/backend_normaliz.py", line 419, in _cone_from_normaliz_data PythonModule("PyNormaliz", spkg="pynormaliz").require() File "/home/release/Sage/local/lib/python3.8/sitepackages/sage/features/__init__.py", line 191, in require raise FeatureNotPresentError(self, presence.reason, presence.resolution) sage.features.FeatureNotPresentError: PyNormaliz is not available. Failed to import `PyNormaliz`. To install PyNormaliz you can try to run 'sage i pynormaliz'. ********************************************************************** File "src/sage/geometry/polyhedron/backend_normaliz.py", line 1575, in sage.geometry.polyhedron.backend_normaliz.Polyhedron_normaliz._triangulate_normaliz Failed example: C1._triangulate_normaliz() Exception raised: Traceback (most recent call last): File "/home/release/Sage/local/lib/python3.8/sitepackages/sage/doctest/forker.py", line 720, in _run self.compile_and_execute(example, compiler, test.globs) File "/home/release/Sage/local/lib/python3.8/sitepackages/sage/doctest/forker.py", line 1145, in compile_and_execute exec(compiled, globs) File "<doctest sage.geometry.polyhedron.backend_normaliz.Polyhedron_normaliz._triangulate_normaliz[1]>", line 1, in <module> C1._triangulate_normaliz() NameError: name 'C1' is not defined **********************************************************************
comment:30 Changed 7 months ago by
 Commit changed from 63f1b79d8eafab0dc88902a310f8d7a16ef6b6e5 to 8d934b248b5db0d1a2b69fbeccee91919f01a02e
Branch pushed to git repo; I updated commit sha1. New commits:
8d934b2  optional flag

comment:31 Changed 7 months ago by
 Status changed from needs_work to needs_review
comment:32 Changed 7 months ago by
 Status changed from needs_review to positive_review
comment:33 Changed 7 months ago by
Thanks.
comment:34 Changed 7 months ago by
 Branch changed from u/ghkliem/fix_normaliz_triangulation to 8d934b248b5db0d1a2b69fbeccee91919f01a02e
 Resolution set to fixed
 Status changed from positive_review to closed
This has nothing to do with the future. It is already a bug.