Ignore:
Timestamp:
03/03/07 11:36:34 (6 years ago)
Branch:
default
Message:

prelimnary partial implementation of decomposition

Location:
sage
Files:
6 edited

Unmodified
Removed
• ## sage/matrix/benchmark.py

 r3103 A = random_matrix(ZZ, n, n, x=min, y=max+1).change_ring(QQ) t = cputime() v = A**(-1) v = ~A return cputime(t) elif system == 'magma':
• ## sage/matrix/matrix0.pyx

 r3254 INPUT: v -- list v -- list of length at most the number of rows of self. EXAMPLES: R = self.rows() n = len(R) if len(v) != n: raise ValueError, "length of v must equal number of rows." if len(v) > n: raise ValueError, "length of v (=%s) must be at most the number (=%s) of rows."%(len(v), n) zero = self._base_ring(0) s = None for i from 0 <= i < n: for i from 0 <= i < len(v): if v[i] != zero: a = v[i] * R[i] s = a else: s = s + a s += a if s is None: return self.parent().row_space()(0)
• ## sage/matrix/matrix2.pyx

 r3222 """ M = self._row_ambient_module() return M.span(self.rows()) if self.fetch('in_echelon_form'): return M.span(self.rows(), already_echelonized=True) else: return M.span(self.rows(), already_echelonized=True) def row_space(self): """ Returns the decomposition of the free module on which this matrix acts from the right, along with whether this matrix acts irreducibly on each factor.  The factors are guaranteed to be sorted in the same way as the corresponding factors of the characteristic polynomial. matrix A acts from the right (i.e., the action is x goes to x A), along with whether this matrix acts irreducibly on each factor.  The factors are guaranteed to be sorted in the same way as the corresponding factors of the characteristic polynomial. Let A be the matrix acting from the on the vector space V of F.sort() for g, m in f.factor(): t = verbose('decomposition -- Computing g(self) for an irreducible factor g of degree %s'%g.degree(),level=2) if is_diagonalizable: B = g(self) else: B = g(self) ** m B = g(self) t2 = verbose('decomposition -- raising g(self) to the power %s'%m,level=2) B = B ** m verbose('done powering',t2) t = verbose('decomposition -- done computing g(self)', level=2, t=t) E.append((B.kernel(), m==1)) t = verbose('decomposition -- time to compute kernel', level=2, t=t) if dual: Edual.append((B.transpose().kernel(), m==1)) verbose('decomposition -- time to compute dual kernel', level=2, t=t) if dual: return E, Edual return E def _decomposition_devel(self, is_diagonalizable=False, dual=False, echelon_algorithm='default', height_guess=None): """ Returns the decomposition of the free module on which this matrix A acts from the right (i.e., the action is x goes to x A), along with whether this matrix acts irreducibly on each factor.  The factors are guaranteed to be sorted in the same way as the corresponding factors of the characteristic polynomial. Let A be the matrix acting from the on the vector space V of column vectors.  Assume that A is square.  This function computes maximal subspaces W_1, ..., W_n corresponding to Galois conjugacy classes of eigenvalues of A.  More precisely, let f(X) be the characteristic polynomial of A.  This function computes the subspace \$W_i = ker(g_(A)^n)\$, where g_i(X) is an irreducible factor of f(X) and g_i(X) exactly divides f(X). If the optional parameter is_diagonalizable is True, then we let W_i = ker(g(A)), since then we know that ker(g(A)) = \$ker(g(A)^n)\$. If dual is True, also returns the corresponding decomposition of V under the action of the transpose of A.  The factors are guarenteed to correspond. INPUT: self -- a matrix over a field OUTPUT: Sequence -- list of pairs (V,t), where V is a vector spaces and t is a bool, and t is True exactly when the charpoly of self on V is irreducible. (optional) list -- list of pairs (W,t), where W is a vector space and t is a bool, and t is True exactly when the charpoly of the transpose of self on W is irreducible. EXAMPLES: sage: MS1 = MatrixSpace(ZZ,4) sage: MS2 = MatrixSpace(QQ,6) sage: A = MS1.matrix([3,4,5,6,7,3,8,10,14,5,6,7,2,2,10,9]) sage: B = MS2(range(36)) sage: B*11   # random output [-11  22 -11 -11 -11 -11] [ 11 -22 -11 -22  11  11] [-11 -11 -11 -22 -22 -11] [-22  22 -22  22 -11  11] [ 22 -11  11 -22  11  22] [ 11  11  11 -22  22  22] sage: decomposition(A) [ (Ambient free module of rank 4 over the principal ideal domain Integer Ring, 1) ] sage: decomposition(B) [ (Vector space of degree 6 and dimension 2 over Rational Field Basis matrix: [ 1  0 -1 -2 -3 -4] [ 0  1  2  3  4  5], 1), (Vector space of degree 6 and dimension 4 over Rational Field Basis matrix: [ 1  0  0  0 -5  4] [ 0  1  0  0 -4  3] [ 0  0  1  0 -3  2] [ 0  0  0  1 -2  1], 0) ] """ if not self.is_square(): raise ArithmeticError, "self must be a square matrix" if not self.base_ring().is_field(): raise TypeError, "self must be over a field." if self.nrows() == 0: return decomp_seq([]) f = self.charpoly('x') E = decomp_seq([]) if dual: Edual = decomp_seq([]) t = verbose('decomposition -- factoring the characteristic polynomial', level=2) F = f.factor() verbose('decomposition -- done factoring', t=t, level=2) V = sage.modules.free_module.FreeModule( self.base_ring(), self.nrows(), sparse=self.is_sparse()) if len(F) == 1: m = F[0][1] if dual: return decomp_seq([(V,m==1)]), decomp_seq([(V,m==1)]) else: return decomp_seq([(V,m==1)]) v = V.random_element() num_iterates = max([f.degree() - g.degree() for g, _ in F]) + 1 t = verbose('decomposition -- computing %s iterates of a random vector.'%num_iterates) S = self.iterates(v, num_iterates) verbose('decomposition -- done computing iterates.', t = t) F.sort() for i in range(len(F)): g, m = F[i] # Compute the complementary factor. h = f // (g**m) # Compute one element of the kernel of g(self)**m. t = verbose('decomposition -- compute element of kernel of g(self), for g of degree %s'%g.degree(),level=2) w = S.linear_combination_of_rows(h.list()) t = verbose('decomposition -- done computing element of kernel of g(self)', t=t,level=2) # normalize?? t = verbose('decomposition -- normalize vector', level=2) w = w.normalize() verbose('decomposition -- normalize vector', t, level = 2) # Get the rest of the kernel. t = verbose('decomposition -- fill out rest of kernel',level=2) W = self.iterates(w, g.degree()) t = verbose('decomposition -- finished filling out rest of kernel',level=2, t=t) t = verbose('decomposition -- now computing row space', level=2) W.echelonize(algorithm = echelon_algorithm, height_guess=height_guess) E.append((W.row_space(), m==1)) verbose('decomposition -- computed row space', level=2,t=t) return E
