New `random_cone()` function

[mjo]

For testing algebraic properties of cones (for example, the dual of a dual cone is the original cone) it is useful to be able to generate "random" cones.

[mjo]

New commits:

​f364020	Trac #18454: Add `is_full_space()` method for polyhedral cones.
​b6e06ed	Trac #18454: Add random_cone() function to sage.geometry.cone.
​1bbb2d1	Trac #18454: Add random tests to existing cone methods.

[novoselt]

I will surely have more picks, but for starters:

• it would be nice to have an option of specifying the lattice of the random cone

• decision to limit maximum number of rays to double dimension is not natural - I would drop it completely, but perhaps warn the user in documentation that it may take a while to generate a random cone with a lot of rays of low dimension. If you are up to the "guaranteed possible maximum" then it is dimension plus one - consider the cone on the vertices of a simplex containing the origin.

[mjo]

Replying to novoselt:

I will surely have more picks, but for starters:

• it would be nice to have an option of specifying the lattice of the random cone

Thanks, I can try to do this one.

• decision to limit maximum number of rays to double dimension is not natural - I would drop it completely, but perhaps warn the user in documentation that it may take a while to generate a random cone with a lot of rays of low dimension.

I wasn't sure what to do here. I was trying to avoid returning a cone with e.g. four rays when the user specified min_rays == max_rays == 10 (for example). What do we do if the user requests a minimum of 100 rays in R²? It's going to take a while indeed =)

In R³, it might happen by chance, but the current algorithm won't get there eventually: we're appending new rays to a list, and once we have plus/minus the standard basis, we can append forever and never get any new generators. We'd have to throw out the cone once it becomes the whole space and start over.

[git]

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

​55da704

Trac #18454: Allow random_cone() to take a "lattice" parameter.

[novoselt]

Well, it would be helpful to know in what sense the cone is "random". If it is a cone on a random set of rays, then dimension+1 is the only sensible upper bound to me - such a cone always can be constructed. In R² it may be possible to force construction of cones with more than 4 rays - given that the code can handle 4 instead of 3 for the whole space, probably it can live with 100. But if we are talking about the minimal number of extremal rays, then for R^1,2 maximum is the dimension and for all others we can do anything - generate a random n-gon in a plane and lift it.

In most cases I think you would want a strictly convex cone, so that's exactly what you want with bonus points if primitive generators are not necessarily in the same hyperplane. Algorithm: generate random vectors with positive last component. There may be an extra switch to allow linear subspaces in cones.

[mjo]

Replying to novoselt:

Well, it would be helpful to know in what sense the cone is "random". If it is a cone on a random set of rays, then dimension+1 is the only sensible upper bound to me - such a cone always can be constructed.

In any dimension you can do better, up to 2*dimension -- just take the standard basis and add negative multiples of them. The resulting come will have 2*dimension generating rays and be equal to the entire space.

In R² it may be possible to force construction of cones with more than 4 rays - given that the code can handle 4 instead of 3 for the whole space, probably it can live with 100.

Can you really get more than four in R²? I haven't tried to prove it but geometrically, once you have four and try to add one more, the fifth one should either be contained in the cone already (obsoleting the new one), or be above/below some other generator (obsoleting the old one).

But if we are talking about the minimal number of extremal rays, then for R^1,2 maximum is the dimension and for all others we can do anything - generate a random n-gon in a plane and lift it.

Right, so here you definitely wouldn't want to limit the number of rays to dimension+1.

In most cases I think you would want a strictly convex cone, so that's exactly what you want with bonus points if primitive generators are not necessarily in the same hyperplane. Algorithm: generate random vectors with positive last component. There may be an extra switch to allow linear subspaces in cones.

When I started working on this, I thought I was interested in proper (strictly convex, nonempty interior) cones. But the stuff I'm doing appears to generalize, and none of my test cases require this (nor do the test cases I added in commit 1bbb2d1). But I agree it would be useful. I'll try to add a strictly_convex = None/True/False parameter. Likewise for solid = None/True/False if it doesn't look too hard.

