From 823fb2a587e26436f46854fe44be0e8df46a6715 Mon Sep 17 00:00:00 2001 From: Michael Orlitzky Date: Wed, 4 Nov 2020 08:31:51 -0500 Subject: [PATCH] eja: simplify and unify the charpoly/rank stuff. --- mjo/eja/eja_algebra.py | 165 ++++------------------------------------- mjo/eja/eja_element.py | 12 +-- 2 files changed, 22 insertions(+), 155 deletions(-) diff --git a/mjo/eja/eja_algebra.py b/mjo/eja/eja_algebra.py index d1c0fa2..2b769ac 100644 --- a/mjo/eja/eja_algebra.py +++ b/mjo/eja/eja_algebra.py @@ -283,8 +283,6 @@ class FiniteDimensionalEuclideanJordanAlgebra(CombinatorialFreeModule): return V.span_of_basis(b) - - @cached_method def _charpoly_coeff(self, i): """ Return the coefficient polynomial "a_{i}" of this algebra's @@ -294,102 +292,7 @@ class FiniteDimensionalEuclideanJordanAlgebra(CombinatorialFreeModule): store the trace/determinant (a_{r-1} and a_{0} respectively) separate from the entire characteristic polynomial. """ - (A_of_x, x, xr, detA) = self._charpoly_matrix_system() - R = A_of_x.base_ring() - - if i == self.rank(): - return R.one() - if i > self.rank(): - # Guaranteed by theory - return R.zero() - - # Danger: the in-place modification is done for performance - # reasons (reconstructing a matrix with huge polynomial - # entries is slow), but I don't know how cached_method works, - # so it's highly possible that we're modifying some global - # list variable by reference, here. In other words, you - # probably shouldn't call this method twice on the same - # algebra, at the same time, in two threads - Ai_orig = A_of_x.column(i) - A_of_x.set_column(i,xr) - numerator = A_of_x.det() - A_of_x.set_column(i,Ai_orig) - - # We're relying on the theory here to ensure that each a_i is - # indeed back in R, and the added negative signs are to make - # the whole charpoly expression sum to zero. - return R(-numerator/detA) - - - @cached_method - def _charpoly_matrix_system(self): - """ - Compute the matrix whose entries A_ij are polynomials in - X1,...,XN, the vector ``x`` of variables X1,...,XN, the vector - corresponding to `x^r` and the determinent of the matrix A = - [A_ij]. In other words, all of the fixed (cachable) data needed - to compute the coefficients of the characteristic polynomial. - """ - r = self.rank() - n = self.dimension() - - # Turn my vector space into a module so that "vectors" can - # have multivatiate polynomial entries. - names = tuple('X' + str(i) for i in range(1,n+1)) - R = PolynomialRing(self.base_ring(), names) - - # Using change_ring() on the parent's vector space doesn't work - # here because, in a subalgebra, that vector space has a basis - # and change_ring() tries to bring the basis along with it. And - # that doesn't work unless the new ring is a PID, which it usually - # won't be. - V = FreeModule(R,n) - - # Now let x = (X1,X2,...,Xn) be the vector whose entries are - # indeterminates... - x = V(names) - - # And figure out the "left multiplication by x" matrix in - # that setting. - lmbx_cols = [] - monomial_matrices = [ self.monomial(i).operator().matrix() - for i in range(n) ] # don't recompute these! - for k in range(n): - ek = self.monomial(k).to_vector() - lmbx_cols.append( - sum( x[i]*(monomial_matrices[i]*ek) - for i in range(n) ) ) - Lx = matrix.column(R, lmbx_cols) - - # Now we can compute powers of x "symbolically" - x_powers = [self.one().to_vector(), x] - for d in range(2, r+1): - x_powers.append( Lx*(x_powers[-1]) ) - - idmat = matrix.identity(R, n) - - W = self._charpoly_basis_space() - W = W.change_ring(R.fraction_field()) - - # Starting with the standard coordinates x = (X1,X2,...,Xn) - # and then converting the entries to W-coordinates allows us - # to pass in the standard coordinates to the charpoly and get - # back the right answer. Specifically, with x = (X1,X2,...,Xn), - # we have - # - # W.coordinates(x^2) eval'd at (standard z-coords) - # = - # W-coords of (z^2) - # = - # W-coords of (standard coords of x^2 eval'd at std-coords of z) - # - # We want the middle equivalent thing in our matrix, but use - # the first equivalent thing instead so that we can pass in - # standard coordinates. - x_powers = [ W.coordinate_vector(xp) for xp in x_powers ] - l2 = [idmat.column(k-1) for k in range(r+1, n+1)] - A_of_x = matrix.column(R, n, (x_powers[:r] + l2)) - return (A_of_x, x, x_powers[r], A_of_x.det()) + return self._charpoly_coefficients()[i] @cached_method @@ -436,20 +339,21 @@ class FiniteDimensionalEuclideanJordanAlgebra(CombinatorialFreeModule): r = self.rank() n = self.dimension() - # The list of coefficient polynomials a_0, a_1, a_2, ..., a_n. - a = [ self._charpoly_coeff(i) for i in range(r+1) ] + # The list of coefficient polynomials a_0, a_1, a_2, ..., a_(r-1). + a = self._charpoly_coefficients() # We go to a bit of trouble here to reorder the # indeterminates, so that it's easier to evaluate the # characteristic polynomial at x's coordinates and get back # something in terms of t, which is what we want. - R = a[0].parent() S = PolynomialRing(self.base_ring(),'t') t = S.gen(0) - S = PolynomialRing(S, R.variable_names()) - t = S(t) + if r > 0: + R = a[0].parent() + S = PolynomialRing(S, R.variable_names()) + t = S(t) - return sum( a[k]*(t**k) for k in range(len(a)) ) + return (t**r + sum( a[k]*(t**k) for k in range(r) )) def inner_product(self, x, y): @@ -867,14 +771,10 @@ class FiniteDimensionalEuclideanJordanAlgebra(CombinatorialFreeModule): r""" Return the rank of this EJA. - ALGORITHM: - - We first compute the polynomial "column matrices" `p_{k}` that - evaluate to `x^k` on the coordinates of `x`. Then, we begin - adding them to a matrix one at a time, and trying to solve the - system that makes `p_{0}`,`p_{1}`,..., `p_{s-1}` add up to - `p_{s}`. This will succeed only when `s` is the rank of the - algebra, as proven in a recent draft paper of mine. + This is a cached method because we know the rank a priori for + all of the algebras we can construct. Thus we can avoid the + expensive ``_charpoly_coefficients()`` call unless we truly + need to compute the whole characteristic polynomial. SETUP:: @@ -955,7 +855,6 @@ class FiniteDimensionalEuclideanJordanAlgebra(CombinatorialFreeModule): sage: J.rank.clear_cache() sage: J.rank() 2 - """ return len(self._charpoly_coefficients()) @@ -1097,7 +996,7 @@ class MatrixEuclideanJordanAlgebra(FiniteDimensionalEuclideanJordanAlgebra): a multiplication table because the latter can be computed in terms of the former when the product is known (like it is here). """ - # Used in this class's fast _charpoly_coeff() override. + # Used in this class's fast _charpoly_coefficients() override. self._basis_normalizers = None # We're going to loop through this a few times, so now's a good @@ -1126,7 +1025,7 @@ class MatrixEuclideanJordanAlgebra(FiniteDimensionalEuclideanJordanAlgebra): @cached_method - def rank(self): + def _charpoly_coefficients(self): r""" Override the parent method with something that tries to compute over a faster (non-extension) field. @@ -1134,7 +1033,7 @@ class MatrixEuclideanJordanAlgebra(FiniteDimensionalEuclideanJordanAlgebra): if self._basis_normalizers is None: # We didn't normalize, so assume that the basis we started # with had entries in a nice field. - return super(MatrixEuclideanJordanAlgebra, self).rank() + return super(MatrixEuclideanJordanAlgebra, self)._charpoly_coefficients() else: basis = ( (b/n) for (b,n) in zip(self.natural_basis(), self._basis_normalizers) ) @@ -1145,39 +1044,7 @@ class MatrixEuclideanJordanAlgebra(FiniteDimensionalEuclideanJordanAlgebra): J = MatrixEuclideanJordanAlgebra(QQ, basis, normalize_basis=False) - return J.rank() - - @cached_method - def _charpoly_coeff(self, i): - """ - Override the parent method with something that tries to compute - over a faster (non-extension) field. - """ - if self._basis_normalizers is None: - # We didn't normalize, so assume that the basis we started - # with had entries in a nice field. - return super(MatrixEuclideanJordanAlgebra, self)._charpoly_coeff(i) - else: - basis = ( (b/n) for (b,n) in zip(self.natural_basis(), - self._basis_normalizers) ) - - # Do this over the rationals and convert back at the end. - J = MatrixEuclideanJordanAlgebra(QQ, - basis, - normalize_basis=False) - (_,x,_,_) = J._charpoly_matrix_system() - p = J._charpoly_coeff(i) - # p might be missing some vars, have to substitute "optionally" - pairs = zip(x.base_ring().gens(), self._basis_normalizers) - substitutions = { v: v*c for (v,c) in pairs } - result = p.subs(substitutions) - - # The result of "subs" can be either a coefficient-ring - # element or a polynomial. Gotta handle both cases. - if result in QQ: - return self.base_ring()(result) - else: - return result.change_ring(self.base_ring()) + return J._charpoly_coefficients() @staticmethod diff --git a/mjo/eja/eja_element.py b/mjo/eja/eja_element.py index da4b123..926f2bf 100644 --- a/mjo/eja/eja_element.py +++ b/mjo/eja/eja_element.py @@ -386,11 +386,11 @@ class FiniteDimensionalEuclideanJordanAlgebraElement(IndexedFreeModuleElement): """ P = self.parent() r = P.rank() - p = P._charpoly_coeff(0) - # The _charpoly_coeff function already adds the factor of - # -1 to ensure that _charpoly_coeff(0) is really what - # appears in front of t^{0} in the charpoly. However, - # we want (-1)^r times THAT for the determinant. + p = P._charpoly_coefficients()[0] + # The _charpoly_coeff function already adds the factor of -1 + # to ensure that _charpoly_coefficients()[0] is really what + # appears in front of t^{0} in the charpoly. However, we want + # (-1)^r times THAT for the determinant. return ((-1)**r)*p(*self.to_vector()) @@ -1400,7 +1400,7 @@ class FiniteDimensionalEuclideanJordanAlgebraElement(IndexedFreeModuleElement): # the trace is an empty sum. return P.base_ring().zero() - p = P._charpoly_coeff(r-1) + p = P._charpoly_coefficients()[r-1] # The _charpoly_coeff function already adds the factor of # -1 to ensure that _charpoly_coeff(r-1) is really what # appears in front of t^{r-1} in the charpoly. However, -- 2.43.2