Opened 8 years ago

Closed 7 years ago

Last modified 5 years ago

#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:

Status badges

Description (last modified by 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.

Change History (30)

comment:1 Changed 8 years ago by mjo

Authors: Michael Orlitzky
Branch: u/mjo/ticket/18454
Commit: 1bbb2d16b104c4f94fcfa56af1e4a2f2fde85ba4
Description: modified (diff)
Status: newneeds_review

New commits:

f364020Trac #18454: Add `is_full_space()` method for polyhedral cones.
b6e06edTrac #18454: Add random_cone() function to sage.geometry.cone.
1bbb2d1Trac #18454: Add random tests to existing cone methods.

comment:2 Changed 8 years ago by 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.

comment:3 in reply to:  2 Changed 8 years ago by 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 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 git

Commit: 1bbb2d16b104c4f94fcfa56af1e4a2f2fde85ba455da704f2f101cfdc25ba1c0b35f38072cb0e7f3

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

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

comment:5 Changed 8 years ago by 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 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 in reply to:  5 ; Changed 8 years ago by 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 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 in reply to:  6 ; Changed 8 years ago by 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 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 in reply to:  7 Changed 8 years ago by 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.

comment:9 Changed 8 years ago by git

Commit: 55da704f2f101cfdc25ba1c0b35f38072cb0e7f39f707bb99e6e4bcc6773c7839cb1c509531dfca5

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

b9eb774Trac #18454: Remove the 2*dim restriction on rays in random_cone().
e3f0076Trac #18454: Allow random_cone() to be (non-)strictly-convex.
cda2547Trac #18454: Remove an unnecessary exception in random_cone().
591768cTrac #18454: Set max_dim on a random_cone() test that could run forever.
9f707bbTrac #18454: Add a "solid" parameter to random_cone().

comment:10 Changed 8 years ago by git

Commit: 9f707bb99e6e4bcc6773c7839cb1c509531dfca5ce3cf22e2847f7636d346534214b1eca47c4a523

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

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

comment:11 Changed 8 years ago by 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.

comment:12 Changed 8 years ago by git

Commit: ce3cf22e2847f7636d346534214b1eca47c4a523a93a757e185b762376f48197bf2a027cd1a00c81

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

a93a757Trac #18454: Catch another infinite loop condition.

comment:13 Changed 8 years ago by git

Commit: a93a757e185b762376f48197bf2a027cd1a00c81a1e69de048eb93f4fabbb777ba88435b7c999c56

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

86746d2Trac #18454: Call set_random_seed() before all random doctests.
a1e69deTrac #18454: Speed up random_cone() doctests.

comment:14 Changed 8 years ago by git

Commit: a1e69de048eb93f4fabbb777ba88435b7c999c561683fd87edc145b84b21c3503e122e942e1904ad

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

0a7b4b6Trac #18454: Allow random_cone() to take a "lattice" parameter.
058e4abTrac #18454: Remove the 2*dim restriction on rays in random_cone().
f6faa2bTrac #18454: Allow random_cone() to be (non-)strictly-convex.
f8e1eb0Trac #18454: Remove an unnecessary exception in random_cone().
52c148aTrac #18454: Set max_dim on a random_cone() test that could run forever.
63f92c4Trac #18454: Add a "solid" parameter to random_cone().
cb7cd15Trac #18454: Fix warning block formatting in random_cone().
b86adc1Trac #18454: Catch another infinite loop condition.
3d2151bTrac #18454: Call set_random_seed() before all random doctests.
1683fd8Trac #18454: Speed up random_cone() doctests.

comment:15 Changed 8 years ago by mjo

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 git

Commit: 1683fd87edc145b84b21c3503e122e942e1904ad7bdaf1cd51d8f6f3007f11888991cefc186a4ee1

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

99247ffTrac #18454: Allow random_cone() to take a "lattice" parameter.
de59dd1Trac #18454: Remove the 2*dim restriction on rays in random_cone().
deeb2ecTrac #18454: Allow random_cone() to be (non-)strictly-convex.
44ac645Trac #18454: Remove an unnecessary exception in random_cone().
909997aTrac #18454: Set max_dim on a random_cone() test that could run forever.
bd24822Trac #18454: Add a "solid" parameter to random_cone().
ba66027Trac #18454: Fix warning block formatting in random_cone().
8b2ff99Trac #18454: Catch another infinite loop condition.
78c206fTrac #18454: Call set_random_seed() before all random doctests.
7bdaf1cTrac #18454: Speed up random_cone() doctests.

comment:17 in reply to:  7 Changed 8 years ago by 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.

comment:18 Changed 8 years ago by novoselt

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

comment:19 Changed 8 years ago by 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?

comment:20 Changed 8 years ago by 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?

comment:21 Changed 8 years ago by git

Commit: 7bdaf1cd51d8f6f3007f11888991cefc186a4ee15bf86a61fb7f1e41fa1c472c73789eb51c5586fd

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

52a1e4bTrac #18454: Rename min/max_dim to min/max_ambient_dim in random_cone().
a0235dcTrac #18454: Fix two confusing random_cone() examples.
5b1eccbTrac #18454: Remove some excessive doctests for random_cone().
5bf86a6Trac #18454: Clean up long random_cone() tests.

comment:22 in reply to:  19 Changed 8 years ago by 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...

comment:23 in reply to:  19 Changed 8 years ago by 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.

comment:24 Changed 7 years ago by novoselt

Branch: u/mjo/ticket/18454u/novoselt/ticket/18454

comment:25 Changed 7 years ago by novoselt

Commit: 5bf86a61fb7f1e41fa1c472c73789eb51c5586fda07efa959bcbd088f34e3e4b7bd0a653cfaa998d

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:

cd6aec8Fix isomorphism check for trivial cones.
af4b248Trivial cones in 2-d lattices also have isomorphism issues.
c02beeeFix echelon_form of trivial matrices.
deed947Drop wrong pivots from the output of HNF with transformation.
e6e7a80Merge branch 't/18613/errors_with_is_isomorphic___for_trivial_cones' into t/18454/ticket/18454
a07efa9Reviewer's tweaks to random cones.

comment:26 in reply to:  25 Changed 7 years ago by 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.

comment:27 Changed 7 years ago by mjo

Branch: u/novoselt/ticket/18454u/mjo/ticket/18454
Commit: a07efa959bcbd088f34e3e4b7bd0a653cfaa998d8c962e18f07c294b96aedf12ae88069f456f099b

Last 10 new commits:

8b2ff99Trac #18454: Catch another infinite loop condition.
78c206fTrac #18454: Call set_random_seed() before all random doctests.
7bdaf1cTrac #18454: Speed up random_cone() doctests.
52a1e4bTrac #18454: Rename min/max_dim to min/max_ambient_dim in random_cone().
a0235dcTrac #18454: Fix two confusing random_cone() examples.
5b1eccbTrac #18454: Remove some excessive doctests for random_cone().
5bf86a6Trac #18454: Clean up long random_cone() tests.
e6e7a80Merge branch 't/18613/errors_with_is_isomorphic___for_trivial_cones' into t/18454/ticket/18454
a07efa9Reviewer's tweaks to random cones.
8c962e1Trac #18454: Remove more redundant (long) tests.

comment:28 Changed 7 years ago by novoselt

Reviewers: Andrey Novoseltsev
Status: needs_reviewpositive_review

Thumbs up!

comment:29 Changed 7 years ago by vbraun

Branch: u/mjo/ticket/184548c962e18f07c294b96aedf12ae88069f456f099b
Resolution: fixed
Status: positive_reviewclosed

comment:30 Changed 5 years ago by jdemeyer

Commit: 8c962e18f07c294b96aedf12ae88069f456f099b

This recently started breaking, no idea why...

See #24517

Note: See TracTickets for help on using tickets.