• ## sage/matrix/matrix_integer_dense.pyx

 r3259 cdef Matrix_integer_dense M cdef Integer D if self._nrows != self._ncols: raise ArithmeticError, "self must be square" A = self # Step 1: Compute the rank t = verbose('computing rank', level=2, caller_name='p-adic echelon') r = A.rank() verbose('done computing rank', level=2, t=t, caller_name='p-adic echelon') if r == self._nrows: # The input matrix already has full rank. non_pivots = [i for i in range(B.ncols()) if not i in pivots_] D = B.matrix_from_columns(non_pivots) t = verbose('calling IML solver', level=2, caller_name='p-adic echelon') X, d = C._solve_iml(D, right=True) t = verbose('finished IML solver', level=2, caller_name='p-adic echelon', t=t) # Step 6: Verify that we had chosen the correct pivot columns.
• ## sage/matrix/matrix_rational_dense.pyx

 r3259 cimport sage.structure.element from sage.structure.sequence import Sequence from sage.rings.rational cimport Rational from matrix cimport Matrix height_guess=height_guess, proof=proof) def _decomposition_devel(self, is_diagonalizable=False, dual=False, echelon_algorithm='default', height_guess=None): """ Returns the decomposition of the free module on which this matrix A acts from the right (i.e., the action is x goes to x A), along with whether this matrix acts irreducibly on each factor.  The factors are guaranteed to be sorted in the same way as the corresponding factors of the characteristic polynomial. INPUT: self -- a matrix over a field OUTPUT: Sequence -- list of pairs (V,t), where V is a vector spaces and t is a bool, and t is True exactly when the charpoly of self on V is irreducible. (optional) list -- list of pairs (W,t), where W is a vector space and t is a bool, and t is True exactly when the charpoly of the transpose of self on W is irreducible. """ if not self.is_square(): raise ArithmeticError, "self must be a square matrix" if not self.base_ring().is_field(): raise TypeError, "self must be over a field." if self.nrows() == 0: return decomp_seq([]) f = self.charpoly('x') E = decomp_seq([]) if dual: Edual = decomp_seq([]) t = verbose('decomposition -- factoring the characteristic polynomial', level=2) F = f.factor() verbose('decomposition -- done factoring', t=t, level=2) if len(F) == 1: V = QQ**self.nrows() m = F[0][1] if dual: return decomp_seq([(V,m==1)]), decomp_seq([(V,m==1)]) else: return decomp_seq([(V,m==1)]) V = ZZ**self.nrows() v = V.random_element() num_iterates = max([f.degree() - g.degree() for g, _ in F]) + 1 A, _ = self._clear_denom() t = verbose('decomposition -- computing %s iterates of a random vector.'%num_iterates) S = A.iterates(v, num_iterates) verbose('decomposition -- done computing iterates.', t = t) F.sort() for i in range(len(F)): g, m = F[i] # Compute the complementary factor. h = f // (g**m) h = h * h.denominator() # Compute one element of the kernel of g(self)**m. t = verbose('decomposition -- compute element of kernel of g(self), for g of degree %s'%g.degree(),level=2) w = S.linear_combination_of_rows(h.list()) t = verbose('decomposition -- done computing element of kernel of g(self)', t=t,level=2) # Get the rest of the kernel. t = verbose('decomposition -- fill out rest of kernel',level=2) W = A.iterates(w, g.degree()) t = verbose('decomposition -- finished filling out rest of kernel',level=2, t=t) W = W.change_ring(QQ) t = verbose('decomposition -- now computing row space', level=2) W.echelonize(algorithm = echelon_algorithm, height_guess=height_guess) E.append((W.row_space(), m==1)) verbose('decomposition -- computed row space', level=2,t=t) return E ################################################################ # second implementation of the above, usually over twice as fast cdef decomp_seq(v): return Sequence(v, universe=tuple, check=False, cr=True)
• ## sage/modules/free_module_element.pyx

 r3182 self[i] = x def normalize(self): """ Return this vector divided through by the first nonzero entry of this vector. EXAMPLES: sage: v = vector(QQ,[0,4/3,5,1,2]) sage: v.normalize() (0, 1, 15/4, 3/4, 3/2) """ cdef Py_ssize_t i for i from 0 <= i < self._degree: if self[i] != 0: return (~self[i]) * self return self def inner_product(self, right):
Note: See TracChangeset for help on using the changeset viewer.