cddlib/Polyhedron bug

[sagetrac-mhampton]

The following causes cddlib to crash; I'm not sure if this is fixable without patching the cddlib source:

p4 = polytopes.permutahedron(5,project=True)
pn4 = p4.projection()
p3  = pn4.schlegel()
verts = p3.transformed_coords
edges = p3.lines
topes = []
for q in p4.facial_incidences():
    topes.append([verts[i] for i in q[1]])
Polyhedron(vertices=topes[3], field=RDF, verbose=True)

output ends with:

Facet graph
*Error: Possibly an LP cycling occurs.  Use the Criss-Cross method.

Apply trac_10037_polyhedron_bug.patch to the sage library

Depends on #14479

CC: @vbraun @dimpase @novoselt

Component: geometry

Keywords: cddlib, polyhedron, polyhedra

Author: Volker Braun

Reviewer: Andrey Novoseltsev

Merged: sage-5.10.beta1

Issue created by migration from https://trac.sagemath.org/ticket/10037

[vbraun]

comment:1

This one actually works for me (Fedora 13 x86_64):

sage: Polyhedron(vertices=topes[3], field=RDF, verbose=True)
[... vebose cdd interaction ...]
A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 23 vertices.

Just out of curiosity, which arch is that failing on?

I think the way to go is to implement vertex/facet adjacencies ourselves with a modern LP solver, either cvxopt or PPL.

I've opened #10039 as a first step to switch to PPL.

[sagetrac-mhampton]

comment:2

It fails for me on an intel mac, OS X 10.6. It does work for me on linux (64 bit Ubuntu 9.10).

[vbraun]

comment:3

#14479 adds raising a proper error, so I consider this fixed. Use rationals for exact arithmetic.

Patch is for a regression in calling schlegel() without specifying the direction.

[vbraun]

Author: Volker Braun

[vbraun]

Dependencies: #14479

[vbraun]

Attachment: trac_10037_polyhedron_bug.patch.gz

Initial patch

[vbraun]

comment:5

This trivial patch needs review...

[novoselt]

Reviewer: Andrey Novoseltsev

[jdemeyer]

Merged: sage-5.10.beta1