Optimized computing of relation matrices in certain cases#

sage.modular.modsym.relation_matrix_pyx.sparse_2term_quotient_only_pm1(rels, n)#

Perform 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 – iterable made 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.

The output depends on the order of the input.

EXAMPLES:

sage: from sage.modular.modsym.relation_matrix_pyx import sparse_2term_quotient_only_pm1
sage: rels = [((0,1), (1,-1)), ((1,1), (3,1)), ((2,1),(3,1)), ((4,1),(5,-1))]
sage: n = 6
sage: sparse_2term_quotient_only_pm1(rels, n)
[(3, -1), (3, -1), (3, -1), (3, 1), (5, 1), (5, 1)]