Opened 2 years ago
Closed 20 months ago
#30319 closed defect (fixed)
Upgrade cddlib to fix wrong intersection of polytopes
Reported by:  Vincent Delecroix  Owned by:  

Priority:  blocker  Milestone:  sage9.3 
Component:  geometry  Keywords:  
Cc:  JeanPhilippe Labbé, Matthias Köppe, Dima Pasechnik, Volker Braun  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 2 years ago by
Priority:  major → critical 

comment:3 Changed 2 years ago by
Report Upstream:  N/A → Not yet reported upstream; Will do shortly. 

Could someone please report it upstream (i do not have a github account) ?
comment:4 Changed 2 years ago by
Report Upstream:  Not yet reported upstream; Will do shortly. → Reported upstream. No feedback yet. 

comment:5 Changed 2 years 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 2 years 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 2 years 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 2 years 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 2 years 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 2 years 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 2 years 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 Changed 2 years 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 2 years ago by
Report Upstream:  Reported upstream. No feedback yet. → Reported upstream. Developers acknowledge bug. 

comment:14 Changed 2 years ago by
Milestone:  sage9.2 → sage9.3 

comment:15 Changed 2 years ago by
The fix is in https://github.com/cddlib/cddlib/releases/tag/0.94m
let's upgrade
comment:16 Changed 2 years ago by
Report Upstream:  Reported upstream. Developers acknowledge bug. → Fixed upstream, in a later stable release. 

comment:17 followup: 22 Changed 2 years ago by
Report Upstream:  Fixed upstream, in a later stable release. → Reported upstream. Developers acknowledge bug. 

How important do we consider this bug. Should we reject older system installs?
comment:18 Changed 2 years ago by
Report Upstream:  Reported upstream. Developers acknowledge bug. → 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 2 years ago by
There is a bug in latte_int with the new header location that needs fixing yet:
comment:20 Changed 2 years ago by
Cc:  Matthias Köppe added 

@mkoeppe
There is already a patch for latte, but I'm incapable of creating a patch for latteint not latteintegral.
comment:21 Changed 2 years ago by
Branch:  → public/30319 

Commit:  → 406cb29f98626dce6ca86f27983874ab72fcd08d 
New commits:
406cb29  update cddlib

comment:22 Changed 2 years ago by
Replying to ghkliem:
How important do we consider this bug. Should we reject older system installs?
A good idea, I think.
comment:24 Changed 21 months ago by
Summary:  wrong intersection of polytopes → wrong intersection of polytopes: Upgrade cddlib 

comment:25 Changed 21 months ago by
Dependencies:  → #31482 

Summary:  wrong intersection of polytopes: Upgrade cddlib → wrong intersection of polytopes 
Work issues:  → rebase on #31482  latte_int upgrade 
comment:26 Changed 21 months 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 21 months ago by
Dependencies:  #31482 → #31482, #25993 

Work issues:  rebase on #31482  latte_int upgrade → rebase on dependencies 
comment:28 Changed 21 months 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 21 months 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 21 months 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 21 months ago by
Work issues:  rebase on dependencies → 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 21 months ago by
Work issues:  rebase on dependencies, I$SAGE_LOCAL/include/cddlib for gfan → 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 21 months 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 21 months 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 21 months ago by
Commit:  406cb29f98626dce6ca86f27983874ab72fcd08d → ed3ed2a20f98f534d13b461d7b476fbc776928a1 

comment:36 followup: 38 Changed 21 months ago by
Authors:  → Jonathan Kliem, Matthias Koeppe 

Work issues:  rebase on dependencies, I$SAGE_LOCAL/include/cddlib for gfan, topcom configure 
Do you know how to test for the cddlib bug in spkgconfigure.m4?
comment:37 followup: 39 Changed 21 months ago by
comment:38 Changed 21 months 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 Changed 21 months 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 21 months ago by
Or is there a package that no longer finds a prefixless system cdd?
comment:41 Changed 21 months ago by
I see.
Ok, then technically the latte upgrade isn't a decency anymore.
comment:42 Changed 21 months ago by
Commit:  ed3ed2a20f98f534d13b461d7b476fbc776928a1 → 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 21 months ago by
Dependencies:  #31482, #25993 

comment:44 Changed 21 months ago by
Description:  modified (diff) 

comment:45 Changed 21 months ago by
Summary:  wrong intersection of polytopes → Upgrade cddlib to fix wrong intersection of polytopes 

comment:46 Changed 21 months ago by
Status:  new → 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 21 months ago by
Cc:  Dima Pasechnik added 

comment:48 Changed 21 months ago by
Reviewers:  → https://github.com/mkoeppe/sage/actions/runs/666698487 

comment:50 Changed 20 months ago by
Reviewers:  https://github.com/mkoeppe/sage/actions/runs/666698487 → Matthias Koeppe, ... 

comment:51 Changed 20 months ago by
Reviewers:  Matthias Koeppe, ... → Matthias Koeppe, Dima Pasechnik 

Status:  needs_review → positive_review 
ok
comment:54 Changed 20 months ago by
Priority:  critical → blocker 

Setting priority to blocker to bring this ticket to the attention of the release bot.
comment:55 Changed 20 months ago by
Branch:  public/30319 → 167c83211f146c119ec377cf00e3b872a6d305d6 

Resolution:  → fixed 
Status:  positive_review → closed 
Looks like a
cdd
bug.For some reason
cdd
thinks that row1
is redundant. If you drop an inequality, everything is fine.