#18454 closed enhancement (fixed)
New `random_cone()` function
Reported by:  mjo  Owned by:  

Priority:  major  Milestone:  sage6.8 
Component:  geometry  Keywords:  
Cc:  Merged in:  
Authors:  Michael Orlitzky  Reviewers:  Andrey Novoseltsev 
Report Upstream:  N/A  Work issues:  
Branch:  8c962e1 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
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.
Change History (30)
comment:1 Changed 8 years ago by
Authors:  → Michael Orlitzky 

Branch:  → u/mjo/ticket/18454 
Commit:  → 1bbb2d16b104c4f94fcfa56af1e4a2f2fde85ba4 
Description:  modified (diff) 
Status:  new → needs_review 
comment:2 followup: 3 Changed 8 years ago by
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.
comment:3 Changed 8 years ago by
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^{2}? It's going to take a while indeed =)
In R^{3}, 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.
comment:4 Changed 8 years ago by
Commit:  1bbb2d16b104c4f94fcfa56af1e4a2f2fde85ba4 → 55da704f2f101cfdc25ba1c0b35f38072cb0e7f3 

Branch pushed to git repo; I updated commit sha1. New commits:
55da704  Trac #18454: Allow random_cone() to take a "lattice" parameter.

comment:5 followup: 6 Changed 8 years ago by
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^{2} 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 ngon 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.
comment:6 followup: 7 Changed 8 years ago by
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^{2} 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^{2}? 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 ngon 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.
comment:7 followups: 8 17 Changed 8 years ago by
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^{2} 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^{2}?
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 ngon 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!
comment:8 Changed 8 years ago by
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.
comment:9 Changed 8 years ago by
Commit:  55da704f2f101cfdc25ba1c0b35f38072cb0e7f3 → 9f707bb99e6e4bcc6773c7839cb1c509531dfca5 

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)strictlyconvex.

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().

comment:10 Changed 8 years ago by
Commit:  9f707bb99e6e4bcc6773c7839cb1c509531dfca5 → ce3cf22e2847f7636d346534214b1eca47c4a523 

Branch pushed to git repo; I updated commit sha1. New commits:
ce3cf22  Trac #18454: Fix warning block formatting in random_cone().

comment:11 Changed 8 years ago by
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.
comment:12 Changed 8 years ago by
Commit:  ce3cf22e2847f7636d346534214b1eca47c4a523 → a93a757e185b762376f48197bf2a027cd1a00c81 

Branch pushed to git repo; I updated commit sha1. New commits:
a93a757  Trac #18454: Catch another infinite loop condition.

comment:13 Changed 8 years ago by
Commit:  a93a757e185b762376f48197bf2a027cd1a00c81 → a1e69de048eb93f4fabbb777ba88435b7c999c56 

comment:14 Changed 8 years ago by
Commit:  a1e69de048eb93f4fabbb777ba88435b7c999c56 → 1683fd87edc145b84b21c3503e122e942e1904ad 

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)strictlyconvex.

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.

comment:15 Changed 8 years ago by
There are no new changes there, just a rebase on top of 6.8.beta4 for the sake of ticket #18696.
comment:16 Changed 8 years ago by
Commit:  1683fd87edc145b84b21c3503e122e942e1904ad → 7bdaf1cd51d8f6f3007f11888991cefc186a4ee1 

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)strictlyconvex.

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.

comment:17 Changed 8 years ago by
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 viceversa) 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.
comment:18 Changed 8 years ago by
I really hope to review it this coming week! (As well as small follow ups that you have posted.)
comment:19 followups: 22 23 Changed 8 years ago by
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) 0d cone in 4d 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?
comment:20 Changed 8 years ago by
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?
comment:21 Changed 8 years ago by
Commit:  7bdaf1cd51d8f6f3007f11888991cefc186a4ee1 → 5bf86a61fb7f1e41fa1c472c73789eb51c5586fd 

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.

comment:22 Changed 8 years ago by
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...
comment:23 Changed 8 years ago by
Replying to novoselt:
I would be in favour of using
min/max_dim
for the dimension of the cone, allowing specifyinglattice
together with these parameters as long as its dimension is at leastmax_dim
, and when not given defaulting tomax_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.
comment:24 Changed 7 years ago by
Branch:  u/mjo/ticket/18454 → u/novoselt/ticket/18454 

comment:25 followup: 26 Changed 7 years ago by
Commit:  5bf86a61fb7f1e41fa1c472c73789eb51c5586fd → a07efa959bcbd088f34e3e4b7bd0a653cfaa998d 

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 overcommented 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 2d 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.

comment:26 Changed 7 years ago by
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.
comment:27 Changed 7 years ago by
Branch:  u/novoselt/ticket/18454 → u/mjo/ticket/18454 

Commit:  a07efa959bcbd088f34e3e4b7bd0a653cfaa998d → 8c962e18f07c294b96aedf12ae88069f456f099b 
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.

comment:28 Changed 7 years ago by
Reviewers:  → Andrey Novoseltsev 

Status:  needs_review → positive_review 
Thumbs up!
comment:29 Changed 7 years ago by
Branch:  u/mjo/ticket/18454 → 8c962e18f07c294b96aedf12ae88069f456f099b 

Resolution:  → fixed 
Status:  positive_review → closed 
comment:30 Changed 5 years ago by
Commit:  8c962e18f07c294b96aedf12ae88069f456f099b 

This recently started breaking, no idea why...
See #24517
New commits:
Trac #18454: Add `is_full_space()` method for polyhedral cones.
Trac #18454: Add random_cone() function to sage.geometry.cone.
Trac #18454: Add random tests to existing cone methods.