backend_polymake for Polyhedron #22683

mkoeppe · 2017-03-26T19:43:10Z

Building upon #22658 (Support interface coercion polymake(X) for Polyhedron), we provide a backend in backend_polymake.py that does all Polyhedron computations using polymake (in particular, the initial computation of the double description).

For quadratic field extensions of the rationals, this backend should be faster than the generic implementation in Python (unless the pexpect overhead dominates).

Depends on #22658

CC: @simon-king-jena @jplab @videlec @tscrim @yuan-zhou

Component: geometry

Author: Matthias Koeppe

Branch/Commit: 6d1774b

Reviewer: Travis Scrimshaw

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

The text was updated successfully, but these errors were encountered:

mkoeppe · 2017-03-26T22:31:02Z

Branch: u/mkoeppe/backend_polymake_for_polyhedron

mkoeppe · 2017-03-26T22:31:45Z

comment:2

As preparation, I have implemented the _sage_ method.

Last 10 new commits:

`7588b62`	Polyhedron_base: Provide `_polymake_init_` instead of @cached_method _polymake_
`07270d4`	`Polyhedron_base._polymake_init_: Pass both representations to polymake, add tests`
`5fadbcd`	Add `_polymake_init_` for some rings
`3d3cef2`	`Polymake: fix typo in docstring`
`6598823`	`Polyhedron_base._polymake_init_: Support polyhedra over quadratic extensions`
`ef23af4`	`Polyhedron_base._polymake_init_: Add test for RDF polyhedra`
`205879f`	`Matrix, MatrixSpace: Add coercion to polymake interface`
`e49765e`	`Polymake: Fix tests whose error messages changed because we do not use files`
`51af468`	`PolymakeElement.__iter__: New`
`2f0e059`	`PolymakeElement._sage_: Implement for Vector, Matrix, QuadraticExtension`

mkoeppe · 2017-03-26T22:31:45Z

Commit: 2f0e059

mkoeppe · 2017-03-26T22:39:17Z

Dependencies: #22658

mkoeppe · 2017-03-26T22:39:34Z

Author: Matthias Koeppe

sagetrac-git · 2017-03-27T06:15:57Z

Branch pushed to git repo; I updated commit sha1. New commits:

`218daca`	`Add Polyhedron_polymake`

sagetrac-git · 2017-03-27T06:15:57Z

Changed commit from 2f0e059 to 218daca

sagetrac-git · 2017-03-27T06:19:48Z

Changed commit from 218daca to 5ab94a2

sagetrac-git · 2017-03-27T06:19:48Z

Branch pushed to git repo; I updated commit sha1. New commits:

`5ab94a2`	`Merge tag '7.6' into t/22683/backend_polymake_for_polyhedron`

tscrim · 2017-03-27T14:43:01Z

comment:8

Two things I see:

def _polymake_ is missing doctests.
In __iter__, you should use ``self`` in the docstrings. You also don't need to have an INPUT: block since there essentially no input.

Otherwise LGTM modulo the dependency.

sagetrac-git · 2017-03-27T23:34:59Z

Branch pushed to git repo; I updated commit sha1. New commits:

`8fd81c7`	`Polyhedron_polymake._polymake_: Add doctest`
`952b860`	`PolymakeElement.__iter__: Doc fixes`

sagetrac-git · 2017-03-27T23:34:59Z

Changed commit from 5ab94a2 to 952b860

tscrim · 2017-03-28T02:36:55Z

Reviewer: Travis Scrimshaw

tscrim · 2017-03-28T02:36:55Z

comment:10

Thank you.

mkoeppe · 2017-03-28T02:38:01Z

comment:11

Thanks for reviewing!

tscrim · 2017-03-28T02:40:17Z

comment:12

Not a problem; happy to help.

kiwifb · 2017-04-01T22:15:29Z

comment:13

I suspect this will pass tests on the bots with stand-alone sage. It gives me trouble in sage-on-gentoo while building the documentation, I am not sure how other distros deal with the doc building. I have the following failure related to this ticket

