Opened 3 years ago

Closed 4 months ago

#27366 closed enhancement (fixed)

Polyhedron.affine_hull: more output options

Reported by: dkrenn Owned by:
Priority: major Milestone: sage-9.4
Component: geometry Keywords: polytope
Cc: jipilab, vdelecroix, gh-kliem Merged in:
Authors: Daniel Krenn, Matthias Koeppe, Jonathan Kliem Reviewers: Matthias Koeppe, Jonathan Kliem
Report Upstream: N/A Work issues:
Branch: eee1aad (Commits, GitHub, GitLab) Commit: eee1aadd98f1ef91f7a07bd478ac8613a83a94d7
Dependencies: #30551 Stopgaps:

Status badges

Description (last modified by mkoeppe)

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.

Change History (61)

comment:1 Changed 3 years ago by dkrenn

  • Branch set to u/dkrenn/affine-hull-more

comment:2 Changed 3 years ago by dkrenn

  • Commit set to 2075a6bc042a4e1bcf9941fa52e542fd29e76124
  • Dependencies set to #27329

New commits:

1ca3e2cTrac #27329: actually use **kwds as promised in docs
4efdb48Trac #27329: insert 3 whitespaces (PEP8)
74470e2Trac #27329: insert an additional doctest enhancing the readability of
9bedce6Trac #27366: new output parameters for affine_hull
2075a6bTrac #27366: use new parameter-options in .volume

comment:3 Changed 3 years ago by git

  • Commit changed from 2075a6bc042a4e1bcf9941fa52e542fd29e76124 to e9ed7ee67fc08c2368aac374fe126e9989f6271f

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

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

comment:4 Changed 3 years ago by git

  • Commit changed from e9ed7ee67fc08c2368aac374fe126e9989f6271f to 0cf6bc5b1307db2c4561c9b05babd9e0889e14e0

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

0cf6bc5Trac #27366: docstring fixup

comment:5 Changed 3 years ago by git

  • Commit changed from 0cf6bc5b1307db2c4561c9b05babd9e0889e14e0 to 2bbfdc2df0fb5a2ef869ce0c2bb13c7ef8e47d69

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

f8cb228Trac #27366 factor out parametric_form
8fa37dfTrac #27366 use new .parametric_form
294fbe1Trac #27366 output affine_map
6cf71c7Trac #27366 update .volume (to new parameter set)
477923bTrac #27366 compute coordinate images
2bbfdc2Trac #27366: update docs

comment:6 Changed 3 years ago by git

  • Commit changed from 2bbfdc2df0fb5a2ef869ce0c2bb13c7ef8e47d69 to 3c09477e154b426b44c23a754a19605b1a668951

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

3c09477Trac #27366: fix no-variables-bug-wrong-parent bug

comment:7 Changed 3 years ago by dkrenn

  • Status changed from new to needs_review

comment:8 Changed 3 years ago by git

  • Commit changed from 3c09477e154b426b44c23a754a19605b1a668951 to 3bdea15eafc77d3d9cd593933097934ae3d68f1b

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

82ad45bTrac #27366: cache affine hull
3bdea15Trac #27366: reintegrate parametric form and solve dimension bug

comment:9 Changed 3 years ago by embray

  • Milestone changed from sage-8.7 to sage-8.8

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

comment:10 Changed 2 years ago by embray

  • Milestone changed from sage-8.8 to sage-8.9

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

comment:11 Changed 2 years ago by chapoton

  • Status changed from needs_review to needs_work

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

comment:12 Changed 2 years ago by jipilab

  • Cc jipilab vdelecroix gh-kliem added

comment:13 Changed 2 years ago by jipilab

  • Keywords polytope added

comment:14 Changed 21 months ago by embray

  • Milestone changed from sage-8.9 to sage-9.1

Ticket retargeted after milestone closed

comment:15 Changed 18 months ago by mkoeppe

  • Milestone changed from sage-9.1 to sage-9.2

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

comment:16 Changed 13 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:17 Changed 8 months ago by mkoeppe

  • Milestone changed from sage-9.3 to sage-9.4

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

comment:18 Changed 6 months ago by mkoeppe

  • Branch changed from u/dkrenn/affine-hull-more to u/mkoeppe/affine-hull-more

