Polyhedron.affine_hull: more output options

[dkrenn]

At the moment when calling .affine_hull, either the polyhedron or the affine map can be returned. If both needed, parts need to be recomputed, so we extend the parameters to allow returning both at the same time.

Moreover, we also allow to additionally return the section map, i.e., the right inverse of the projection map. This is a preparation for #27365 and #31659.

Depends on #30551

CC: @jplab @videlec @kliem

Component: geometry

Keywords: polytope

Author: Daniel Krenn, Matthias Koeppe, Jonathan Kliem

Branch/Commit: eee1aad

Reviewer: Matthias Koeppe, Jonathan Kliem

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

[dkrenn]

Branch: u/dkrenn/affine-hull-more

[dkrenn]

Commit: 2075a6b

[dkrenn]

New commits:

1ca3e2c	Trac #27329: actually use **kwds as promised in docs
4efdb48	Trac #27329: insert 3 whitespaces (PEP8)
74470e2	Trac #27329: insert an additional doctest enhancing the readability of
9bedce6	Trac #27366: new output parameters for affine_hull
2075a6b	Trac #27366: use new parameter-options in .volume

[dkrenn]

Dependencies: #27329

[sagetrac-git]

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

e9ed7ee

Trac #27366: fixup (lines forgotten to commit in ~2)

[sagetrac-git]

Changed commit from 2075a6b to e9ed7ee

[sagetrac-git]

Changed commit from e9ed7ee to 0cf6bc5

[sagetrac-git]

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

0cf6bc5

Trac #27366: docstring fixup

[sagetrac-git]

Changed commit from 0cf6bc5 to 2bbfdc2

[sagetrac-git]

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

f8cb228	Trac #27366 factor out parametric_form
8fa37df	Trac #27366 use new .parametric_form
294fbe1	Trac #27366 output affine_map
6cf71c7	Trac #27366 update .volume (to new parameter set)
477923b	Trac #27366 compute coordinate images
2bbfdc2	Trac #27366: update docs

[sagetrac-git]

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

3c09477

Trac #27366: fix no-variables-bug-wrong-parent bug

[sagetrac-git]

Changed commit from 2bbfdc2 to 3c09477

[sagetrac-git]

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

82ad45b	Trac #27366: cache affine hull
3bdea15	Trac #27366: reintegrate parametric form and solve dimension bug

[sagetrac-git]

Changed commit from 3c09477 to 3bdea15

[embray]

comment:9

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)

[embray]

comment:10

Moving tickets from the Sage 8.8 milestone that have been actively worked on in the last six months to the next release milestone (optimistically).

[fchapoton]

comment:11

red branch, needs to be rebased on top of the latest beta

[jplab]

Changed keywords from none to polytope

[embray]

comment:14

Ticket retargeted after milestone closed

[mkoeppe]

comment:46

Green patchbot.