[discrete_] /dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python2_7/doc/en/reference/discrete_geometry/sage/geometry/polyhedron/library.rst:11: WARNING: autodoc: failed to import module u'sage.geometry.polyhedron.library'; the following exception was raised:
[discrete_] Traceback (most recent call last):
[discrete_] File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python2_7/sage_setup/docbuild/ext/sage_autodoc.py", line 525, in import_object
[discrete_] __import__(self.modname)
[discrete_] File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python2_7/build/lib/sage/geometry/polyhedron/library.py", line 75, in <module>
[discrete_] from sage.combinat.root_system.associahedron import Associahedron
[discrete_] File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python2_7/build/lib/sage/combinat/root_system/associahedron.py", line 23, in <module>
[discrete_] from sage.geometry.polyhedron.parent import Polyhedra_QQ_ppl
[discrete_] File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python2_7/build/lib/sage/geometry/polyhedron/parent.py", line 825, in <module>
[discrete_] from sage.geometry.polyhedron.backend_polymake import Polyhedron_polymake
[discrete_] File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python2_7/build/lib/sage/geometry/polyhedron/backend_polymake.py", line 31, in <module>
[discrete_] from sage.rings.integer import LCM_list
[discrete_] ImportError: cannot import name LCM_list
[discrete_] /dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python2_7/doc/en/reference/discrete_geometry/sage/geometry/polyhedron/parent.rst:11: WARNING: autodoc: failed to import module u'sage.geometry.polyhedron.parent'; the following exception was raised:
[discrete_] Traceback (most recent call last):
[discrete_] File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python2_7/sage_setup/docbuild/ext/sage_autodoc.py", line 525, in import_object
[discrete_] __import__(self.modname)
[discrete_] File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python2_7/build/lib/sage/geometry/polyhedron/parent.py", line 825, in <module>
[discrete_] from sage.geometry.polyhedron.backend_polymake import Polyhedron_polymake
[discrete_] File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python2_7/build/lib/sage/geometry/polyhedron/backend_polymake.py", line 31, in <module>
[discrete_] from sage.rings.integer import LCM_list
[discrete_] ImportError: cannot import name LCM_list

which itself comes from #22630. Volker is currently testing the ticket so don't touch it now. If it is accepted as is, could we have a follow up to import LCM_list directly from sage.arith.functions? Although if I have problems with lazy_import, I will be fighting symptoms rather than the disease by doing that.

tscrim · 2017-04-02T00:01:35Z

comment:14

LCM_list is never called in the code AFAICS. So it should just be as simple as removing the import so this doesn't have to be based on #22630. Which ticket do you mean by "the ticket"?

kiwifb · 2017-04-02T03:39:00Z

comment:15

Replying to @tscrim:

LCM_list is never called in the code AFAICS. So it should just be as simple as removing the import so this doesn't have to be based on #22630. Which ticket do you mean by "the ticket"?

This, here, ticket. I am signaling because I need to keep track of these things but I don't want to stop normal progress. Any issue I have, could be dealt with in a follow up ticket. Volker's already merged this ticket in his testing branch and if all goes well we shouldn't prevent the closing of this ticket because of sage-on-gentoo [OK, I would stop it if I thought you did something terrible].

mkoeppe · 2017-04-02T04:02:21Z

comment:16

Follow-up ticket at #22740.

vbraun · 2017-04-02T14:22:10Z

comment:17

Documentation doesn't build

sagetrac-git · 2017-04-02T19:01:03Z

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

`b47f6f9`	`Polyhedron_base._polymake_init_: Add work around for empty polytopes with Polymake 3.0`
`3b49a54`	`Polymake: Fix another test whose error message depends on whether we use files`
`07a1757`	`Polyhedron_base._polymake_init_: Fix comment`
`09942e7`	`coercion tutorial: Update introspection results`
`19d05f1`	`Add more 'optional - polymake`
`cd583e2`	`Remove one unneccessary 'optional - polymake`
`7bcc04c`	`Merge tag '8.0.beta0' into t/22658/polyhedron_methods_using_the_polymake_pexpect_interface`
`d7d4234`	`Add '# optional - polymake'`
`4719102`	`Merge remote-tracking branch 'trac/u/mkoeppe/polyhedron_methods_using_the_polymake_pexpect_interface' into t/22683/backend_polymake_for_polyhedron`
`6d1774b`	`Reference manual: Add backend_polymake`

sagetrac-git · 2017-04-02T19:01:03Z

Changed commit from 952b860 to 6d1774b

mkoeppe · 2017-04-02T19:03:35Z

comment:19

I've merged in #22740, which was intended to be a follow-up ticket, hoping that this will fix the doc build problems.
Also merged the updated branch prereq #22658 (which I'll mark as dup), which brings in 8.0.beta0.
And added backend_polymake to the discrete geometry section of the manual.
Documentation builds for me on this branch.

