Opened 9 months ago
Closed 6 weeks ago
#30319 closed defect (fixed)
Upgrade cddlib to fix wrong intersection of polytopes
Reported by:  vdelecroix  Owned by:  

Priority:  blocker  Milestone:  sage9.3 
Component:  geometry  Keywords:  
Cc:  jipilab, mkoeppe, dimpase, vbraun  Merged in:  
Authors:  Jonathan Kliem, Matthias Koeppe  Reviewers:  Matthias Koeppe, Dima Pasechnik 
Report Upstream:  Fixed upstream, in a later stable release.  Work issues:  
Branch:  167c832 (Commits, GitHub, GitLab)  Commit:  167c83211f146c119ec377cf00e3b872a6d305d6 
Dependencies:  Stopgaps: 
Description (last modified by )
As reported in this sagedevel thread, the intersection of polytopes is sometimes very wrong
a = Polyhedron([[0, 1, 1], [1, 1, 1], [1, 1, 1]]) b = Polyhedron([[0.0, 0.5, 1.5], [1.0, 0.5, 1.5], [1.0, 1.5, 0.5]]) c = a.intersection(b)
Here c
should have been empty but is equal to b
.
We fix it by upgrading to cddlib 0.94m, installing symlinks so that consumers of cddlib that have not been updated to work with the new header file locations (#29413) continue to work.
Change History (55)
comment:1 Changed 9 months ago by
 Priority changed from major to critical
comment:2 Changed 9 months ago by
comment:3 Changed 9 months ago by
 Report Upstream changed from N/A to Not yet reported upstream; Will do shortly.
Could someone please report it upstream (i do not have a github account) ?
comment:4 Changed 9 months ago by
 Report Upstream changed from Not yet reported upstream; Will do shortly. to Reported upstream. No feedback yet.
comment:5 Changed 8 months ago by
Note that with data in comment:2 one has
sage: Polyhedron(eqns=new_eqns) The empty polyhedron in RDF^3
so the emptiness should have been detected earlier.
comment:6 Changed 8 months ago by
Are you proposing that we test whether the equations are infeasible ourselves as a workaround?
Sounds like a workaround that should work for us.
Is cdd
specifically excluding this case?
comment:7 Changed 8 months ago by
Something like
new_eqns_matrix = matrix(new_eqns) feasible_directions = new_eqns_matrix.right_kernel_matrix() if feasible_directions.column(0).is_zero(): initialize_empty_polyhedron()
should work.
comment:8 Changed 8 months ago by
On the other hand, with RDF data and the internal representation used by cdd
, it is not so hard to come up with (ugly) examples on which it can fail to produce a meaningful answer.
I'd say that computing c
like in the ticket description should throw an error,
as a
is exact and b
is not.
Or at the very least print a warning like
sage: a = Polyhedron([[0, 1, 1], [1, 1, 1], [1, 1, 1]],base_ring=RDF) ....: b = Polyhedron([[0.0, 0.5, 1.5], [1.0, 0.5, 1.5], [1.0, 1.5, 0.5]]) sage: a.intersection(b) /mnt/opt/Sage/sagedev/local/lib/python3.8/sitepackages/sage/geometry/polyhedron/backend_cdd.py:151: UserWarning: This polyhedron data is numerically complicated; cdd could not convert between the inexact V and H representation without loss of data. The resulting object might show inconsistencies. warn("This polyhedron data is numerically complicated; cdd could not convert between the inexact V and H representation without loss of data. The resulting object might show inconsistencies.") A 2dimensional polyhedron in RDF^3 defined as the convex hull of 3 vertices
comment:9 Changed 8 months ago by
it's also weird that no warning is printed in this case:
sage: a = Polyhedron([[0, 1, 1], [1, 1, 1], [1, 1, 1]]) ....: b = Polyhedron([[0.0, 0.5, 1.5], [1.0, 0.5, 1.5], [1.0, 1.5, 0.5]]) ....: b.intersection(a) A 2dimensional polyhedron in RDF^3 defined as the convex hull of 3 vertices
as if seeing the exact a
to intersect b
with convinces cdd that everything should be fine.
comment:10 followup: ↓ 12 Changed 8 months ago by
The behavior of coercing base rings is the correct and expected behaviour, I would say.
The failure of cdd
has nothing to do with inexactness:
sage: a = Polyhedron([[0, 1, 1], [1, 1, 1], [1, 1, 1]], backend='cdd') sage: b = Polyhedron([[0, 1/2, 3/2], [1, 1/2, 3/2], [1, 3/2, 1/2]], backend='cdd') sage: a.intersection(b) A 2dimensional polyhedron in QQ^3 defined as the convex hull of 3 vertices
comment:11 Changed 8 months ago by
cdd
for some reason determines that one of the equations is redundant. After this the calculation is correct. For this reason, no warning is printed. Because converting from Vrepresention to Hrepresentation works.
The output of cdd
is numerical consistent, but incorrect.
comment:12 in reply to: ↑ 10 Changed 8 months ago by
Replying to ghkliem:
The behavior of coercing base rings is the correct and expected behaviour, I would say.
The failure of
cdd
has nothing to do with inexactness:
OK, I see, you're right  I thought it's an inexactness issue, such as computing rank of an RDF matrix, sorry.
comment:13 Changed 8 months ago by
 Report Upstream changed from Reported upstream. No feedback yet. to Reported upstream. Developers acknowledge bug.
comment:14 Changed 7 months ago by
 Milestone changed from sage9.2 to sage9.3
comment:15 Changed 5 months ago by
The fix is in https://github.com/cddlib/cddlib/releases/tag/0.94m
let's upgrade
comment:16 Changed 5 months ago by
 Report Upstream changed from Reported upstream. Developers acknowledge bug. to Fixed upstream, in a later stable release.
comment:17 followup: ↓ 22 Changed 5 months ago by
 Report Upstream changed from Fixed upstream, in a later stable release. to Reported upstream. Developers acknowledge bug.
How important do we consider this bug. Should we reject older system installs?
comment:18 Changed 5 months ago by
 Report Upstream changed from Reported upstream. Developers acknowledge bug. to Fixed upstream, in a later stable release.
Ok, it warned me because of a conflict, but I did not expect it to change the description back.
comment:19 Changed 5 months ago by
There is a bug in latte_int with the new header location that needs fixing yet:
comment:20 Changed 5 months ago by
 Cc mkoeppe added
@mkoeppe
There is already a patch for latte, but I'm incapable of creating a patch for latteint not latteintegral.
comment:21 Changed 5 months ago by
 Branch set to public/30319
 Commit set to 406cb29f98626dce6ca86f27983874ab72fcd08d
New commits:
406cb29  update cddlib

comment:22 in reply to: ↑ 17 Changed 5 months ago by
Replying to ghkliem:
How important do we consider this bug. Should we reject older system installs?
A good idea, I think.
comment:23 Changed 5 months ago by
I agree as well.
comment:24 Changed 8 weeks ago by
 Summary changed from wrong intersection of polytopes to wrong intersection of polytopes: Upgrade cddlib
comment:25 Changed 8 weeks ago by
 Dependencies set to #31482
 Summary changed from wrong intersection of polytopes: Upgrade cddlib to wrong intersection of polytopes
 Work issues set to rebase on #31482  latte_int upgrade
comment:26 Changed 8 weeks ago by
It seems that the system cdd will also leak into singular:
Singular/m4/gfanlibcheck.m4
:
AC_CHECK_HEADERS([setoper.h cdd/setoper.h cddlib/setoper.h]) if test "x$ac_cv_header_setoper_h" = xno a "x$ac_cv_header_cdd_setoper_h" = xno a "x$ac_cv_header_cddlib_setoper_h" = xno then if test "x$ENABLE_GFANLIB" = "xyes"; then AC_MSG_ERROR([Error, setoper.h is missing!]) fi
comment:27 Changed 8 weeks ago by
 Dependencies changed from #31482 to #31482, #25993
 Work issues changed from rebase on #31482  latte_int upgrade to rebase on dependencies
comment:28 Changed 8 weeks ago by
Singular always prefers <cdd/....h>
over <cddlib/....h
. This means that on debian a system cdd will always be prefered, if I'm not mistaken.
I don't know if this leads to any problems?
We could patch singular to modify the preference to <cddlib/....h>
over <cdd/....h>
. If we set up the path correctly, then sage's cdd will be prefered, even if there is a system cdd that is also in <cdd/....h>
. Right??
This would be preferable in general I think (for singular as well). If there is a seperate install of cdd, it will always be in cddlib/
.
comment:29 Changed 8 weeks ago by
I suppose we can also just install a few symlinks in cddlib's spkginstall. Then we could finish the present ticket without having to wait for all the dependencies. Later, in a followup ticket when packages have been updated, we could eliminate the symlinks again.
comment:30 Changed 8 weeks ago by
We could to that with the symlinks and singular will pull in the correct library then, I think (at least if my assumption that the path is an ordered list and we lock for headers from sage first is correct).
I don't think we have to wait on singular. It's been leaking all along prefering the cdd
system one over sage's header. It also checks for cddlib
, so it won't fail.
comment:31 Changed 8 weeks ago by
 Work issues changed from rebase on dependencies to rebase on dependencies, I$SAGE_LOCAL/include/cddlib for gfan
gfan only checks plain cdd.h
In fact it looks to me, like gfan wouldn't be able to pick up a systems cdd at all (because the headers are in the subfolder cddlib resp. cdd). So that is actually a bug in the install system. Because if you have cdd installed in your system, but gfan not, then you won't be able to build gfan.
comment:32 Changed 8 weeks ago by
 Work issues changed from rebase on dependencies, I$SAGE_LOCAL/include/cddlib for gfan to rebase on dependencies, I$SAGE_LOCAL/include/cddlib for gfan, topcom configure
We should also update topcom's configure patch to match t, the updated version of latte. This should be easy, as we completely control topcom's configure
comment:33 Changed 8 weeks ago by
Polymake is a different topic.
According to this https://github.com/polymake/polymake/blob/c2a326f240b11a06e1b1d5fd1c2ca7278bbe60a2/bundled/cdd/support/configure.pl
we probably need to specify the path to cdd. But I wouldn't know how to make this work for the systems cdd. But then again, I don't understand perl at all.
comment:34 Changed 8 weeks ago by
I think if we only make sure things don't get worse as they have been, this ticket is very much doable.
We probably need a follow up ticket to fix gfan to work with systems cdd.
comment:35 followup: ↓ 37 Changed 8 weeks ago by
 Commit changed from 406cb29f98626dce6ca86f27983874ab72fcd08d to ed3ed2a20f98f534d13b461d7b476fbc776928a1
comment:36 followup: ↓ 38 Changed 8 weeks ago by
 Work issues rebase on dependencies, I$SAGE_LOCAL/include/cddlib for gfan, topcom configure deleted
Do you know how to test for the cddlib bug in spkgconfigure.m4?
comment:37 in reply to: ↑ 35 ; followup: ↓ 39 Changed 8 weeks ago by
comment:38 in reply to: ↑ 36 Changed 8 weeks ago by
Create a file
test.ine
with
Hrepresentation linearity 2 1 2 begin 5 4 real 0.0 0.0 1.0 1.0 1.0 0.0 1.0 1.0 1.0 2.0 1.0 0.0 1.0 4.0 2.0 0.0 1 0 0 0 end
and run cddexec redcheck <test.ine
.
The line Redundant rows are
should not contain a 1
.
comment:39 in reply to: ↑ 37 Changed 8 weeks ago by
Replying to ghkliem:
I'm a bit confused on why you deleted the work issues. Did you forget to push something?
I thought the result of our discussion was that by installing the symlinks, we do not have to fix anything in the other packages.
comment:40 Changed 8 weeks ago by
Or is there a package that no longer finds a prefixless system cdd?
comment:41 Changed 8 weeks ago by
I see.
Ok, then technically the latte upgrade isn't a decency anymore.
comment:42 Changed 8 weeks ago by
 Commit changed from ed3ed2a20f98f534d13b461d7b476fbc776928a1 to 167c83211f146c119ec377cf00e3b872a6d305d6
Branch pushed to git repo; I updated commit sha1. New commits:
167c832  build/pkgs/cddlib/spkgconfigure.m4: Add test for cddexec redcheck bug

comment:43 Changed 8 weeks ago by
 Dependencies #31482, #25993 deleted
comment:44 Changed 8 weeks ago by
 Description modified (diff)
comment:45 Changed 8 weeks ago by
 Summary changed from wrong intersection of polytopes to Upgrade cddlib to fix wrong intersection of polytopes
comment:46 Changed 8 weeks ago by
 Status changed from new to needs_review
OK... the new configure check works correctly on homebrewmacosstandard
(result: yes
 but then the package is rejected because the headers are in the new place) and on ubuntufocalstandard
(result: no
).
comment:47 Changed 8 weeks ago by
 Cc dimpase added
comment:48 Changed 8 weeks ago by
 Reviewers set to https://github.com/mkoeppe/sage/actions/runs/666698487
comment:50 Changed 7 weeks ago by
 Reviewers changed from https://github.com/mkoeppe/sage/actions/runs/666698487 to Matthias Koeppe, ...
comment:51 Changed 7 weeks ago by
 Reviewers changed from Matthias Koeppe, ... to Matthias Koeppe, Dima Pasechnik
 Status changed from needs_review to positive_review
ok
comment:52 Changed 7 weeks ago by
Thank you.
comment:53 Changed 7 weeks ago by
Thanks!
comment:54 Changed 6 weeks ago by
 Priority changed from critical to blocker
Setting priority to blocker to bring this ticket to the attention of the release bot.
comment:55 Changed 6 weeks ago by
 Branch changed from public/30319 to 167c83211f146c119ec377cf00e3b872a6d305d6
 Resolution set to fixed
 Status changed from positive_review to closed
Looks like a
cdd
bug.For some reason
cdd
thinks that row1
is redundant. If you drop an inequality, everything is fine.