#30248 closed defect (fixed)

Normaliz backend is broken with double description input

Reported by: jipilab Owned by:
Priority: critical Milestone: sage-9.2
Component: geometry Keywords: polytope, backend, normaliz, hyperplane, regions
Cc: gh-kliem, gh-LaisRast, mkoeppe, tscrim Merged in:
Authors: Jean-Philippe Labbé Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 83453fb (Commits, GitHub, GitLab) Commit: 83453fb76a747556812266da84afb98b64fc7eab
Dependencies: Stopgaps:

Status badges

Description

This bug was found while manipulating hyperplane arrangements.

A minimal example to reproduce the bug is:

sage: p1 = Polyhedron(backend='normaliz', base_ring=AA, rays=[(AA(0), AA(0), AA(1)), (AA(0), AA(1), AA(-1)), (AA(1), AA(0), AA(-1))], vertices=[(AA(0), AA(0), AA(0))])
sage: p1
A 3-dimensional polyhedron in AA^3 defined as the convex hull of 1 vertex and 3 rays
sage: -p1
A 3-dimensional polyhedron in AA^3 defined as the convex hull of 1 vertex and 3 lines
sage: p2 = Polyhedron(backend='normaliz', base_ring=AA, rays=[(AA(-1), AA(0), AA(1)), (AA(-1), AA(1), AA(0)), (AA(0), AA(0), AA(-1))], vertices=[(AA(0), AA(0), AA(0))])
sage: p2
A 3-dimensional polyhedron in AA^3 defined as the convex hull of 1 vertex and 3 rays
sage: -p2
A 3-dimensional polyhedron in AA^3 defined as the convex hull of 1 vertex and 3 lines

Looking at dilation it seems that dilation is not the problem, it does the right thing, but the parent.element_class call messes things up.

Notice that changing the base ring to QQ or ZZ or removing the 'normaliz' backend, one does not get the error... This is nasty.

In the hyperplane arrangement, there are some rational regions, and some irrational regions...

Change History (12)

comment:1 Changed 12 months ago by gh-kliem

Notice that normaliz doesn't use precomputed double description yet (waiting for the package upgrade). I suspect intitialzing from inequaltities doesn't work correctly and there is an even simpler one line example for this.

comment:2 Changed 12 months ago by gh-kliem

What might be causing it, is passing a generator for the inequalries (in this case you cannot get the error with the normal constructor).

If we iterate twice through it (only for number fields), the second time you obviosly don't get anything, which explains the three lines.

One solution may be to make a tuple out of the generators, once we decided what we dispose in Polyhedron_base.__init__. The main reason for the generators is that we do not want to generate something, which we dispose of a few lines later.

comment:3 Changed 12 months ago by mkoeppe

  • Priority changed from major to critical

comment:4 Changed 12 months ago by jipilab

Found it.

Line 858 and 859 in backend_normaliz in the method _compute_nmz_data_lists_and_field, which is called by _init_H_representation.

The fact that the base ring is enforced to be AA while the data is really in QQ is taken care of by these 2 lines (normaliz should be used and not Qnormaliz). But! Since dilation ships 2 maps for the Hreps, the data_lists are empty at that point!

Ouff! Ok, I think this shouldn't be too hard to fix.

...this is a sign that this use-case was not really tested... It pops up when one wants to deal with lots of sorts of polyhedra and eventually need to fix a base ring (done in Hyperplane arrangements). Oiii.

comment:5 follow-up: Changed 12 months ago by gh-kliem

I implemented a few test suite methods already. If you run a test suite on your polyhedron, does it succeed?

comment:6 Changed 12 months ago by jipilab

  • Branch set to public/30248
  • Commit set to 83453fb76a747556812266da84afb98b64fc7eab
  • Status changed from new to needs_review

New commits:

83453fbFix Hrepr of normaliz for iterators

comment:7 in reply to: ↑ 5 ; follow-up: Changed 12 months ago by jipilab

Replying to gh-kliem:

I implemented a few test suite methods already. If you run a test suite on your polyhedron, does it succeed?

Yes. It seems so.

comment:8 Changed 12 months ago by jipilab

  • Authors set to Jean-Philippe Labbé

comment:9 in reply to: ↑ 7 Changed 12 months ago by gh-kliem

Replying to jipilab:

Replying to gh-kliem:

I implemented a few test suite methods already. If you run a test suite on your polyhedron, does it succeed?

Yes. It seems so.

OK. Then this is a friendly reminder to go on with it.

comment:10 Changed 12 months ago by jipilab

  • Cc tscrim added

Ping! I think it would be important to have this ticket in the next release...

comment:11 Changed 12 months ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

LGTM.

comment:12 Changed 12 months ago by vbraun

  • Branch changed from public/30248 to 83453fb76a747556812266da84afb98b64fc7eab
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.