[novoselt]

Replying to mjo:

Replying to novoselt:

Well, it would be helpful to know in what sense the cone is "random". If it is a cone on a random set of rays, then dimension+1 is the only sensible upper bound to me - such a cone always can be constructed.

In any dimension you can do better, up to 2*dimension -- just take the standard basis and add negative multiples of them. The resulting come will have 2*dimension generating rays and be equal to the entire space.

"Better" in what sense? Take (or "generate randomly") rays (1,0), (0,1), (-1,-1) in the plane and you can no longer add rays which are independent of these three. "Random generation" of four rays in opposite pairs is much less likely to happen. So if you keep generating rays removing those which are dependent with already constructed ones until you reach a predefined maximum, you cannot guarantee that more than 3 are possible.

In R² it may be possible to force construction of cones with more than 4 rays - given that the code can handle 4 instead of 3 for the whole space, probably it can live with 100.

Can you really get more than four in R²?

I meant that you can have a cone in the plane with a hundred rays that you decided to call generating ones - Sage constructors may allow you to do it for cones with linear subspaces, although I don't know why one would want it.

But if we are talking about the minimal number of extremal rays, then for R^1,2 maximum is the dimension and for all others we can do anything - generate a random n-gon in a plane and lift it.

Right, so here you definitely wouldn't want to limit the number of rays to dimension+1.

Nor to twice the dimension!

[mjo]

Replying to novoselt:

Right, so here you definitely wouldn't want to limit the number of rays to dimension+1.

Nor to twice the dimension!

Ok, point taken =)

I'll remove the restriction in the next commit and add warnings to the docs. It looks easy to add a strictly_convex parameter, so that's on its way too. Letting the user request a solid cone is a mess, though.

[git]

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

​b9eb774	Trac #18454: Remove the 2*dim restriction on rays in random_cone().
​e3f0076	Trac #18454: Allow random_cone() to be (non-)strictly-convex.
​cda2547	Trac #18454: Remove an unnecessary exception in random_cone().
​591768c	Trac #18454: Set max_dim on a random_cone() test that could run forever.
​9f707bb	Trac #18454: Add a "solid" parameter to random_cone().

[git]

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

​ce3cf22

Trac #18454: Fix warning block formatting in random_cone().

[mjo]

That wasn't too bad. I removed all of the unnecessary restrictions. The only ones that remain avoid (guaranteed) infinite loops. Almost all of the code is in sanity checks, error reporting, and tests.

Once I refactored for strictly_convex, solid wasn't so hard anymore. By putting everything in a loop, it makes it easy to throw the current cone away and start over. We therefore don't have to try too hard to fix an unpromising cone.

[git]

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

​a93a757

Trac #18454: Catch another infinite loop condition.

[git]

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

​86746d2	Trac #18454: Call set_random_seed() before all random doctests.
​a1e69de	Trac #18454: Speed up random_cone() doctests.

[git]

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

​0a7b4b6	Trac #18454: Allow random_cone() to take a "lattice" parameter.
​058e4ab	Trac #18454: Remove the 2*dim restriction on rays in random_cone().
​f6faa2b	Trac #18454: Allow random_cone() to be (non-)strictly-convex.
​f8e1eb0	Trac #18454: Remove an unnecessary exception in random_cone().
​52c148a	Trac #18454: Set max_dim on a random_cone() test that could run forever.
​63f92c4	Trac #18454: Add a "solid" parameter to random_cone().
​cb7cd15	Trac #18454: Fix warning block formatting in random_cone().
​b86adc1	Trac #18454: Catch another infinite loop condition.
​3d2151b	Trac #18454: Call set_random_seed() before all random doctests.
​1683fd8	Trac #18454: Speed up random_cone() doctests.

[mjo]

