Optimized computing of relation matrices in certain cases¶

sage.modular.modsym.relation_matrix_pyx.sparse_2term_quotient_only_pm1(rels, n)[source]¶

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 – integer; the \(x_i\) are \(x_0, \ldots, 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

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)]

Python

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

Sage Live

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