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 *
 
 
 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"""
 
 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.
 
     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:
 
 
     .. 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)
 
             # 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)
 
     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
     # 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
     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
     # 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)
 
         rays.append(L.random_element())
         K = Cone(rays)