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: sage-9.3
Component: geometry Keywords:
Cc: Jean-Philippe 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:

Status badges

Description (last modified by Matthias Köppe)

As reported in this sage-devel 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 Matthias Köppe

Priority: majorcritical

comment:2 Changed 2 years ago by gh-kliem

Looks like a cdd bug.

sage: a = Polyhedron([[0, -1, 1], [1, -1, 1], [1, 1, -1]])
sage: b = Polyhedron([[0.0, -0.5, 1.5], [1.0, -0.5, 1.5], [1.0, 1.5, -0.5]])
sage: a = a.change_ring(RDF)
sage: new_eqns = a.equations() + b.equations()
sage: new_ieqs = a.inequalities() + b.inequalities()
sage: Polyhedron(eqns=new_eqns, ieqs=new_ieqs[1:2]+new_ieqs[4:5], verbose=True)
---- CDD input -----
H-representation
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

---- CDD output -----
Canonicalize the matrix.
Implicit linearity rows are:

Redundant rows are:1 3 5 

Nonredundant representation:
The new row positions are as follows (orig:new).
Each redundant row has the new number 0.
Each deleted duplicated row has a number nagative of the row that
represents its equivalence class.
 1:0 2:1 3:0 4:2 5:0
H-representation
linearity 1  1
begin
 2 4 real
 -1  0  1  1
 -1  4 -2  0
end

size = 5 x 4
Number Type = real

---- CDD input -----
Canonicalize the matrix.
Implicit linearity rows are:

Redundant rows are:1 3 5 

Nonredundant representation:
The new row positions are as follows (orig:new).
Each redundant row has the new number 0.
Each deleted duplicated row has a number nagative of the row that
represents its equivalence class.
 1:0 2:1 3:0 4:2 5:0
H-representation
linearity 1  1
begin
 2 4 real
 -1  0  1  1
 -1  4 -2  0
end

---- CDD output -----
The second representation:
V-representation
linearity 1  3
begin
 3 4 real
  0  1  0  0
  1  7.500000000E-01  1  0
  0 -5.000000000E-01 -1  1
end

Vertex incidence
ecd_file: Incidence of generators and inequalities
begin
  3    3
 1 -2 : 2 
 2 -2 : 3 
 3 -3 : 
end

Vertex adjacency
ead_file: Adjacency of generators
begin
  3    3
 1 1 : 2 
 2 1 : 1 
 3 0 : 
end

The first (input) representation
H-representation
linearity 1  1
begin
 2 4 real
 -1  0  1  1
 -1  4 -2  0
end

Facet incidence
icd_file: Incidence of inequalities and generators
begin
  3    3
 1 -3 : 
 2 -2 : 1 
 3 -2 : 2 
end

Facet adjacency
iad_file: Adjacency of inequalities
begin
  3    3
 1 -2 : 1 
 2 -2 : 2 
 3 -2 : 3 
end

size = 2 x 4
Number Type = real

---- CDD input -----
The second representation:
V-representation
linearity 1  3
begin
 3 4 real
  0  1  0  0
  1  7.500000000E-01  1  0
  0 -5.000000000E-01 -1  1
end
---- CDD output -----
The second representation:
H-representation
linearity 1  3
begin
 3 4 real
  1  0  0  0
 -1  4 -2  0
 -1  0  1  1
end

size = 3 x 4
Number Type = real

A 2-dimensional polyhedron in RDF^3 defined as the convex hull of 1 vertex, 1 ray, 1 line

For some reason cdd thinks that row 1 is redundant. If you drop an inequality, everything is fine.

Last edited 2 years ago by gh-kliem (previous) (diff)

comment:3 Changed 2 years ago by Thierry Monteil

Report Upstream: N/ANot 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 gh-kliem

Report Upstream: Not yet reported upstream; Will do shortly.Reported upstream. No feedback yet.

comment:5 Changed 2 years ago by Dima Pasechnik

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 gh-kliem

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 gh-kliem

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 Dima Pasechnik

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/sage-dev/local/lib/python3.8/site-packages/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 2-dimensional polyhedron in RDF^3 defined as the convex hull of 3 vertices

comment:9 Changed 2 years ago by Dima Pasechnik

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 2-dimensional 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 Changed 2 years ago by gh-kliem

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 2-dimensional polyhedron in QQ^3 defined as the convex hull of 3 vertices

comment:11 Changed 2 years ago by gh-kliem

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 2 years ago by Dima Pasechnik

Replying to gh-kliem:

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 gh-kliem

Report Upstream: Reported upstream. No feedback yet.Reported upstream. Developers acknowledge bug.

comment:14 Changed 2 years ago by Matthias Köppe

Milestone: sage-9.2sage-9.3

comment:15 Changed 2 years ago by Dima Pasechnik

comment:16 Changed 2 years ago by Dima Pasechnik

Report Upstream: Reported upstream. Developers acknowledge bug.Fixed upstream, in a later stable release.

comment:17 Changed 2 years ago by gh-kliem

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 gh-kliem

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 gh-kliem

There is a bug in latte_int with the new header location that needs fixing yet:

