Using Both Induced Volume and Lrs Engine

[Advay Goel]

Hi All,

I aim to calculate the volumes of not-full dimensional polytopes. Using ambient measure, the volume is always 0. So, I want to use induced measure. At the same time, though, I also want the engine to be Lrs.

If I just do .volume(engine = 'lrs'), I always get 0. Is this an error? Or is this because the system is using ambient measure for the volume?

To try and fix the issue, I want to have both induced measure and lrs engine. However, when I input something like .volume(measure = 'induced', engine = 'lrs'), I get an error. Is there some way for me to get both?

[Nils Bruin]

Did you check the lrs documentation: http://cgm.cs.mcgill.ca/~avis/C/lrslib/USERGUIDE.html#Volume%20Computation ? It only mentions volumes of full polytopes. You could of course project the vertices yourself or pull them back along the embedding of a subspace containing the polytope to get a full one. Then it would be your own responsibility of choosing a basis that expresses the appropriate measure.

[Advay Goel]

Thank you for the response.

I'm not quite sure what you mean by "pull them back along the embedding of a subspace containing the polytope to get a full one." 

For example, I currently have a 10-dimensional polytope that is located in QQ^18. How would I bring this polytope into 10-dimensional space so that I can use LRS to calculate its volume?

[Michael Orlitzky]

On Wed, 2022-02-23 at 10:34 -0800, Advay Goel wrote:


> For example, I currently have a 10-dimensional polytope that is located in
> QQ^18. How would I bring this polytope into 10-dimensional space so that I
> can use LRS to calculate its volume?

If you have a ten-dimensional polytope, there exists a ten-dimensional
space that contains it. Pick a basis for that space, and represent your
polytope in terms of it. Now the vertices of the ten-dimensional
polytope have ten coordinates in a ten-dimensional ambient space.

Caveat: how you choose the basis is important for the notion of volume.
You can choose an isometric one, but you probably won't be able to
remain in QQ then. If you need exact answers, that could be a problem.

[Matthias Koeppe]

What Nils and Michael have explained to you is, of course, already implemented in Sage.

Unfortunately in the combination with lrslib, there is a bug that prevents it from working. 

I have opened https://trac.sagemath.org/ticket/33410 for this.

[Advay Goel]

If there's a bug, what would my next step be? When I do only induced volume, I don't get the correct result. Also, I see in https://trac.sagemath.org/ticket/16045 that people are able to use both induced volume and lrs engine at once. Is this some previous version of sage in which the error wasn't there? How could I circumvent the problem?

[Matthias Koeppe]

Fixed in https://trac.sagemath.org/ticket/33410, ready for use and review

[Advay Goel]

I run Sage in a Sage Cell Server and on Terminal on my laptop. How do I "reload" Sage on both of these to incorporate the fix?

[Advay Goel]

Even after the issue seemed to be fixed here: https://trac.sagemath.org/ticket/33410, I still get the same error as before. I attached a screenshot of part of the error message to this email. 

I run Sage here: https://sagecell.sagemath.org/. Is there some sort of update I need to do in order to incorporate whatever changes were made to Sage? 

[Dima Pasechnik]

On Sat, 26 Feb 2022, 22:42 Advay Goel, <adva...@gmail.com> wrote:

Even after the issue seemed to be fixed here: https://trac.sagemath.org/ticket/33410, I still get the same error as before. I attached a screenshot of part of the error message to this email. 

I run Sage here: https://sagecell.sagemath.org/. Is there some sort of update I need to do in order to incorporate whatever changes were made to Sage? 

I don't know how often sagecell is updated, but this ticket has been only positively reviewed, and not yet merged into our development branch. So it's not there yet.

You can still try running this particular update online (of course you can do it on a local install), using GitPod, on the right in the row of "Status badges".

Assuming you have a GitHub account, and a reasonably fast internet access, it takes 5-10 minutes

to launch, but once it's done, you get a full copy of Sage with the ticket changes running

on a remote host, with an interface in the browser (or you can use a VSCode interface).

