Compute the intersection of two fans

Questions and problems about using polymake go here.
Drew
Posts: 6
Joined: 07 Mar 2013, 21:33

Compute the intersection of two fans

Postby Drew » 03 Dec 2013, 01:49

Suppose I have two (not complete) fans f1 and f2, and I want to compute a fan whose cones are all the intersections c1 \cap c2 where c1 is a cone of f1 and c2 is a cone of f2.

Can polymake do this? I looked at common_refinement, but the documentation says that the fans must be complete.

User avatar
assarf
Developer
Posts: 74
Joined: 12 Oct 2011, 15:52

Re: Compute the intersection of two fans

Postby assarf » 05 Dec 2013, 14:36

In the next release (or beta release) this will be fixed. So you can use common_refinement to intersect arbitrary fans (even with lineality).

If you need this right away, use the attached patch and recompile polymake. Meaning: save the attached file somewhere. Change into the polymake trunk directory. Type:

Code: Select all

patch -p0 < /path/to/common_refinement.patch make
Attachments
common_refinement.patch
patch for common_refinement client
(4.49 KiB) Downloaded 371 times
no signature

juergens
Posts: 3
Joined: 15 May 2014, 09:20

Re: Compute the intersection of two fans

Postby juergens » 20 May 2014, 15:45

Hi!
I have a question concerning the common refinement function provided by your patch. I would like to intersect a fan with a linear space.
Is this possible right now with polymake?
First of all i tried to realize the linear space as a fan consisting of a lineality space (via "INPUT_LINEALITY=>$A" and "LINEALITY_SPACE=>$A", $A the matrix containing the basis). It seems to me that polymake is not happy with the input. Whenever i try to compute the common refinement polymake says:

"WARNING: available properties insufficient to compute 'LINEALITY_SPACE'
ERROR: unexpected undefined value of an input property at input line 1."

Simon Hampes extension atint contains a function called "linear_space_by_matrix". Using that function i get a result. Nevertheless polymake says:

"....
$F = fan::common_refinement($L,$BFM);
polymake: WARNING: could not compute 'FACETS | INEQUALITIES' probably because of unsatisfied preconditions:
precondition : N_RAYS ( FACETS, LINEAR_SPAN : RAYS, LINEALITY_SPACE, RAYS_IN_FACETS )
precondition : N_RAYS ( beneath_beyond.convex_hull.primal, default.triangulation: FACETS, LINEAR_SPAN, RAYS_IN_FACETS, DUAL_GRAPH.ADJACENCY, TRIANGULATION, ESSENTIALLY_GENERIC : RAYS )
precondition : N_RAYS | N_INPUT_RAYS ( lrs.convex_hull.primal: FACETS, LINEAR_SPAN : RAYS | INPUT_RAYS )
precondition : N_RAYS | N_INPUT_RAYS ( cdd.convex_hull.primal: FACETS, LINEAR_SPAN : RAYS | INPUT_RAYS )"

Here $L is a fan with an empty cone and a lineality space ($A) (created via "linear_space_by_matrix"), $BFM is a Bergman fan created via Simon Hampes function "bergman_fan_matroid".
Since polymake calls it "WARNING: ... " the output is correct?
Do you have any advice for me?

I wrote a mini example but the site says "the extension is not allowed". So, let me post it here ;-)

Code: Select all

use application "common"; use vars '$M','$Bases','$n','$A','$BFM','$LS','$F'; $Bases = new Array<Set<Int>>([[0,1,2,3,4,5,6,7],[0,1,2,3,4,5,6,9],[0,1,2,3,4,5,7,8],[0,1,2,3,4,5,8,9],[0,1,2,3,4,6,7,9],[0,1,2,3,4,7,8,9],[0,1,2,3,5,6,7,8],[0,1,2,3,5,6,8,9],[0,1,2,3,6,7,8,9],[0,1,2,4,5,6,7,10],[0,1,2,4,5,6,9,10],[0,1,2,4,5,7,8,10],[0,1,2,4,5,8,9,10],[0,1,2,4,6,7,9,10],[0,1,2,4,7,8,9,10],[0,1,2,5,6,7,8,10],[0,1,2,5,6,8,9,10],[0,1,2,6,7,8,9,10],[0,1,3,4,5,6,7,8],[0,1,3,4,5,6,8,9],[0,1,3,4,6,7,8,9],[0,1,4,5,6,7,8,10],[0,1,4,5,6,8,9,10],[0,1,4,6,7,8,9,10],[0,2,3,4,5,6,7,10],[0,2,3,4,5,6,9,10],[0,2,3,4,5,7,8,10],[0,2,3,4,5,8,9,10],[0,2,3,4,6,7,9,10],[0,2,3,4,7,8,9,10],[0,2,3,5,6,7,8,10],[0,2,3,5,6,8,9,10],[0,2,3,6,7,8,9,10],[0,3,4,5,6,7,8,10],[0,3,4,5,6,8,9,10],[0,3,4,6,7,8,9,10],[1,2,3,4,5,6,7,9],[1,2,3,4,5,7,8,9],[1,2,3,5,6,7,8,9],[1,2,4,5,6,7,9,10],[1,2,4,5,7,8,9,10],[1,2,5,6,7,8,9,10],[1,3,4,5,6,7,8,9],[1,4,5,6,7,8,9,10],[2,3,4,5,6,7,9,10],[2,3,4,5,7,8,9,10],[2,3,5,6,7,8,9,10],[3,4,5,6,7,8,9,10]]); $n = 11; $A = new Matrix<Rational>([[3,2,2,1,1,1,0,0,0,0,0],[0,0,0,1,0,0,1,0,0,0,0],[0,1,0,1,2,1,1,3,1,0,0],[0,0,1,1,0,1,1,0,2,3,0]]); $M = new matroid::Matroid(BASES=>$Bases,N_ELEMENTS=>$n); use application "atint"; $BFM = bergman_fan_matroid($M); $LS = linear_space_by_matrix($A); $F = fan::common_refinement($BFM,$LS);
Best regards,
Christian