tscrim · 2017-04-02T19:10:15Z

comment:20

I would have been somewhat surprised if the doc did build on Volker's testing branch given comment:13. Changes LGTM.

kiwifb · 2017-04-02T19:49:06Z

comment:21

Well, I would have thought you build your branch and the documentation. So, to me it was probably a problem on my side.

tscrim · 2017-04-02T19:59:32Z

comment:22

I didn't test it in conjunction with #22630 and didn't notice the conflict.

vbraun · 2017-04-05T19:37:55Z

Changed branch from u/mkoeppe/backend_polymake_for_polyhedron to 6d1774b

mkoeppe added this to the sage-8.0 milestone Mar 26, 2017

mkoeppe added c: geometry labels Mar 26, 2017

mkoeppe added the s: needs review label Mar 27, 2017

tscrim added s: positive review and removed s: needs review labels Mar 28, 2017

tscrim added s: needs work and removed s: positive review labels Apr 2, 2017

kiwifb added s: positive review and removed s: needs work labels Apr 2, 2017

vbraun added s: needs work and removed s: positive review labels Apr 2, 2017

mkoeppe added s: needs review and removed s: needs work labels Apr 2, 2017

tscrim added s: positive review and removed s: needs review labels Apr 2, 2017

vbraun removed the s: positive review label Apr 5, 2017

vbraun closed this as completed in 4262c41 Apr 5, 2017

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

backend_polymake for Polyhedron #22683

backend_polymake for Polyhedron #22683

mkoeppe commented Mar 26, 2017

mkoeppe commented Mar 26, 2017

mkoeppe commented Mar 26, 2017

mkoeppe commented Mar 26, 2017

mkoeppe commented Mar 26, 2017

mkoeppe commented Mar 26, 2017

sagetrac-git mannequin commented Mar 27, 2017

sagetrac-git mannequin commented Mar 27, 2017

sagetrac-git mannequin commented Mar 27, 2017

sagetrac-git mannequin commented Mar 27, 2017

tscrim commented Mar 27, 2017

sagetrac-git mannequin commented Mar 27, 2017

sagetrac-git mannequin commented Mar 27, 2017

tscrim commented Mar 28, 2017

tscrim commented Mar 28, 2017

mkoeppe commented Mar 28, 2017

tscrim commented Mar 28, 2017

kiwifb commented Apr 1, 2017

tscrim commented Apr 2, 2017

kiwifb commented Apr 2, 2017

mkoeppe commented Apr 2, 2017

vbraun commented Apr 2, 2017

sagetrac-git mannequin commented Apr 2, 2017

sagetrac-git mannequin commented Apr 2, 2017

mkoeppe commented Apr 2, 2017

tscrim commented Apr 2, 2017

kiwifb commented Apr 2, 2017

tscrim commented Apr 2, 2017

vbraun commented Apr 5, 2017

backend_polymake for Polyhedron #22683

backend_polymake for Polyhedron #22683

Comments

mkoeppe commented Mar 26, 2017

mkoeppe commented Mar 26, 2017

mkoeppe commented Mar 26, 2017

mkoeppe commented Mar 26, 2017

mkoeppe commented Mar 26, 2017

mkoeppe commented Mar 26, 2017

sagetrac-git mannequin commented Mar 27, 2017

sagetrac-git mannequin commented Mar 27, 2017

sagetrac-git mannequin commented Mar 27, 2017

sagetrac-git mannequin commented Mar 27, 2017

tscrim commented Mar 27, 2017

sagetrac-git mannequin commented Mar 27, 2017

sagetrac-git mannequin commented Mar 27, 2017

tscrim commented Mar 28, 2017

tscrim commented Mar 28, 2017

mkoeppe commented Mar 28, 2017

tscrim commented Mar 28, 2017

kiwifb commented Apr 1, 2017

tscrim commented Apr 2, 2017

kiwifb commented Apr 2, 2017

mkoeppe commented Apr 2, 2017

vbraun commented Apr 2, 2017

sagetrac-git mannequin commented Apr 2, 2017

sagetrac-git mannequin commented Apr 2, 2017

mkoeppe commented Apr 2, 2017

tscrim commented Apr 2, 2017

kiwifb commented Apr 2, 2017

tscrim commented Apr 2, 2017

vbraun commented Apr 5, 2017