comment:19 Changed 6 months ago by mkoeppe

  • Commit changed from 3bdea15eafc77d3d9cd593933097934ae3d68f1b to b407987152fe0d7683a5224d4ec51edc4863f72e

Merged with current develop.


New commits:

b407987Merge tag '9.3.rc2' into t/27366/affine-hull-more

comment:20 Changed 6 months ago by mkoeppe

  • Status changed from needs_work to needs_review

Untested so far...

comment:21 Changed 6 months ago by git

  • Commit changed from b407987152fe0d7683a5224d4ec51edc4863f72e to 7e0f31dedcf66d43ed4b15b5e62ab770b774f5f4

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

d25f7f3Fixup merge
7e0f31daffine_hull -> affine_hull_projection in doctests

comment:22 Changed 6 months ago by mkoeppe

  • Dependencies #27329 deleted

comment:23 Changed 6 months ago by git

  • Commit changed from 7e0f31dedcf66d43ed4b15b5e62ab770b774f5f4 to 58e6dcc12549380bc130b9dacebf42bba5ecec4b

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

58e6dccMerge tag '9.3.rc3' into t/27366/affine-hull-more

comment:24 Changed 6 months ago by git

  • Commit changed from 58e6dcc12549380bc130b9dacebf42bba5ecec4b to 84140398fe84337784834e13f5c4fc5cb73ab667

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

8414039Polyhedron_base.affine_hull_projection: Document a weaker guarantee of parametric_form

comment:25 Changed 6 months ago by mkoeppe

I plan to rework this so the output is a bit more straightforward.

We have affine_map, which is the projection that sends the affine hull (k-dimensional affine subspace of Rn) to Rk.

What's missing is simply its section map that sends back Rk to the affine hull.

I think both parametric_form and coordinate_images somehow represent this section map.

As the section map is affine linear, we should represent it in the same way as affine_map: A linear transformation and a shift.

Last edited 6 months ago by mkoeppe (previous) (diff)

comment:26 Changed 6 months ago by git

  • Commit changed from 84140398fe84337784834e13f5c4fc5cb73ab667 to dba27635d03a6453c07a884199d2f2062aea8ad9

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

dba2763Polyhedron_base.affine_hull_projection: Replace 'affine_map' by 'projection_map', 'parametric_form'/'coordinate_images' by 'section_map'

comment:27 Changed 6 months ago by mkoeppe

  • Authors changed from Daniel Krenn to Daniel Krenn, Matthias Koeppe
  • Status changed from needs_review to needs_work

For the non-orthogonal case, the section_map still needs to be computed.

But comments are already welcome

comment:28 Changed 6 months ago by git

  • Commit changed from dba27635d03a6453c07a884199d2f2062aea8ad9 to d49c3136036a247843d4a2b9e83c320ce01f05c5

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

d49c313Polyhedron_base.affine_hull_projection: section map for non-orthogonal case

comment:29 Changed 6 months ago by git

  • Commit changed from d49c3136036a247843d4a2b9e83c320ce01f05c5 to d77181b4e6da158661dea4a4fc37269d58489ada

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

d77181bAdd doctest

comment:30 Changed 6 months ago by mkoeppe

  • Description modified (diff)
  • Status changed from needs_work to needs_review

comment:31 Changed 6 months ago by mkoeppe

  • Status changed from needs_review to needs_work

Still some issues with algebraic numbers:

sage: D = polytopes.dodecahedron()
sage: D.facets()[0].as_polyhedron().affine_hull_projection()                                                                       
A 2-dimensional polyhedron in (Number Field in sqrt5 with defining polynomial x^2 - 5 with sqrt5 = 2.236067977499790?)^2 defined as the convex hull of 5 vertices
sage: D.facets()[0].as_polyhedron().affine_hull_projection(return_all_data=True)  
TypeError: (-sqrt5 + 1, -2*sqrt5 + 4, 0) fails to convert into the map's domain Vector space of dimension 3 over Rational Field, but a `pushforward` method is not properly implemented

comment:32 Changed 6 months ago by gh-kliem

I have a fix almost ready and added a test method.

However, there is going to be one more ticket in the dependency chain:

sage: D = polytopes.dodecahedron()                                                                                                                                                  
sage: D.change_ring(AA) == D                                                                                                                                                        
False

