Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
""" Optimized Cython code for computing relation matrices in certain cases. """
############################################################################# # Copyright (C) 2010 William Stein <wstein@gmail.com> # Distributed under the terms of the GNU General Public License (GPL) v2+. # The full text of the GPL is available at: # http://www.gnu.org/licenses/ ############################################################################# from __future__ import absolute_import
from sage.rings.rational cimport Rational
r""" Performs Sparse Gauss elimination on a matrix all of whose columns have at most 2 nonzero entries with relations all 1 or -1.
This algorithm is more subtle than just "identify symbols in pairs", since complicated relations can cause generators to equal 0.
NOTE: Note the condition on the s,t coefficients in the relations being 1 or -1 for this optimized function. There is a more general function in relation_matrix.py, which is much, much slower.
INPUT:
- ``rels`` - set of pairs ((i,s), (j,t)). The pair represents the relation s*x_i + t*x_j = 0, where the i, j must be Python int's, and the s,t must all be 1 or -1.
- ``n`` - int, the x_i are x_0, ..., x_n-1.
OUTPUT:
- ``mod`` - list such that mod[i] = (j,s), which means that x_i is equivalent to s*x_j, where the x_j are a basis for the quotient.
EXAMPLES::
sage: v = [((0,1), (1,-1)), ((1,1), (3,1)), ((2,1),(3,1)), ((4,1),(5,-1))] sage: rels = set(v) sage: n = 6 sage: from sage.modular.modsym.relation_matrix_pyx import sparse_2term_quotient_only_pm1 sage: sparse_2term_quotient_only_pm1(rels, n) [(3, -1), (3, -1), (3, -1), (3, 1), (5, 1), (5, 1)] """ raise TypeError("rels must be a set")
cdef int c0, c1, i, die
# Mod out by the following relation: # # c0*free[v0[0]] + c1*free[v1[0]] = 0. # pass # all xi equal to free[v0[0]] must now equal to zero. else: # x1 = -c1/c0 * x2. raise ValueError("coefficients must all be -1 or 1.")
# Special casing the rationals leads to a huge speedup, # actually. (All the code above is slower than just this line # without this special case.)
|