Do you see "Open in GitPod" button in the top part of the ticket page, to

On Wednesday, February 23, 2022 at 3:22:53 PM UTC-5 Advay Goel wrote:

I run Sage in a Sage Cell Server and on Terminal on my laptop. How do I "reload" Sage on both of these to incorporate the fix?

On Wednesday, February 23, 2022 at 3:21:13 PM UTC-5 Matthias Koeppe wrote:

Fixed in https://trac.sagemath.org/ticket/33410, ready for use and review

On Wednesday, February 23, 2022 at 12:09:57 PM UTC-8 adva...@gmail.com wrote:

If there's a bug, what would my next step be? When I do only induced volume, I don't get the correct result. Also, I see in https://trac.sagemath.org/ticket/16045 that people are able to use both induced volume and lrs engine at once. Is this some previous version of sage in which the error wasn't there? How could I circumvent the problem?

On Wednesday, February 23, 2022 at 2:40:32 PM UTC-5 Matthias Koeppe wrote:

What Nils and Michael have explained to you is, of course, already implemented in Sage.

Unfortunately in the combination with lrslib, there is a bug that prevents it from working. 

I have opened https://trac.sagemath.org/ticket/33410 for this.

On Wednesday, February 23, 2022 at 7:57:34 AM UTC-8 adva...@gmail.com wrote:

Hi All,

I aim to calculate the volumes of not-full dimensional polytopes. Using ambient measure, the volume is always 0. So, I want to use induced measure. At the same time, though, I also want the engine to be Lrs.

If I just do .volume(engine = 'lrs'), I always get 0. Is this an error? Or is this because the system is using ambient measure for the volume?

To try and fix the issue, I want to have both induced measure and lrs engine. However, when I input something like .volume(measure = 'induced', engine = 'lrs'), I get an error. Is there some way for me to get both?

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/3466467a-82f2-4588-9691-ea87ddbdf4b2n%40googlegroups.com.

[Dima Pasechnik]

some rows got messed up in the reply, here is an update:

On Sat, Feb 26, 2022 at 11:19 PM Dima Pasechnik <dim...@gmail.com> wrote:
>
>
>
> On Sat, 26 Feb 2022, 22:42 Advay Goel, <adva...@gmail.com> wrote:
>>
>>
>> Even after the issue seemed to be fixed here: https://trac.sagemath.org/ticket/33410, I still get the same error as before. I attached a screenshot of part of the error message to this email.
>>
>> I run Sage here: https://sagecell.sagemath.org/. Is there some sort of update I need to do in order to incorporate whatever changes were made to Sage?
>
>
> I don't know how often sagecell is updated, but this ticket has been only positively reviewed, and not yet merged into our development branch. So it's not there yet.
>

You can still try running this particular update online (of course you
can do it on a local install), using GitPod, on the right in the row
of "Status badges"

on https://trac.sagemath.org/ticket/33410 (just above Description)

> Assuming you have a GitHub account, and a reasonably fast internet access, it takes 5-10 minutes
> to launch, but once it's done, you get a full copy of Sage with the ticket changes running
> on a remote host, with an interface in the browser (or you can use a VSCode interface).
>
>
>>

[Dima Pasechnik]

PS. After the GitPod has launched the image, you'll need to install
lrs into the local copy
of Sage, by going to the righ/bottom part, where you see a shell prompt, and run

make lrslib

after that, you can launch Sage there:

./sage

and try things like

sage: polytopes.hypercube(3)._volume_lrs()
8
sage: P = Polyhedron([[0, 0], [1, 1]])
sage: P.volume(measure='induced', engine='lrs')
1.414213562373095?

[Advay Goel]

Thank you so much. I ran the code in the GitPod and it compiled. However, the results I'm getting for volume are still different than what I'm expecting it to be. 

I am trying to find the volume of Flow Polytopes, which are defined by a Digraph and a vector. Papers like these (which are widely accepted to be true in the Flow Polytopes community) give explicit volume formulas for flow polytopes, but for some reason, the Sage always seems to give a different answer? Does anyone else face a similar problem/know what to do? 