comment:33 Changed 6 months ago by gh-kliem

The behavior is actually consistent with rings, I still don't like it.

Looks, like this is related to #4621:

sage: D = polytopes.dodecahedron()                                                                                                                                                  
sage: D.base_ring()                                                                                                                                                                 
Number Field in sqrt5 with defining polynomial x^2 - 5 with sqrt5 = 2.236067977499790?
sage: sqrt5 = D.base_ring().gens()[0]                                                                                                                                               
sage: sqrt5 == AA(sqrt5)                                                                                                                                                            
False
sage: 0*sqrt5 == AA(0)                                                                                                                                                              
False

This is extremely stupid. At least it should throw an error instead of giving a false negative. But its pointless to be fixed here.

Edit: I realized that equality checks should never throw an error. So it is really hard to do the right thing here. The base ring of algebraic polyhedra has a specified embedding into RLF, which makes it incomparable with AA.

Last edited 6 months ago by gh-kliem (previous) (diff)

comment:34 Changed 6 months ago by gh-kliem

  • Authors changed from Daniel Krenn, Matthias Koeppe to Daniel Krenn, Matthias Koeppe, Jonathan Kliem

Unfortunately, it is still at "needs work".

The test suite fails for polytopes.Birkhoff(3) terribly (the section map has incorrect rank).

It also fails for the 0-dimensional polyhedron, but maybe that is just the way it is.

It fails for unbounded polyhedron, in particular Polyhedron(rays=[[0, 1]]).

comment:35 Changed 6 months ago by gh-kliem

  • Branch changed from u/mkoeppe/affine-hull-more to u/gh-kliem/affine-hull-more
  • Commit changed from d77181b4e6da158661dea4a4fc37269d58489ada to 69ceebcca7df21e39a4ab1bb719cdfaea9b6986d

New commits:

ab10ce2correct base_rings for projection and section map and test suite method
69ceebcbase extend in test; only run defined tests

comment:36 Changed 6 months ago by mkoeppe

Thanks a lot! Great idea to add the test method

comment:37 Changed 6 months ago by gh-kliem

I started adding doctests and I realized that they are extremely long and nobody is actually going to check them...

comment:38 Changed 6 months ago by mkoeppe

  • Branch changed from u/gh-kliem/affine-hull-more to u/mkoeppe/affine-hull-more

comment:39 Changed 6 months ago by git

  • Commit changed from 69ceebcca7df21e39a4ab1bb719cdfaea9b6986d to 9629620ed8e4e824adace4a7f867059961fce877

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

9629620Polyhedron_base.affine_hull_projection: Fix up use of echelong form

comment:40 Changed 6 months ago by mkoeppe

  • Status changed from needs_work to needs_review

comment:41 Changed 6 months ago by mkoeppe

  • Reviewers set to Matthias Koeppe, ...

comment:42 Changed 6 months ago by git

  • Commit changed from 9629620ed8e4e824adace4a7f867059961fce877 to 8c24c5c3590df6dbdf033e7a3c936941e4ff2caa

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

8c24c5cPolyhedron_base.affine_hull_projection: Remove last occurrence of 'parametric_form'

comment:43 Changed 6 months ago by gh-kliem

There is still a doctest that fails terribly. (After fixing an incorrect doctest that I will push in a minute).

sage: p = data['polyhedron'].linear_transformation(data['section_map'][0].matrix().transpose()) + data['section_map'][1]                                                            
sage: p = Polyhedron([(0,0)], base_ring=RDF)                                                                                                                                        
sage: data = p.affine_hull_projection(return_all_data=True, orthogonal=True, extend=True)                                                                                           
sage: p1 = data['polyhedron'].linear_transformation(data['section_map'][0].matrix().transpose()) + data['section_map'][1]                                                           
sage: p1 == p                                                                                                                                                                       
True
sage: p1 = data['polyhedron'].linear_transformation(data['section_map'][0].matrix().transpose()) + data['section_map'][1]                
sage: p1 == p                                                         
True

Somehow linear transformation applied to a 0-dimensional polyhedron isn't stable. The problem really seems to be connected to underlying matrices:

