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:  sage9.4 
Component:  geometry  Keywords:  polytope 
Cc:  jipilab, vdelecroix, ghkliem  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: 
Description (last modified by )
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
 Branch set to u/dkrenn/affinehullmore
comment:2 Changed 3 years ago by
 Commit set to 2075a6bc042a4e1bcf9941fa52e542fd29e76124
 Dependencies set to #27329
comment:3 Changed 3 years ago by
 Commit changed from 2075a6bc042a4e1bcf9941fa52e542fd29e76124 to e9ed7ee67fc08c2368aac374fe126e9989f6271f
Branch pushed to git repo; I updated commit sha1. New commits:
e9ed7ee  Trac #27366: fixup (lines forgotten to commit in ~2)

comment:4 Changed 3 years ago by
 Commit changed from e9ed7ee67fc08c2368aac374fe126e9989f6271f to 0cf6bc5b1307db2c4561c9b05babd9e0889e14e0
Branch pushed to git repo; I updated commit sha1. New commits:
0cf6bc5  Trac #27366: docstring fixup

comment:5 Changed 3 years ago by
 Commit changed from 0cf6bc5b1307db2c4561c9b05babd9e0889e14e0 to 2bbfdc2df0fb5a2ef869ce0c2bb13c7ef8e47d69
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

comment:6 Changed 3 years ago by
 Commit changed from 2bbfdc2df0fb5a2ef869ce0c2bb13c7ef8e47d69 to 3c09477e154b426b44c23a754a19605b1a668951
Branch pushed to git repo; I updated commit sha1. New commits:
3c09477  Trac #27366: fix novariablesbugwrongparent bug

comment:7 Changed 3 years ago by
 Status changed from new to needs_review
comment:8 Changed 3 years ago by
 Commit changed from 3c09477e154b426b44c23a754a19605b1a668951 to 3bdea15eafc77d3d9cd593933097934ae3d68f1b
comment:9 Changed 3 years ago by
 Milestone changed from sage8.7 to sage8.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
 Milestone changed from sage8.8 to sage8.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
 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
 Cc jipilab vdelecroix ghkliem added
comment:13 Changed 2 years ago by
 Keywords polytope added
comment:14 Changed 21 months ago by
 Milestone changed from sage8.9 to sage9.1
Ticket retargeted after milestone closed
comment:15 Changed 18 months ago by
 Milestone changed from sage9.1 to sage9.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
 Milestone changed from sage9.2 to sage9.3
comment:17 Changed 8 months ago by
 Milestone changed from sage9.3 to sage9.4
Setting new milestone based on a cursory review of ticket status, priority, and last modification date.
comment:18 Changed 6 months ago by
 Branch changed from u/dkrenn/affinehullmore to u/mkoeppe/affinehullmore
comment:19 Changed 6 months ago by
 Commit changed from 3bdea15eafc77d3d9cd593933097934ae3d68f1b to b407987152fe0d7683a5224d4ec51edc4863f72e
comment:20 Changed 6 months ago by
 Status changed from needs_work to needs_review
Untested so far...
comment:21 Changed 6 months ago by
 Commit changed from b407987152fe0d7683a5224d4ec51edc4863f72e to 7e0f31dedcf66d43ed4b15b5e62ab770b774f5f4
comment:22 Changed 6 months ago by
 Dependencies #27329 deleted
comment:23 Changed 6 months ago by
 Commit changed from 7e0f31dedcf66d43ed4b15b5e62ab770b774f5f4 to 58e6dcc12549380bc130b9dacebf42bba5ecec4b
Branch pushed to git repo; I updated commit sha1. New commits:
58e6dcc  Merge tag '9.3.rc3' into t/27366/affinehullmore

comment:24 Changed 6 months ago by
 Commit changed from 58e6dcc12549380bc130b9dacebf42bba5ecec4b to 84140398fe84337784834e13f5c4fc5cb73ab667
Branch pushed to git repo; I updated commit sha1. New commits:
8414039  Polyhedron_base.affine_hull_projection: Document a weaker guarantee of parametric_form

comment:25 Changed 6 months ago by
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 (kdimensional affine subspace of R^{n}) to R^{k}.
What's missing is simply its section map that sends back R^{k} 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.
comment:26 Changed 6 months ago by
 Commit changed from 84140398fe84337784834e13f5c4fc5cb73ab667 to dba27635d03a6453c07a884199d2f2062aea8ad9
Branch pushed to git repo; I updated commit sha1. New commits:
dba2763  Polyhedron_base.affine_hull_projection: Replace 'affine_map' by 'projection_map', 'parametric_form'/'coordinate_images' by 'section_map'

comment:27 Changed 6 months ago by
 Status changed from needs_review to needs_work
For the nonorthogonal case, the section_map
still needs to be computed.
But comments are already welcome
comment:28 Changed 6 months ago by
 Commit changed from dba27635d03a6453c07a884199d2f2062aea8ad9 to d49c3136036a247843d4a2b9e83c320ce01f05c5
Branch pushed to git repo; I updated commit sha1. New commits:
d49c313  Polyhedron_base.affine_hull_projection: section map for nonorthogonal case

comment:29 Changed 6 months ago by
 Commit changed from d49c3136036a247843d4a2b9e83c320ce01f05c5 to d77181b4e6da158661dea4a4fc37269d58489ada
