#18454 closed enhancement (fixed)
New `random_cone()` function
Reported by: | mjo | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.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 follow-up: 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 R2? It's going to take a while indeed =)
In R3, 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 follow-up: 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 R2 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 R1,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.
comment:6 follow-up: 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 R2 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 R2? 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 R1,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.
comment:7 follow-ups: 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 R2 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 R2?
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 R1,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!
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-)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().
|
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-)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.
|
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-)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.
|
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 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.
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 follow-ups: 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) 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?
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 follow-up: 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 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.
|
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.