sage: p = Polyhedron([(0,0)], base_ring=RDF)                                                                                                                                        
sage: data = p.affine_hull_projection(return_all_data=True, orthogonal=True, extend=True)                                                                                           
sage: M = data['section_map'][0].matrix().transpose()                                                                                                                               
sage: V = data['polyhedron'].vertices_matrix()                                                                                                                                      
sage: M*V                                                                                                                                                                           
[3.445383e-316]
[          0.0]
sage: M*V                                                                                                                                                                           
[3.445383e-316]
[          0.0]
sage: M*V                                                                                                                                                                           
[3.17525635e-316]
[            0.0]
sage: p1 = data['polyhedron'].linear_transformation(data['section_map'][0].matrix().transpose()) + data['section_map'][1]                                                           
sage: M*V                                                                                                                                                                           
[0.0]
[0.0]
sage: M*V                                                                                                                                                                           
[1.0]
[0.0]
sage: M*V                                                                                                                                                                           
[0.0]
[1.0]
sage: M*V                                                                                                                                                                           
[0.0]
[0.0]
sage: M*V                                                                                                                                                                           
[0.0]
[0.0]

Apparently, the content of the matrix is never initialized. You might say that multiplication of those matrices isn't well-defined. However, if you think of this as linear maps, there is only one linear map from RLF^0 to RLF^2.

comment:44 Changed 6 months ago by gh-kliem

  • Branch changed from u/mkoeppe/affine-hull-more to u/gh-kliem/affine-hull-more
  • Commit changed from 8c24c5c3590df6dbdf033e7a3c936941e4ff2caa to f9faa025d7598c07549691ef9c6c922d31caeb8d

Ok, seems to work now.

Fixing the problem with real matrices was actually quite easy. The matrix was not initialized as I thought. Should I open a seperate ticket for this?


New commits:

9f5560ainitialize empty matrix after trivial multiplication
f9faa02minimal extension only avoid AA if the base ring is not already AA

comment:45 Changed 5 months ago by mkoeppe

Thanks for fixing this! I think it's fine to keep it on this ticket

comment:46 Changed 5 months ago by mkoeppe

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

comment:47 Changed 5 months ago by mkoeppe

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

comment:48 Changed 5 months ago by mkoeppe

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

comment:49 Changed 5 months ago by mkoeppe

  • Branch changed from u/gh-kliem/affine-hull-more to u/mkoeppe/affine-hull-more

comment:50 Changed 5 months ago by git

  • Commit changed from f9faa025d7598c07549691ef9c6c922d31caeb8d to 57fd3e185cf891c27fe93cde9fe9cabb9290468d

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

57fd3e1Fixup doctest formatting

comment:51 Changed 5 months ago by gh-kliem

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

comment:52 Changed 5 months ago by mkoeppe

  • Dependencies set to #30551

comment:53 Changed 5 months ago by mkoeppe

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

comment:54 Changed 5 months ago by mkoeppe

I have opened #31705 for the lazy import improvements

comment:55 Changed 5 months ago by gh-kliem

  • Status changed from needs_review to needs_work
                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

comment:56 Changed 5 months ago by gh-kliem

  • Branch changed from u/mkoeppe/affine-hull-more to u/gh-kliem/affine-hull-more
  • Commit changed from 57fd3e185cf891c27fe93cde9fe9cabb9290468d to b17aa8ca5cd80b6895b0d4442c2e473c34b96f29

New commits:

b17aa8cadd another doctest

comment:57 Changed 5 months ago by git

  • Commit changed from b17aa8ca5cd80b6895b0d4442c2e473c34b96f29 to eee1aadd98f1ef91f7a07bd478ac8613a83a94d7

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

eee1aadfix section map

comment:58 Changed 5 months ago by gh-kliem

  • Status changed from needs_work to needs_review

comment:59 Changed 5 months ago by gh-kliem

  • Reviewers changed from Matthias Koeppe, ... to Matthias Koeppe, Jonathan Kliem

I'm happy with it now.

comment:60 Changed 5 months ago by mkoeppe

  • Keywords removed
  • Status changed from needs_review to positive_review

Thanks a lot for finding this elegant fix.

comment:61 Changed 4 months ago by vbraun

  • Branch changed from u/gh-kliem/affine-hull-more to eee1aadd98f1ef91f7a07bd478ac8613a83a94d7
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.