User avatar
assarf
Developer
Posts: 74
Joined: 12 Oct 2011, 15:52

Re: Compute the intersection of two fans

Postby assarf » 21 May 2014, 13:35

indeed there is something wrong. Thank you.

We will fix that. Please stay tuned.

Bye
no signature

User avatar
assarf
Developer
Posts: 74
Joined: 12 Oct 2011, 15:52

Re: Compute the intersection of two fans

Postby assarf » 22 May 2014, 15:34

This issue will be fixed in the next perpetual beta version. In the meanwhile here is a patch for it. Just apply it like in the previous post. Please report back if it works. I did not try your example, since I do not have atint installed at the moment.
Attachments
common_refinement_2.patch
(3.68 KiB) Downloaded 338 times
no signature

juergens
Posts: 3
Joined: 15 May 2014, 09:20

Re: Compute the intersection of two fans

Postby juergens » 23 May 2014, 13:49

Thank you for your quick answer. Unfortunately, polymake is still bothered by something. This is the output:

Code: Select all

... atint > $F = fan::common_refinement($BFM,$LS); polymake: used package cddlib Implementation of the double description method of Motzkin et al. Copyright by Komei Fukuda. http://www.ifor.math.ethz.ch/~fukuda/cdd_home/cdd.html polymake: WARNING: could not compute 'FACETS | INEQUALITIES' probably because of unsatisfied preconditions: precondition : N_RAYS ( beneath_beyond.convex_hull.primal, default.triangulation: FACETS, LINEAR_SPAN, RAYS_IN_FACETS, DUAL_GRAPH.ADJACENCY, TRIANGULATION, ESSENTIALLY_GENERIC : RAYS ) precondition : N_RAYS | N_INPUT_RAYS ( cdd.convex_hull.primal: FACETS, LINEAR_SPAN : RAYS | INPUT_RAYS ) precondition : N_RAYS ( FACETS, LINEAR_SPAN : RAYS, LINEALITY_SPACE, RAYS_IN_FACETS ) precondition : N_RAYS | N_INPUT_RAYS ( lrs.convex_hull.primal: FACETS, LINEAR_SPAN : RAYS | INPUT_RAYS )

User avatar
assarf
Developer
Posts: 74
Joined: 12 Oct 2011, 15:52

Re: Compute the intersection of two fans

Postby assarf » 26 May 2014, 11:59

Ok, thank you. I downloaded atint and tried it. The warning is because the input is not quite right. But one can discuss which behavior is "correct".

as you can see your fan $LS has one empty maximal cone.

Code: Select all

atint > print $LS->MAXIMAL_CONES; {}
But if you define such a fan with the dedicated input properties you get something different:

Code: Select all

fan > $g = new PolyhedralFan(INPUT_RAYS=>[[]],INPUT_LINEALITY=>[[1,1]], INPUT_CONES=>[[]]); fan > print $g->MAXIMAL_CONES;
You get no maximal cones (not even an empty one). And indeed if I change your input in the following way:

Code: Select all

atint > $LSF = new fan::PolyhedralFan(RAYS=>$LS->RAYS, LINEALITY_SPACE=>$LS->LINEALITY_SPACE, MAXIMAL_CONES=>[]); atint > $LSF->MAXIMAL_CONES; atint > $F = fan::common_refinement($BFM,$LSF);
it works without any warnings. So the function linear_space_by_matrix from the atint extension does produce a fan (weighted complex) with an empty maximal cone which produces the warning. But the output seems to be the same in both cases. At least both outputs have the same rays, lineality_space and maximal_cones
no signature

juergens
Posts: 3
Joined: 15 May 2014, 09:20

Re: Compute the intersection of two fans

Postby juergens » 03 Jun 2014, 14:38

Thank you for the explanation. I copied the code into the polymake shell. Everything worked fine. Unfortunately, there appear segmentation faults if I try to print rays or something else. Reinstalling polymake (2.13-1) did not solve the problem. Using atints function and ignoring warnings still works.

ren
Posts: 38
Joined: 03 May 2011, 15:21

Re: Compute the intersection of two fans

Postby ren » 03 Jun 2014, 15:50

Hm, if I may highjack this thread: if I want to create a fan consisting solely out of the lineality space, what would be the prefered way?

a) a fan consisting of a lineality space and the empty cone as maximal cone

b) a fan consisting of a lineality space and the origin as maximal cone

Simon chose the first option in his extention, but both would make sense to me, so I just wanted to be sure.

User avatar
assarf
Developer
Posts: 74
Joined: 12 Oct 2011, 15:52

Re: Compute the intersection of two fans

Postby assarf » 03 Jun 2014, 16:01

Hey juergens,

unfortunately (well... maybe fortunately *g*) I could not reproduce this segmentation fault. With a fresh 2.13-1 it works fine here. But this can have several reasons. One reason might be that something in your polymake config is broken. Or you prefer a different convex hull algorithm which produces the segmentation fault.

Here are some things you could try:
  • remove your .polymake folder in your home folder. warning this kills your complete polymake configuration. Meaning you have to import the extension one more time. And you have no history. (you can move your .polymake folder somewhere else, instead of deleting it. So you do not throw everything in the trash)
  • try the polymake perpetual beta (on github)
  • (last resort) try to run polymake in gdb and when it crashes enter bt to get a backtrace. So we can analyze which client crashes and when.
no signature


Return to “Helpdesk”