From b1f56b9fd21ce64f0d4613d1d07e090e89eba621 Mon Sep 17 00:00:00 2001 From: Michael Orlitzky Date: Tue, 19 May 2015 14:15:23 -0400 Subject: [PATCH] Don't count on 2*dim(V) rays generating V. --- mjo/cone/cone.py | 37 ++++++++++++++++--------------------- 1 file changed, 16 insertions(+), 21 deletions(-) diff --git a/mjo/cone/cone.py b/mjo/cone/cone.py index 132c6d9..3b724a7 100644 --- a/mjo/cone/cone.py +++ b/mjo/cone/cone.py @@ -7,13 +7,6 @@ addsitedir(abspath('../../')) from sage.all import * -# TODO: This test fails, maybe due to a bug in the existing cone code. -# If we request enough generators to span the space, then the returned -# cone should equal the ambient space:: -# -# sage: K = random_cone(min_dim=5, max_dim=5, min_rays=10, max_rays=10) -# sage: K.lines().dimension() == K.lattice_dim() -# True def random_cone(min_dim=0, max_dim=None, min_rays=0, max_rays=None): r""" @@ -24,11 +17,13 @@ def random_cone(min_dim=0, max_dim=None, min_rays=0, max_rays=None): lower bound is left unspecified, it defaults to zero. Unspecified upper bounds will be chosen randomly. - The number of generating rays is naturally limited to twice the - dimension of the ambient space. Take for example $\mathbb{R}^{2}$. - You could have the generators $\left\{ \pm e_{1}, \pm e_{2} - \right\}$, with cardinality $4 = 2 \cdot 2$; however any other ray - in the space is a nonnegative linear combination of those four. + The lower bound on the number of rays is limited to twice the + maximum dimension of the ambient vector space. To see why, consider + the space $\mathbb{R}^{2}$, and suppose we have generated four rays, + $\left\{ \pm e_{1}, \pm e_{2} \right\}$. Clearly any other ray in + the space is a nonnegative linear combination of those four, + so it is hopeless to generate more. It is therefore an error + to request more in the form of ``min_rays``. .. NOTE: @@ -167,6 +162,11 @@ def random_cone(min_dim=0, max_dim=None, min_rays=0, max_rays=None): # ZZ.random_element() docs. return l + ZZ.random_element(u - l + 1) + def is_full_space(K): + r""" + Is this cone equivalent to the full ambient vector space? + """ + return K.lines().dim() == K.lattice_dim() d = random_min_max(min_dim, max_dim) r = random_min_max(min_rays, max_rays) @@ -177,13 +177,7 @@ def random_cone(min_dim=0, max_dim=None, min_rays=0, max_rays=None): # 2*v as our "two rays." In that case, the resuting cone would # have one generating ray. To avoid such a situation, we start by # generating ``r`` rays where ``r`` is the number we want to end - # up with. - # - # However, since we're going to *check* whether or not we actually - # have ``r``, we need ``r`` rays to be attainable. So we need to - # limit ``r`` to twice the dimension of the ambient space. - # - r = min(r, 2*d) + # up with... rays = [L.random_element() for i in range(0, r)] # (The lattice parameter is required when no rays are given, so we @@ -193,8 +187,9 @@ def random_cone(min_dim=0, max_dim=None, min_rays=0, max_rays=None): # Now if we generated two of the "same" rays, we'll have fewer # generating rays than ``r``. In that case, we keep making up new # rays and recreating the cone until we get the right number of - # independent generators. - while r > K.nrays(): + # independent generators. We can obviously stop if ``K`` is the + # entire ambient vector space. + while r > K.nrays() and not is_full_space(K): rays.append(L.random_element()) K = Cone(rays) -- 2.44.2