Ex:

sage: G=DiGraph({0:[1,2,3,4], 1:[2,3,4], 2:[3,4], 3:[4]})

sage: G.flow_polytope().volume(measure = "induced", engine = "lrs").radical_expression()

1/72*sqrt(5)

In reality, the volume should be 2. And as I try different cases, I can't seem to find some common factor by which the volumes are being dilated.

Any help would be greatly appreciated.

[Dima Pasechnik]

sage: sage: G=DiGraph({0:[1,2,3,4], 1:[2,3,4], 2:[3,4], 3:[4]})
....: sage: G.flow_polytope().volume(measure = "induced", engine = "lrs")
0.03105649968749708?
sage: sage: G=DiGraph({0:[1,2,3,4], 1:[2,3,4], 2:[3,4], 3:[4]})
....: sage: G.flow_polytope().volume(measure = "induced")
0.03105649968749708?
sage: G.flow_polytope()
A 6-dimensional polyhedron in QQ^10 defined as the convex hull of 8 vertices
sage: G.flow_polytope().vertices()
(A vertex at (0, 0, 0, 1, 0, 0, 0, 0, 0, 0),
A vertex at (0, 0, 1, 0, 0, 0, 0, 0, 0, 1),
A vertex at (0, 1, 0, 0, 0, 0, 0, 1, 0, 1),
A vertex at (0, 1, 0, 0, 0, 0, 0, 0, 1, 0),
A vertex at (1, 0, 0, 0, 0, 0, 1, 0, 0, 0),
A vertex at (1, 0, 0, 0, 0, 1, 0, 0, 0, 1),
A vertex at (1, 0, 0, 0, 1, 0, 0, 0, 1, 0),
A vertex at (1, 0, 0, 0, 1, 0, 0, 1, 0, 1))

Can you verify that the description of the flow polytope for this
digraph is correct as above?

---------------

In fact, it seems that the paper you cite uses a rather unusual way
to normalise the volume:

"The normalized volume vol(P) of a d-dimensional polytope P ⊂ R m is
the volume form which assigns a volume of one to the smallest
d-dimensional integer simplex in the affine span of P."

Whereas Sage just does a standard linear algebra thing, as far as I understand.

HTH
Dima

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/6dd91dc5-1f2f-4282-b1b5-6f5696508e2dn%40googlegroups.com.

[Dima Pasechnik]

Indeed, with this definition the volume (i.e. length) of
conv([0,0],[1,2]) would be
1, and not sqrt(5).

volume(measure = "induced") doesn't know anything about the integer
lattice structure on
the affine span.

[Advay Goel]

To reply to your last email, if measure = "induced" does not work, what would you suggest since flow polytopes are not fully dimensional? Also, in your penultimate email, you mentioned that Sage normalizes volume using linear algebra -- how exactly does that process work? what is it called? 

Also, I realized I sent the wrong code in my previous email. I use the following Flow Polytopes class + methods: 

def elemv(i,n):
        return matrix.identity(n)[i]

def completeDiGraph(n):
    return DiGraph({i:[j for j in range(i+1,n)] for i in range(n)})
   
def CRYA(n):
    """
    returns Chan-Robbins-Yuen flow polytope of order n
    """
    return FlowPolytope(completeDiGraph(n),tuple([1,]+[0 for i in range(n-2)]+[-1,]))
   
def CatPoly(n):
    """
    returns flow polytope with n vertices whose volume is the nth Catalan number.
    """
    cn = {j:[j+1,n-1] for j in range(1,n-2)}
    cn[0] = range(1,n-1)
    cn[n-2] = [n-1,]
    return FlowPolytope(DiGraph(cn), tuple([1,]+[0 for i in range(n-2)]+[-1,]))
   
def EulPoly(n):
    """
    returns flow polytope with n vertices whose volume is given by an Eulerian number
    """
    eg = {j:[j+1,j+2] for j in range(n-2)}
    eg[n-2]=[n-1,]
    return FlowPolytope(DiGraph(eg), tuple([1,]+[0 for i in range(n-2)]+[-1,]))