https://github.com/latte-int/latte/issues/15

comment:20 Changed 2 years ago by gh-kliem

Cc: Matthias Köppe added

@mkoeppe

There is already a patch for latte, but I'm incapable of creating a patch for latte-int not latte-integral.

comment:21 Changed 2 years ago by gh-kliem

Branch: public/30319
Commit: 406cb29f98626dce6ca86f27983874ab72fcd08d

New commits:

406cb29update cddlib

comment:22 in reply to:  17 Changed 2 years ago by Dima Pasechnik

Replying to gh-kliem:

How important do we consider this bug. Should we reject older system installs?

A good idea, I think.

comment:23 Changed 2 years ago by Matthias Köppe

I agree as well.

comment:24 Changed 21 months ago by Matthias Köppe

Summary: wrong intersection of polytopeswrong intersection of polytopes: Upgrade cddlib

comment:25 Changed 21 months ago by Matthias Köppe

Dependencies: #31482
Summary: wrong intersection of polytopes: Upgrade cddlibwrong intersection of polytopes
Work issues: rebase on #31482 - latte_int upgrade

comment:26 Changed 21 months ago by gh-kliem

It seems that the system cdd will also leak into singular:

Singular/m4/gfanlib-check.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 Matthias Köppe

Dependencies: #31482#31482, #25993
Work issues: rebase on #31482 - latte_int upgraderebase on dependencies

comment:28 Changed 21 months ago by gh-kliem

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 Matthias Köppe

I suppose we can also just install a few symlinks in cddlib's spkg-install. 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 gh-kliem

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 gh-kliem

Work issues: rebase on dependenciesrebase 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 gh-kliem

Work issues: rebase on dependencies, -I$SAGE_LOCAL/include/cddlib for gfanrebase 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 gh-kliem

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 gh-kliem

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.

Version 0, edited 21 months ago by gh-kliem (next)

comment:35 Changed 21 months ago by git

Commit: 406cb29f98626dce6ca86f27983874ab72fcd08ded3ed2a20f98f534d13b461d7b476fbc776928a1

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

308274dupdate cddlib
ed3ed2abuild/pkgs/cddlib/spkg-install.in: Install symlinks for cddlib/*.h

comment:36 Changed 21 months ago by Matthias Köppe

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 spkg-configure.m4?

comment:37 in reply to:  35 ; Changed 21 months ago by gh-kliem

Replying to git:

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

308274dupdate cddlib
ed3ed2abuild/pkgs/cddlib/spkg-install.in: Install symlinks for cddlib/*.h

I'm a bit confused on why you deleted the work issues. Did you forget to push something?

comment:38 in reply to:  36 Changed 21 months ago by gh-kliem

Create a file

test.ine

with

H-representation
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 21 months ago by Matthias Köppe

Replying to gh-kliem:

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 Matthias Köppe

Or is there a package that no longer finds a prefix-less system cdd?

comment:41 Changed 21 months ago by gh-kliem

I see.

Ok, then technically the latte upgrade isn't a decency anymore.

comment:42 Changed 21 months ago by git

Commit: ed3ed2a20f98f534d13b461d7b476fbc776928a1167c83211f146c119ec377cf00e3b872a6d305d6

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

167c832build/pkgs/cddlib/spkg-configure.m4: Add test for cddexec --redcheck bug

comment:43 Changed 21 months ago by Matthias Köppe

Dependencies: #31482, #25993

comment:44 Changed 21 months ago by Matthias Köppe

Description: modified (diff)

comment:45 Changed 21 months ago by Matthias Köppe

Summary: wrong intersection of polytopesUpgrade cddlib to fix wrong intersection of polytopes

comment:46 Changed 21 months ago by Matthias Köppe

Status: newneeds_review

OK... the new configure check works correctly on homebrew-macos-standard (result: yes - but then the package is rejected because the headers are in the new place) and on ubuntu-focal-standard (result: no).

comment:47 Changed 21 months ago by Matthias Köppe

Cc: Dima Pasechnik added

comment:48 Changed 21 months ago by Matthias Köppe

Reviewers: https://github.com/mkoeppe/sage/actions/runs/666698487

comment:49 Changed 21 months ago by Matthias Köppe

Cc: Volker Braun added

Let's please get this fix into 9.3

comment:50 Changed 20 months ago by Matthias Köppe

Reviewers: https://github.com/mkoeppe/sage/actions/runs/666698487Matthias Koeppe, ...

comment:51 Changed 20 months ago by Dima Pasechnik

Reviewers: Matthias Koeppe, ...Matthias Koeppe, Dima Pasechnik
Status: needs_reviewpositive_review

ok

comment:52 Changed 20 months ago by gh-kliem

Thank you.

comment:53 Changed 20 months ago by Matthias Köppe

Thanks!

comment:54 Changed 20 months ago by Matthias Köppe

Priority: criticalblocker

Setting priority to blocker to bring this ticket to the attention of the release bot.

comment:55 Changed 20 months ago by Volker Braun

Branch: public/30319167c83211f146c119ec377cf00e3b872a6d305d6
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.