Package sage :: Package modular :: Package modsym :: Module relation_matrix
[show private | hide private]
[frames | no frames]

Module sage.modular.modsym.relation_matrix

Relations matrices for modular symbols.
Function Summary
  compute_presentation(syms, sign, field, weight)
Compute the presentation for self, as a quotient of Manin symbols modulo relations.
  gens_to_basis_matrix(syms, relation_matrix, mod, field)
Compute echelon form of 3-term relation matrix, and read off each generator in terms of basis.
  modI_relations(syms, sign)
Compute quotient of Manin symbols by the S relations.
  modS_relations(syms)
Compute quotient of Manin symbols by the S relations.
  sparse_2term_quotient(rels, n, F)
Performs Sparse Gauss elimination on a matrix all of whose columns have at most 2 nonzero entries.
  sparse_relation_matrix_wt2_g0n(list, field, sign)
Create the sparse relation matrix over Q for Manin symbols of weight 2 on Gamma0(N), with given sign.
  sparse_relation_matrix_wtk_g0n(M, field, sign)
Create the sparse relation matrix over Q for Manin symbols of given weight on Gamma0(N), with given sign.
  T_relation_matrix_wtk_g0(syms, mod, field, weight)
Compute a matrix whose echelon form gives the quotient by 3-term T relations.

Function Details

compute_presentation(syms, sign, field, weight)

Compute the presentation for self, as a quotient of Manin
symbols modulo relations.
INPUT:
    syms -- manin_symbols.ManinSymbols
    sign -- integer (-1, 0, 1)
    field -- a field
    weight -- integer weight
OUTPUT:
    -- sparse matrix whose rows give each generator in terms
       of a basis for the quotient
    -- list of integers that give the basis for the quotient
    -- mod: list where mod[i]=(j,s) means that x_i = s*x_j modulo
            the 2-term S (and I) relations.
ALGORITHM:
* Let S = [0,-1; 1,0], T = [0,-1; 1,-1], and I = [-1,0; 0,1].
* Let x_0, ..., x_{n-1} by a list of all Manin symbols.
* Form quotient by 2-term S and (possibly) I relations.
* Create a sparse matrix A with m columns, whose rows 
  encode the relations
         <x_i> + <x_i*T> + <x_i*T^2> = 0.
  There are about n such rows.
  The number of nonzero entries per row is at most 3*(k-1).
  Note that we must include rows for *all* i, since
  even if <x_i> = <x_j>, it need not be the case that
  <x_i*T> = <x_j*T>, since S and T do not commute.
  However, we have an a priori formula for the dimension
  of the quotient by all these relations, so we could omit
  many relations and just check that there are enough at the
  end---if there aren't, we add in more.
* Compute the reduced row echelon form of A using sparse
  intelligent Gaussian elimination.   
* Use what we've done above to read off a sparse matrix R
  that expresses each of the n Manin symbols in terms of
  a basis of Manin symbols, modulo the relations.

gens_to_basis_matrix(syms, relation_matrix, mod, field)

Compute echelon form of 3-term relation matrix, and read off each
generator in terms of basis.
INPUT:
    syms -- manin_symbols.ManinSymbols 
    relation_matrix -- as output by __compute_T_relation_matrix(self, mod)
    mod -- quotient mod S (and I) relations
    field -- base field
OUTPUT:
    Matrix -- a matrix whose ith row expresses the Manin symbol generators
              in terms of a basis of Manin symbols (modulo the S,I, and T rels)
              Note that the entries of Matrix need not be integers.
    list --  integers i, such that the Manin symbols x_i are a basis.

modI_relations(syms, sign)

Compute quotient of Manin symbols by the S relations.
INPUT:
    syms -- manin_symbols.ManinSymbols  
    sign -- int (either -1, 0, or 1)
OUTPUT:
    rels -- set of pairs of pairs (j, s), where if mod[i] = (j,s),
           then x_i = s*x_j (mod S relations)
WARNING: We quotient by the involution eta((u,v)) = (-u,v),
which has the opposite sign as the involution in Merel's 
Springer LNM 1585 paper!  Thus our +1 eigenspace is his -1
eigenspace, etc.  We do this for consistency with MAGMA.

modS_relations(syms)

Compute quotient of Manin symbols by the S relations.  

Here       S = [0  -1]
               [1   0].
INPUT:
    syms -- manin_symbols.ManinSymbols  
OUTPUT:
    rels -- set of pairs of pairs (j, s), where if mod[i] = (j,s),
           then x_i = s*x_j (mod S relations)
