Optimized Cython code for computing relation matrices in certain cases.¶
-
sage.modular.modsym.relation_matrix_pyx.
sparse_2term_quotient_only_pm1
(rels, n)¶ 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)]