class FlowPolytope():
       
    def __init__(self, g, v):
        """
        g has to be a directed graph
        """
        self.dgraph = g
        self.v = v
        nume = len(g.edges())
        numv = len(g.vertices())
        m = matrix.identity(nume+1)
        IEQS = [m[i+1] for i in range(nume)]
        vv = [-i for i in v]
        edgemat = matrix([vv]+[elemv(e[0],numv)-elemv(e[1],numv) for e in g.edges()])
        EQS = edgemat.columns()
        #print(IEQS,EQS)
        self.poly = Polyhedron(ieqs=IEQS, eqns=EQS)
   
    def __repr__(self):
        return "Flow polytope: " + self.poly.__repr__() + ", netflow " + str(self.v)
       
   
    def getNetflow(self):
        return self.v
   
    def getGraph(self):
        return self.dgraph
   
    def getPolytope(self):
        return self.poly
   
    def getVolume(self):
        """
        needs Sage 5.9 for 'lrs' engine
        """
        return self.poly.volume(measure = "induced", engine = "lrs")*factorial(self.poly.dim())
   
    def getVertices(self):
        return self.poly.vertices()

I know for a fact that this class creates the Flow Polytope correctly (e.g. a 6-dimensional polytope in QQ^10). 

Ex:

sage: G=DiGraph({0:[1,2,3,4], 1:[2,3,4], 2:[3,4], 3:[4]})

sage: F = FlowPolytope(G, [1,1,1,1,-4])       \\in this case, the [1,1,1,1,-4] vector is the "netflow" that the paper refers to as a. 

sage: F.getVolume().radical_expression()

800*sqrt(5)

In reality, it should be 160.

In this case, the digraph that I entered was the complete graph on 5 vertices. In general, I noticed that regardless of the netflow, whenever I have a flow polytope with a digraph as the complete graph on n+1 vertices, Sage's volume is $\sqrt{ (n+1)^{n-1}}$ times the actual volume (in this case, plugging in n = 4, the volume got dilated by a factor of 5*sqrt(5)). 

What doesn't make sense to me is that if you look at Theorem 1.1 in the paper, which gives the volume formula for the flow polytope with digraph as complete graph on n+1 vertices and the netflow vector I inputted, there is actually no way for a radical to show up. The formula has a factorial, a power of 2, and a product of factorials - no radicals appear. 

[Matthias Koeppe]

On Sunday, February 27, 2022 at 4:16:05 PM UTC-8 Dima Pasechnik wrote:

In fact, it seems that the paper you cite uses a rather unusual way
to normalise the volume:

"The normalized volume vol(P) of a d-dimensional polytope P ⊂ R m is
the volume form which assigns a volume of one to the smallest
d-dimensional integer simplex in the affine span of P."

Sage has this normalization too. It's called "induced_lattice".

 

[Dima Pasechnik]

Indeed:

sage: sage: G=DiGraph({0:[1,2,3,4], 1:[2,3,4], 2:[3,4], 3:[4]})

....: sage: G.flow_polytope().volume(measure = "induced_lattice")
2

There is also "induced_rational". With it, one gets the answer
consistent with the cited paper, too:

sage: sage: G=DiGraph({0:[1,2,3,4], 1:[2,3,4], 2:[3,4], 3:[4]})

....: sage: G.flow_polytope().volume(measure = "induced_rational",
engine = "latte")
1/360

(to get the paper's normalisation, multiply by 720=6!)

>
>
>
>
> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/04fde886-10b1-4938-bae0-ced76e0e9ae6n%40googlegroups.com.

[Matthias Koeppe]

Yes, I guess, "induced_rational" is the one I meant.

I don't recall if it works together with using "lrs" as the engine.

If it doesn't, https://trac.sagemath.org/ticket/31730 ("Polyhedron.affine_hull: New option 'unimodular'") is how to implement it.