EXAMPLES:
    >>> from manin_symbols import ManinSymbolList_gamma0
    >>> syms = ManinSymbolList_gamma0(2, 4); syms
    Manin Symbol List of weight 4 for Gamma0(2)
    >>> modS_relations(syms)
    set([((3, -1), (4, 1)), ((5, -1), (5, 1)), ((1, 1), (6, 1)), ((0, 1), (7, 1)), ((3, 1), (4, -1)), ((2, 1), (8, 1))])
    
    >>> syms = ManinSymbolList_gamma0(7, 2); syms
    Manin Symbol List of weight 2 for Gamma0(7)
    >>> modS_relations(syms)
    set([((3, 1), (4, 1)), ((2, 1), (7, 1)), ((5, 1), (6, 1)), ((0, 1), (1, 1))])
    
Next we do an example with Gamma1:
    >>> from manin_symbols import ManinSymbolList_gamma1
    >>> syms = ManinSymbolList_gamma1(3,2); syms
    Manin Symbol List of weight 2 for Gamma1(3)
    >>> modS_relations(syms)
    set([((3, 1), (6, 1)), ((0, 1), (5, 1)), ((0, 1), (2, 1)), ((3, 1), (4, 1)), ((6, 1), (7, 1)), ((1, 1), (2, 1)), ((1, 1), (5, 1)), ((4, 1), (7, 1))])

sparse_2term_quotient(rels, n, F)

Performs Sparse Gauss elimination on a matrix all of      
whose columns have at most 2 nonzero entries.  We     
use an obvious algorithm, whichs runs fast enough. 
(Typically making the list of relations takes more time 
than computing this quotient.)
This algorithm is more subtle than just ``identify symbols in pairs'',
since complicated relations can cause generators to surprisingly
equal 0.
INPUT:
    rels -- set of pairs ((i,s), (j,t)).  The pair represents 
            the relation
                  s*x_i + t*x_j = 0.
    n -- int, the x_i are x_0, ..., x_{n-1}.
    F -- base field
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. 
EXAMPLE:
We quotient out by the relations
       3*x0 - x1 = 0,  x1 + x3 = 0,   x2 + x3 = 0,  x4 - x5 = 0
to get
    >>> Q = rings.RationalField()
    >>> rels = set([((0,3), (1,-1)), ((1,1), (3,1)), ((2,1),(3,1)), ((4,1),(5,-1))])
    >>> n = 6
    >>> sparse_2term_quotient(rels, n, Q)
    [(3, -1/3), (3, -1), (3, -1), (3, 1), (5, 1), (5, 1)]

sparse_relation_matrix_wt2_g0n(list, field, sign=0)

Create the sparse relation matrix over Q for Manin symbols of weight 2 on
Gamma0(N), with given sign.
INPUT:
    list -- sage.modular.modsym.p1list.List
OUTPUT:
    A -- a sage.linalg.sparse_matrix.SparseMatrix
         that gives the 2-term and 3-term relations between
         Manin symbols.
         
MORE DETAILS:
    1. Create an empty sparse matrix.
    2. Let S = [0,-1; 1,0], T = [0,-1; 1,-1], I = [-1,0; 0,1]
    3. Enter the T relations:                                             
               x + x*T = 0                                                
       Remove x and x*T from reps to consider.
    4. If sign =/= 0, enter the I relations:
               x - sign*x*I = 0.
    5. Enter the S relations in the matrix:                               
               x + x*S + x*S^2 = 0                                        
       by putting 1s at cols corresponding to x, x*S, and x*S^2.          
       Remove x, x*S, and x*S^2 from list of reps to consider.

sparse_relation_matrix_wtk_g0n(M, field, sign=0)

Create the sparse relation matrix over Q for Manin symbols of given weight
on Gamma0(N), with given sign.
INPUT:
    M -- manin_symbols.ManinSymbolList
    field -- base field
    weight -- the weight, an integer > 2
    sign -- element of [-1,0,1]
OUTPUT:
    A -- a sage.linalg.sparse_matrix.SparseMatrix
         that gives the 2-term and 3-term relations between
         Manin symbols.
MORE DETAILS:
    1. Create an empty sparse matrix.
    2. Let S = [0,-1; 1,0], T = [0,-1; 1,-1], I = [-1,0; 0,1]
    3. Enter the T relations:                                             
               x + x*T = 0                                                
       Remove x and x*T from reps to consider.
    4. If sign =/= 0, enter the I relations:
               x + sign*x*I = 0.
    5. Enter the S relations in the matrix:                               
               x + x*S + x*S^2 = 0                                        
       by putting 1s at cols corresponding to x, x*S, and x*S^2.          
       Remove x from list of reps to consider.

T_relation_matrix_wtk_g0(syms, mod, field, weight)

Compute a matrix whose echelon form gives the quotient by 
3-term T relations.
INPUT:
    syms -- manin_symbols.ManinSymbols 
    mod -- list that gives quotient modulo some two-term relations,
           i.e., the S relations, and if sign is nonzero, 
           the I relations.
    field -- base_field
    weight -- int
OUTPUT:
    A sparse matrix whose rows correspond to the reduction of
    the T relations modulo the S and I relations.

Generated by Epydoc 2.1 on Mon May 9 17:57:02 2005 http://epydoc.sf.net