But we may want to consider making the result a dataclass (https://docs.python.org/3/library/dataclasses.html) instead of a dictionary

[mkoeppe]

comment:47

(depends on #30551 - Drop Python 3.6 support - which is planned for 9.4 anyway)

[mkoeppe]

comment:48

from dataclasses import dataclass
from typing import Any
@dataclass
class AffineHullProjectionData:
   polyhedron: Any
   projection_linear_map: Any
   projection_translation: Any
   section_linear_map: Any
   section_translation: Any

Note, unpacking the pairs -- this would be future-proof in case we ever decide to add proper affine linear maps to Sage

[mkoeppe]

Changed branch from u/gh-kliem/affine-hull-more to u/mkoeppe/affine-hull-more

[sagetrac-git]

Changed commit from f9faa02 to 57fd3e1

[sagetrac-git]

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

57fd3e1

Fixup doctest formatting

[kliem]

comment:51

This ticket should depend now on #30551, right?

Apparently sage.geometry.polyhedron.base is a startup module, which is terrible. I chased it down and it seems one needs to do a series of lazy/more careful imports.

• It starts with sage/schemes/toric/all.py, which just imports a everything right away.

• sage/schemes/toric/variety.py imports Cone, is_Cone. Both of them are only needed twice in the entire module and not even in popular places, it seems. (There are other places where is_Cone is just imported in the module, although it is only used in special methods.

• sage/geometry/all.py could just do a lot more lazy imports (I think all of them should be lazy).

• sage/geometry/cone.py could use a lot more careful imports. E.g. FinitePoset is imported, but it is only used for the face lattice. In particular the function is_Cone could live without all those imports. If your object isn't a cone, you probably won't need them anyway.

  In particular it imports is_Polyhedron in sage.geometry.polyhedron.base.

• Again sage/geometry/polyhedron/base.py imports a lot of stuff that is definetly not needed for is_Polyhedron.

Adding some lazy imports above, I can avoid the import of `sage.geometry.polyhedron.base'.

[mkoeppe]

Dependencies: #30551

[mkoeppe]

comment:53

Yes, I've added the dependency. But I don't think we need to merge in the branch of that.

[mkoeppe]

comment:54

I have opened #31705 for the lazy import improvements

[kliem]

comment:55

                L_section = linear_transformation(matrix(len(pivots), self.ambient_dim(),
                                                         [E[i] for i in range(len(pivots))]).transpose(),
                                                  side='right')

This is not always an inverse to A:

sage: set_random_seed(0)                                                                                                              
sage: M = random_matrix(ZZ, 5, 5, distribution='uniform')                                                                             
sage: while True: 
....:     M = random_matrix(ZZ, 5, 5, distribution='uniform')   
....:     if M.rank() != 5: 
....:         break 
....:                                                                                                                                 
sage: P = Polyhedron(M)                                                                                                               
sage: P._test_affine_hull_projection()                                                                                                
---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-23-f3c92d590b2b> in <module>
----> 1 P._test_affine_hull_projection()

~/Applications/sage/local/lib/python3.8/site-packages/sage/geometry/polyhedron/base.py in _test_affine_hull_projection(self, tester, verbose, **options)
  10487             else:
  10488                 self_extend = self
> 10489             tester.assertEqual(data.polyhedron.linear_transformation(M)
  10490                                + data.section_translation,
  10491                                self_extend)

/usr/lib/python3.8/unittest/case.py in assertEqual(self, first, second, msg)
    910         """
    911         assertion_func = self._getAssertEqualityFunc(first, second)
--> 912         assertion_func(first, second, msg=msg)
    913 
    914     def assertNotEqual(self, first, second, msg=None):

/usr/lib/python3.8/unittest/case.py in _baseAssertEqual(self, first, second, msg)
    903             standardMsg = '%s != %s' % _common_shorten_repr(first, second)
    904             msg = self._formatMessage(msg, standardMsg)
--> 905             raise self.failureException(msg)
    906 
    907     def assertEqual(self, first, second, msg=None):

AssertionError: A 4-dimensional polyhedron in QQ^5 defined as the convex hull of 5 vertices != A 4-dimensional polyhedron in ZZ^5 defined as the convex hull of 5 vertices

[kliem]

Changed branch from u/mkoeppe/affine-hull-more to u/gh-kliem/affine-hull-more

[kliem]

Changed commit from 57fd3e1 to b17aa8c

[kliem]

New commits:

b17aa8c

add another doctest

[sagetrac-git]

Changed commit from b17aa8c to eee1aad

[sagetrac-git]

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

eee1aad

fix section map

[kliem]

Changed reviewer from Matthias Koeppe, ... to Matthias Koeppe, Jonathan Kliem

[kliem]

comment:59

I'm happy with it now.

[mkoeppe]

comment:60

Thanks a lot for finding this elegant fix.

[vbraun]

Changed branch from u/gh-kliem/affine-hull-more to eee1aad