Don't count on 2*dim(V) rays generating V.

[sage.d.git] / mjo / cone / cone.py

diff --git a/mjo/cone/cone.py b/mjo/cone/cone.py
index 132c6d9e8e63ebbc5e0065becd813f341e993dd0..3b724a7c0fe8d0305351aae778b23978ed79e8f4 100644 (file)
--- 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)