Polyhedron(backend='number_field')

[mkoeppe]

(from #33752)

We lift the conversion code that sends symbolic and AA elements to a suitable embedded number field and back from the backend normaliz and create a new backend number_field, which just runs backend field on the converted number field elements.

This results in rather general (but slow) polyhedral code for algebraic data in pure Python.

Depends on #34195

CC: @yuan-zhou @kliem @jplab @videlec @tscrim

Component: geometry

Author: Matthias Koeppe, Yuan Zhou

Branch/Commit: c729884

Reviewer: Matthias Koeppe, Travis Scrimshaw

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

[mkoeppe]

Branch: u/mkoeppe/polyhedron_backend__number_field__

[sagetrac-git]

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

7ff3df5

src/sage/geometry/polyhedron/{base,backend}_number_field.py: New, move some code here from backend_normaliz

[sagetrac-git]

Commit: 7ff3df5

[mkoeppe]

Author: Matthias Koeppe, ...

[mkoeppe]

Dependencies: #34195

[sagetrac-git]

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

278b93f	sage.geometry: More # optional - sage.rings.number_field
0f12ac2	src/sage/geometry/polyhedron/base0.py: Restore lost imports
74bc04b	src/sage/geometry/polyhedron/base{3,6}.py: Muffle pyflakes warnings about unused imports
7db47e1	src/sage/geometry/polyhedron/parent.py: Muffle pyflakes warning
6dd4f07	src/sage/geometry/polyhedron/base.py: Remove unused import
1ede214	src/sage/geometry/polyhedron/backend_normaliz.py: Add missing imports
341475c	src/sage/geometry/polyhedron/base_ZZ.py: Replace .all import
dd87ab9	Merge tag '9.7.rc0' into t/34195/sage_geometry_polyhedron__more___optional___sage_rings_number_field
f12e71c	Merge #34195
ffe0fda	Fix remaining imports

[sagetrac-git]

Changed commit from 7ff3df5 to ffe0fda

[sagetrac-git]

Changed commit from ffe0fda to 4a84278

[sagetrac-git]

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

4a84278

src/sage/geometry/polyhedron/parent.py: Add Polyhedra_number_field

[sagetrac-git]

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

58218d2

src/sage/geometry/polyhedron/backend_number_field.py: Add stubs for methods in which conversion needs to be called

[sagetrac-git]

Changed commit from 4a84278 to 58218d2

[sheerluck]

comment:10

assert polymake_base_field # to muffle pyflakes breaks polymake tests

My workaround is

     elif backend == 'polymake':
         base_field = base_ring.fraction_field()
         try:
-            from sage.interfaces.polymake import polymake
+            from sage.interfaces.polymake import polymake, PolymakeElement
             polymake_base_field = polymake(base_field)
+            assert isinstance(polymake_base_field, PolymakeElement)  # to muffle pyflakes
         except TypeError:

[mkoeppe]

comment:11

Thanks for catching this. This is actually from #34195

[yuan-zhou]

Changed branch from u/mkoeppe/polyhedron_backend__number_field__ to u/yzh/polyhedron_backend__number_field__

[sagetrac-git]

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

805b8b7

transform data to number field

[sagetrac-git]

Changed commit from 58218d2 to 805b8b7

[yuan-zhou]

Changed author from Matthias Koeppe, ... to Matthias Koeppe, Yuan Zhou

[mkoeppe]

comment:15

Probably _compute_nmz_data_lists_and_field should be renamed

[mkoeppe]

comment:16

     def _init_from_Vrepresentation(self, vertices, rays, lines,
-                                   minimize=True, verbose=False):
+                                   minimize=True, verbose=False, number_field=None):

Also this new parameter should probably not be called number_field but rather internal_base_ring or something like this.

That we use a number field for the computation is specific to the new subclass Polyhedron_number_field. (Later, another subclass could be using SymbolicValuesRing from #30234.)

[mkoeppe]

Changed branch from u/yzh/polyhedron_backend__number_field__ to u/mkoeppe/polyhedron_backend__number_field__

[mkoeppe]

Changed commit from 805b8b7 to ad74e4d

[mkoeppe]

New commits:

ad74e4d

polyopes.generalized_polyhedron: Restructure doctests, add backend='number_field' tests

[yuan-zhou]

comment:19

How about renaming it to _compute_data_lists_and_internal_base_ring?
Replying to Matthias Köppe:

Probably _compute_nmz_data_lists_and_field should be renamed

[yuan-zhou]

comment:20

Sounds good. I notice that backend_normaliz.py has a similar attribute self._normaliz_field = normaliz_field, which is not always a field. Do we need to change that too?

Replying to Matthias Köppe:

     def _init_from_Vrepresentation(self, vertices, rays, lines,
-                                   minimize=True, verbose=False):
+                                   minimize=True, verbose=False, number_field=None):

Also this new parameter should probably not be called number_field but rather internal_base_ring or something like this.

That we use a number field for the computation is specific to the new subclass Polyhedron_number_field. (Later, another subclass could be using SymbolicValuesRing from #30234.)

[mkoeppe]

comment:21

Replying to Yuan Zhou:

How about renaming it to _compute_data_lists_and_internal_base_ring?

Sounds good

[mkoeppe]

comment:22

Replying to Yuan Zhou:

backend_normaliz.py has a similar attribute self._normaliz_field = normaliz_field, which is not always a field. Do we need to change that too?

Probably a good idea to rename it too

[yuan-zhou]

Changed branch from u/mkoeppe/polyhedron_backend__number_field__ to u/yzh/polyhedron_backend__number_field__

[yuan-zhou]

Changed commit from ad74e4d to 1a9dd70

[yuan-zhou]

comment:24

Renamed.

---

New commits:

8380bb1	rename _compute_nmz_data_lists_and_field to _compute_data_lists_and_internal_base_ring
6b661a1	rename number_field in the output of Polyhedron_base_number_field._compute_data_lists_and_internal_base_ring to internal_base_ring
278f6a7	rename variables inside _compute_data_lists_and_internal_base_ring
1a9dd70	rename normaliz_field to internal_base_ring

[sagetrac-git]

Changed commit from 1a9dd70 to 60516e7

[sagetrac-git]

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

60516e7

fix a typo

[mkoeppe]

Changed branch from u/yzh/polyhedron_backend__number_field__ to u/mkoeppe/polyhedron_backend__number_field__

[mkoeppe]

Changed commit from 60516e7 to 3eb2cc3

[mkoeppe]

comment:27

This works well

---

New commits:

3eb2cc3

src/sage/geometry/polyhedron: Fix typos, reformat doctests

[mkoeppe]

Reviewer: ..., Matthias Koeppe

[sagetrac-git]

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

bc7aba3

src/doc/en/reference/discrete_geometry/index.rst: Add backend_number_field

[sagetrac-git]

Changed commit from 3eb2cc3 to bc7aba3

[sagetrac-git]

Changed commit from bc7aba3 to c729884

[sagetrac-git]

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

c729884

src/sage/geometry/polyhedron/backend_number_field.py: Fix doc markup

[tscrim]

comment:31

I would be happy to mark it as a positive review once the patchbot comes back green. If anyone has any objections before that, please do so.

[tscrim]

Changed reviewer from ..., Matthias Koeppe to Matthias Koeppe, Travis Scrimshaw

[mkoeppe]

comment:33

All green, Lint failures unrelated.

[vbraun]

Changed branch from u/mkoeppe/polyhedron_backend__number_field__ to c729884