Changeset 7488:ee41e552f7c7

Timestamp:

12/01/07 21:59:22 (6 years ago)

Author:

mabshoff@…

Branch:

default

Parents:

7486:b75f20360b8d (diff), 7487:733fe81ceb61 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

merge

Files:

• sage/matrix/matrix2.pyx (modified) (3 diffs)
• sage/matrix/matrix2.pyx (modified) (1 diff)

sage/matrix/matrix2.pyx

@@ -381 +381 @@
             return R(0)
 
-        k = int(k)
         pm = 0
         for cols in _choose(n,k):
@@ -3062 +3061 @@
         return -1
 
+
 def _choose(Py_ssize_t n, Py_ssize_t t):
     """
     Returns all possible sublists of length t from range(n)
 
-    Based on algoritm L from Knuth's taocp part 4: 7.2.1.3 p.4
+    Based on algoritm T from Knuth's taocp part 4: 7.2.1.3 p.5
+    This fuction replaces the one base on algorithm L because it is faster.
+
+    EXAMPLES:
+        sage: from sage.matrix.matrix2 import _choose
+        sage: _choose(1,1)
+        [[0]]
+        sage: _choose(4,1)
+        [[0], [1], [2], [3]]
+        sage: _choose(4,4)
+        [[0, 1, 2, 3]]
 
     AUTHOR:
-        -- Jaap Spies (2007-10-22)
+        -- Jaap Spies (2007-11-14)
     """
-    cdef Py_ssize_t j
-
-    x = []
+    cdef Py_ssize_t j, temp
+
+    x = []               # initialize T1
     c = range(t)
+    if t == n:
+        x.append(c)
+        return x
     c.append(n)
     c.append(0)
-    j = 0
-
-    while j < t:
-        x.append(c[:t])
-        j = 0
-        while c[j]+1 == c[j+1]:
-           c[j] = j
-           j = j+1
-        c[j] = c[j]+1
+    j = t-1
+
+    while True:
+        x.append(c[:t])    # visit T2
+        if j >= 0:
+            c[j] = j+1
+            j = j-1
+            continue       # goto T2
+
+        if c[0]+1 < c[1]:  # T3 easy case!
+            c[0] = c[0]+1
+            continue
+        else:
+            j = 1
+
+        while True:
+            c[j-1] = j-1      # T4 find j
+            temp = c[j]+1
+            if temp == c[j+1]:
+                j = j+1
+            else:
+                break
+
+
+        if j >= t:     # T5 stop?
+            break
+
+        c[j] = temp    # T6
+        j = j-1
 
     return x
+
 
 def _binomial(Py_ssize_t n, Py_ssize_t k):
     """
     Fast and unchecked implementation of binomial(n,k)
+    This is only for internal use.
+
+    EXAMPLES:
+        sage: from sage.matrix.matrix2 import _binomial
+        sage: _binomial(10,2)
+        45
+        sage: _binomial(10,5)
+        252
 
     AUTHOR:
@@ -3112 +3154 @@
     return result
 
-

sage/matrix/matrix2.pyx

@@ -2967 +2967 @@
         return self.__invert__()
 
+    def gramm_schmidt(self):
+        r"""
+        Return the matrix G whose rows are obtained from the rows of self (=A) by
+        applying the Gramm-Schmidt orthogonalization process.  Also return
+        the coefficients mu ij, i.e., a matrix mu such that \code{(mu + 1)*G == A}.
+
+        OUTPUT:
+            G -- a matrix whose rows are orthogonal
+            mu -- a matrix that gives the transformation, via the relation
+                  (mu + 1)*G == self
+        
+        EXAMPLES:
+            sage: A = matrix(ZZ, 3, [-1, 2, 5, -11, 1, 1, 1, -1, -3]); A
+            [ -1   2   5]
+            [-11   1   1]
+            [  1  -1  -3]
+            sage: G, mu = A.gramm_schmidt()
+            sage: G
+            [     -1       2       5]
+            [  -52/5    -1/5      -2]
+            [  2/187  36/187 -14/187]
+            sage: mu
+            [     0      0      0]
+            [   3/5      0      0]
+            [  -3/5 -7/187      0]
+            sage: G[0] * G[1]
+            0
+            sage: G[0] * G[2]
+            0
+            sage: G[1] * G[2]
+            0
+
+        The relation between mu and A is as follows:
+            sage: (mu + 1)*G == A
+            True
+        """        
+        from sage.modules.misc import gramm_schmidt
+        from constructor import matrix
+        Bstar, mu = gramm_schmidt(self.rows())
+        return matrix(Bstar), mu
+
     
 def _dim_cmp(x,y):