Opened 3 years ago

Closed 3 years ago

#22683 closed enhancement (fixed)

backend_polymake for Polyhedron

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-8.0
Component: geometry Keywords:
Cc: SimonKing, jipilab, vdelecroix, tscrim, yzh Merged in:
Authors: Matthias Koeppe Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 6d1774b (Commits) Commit: 6d1774b1d460ab8927f127abf4abc36305baf674
Dependencies: #22658 Stopgaps:

Description

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).

Change History (23)

comment:1 Changed 3 years ago by mkoeppe

  • Branch set to u/mkoeppe/backend_polymake_for_polyhedron

comment:2 Changed 3 years ago by mkoeppe

  • Commit set to 2f0e0594a0ce0d0342427f0d75ea1e7e4d9e13b3

As preparation, I have implemented the _sage_ method.


Last 10 new commits:

7588b62Polyhedron_base: Provide _polymake_init_ instead of @cached_method _polymake_
07270d4Polyhedron_base._polymake_init_: Pass both representations to polymake, add tests
5fadbcdAdd _polymake_init_ for some rings
3d3cef2Polymake: fix typo in docstring
6598823Polyhedron_base._polymake_init_: Support polyhedra over quadratic extensions
ef23af4Polyhedron_base._polymake_init_: Add test for RDF polyhedra
205879fMatrix, MatrixSpace: Add coercion to polymake interface
e49765ePolymake: Fix tests whose error messages changed because we do not use files
51af468PolymakeElement.__iter__: New
2f0e059PolymakeElement._sage_: Implement for *Vector, *Matrix, QuadraticExtension

comment:3 Changed 3 years ago by mkoeppe

  • Dependencies set to #22658

comment:4 Changed 3 years ago by mkoeppe

  • Authors set to Matthias Koeppe

comment:5 Changed 3 years ago by git

  • Commit changed from 2f0e0594a0ce0d0342427f0d75ea1e7e4d9e13b3 to 218daca488ac24b80c6cea51b6e06fbf28c7874a

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

218dacaAdd Polyhedron_polymake

comment:6 Changed 3 years ago by git

  • Commit changed from 218daca488ac24b80c6cea51b6e06fbf28c7874a to 5ab94a2172c456509036a8dd5e77dbbe692c8635

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

5ab94a2Merge tag '7.6' into t/22683/backend_polymake_for_polyhedron

comment:7 Changed 3 years ago by mkoeppe

  • Status changed from new to needs_review

comment:8 Changed 3 years ago by tscrim

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.

comment:9 Changed 3 years ago by git

  • Commit changed from 5ab94a2172c456509036a8dd5e77dbbe692c8635 to 952b8607c9a4756cf35fe358e2718e33f04bb6b7

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

8fd81c7Polyhedron_polymake._polymake_: Add doctest
952b860PolymakeElement.__iter__: Doc fixes

comment:10 Changed 3 years ago by tscrim

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

Thank you.

comment:11 Changed 3 years ago by mkoeppe

Thanks for reviewing!

comment:12 Changed 3 years ago by tscrim

Not a problem; happy to help.

comment:13 Changed 3 years ago by fbissey

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.

comment:14 follow-up: Changed 3 years ago by tscrim

  • Status changed from positive_review to needs_work

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"?

comment:15 in reply to: ↑ 14 Changed 3 years ago by fbissey

  • Status changed from needs_work to positive_review

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].

comment:16 Changed 3 years ago by mkoeppe

Follow-up ticket at #22740.

comment:17 Changed 3 years ago by vbraun

  • Status changed from positive_review to needs_work

Documentation doesn't build

comment:18 Changed 3 years ago by git

  • Commit changed from 952b8607c9a4756cf35fe358e2718e33f04bb6b7 to 6d1774b1d460ab8927f127abf4abc36305baf674

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

b47f6f9Polyhedron_base._polymake_init_: Add work around for empty polytopes with Polymake 3.0
3b49a54Polymake: Fix another test whose error message depends on whether we use files
07a1757Polyhedron_base._polymake_init_: Fix comment
09942e7coercion tutorial: Update introspection results
19d05f1Add more 'optional - polymake
cd583e2Remove one unneccessary 'optional - polymake
7bcc04cMerge tag '8.0.beta0' into t/22658/polyhedron_methods_using_the_polymake_pexpect_interface
d7d4234Add '# optional - polymake'
4719102Merge remote-tracking branch 'trac/u/mkoeppe/polyhedron_methods_using_the_polymake_pexpect_interface' into t/22683/backend_polymake_for_polyhedron
6d1774bReference manual: Add backend_polymake

comment:19 Changed 3 years ago by mkoeppe

  • Status changed from needs_work to needs_review

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.

comment:20 Changed 3 years ago by tscrim

  • Status changed from needs_review to positive_review

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

comment:21 Changed 3 years ago by fbissey

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

comment:22 Changed 3 years ago by tscrim

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

comment:23 Changed 3 years ago by vbraun

  • Branch changed from u/mkoeppe/backend_polymake_for_polyhedron to 6d1774b1d460ab8927f127abf4abc36305baf674
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.