Branch pushed to git repo; I updated commit sha1. New commits:
d77181b  Add doctest

comment:30 Changed 6 months ago by
 Description modified (diff)
 Status changed from needs_work to needs_review
comment:31 Changed 6 months ago by
 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 2dimensional 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
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
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
.
comment:34 Changed 6 months ago by
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 0dimensional 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
 Branch changed from u/mkoeppe/affinehullmore to u/ghkliem/affinehullmore
 Commit changed from d77181b4e6da158661dea4a4fc37269d58489ada to 69ceebcca7df21e39a4ab1bb719cdfaea9b6986d
comment:36 Changed 6 months ago by
Thanks a lot! Great idea to add the test method
comment:37 Changed 6 months ago by
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
 Branch changed from u/ghkliem/affinehullmore to u/mkoeppe/affinehullmore
comment:39 Changed 6 months ago by
 Commit changed from 69ceebcca7df21e39a4ab1bb719cdfaea9b6986d to 9629620ed8e4e824adace4a7f867059961fce877
Branch pushed to git repo; I updated commit sha1. New commits:
9629620  Polyhedron_base.affine_hull_projection: Fix up use of echelong form

comment:40 Changed 6 months ago by
 Status changed from needs_work to needs_review
comment:41 Changed 6 months ago by
 Reviewers set to Matthias Koeppe, ...
comment:42 Changed 6 months ago by
 Commit changed from 9629620ed8e4e824adace4a7f867059961fce877 to 8c24c5c3590df6dbdf033e7a3c936941e4ff2caa
Branch pushed to git repo; I updated commit sha1. New commits:
8c24c5c  Polyhedron_base.affine_hull_projection: Remove last occurrence of 'parametric_form'

comment:43 Changed 6 months ago by
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 0dimensional 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.445383e316] [ 0.0] sage: M*V [3.445383e316] [ 0.0] sage: M*V [3.17525635e316] [ 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 welldefined. 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
 Branch changed from u/mkoeppe/affinehullmore to u/ghkliem/affinehullmore
 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:
9f5560a  initialize empty matrix after trivial multiplication

f9faa02  minimal extension only avoid AA if the base ring is not already AA

comment:45 Changed 5 months ago by
Thanks for fixing this! I think it's fine to keep it on this ticket
comment:46 Changed 5 months ago by
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
(depends on #30551  Drop Python 3.6 support  which is planned for 9.4 anyway)
comment:48 Changed 5 months ago by
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 futureproof in case we ever decide to add proper affine linear maps to Sage
comment:49 Changed 5 months ago by
 Branch changed from u/ghkliem/affinehullmore to u/mkoeppe/affinehullmore
comment:50 Changed 5 months ago by
 Commit changed from f9faa025d7598c07549691ef9c6c922d31caeb8d to 57fd3e185cf891c27fe93cde9fe9cabb9290468d
Branch pushed to git repo; I updated commit sha1. New commits:
57fd3e1  Fixup doctest formatting

comment:51 Changed 5 months ago by
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
importsCone, 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 whereis_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 functionis_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
insage.geometry.polyhedron.base
.
 Again
sage/geometry/polyhedron/base.py
imports a lot of stuff that is definetly not needed foris_Polyhedron
.
Adding some lazy imports above, I can avoid the import of `sage.geometry.polyhedron.base'.
comment:52 Changed 5 months ago by
 Dependencies set to #30551
comment:53 Changed 5 months ago by
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
I have opened #31705 for the lazy import improvements
comment:55 Changed 5 months ago by
 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) <ipythoninput23f3c92d590b2b> in <module> > 1 P._test_affine_hull_projection() ~/Applications/sage/local/lib/python3.8/sitepackages/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 4dimensional polyhedron in QQ^5 defined as the convex hull of 5 vertices != A 4dimensional polyhedron in ZZ^5 defined as the convex hull of 5 vertices
comment:56 Changed 5 months ago by
 Branch changed from u/mkoeppe/affinehullmore to u/ghkliem/affinehullmore
 Commit changed from 57fd3e185cf891c27fe93cde9fe9cabb9290468d to b17aa8ca5cd80b6895b0d4442c2e473c34b96f29
New commits:
b17aa8c  add another doctest

comment:57 Changed 5 months ago by
 Commit changed from b17aa8ca5cd80b6895b0d4442c2e473c34b96f29 to eee1aadd98f1ef91f7a07bd478ac8613a83a94d7
Branch pushed to git repo; I updated commit sha1. New commits:
eee1aad  fix section map

comment:58 Changed 5 months ago by
 Status changed from needs_work to needs_review
comment:59 Changed 5 months ago by
 Reviewers changed from Matthias Koeppe, ... to Matthias Koeppe, Jonathan Kliem
I'm happy with it now.
comment:60 Changed 5 months ago by
 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
 Branch changed from u/ghkliem/affinehullmore to eee1aadd98f1ef91f7a07bd478ac8613a83a94d7
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Trac #27329: actually use **kwds as promised in docs
Trac #27329: insert 3 whitespaces (PEP8)
Trac #27329: insert an additional doctest enhancing the readability of
Trac #27366: new output parameters for affine_hull
Trac #27366: use new parameteroptions in .volume