cddlib test in ppl.pyx takes a very long time

[jdemeyer]

From the file sage/libs/ppl.pyx starting at line 112:

The computation finishes without noticeable delay on my desktop
(timeit measures it to be 35msec). Cddlib needs about 3 minutes on the
same hardware::

    sage: basis = range(0,6)
    sage: x = [ Variable(i) for i in basis ]
    sage: gs = [ tuple(coeff) for coeff in permutations(basis) ]
    sage: Polyhedron(vertices=gs)   # long time
    A 5-dimensional polyhedron in QQ^6 defined as the convex hull of 720 vertices.

This test takes minutes (as is claimed). This regularly causes timeouts when testing Sage on Skynet.

On sage.math.washington.edu, sage-4.7.2.alpha0:

sage: from sage.libs.ppl import Variable, Generator_System, point, C_Polyhedron
sage: basis = range(0,6)
sage: x = [ Variable(i) for i in basis ]
sage: gs = [ tuple(coeff) for coeff in permutations(basis) ]
sage: time Polyhedron(vertices=gs)
A 5-dimensional polyhedron in QQ^6 defined as the convex hull of 720 vertices.

Time: CPU 0.14 s, Wall: 218.94 s

See also: #10039, #11534.

Apply trac_11849_shorter_long_ppl_test.patch​ and 11849_reviewer.patch​

[vbraun]

You are looking at the wrong code. The

sage: Polyhedron(vertices=gs)   # long time

call takes a very long time, as stated. The PPL computation is a few lines above, and completes within miliseconds:

sage: C_Polyhedron(gs)

We could turn the Polyhedron() call into a shorter # long time example.

Also, I have some patches on trac to switch Polyhedron to PPL, as well.

[jdemeyer]

Replying to vbraun:

sage: C_Polyhedron(gs) }}} We could turn the Polyhedron() call into a shorter # long time example.

Yes, please do that. I think you should aim for something taking at most 10 seconds or so on sage.math.

Also, I would rephrase the paragraph starting from line 112 as

The above computation (using PPL) finishes without noticeable delay (timeit measures it to be 5ms on sage.math). Below we do the same computation with cddlib, which needs about 10 seconds on the same hardware::

    sage: basis = range(0,6)
    sage: x = [ Variable(i) for i in basis ]
    sage: gs = [ tuple(coeff) for coeff in permutations(basis) ]
    sage: Polyhedron(vertices=gs)   # long time (10s on sage.math, 2011)
    A 5-dimensional polyhedron in QQ^6 defined as the convex hull of 720 vertices.

[vbraun]

Initial patch

[vbraun]

The attached patch switches to an computationally easier doctest problem. Now it should complete in < 5.

[jdemeyer]

positive_review modulo the reviewer patch.

[vbraun]

Great, thanks!

[jdemeyer]

Fixed commit message of my reviewer patch.