There are no new changes there, just a rebase on top of 6.8.beta4 for the sake of ticket #18696.

[git]

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

​99247ff	Trac #18454: Allow random_cone() to take a "lattice" parameter.
​de59dd1	Trac #18454: Remove the 2*dim restriction on rays in random_cone().
​deeb2ec	Trac #18454: Allow random_cone() to be (non-)strictly-convex.
​44ac645	Trac #18454: Remove an unnecessary exception in random_cone().
​909997a	Trac #18454: Set max_dim on a random_cone() test that could run forever.
​bd24822	Trac #18454: Add a "solid" parameter to random_cone().
​ba66027	Trac #18454: Fix warning block formatting in random_cone().
​8b2ff99	Trac #18454: Catch another infinite loop condition.
​78c206f	Trac #18454: Call set_random_seed() before all random doctests.
​7bdaf1c	Trac #18454: Speed up random_cone() doctests.

[mjo]

Replying to novoselt:

Is there anything I can do to help get this reviewed? Bribery and/or trade reviews?

I have a bunch of "easy" (new method) tickets in the pipeline for a paper I'm working on, and I've used random testing for many of the properties in those tickets. I'd like to be able to cite Sage in the paper (and vice-versa) as a working implementation if we can get the algorithm merged in time.

If there are any implementation bugs, the output is either random or an error so I can just fix them and no one should notice =)

I'm happy to seek out other reviewers if you'd prefer, but I know the cone code is your baby so I'd prefer that you review it if you can.

[novoselt]

I really hope to review it this coming week! (As well as small follow ups that you have posted.)

[novoselt]

I have a problem with min/max_dim - I was sure they talk about the dimension of the cone, until I got to their description. The example with it is also confusing:

    We can predict the dimension when ``min_dim == max_dim``::

        sage: set_random_seed()
        sage: random_cone(min_dim=4, max_dim=4, min_rays=0, max_rays=0)
        0-d cone in 4-d lattice N

To me this looks like we predict the dimension 0 based on min/max_rays.

I would be in favour of using min/max_dim for the dimension of the cone, allowing specifying lattice together with these parameters as long as its dimension is at least max_dim, and when not given defaulting to max_dim-dimensional lattice. If you don't want to work on such functionality, can we please rename parameters to min/max_ambient_dim to avoid ambiguity when reading calls of this function?

[novoselt]

I am not a big fun of examples that generate multiple cones of the same type to make sure that things are OK. What's the point? These tests WILL be run multiple times by users and patchbots during global testing, aren't these repetitions enough?

[git]

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

​52a1e4b	Trac #18454: Rename min/max_dim to min/max_ambient_dim in random_cone().
​a0235dc	Trac #18454: Fix two confusing random_cone() examples.
​5b1eccb	Trac #18454: Remove some excessive doctests for random_cone().
​5bf86a6	Trac #18454: Clean up long random_cone() tests.

[mjo]

Replying to novoselt:

I have a problem with min/max_dim - I was sure they talk about the dimension of the cone, until I got to their description. The example with it is also confusing:

Right on both counts. I renamed the parameters, and fixed those two doctests. Now I save the result of random_cone() and check only the relevant property.

I also removed a bunch of the redundant tests and cleaned up a little.

I think I'm receiving trac notifications again so I should be more responsive...

[mjo]

Replying to novoselt:

I would be in favour of using min/max_dim for the dimension of the cone, allowing specifying lattice together with these parameters as long as its dimension is at least max_dim, and when not given defaulting to max_dim-dimensional lattice. If you don't want to work on such functionality...

(I forgot to respond to this part).

I don't need this ability, and I'm already pretty deep in trac ticket debt, so I don't want to add any more knobs right now. I'd be willing to add it later on if someone requests it though.

[novoselt]

OK:

• merged current version of #18613 to make isomorphism checks work as expected
• there was a duplicate piece of code, removed
• I tweaked some code, hopefully not unreasonably

