X-Git-Url: http://gitweb.michael.orlitzky.com/?a=blobdiff_plain;f=mjo%2Fcone%2Fdoubly_nonnegative.py;h=5e10e1aebaad4c17de9e129681a57bb736e72886;hb=7af2b9d146a6bf2fb8acc3c342983de577b417ce;hp=56a655e52c5cd60cbf1073c351e65833e5f54500;hpb=95353d1a02424f49e4691d6f4ecef9bd5d267311;p=sage.d.git diff --git a/mjo/cone/doubly_nonnegative.py b/mjo/cone/doubly_nonnegative.py index 56a655e..5e10e1a 100644 --- a/mjo/cone/doubly_nonnegative.py +++ b/mjo/cone/doubly_nonnegative.py @@ -1,4 +1,4 @@ -""" +r""" The doubly-nonnegative cone in `S^{n}` is the set of all such matrices that both, @@ -13,14 +13,9 @@ It is represented typically by either `\mathcal{D}^{n}` or from sage.all import * -# Sage doesn't load ~/.sage/init.sage during testing (sage -t), so we -# have to explicitly mangle our sitedir here so that our module names -# resolve. -from os.path import abspath -from site import addsitedir -addsitedir(abspath('../../')) -from mjo.cone.symmetric_psd import factor_psd, is_symmetric_psd, random_psd -from mjo.matrix_vector import isomorphism +from mjo.cone.symmetric_psd import (factor_psd, + random_symmetric_psd) +from mjo.basis_repr import basis_repr def is_doubly_nonnegative(A): @@ -36,6 +31,10 @@ def is_doubly_nonnegative(A): Either ``True`` if ``A`` is doubly-nonnegative, or ``False`` otherwise. + SETUP:: + + sage: from mjo.cone.doubly_nonnegative import is_doubly_nonnegative + EXAMPLES: Every completely positive matrix is doubly-nonnegative:: @@ -58,17 +57,17 @@ def is_doubly_nonnegative(A): raise ValueError.new(msg) # Check that all of the entries of ``A`` are nonnegative. - if not all([ a >= 0 for a in A.list() ]): + if not all( a >= 0 for a in A.list() ): return False # It's nonnegative, so all we need to do is check that it's # symmetric positive-semidefinite. - return is_symmetric_psd(A) + return A.is_positive_semidefinite() def is_admissible_extreme_rank(r, n): - """ + r""" The extreme matrices of the doubly-nonnegative cone have some restrictions on their ranks. This function checks to see whether the rank ``r`` would be an admissible rank for an ``n``-by-``n`` matrix. @@ -85,6 +84,10 @@ def is_admissible_extreme_rank(r, n): the doubly-nonnegative cone in `$\mathbb{R}^{n}$`, or ``False`` otherwise. + SETUP:: + + sage: from mjo.cone.doubly_nonnegative import is_admissible_extreme_rank + EXAMPLES: For dimension 5, only ranks zero, one, and three are admissible:: @@ -150,6 +153,10 @@ def has_admissible_extreme_rank(A): 26 (1996), no. 4, 1371--1383. doi:10.1216/rmjm/1181071993. http://projecteuclid.org/euclid.rmjm/1181071993. + SETUP:: + + sage: from mjo.cone.doubly_nonnegative import has_admissible_extreme_rank + EXAMPLES: The zero matrix has rank zero, which is admissible:: @@ -196,7 +203,7 @@ def has_admissible_extreme_rank(A): return is_admissible_extreme_rank(r,n) -def E(matrix_space, i,j): +def stdE(matrix_space, i,j): """ Return the ``i``,``j``th element of the standard basis in ``matrix_space``. @@ -215,26 +222,30 @@ def E(matrix_space, i,j): A basis element of ``matrix_space``. It has a single \"1\" in the ``i``,``j`` row,column and zeros elsewhere. + SETUP:: + + sage: from mjo.cone.doubly_nonnegative import stdE + EXAMPLES:: sage: M = MatrixSpace(ZZ, 2, 2) - sage: E(M,0,0) + sage: stdE(M,0,0) [1 0] [0 0] - sage: E(M,0,1) + sage: stdE(M,0,1) [0 1] [0 0] - sage: E(M,1,0) + sage: stdE(M,1,0) [0 0] [1 0] - sage: E(M,1,1) + sage: stdE(M,1,1) [0 0] [0 1] - sage: E(M,2,1) + sage: stdE(M,2,1) Traceback (most recent call last): ... IndexError: Index `i` is out of bounds. - sage: E(M,1,2) + sage: stdE(M,1,2) Traceback (most recent call last): ... IndexError: Index `j` is out of bounds. @@ -253,7 +264,7 @@ def E(matrix_space, i,j): # would be computed as offset 3 into a four-element list and we # would succeed incorrectly. idx = matrix_space.ncols()*i + j - return matrix_space.basis()[idx] + return list(matrix_space.basis())[idx] @@ -272,6 +283,10 @@ def is_extreme_doubly_nonnegative(A): 2. Berman, Abraham and Shaked-Monderer, Naomi. Completely Positive Matrices. World Scientific, 2003. + SETUP:: + + sage: from mjo.cone.doubly_nonnegative import is_extreme_doubly_nonnegative + EXAMPLES: The zero matrix is an extreme matrix:: @@ -338,7 +353,7 @@ def is_extreme_doubly_nonnegative(A): # Short circuit, we know the zero matrix is extreme. return True - if not is_symmetric_psd(A): + if not A.is_positive_semidefinite(): return False # Step 1.5, appeal to Theorem 3.1 in reference #1 to short @@ -355,11 +370,11 @@ def is_extreme_doubly_nonnegative(A): # whenever we come across an index pair `$(i,j)$` with # `$A_{ij} = 0$`. spanning_set = [] - for j in range(0, A.ncols()): - for i in range(0,j): + for j in range(A.ncols()): + for i in range(j): if A[i,j] == 0: M = A.matrix_space() - S = X.transpose() * (E(M,i,j) + E(M,j,i)) * X + S = X.transpose() * (stdE(M,i,j) + stdE(M,j,i)) * X spanning_set.append(S) # The spanning set that we have at this point is of matrices. We @@ -367,7 +382,7 @@ def is_extreme_doubly_nonnegative(A): # can't compute the dimension of a set of matrices anyway, so we # convert them all to vectors and just ask for the dimension of the # resulting vector space. - (phi, phi_inverse) = isomorphism(A.matrix_space()) + (phi, phi_inverse) = basis_repr(A.matrix_space()) vectors = map(phi,spanning_set) V = span(vectors, A.base_ring()) @@ -405,6 +420,11 @@ def random_doubly_nonnegative(V, accept_zero=True, rank=None): A random doubly nonnegative matrix, i.e. a linear transformation from ``V`` to itself. + SETUP:: + + sage: from mjo.cone.doubly_nonnegative import (is_doubly_nonnegative, + ....: random_doubly_nonnegative) + EXAMPLES: Well, it doesn't crash at least:: @@ -439,10 +459,10 @@ def random_doubly_nonnegative(V, accept_zero=True, rank=None): # Generate random symmetric positive-semidefinite matrices until # one of them is nonnegative, then return that. - A = random_psd(V, accept_zero, rank) + A = random_symmetric_psd(V, accept_zero, rank) - while not all([ x >= 0 for x in A.list() ]): - A = random_psd(V, accept_zero, rank) + while not all( x >= 0 for x in A.list() ): + A = random_symmetric_psd(V, accept_zero, rank) return A @@ -475,6 +495,11 @@ def random_extreme_doubly_nonnegative(V, accept_zero=True, rank=None): A random extreme doubly nonnegative matrix, i.e. a linear transformation from ``V`` to itself. + SETUP:: + + sage: from mjo.cone.doubly_nonnegative import (is_extreme_doubly_nonnegative, + ....: random_extreme_doubly_nonnegative) + EXAMPLES: Well, it doesn't crash at least:: @@ -504,7 +529,7 @@ def random_extreme_doubly_nonnegative(V, accept_zero=True, rank=None): """ - if not is_admissible_extreme_rank(rank, V.dimension()): + if rank is not None and not is_admissible_extreme_rank(rank, V.dimension()): msg = 'Rank %d not possible in dimension %d.' raise ValueError(msg % (rank, V.dimension()))