Regarding redundant tests I was mostly complaining about things like

    Ensure that we can generate cones which are not strictly convex
    (can take a long time)::

        sage: set_random_seed()                         # long time
        sage: l = [ random_cone(min_ambient_dim=1,      # long time
        ....:                   max_ambient_dim=8,      # long time
        ....:                   min_rays=2,             # long time
        ....:                   max_rays=10,            # long time
        ....:                   strictly_convex=False)\
        ....:                   .is_strictly_convex()   # long time
        ....:       for i in range(0,10)]               # long time
        sage: any(l)                                    # long time
        False

    As well as ones that are strictly convex::

        sage: set_random_seed()                        # long time
        sage: l = [ random_cone(min_ambient_dim=1,     # long time
        ....:                   max_ambient_dim=8,     # long time
        ....:                   min_rays=2,            # long time
        ....:                   max_rays=10,           # long time
        ....:                   strictly_convex=True)\
        ....:                   .is_strictly_convex()  # long time
        ....:       for i in range(0,10) ]             # long time
        sage: all(l)                                   # long time
        True

given that above we have

    We can also request a strictly convex cone::

        sage: set_random_seed()
        sage: K = random_cone(max_ambient_dim=8, max_rays=10,
        ....:                 strictly_convex=True)
        sage: K.is_strictly_convex()
        True

    Or one that isn't strictly convex::

        sage: set_random_seed()
        sage: K = random_cone(min_ambient_dim=5, min_rays=2,
        ....:                 strictly_convex=False)
        sage: K.is_strictly_convex()
        False

Since this single random tests will be repeated many times on different machines, I see little point in running 10 tests for longer version. But if you really like to keep them it is fine with me.

The code also seems a bit over-commented to me, but if you had to have them there probably others can appreciate it as well. And #18613 has clearly demonstrated that it is a very useful addition!

Bottom line: set to positive review if you are OK with my changes (and perhaps review #18613 as well?-))

---

New commits:

​cd6aec8	Fix isomorphism check for trivial cones.
​af4b248	Trivial cones in 2-d lattices also have isomorphism issues.
​c02beee	Fix echelon_form of trivial matrices.
​deed947	Drop wrong pivots from the output of HNF with transformation.
​e6e7a80	Merge branch 't/18613/errors_with_is_isomorphic___for_trivial_cones' into t/18454/ticket/18454
​a07efa9	Reviewer's tweaks to random cones.

[mjo]

Replying to novoselt:

OK:

• merged current version of #18613 to make isomorphism checks work as expected
• there was a duplicate piece of code, removed
• I tweaked some code, hopefully not unreasonably

Regarding redundant tests I was mostly complaining about things like... But if you really like to keep them it is fine with me.

Nope, I just had some other redundant tests in mind. You're right, I've removed them. Thanks for the rest of the changes, too, they all look good. Just need a thumbs up on my last commit and I think this is ready.

[mjo]

Last 10 new commits:

​8b2ff99	Trac #18454: Catch another infinite loop condition.
​78c206f	Trac #18454: Call set_random_seed() before all random doctests.
​7bdaf1c	Trac #18454: Speed up random_cone() doctests.
​52a1e4b	Trac #18454: Rename min/max_dim to min/max_ambient_dim in random_cone().
​a0235dc	Trac #18454: Fix two confusing random_cone() examples.
​5b1eccb	Trac #18454: Remove some excessive doctests for random_cone().
​5bf86a6	Trac #18454: Clean up long random_cone() tests.
​e6e7a80	Merge branch 't/18613/errors_with_is_isomorphic___for_trivial_cones' into t/18454/ticket/18454
​a07efa9	Reviewer's tweaks to random cones.
​8c962e1	Trac #18454: Remove more redundant (long) tests.

[novoselt]

Thumbs up!

[jdemeyer]

This recently started breaking, no idea why...

See #24517