chap3.txt

  
  3 The Sparse Matrix Data Type
  
  
  3.1 The inner workings of Gauss sparse matrices
  
  When  doing  any  kind  of  computation there is a constant conflict between
  memory load and speed. On the one hand, memory usage is bounded by the total
  available memory, on the other hand, computation time should also not exceed
  certain  proportions.  Memory  usage  and  CPU  time are generally inversely
  proportional,  because the computer needs more time to perform operations on
  a  compactified  data structure. The idea of sparse matrices mirrors exactly
  the  need  for  less  memory  load,  therefore  it  is  natural  that sparse
  algorithms  take  more  time  than  dense  ones.  However,  if the matrix is
  sufficiently large and sparse at the same time, sparse algorithms can easily
  be faster than dense ones while maintaining minimal memory load.
  
  It  should  be  noted  that,  although  matrices  that  appear  naturally in
  homological  algebra  are  almost  always  sparse,  they do not have to stay
  sparse under (R)REF algorithms, especially when the computation is concerned
  with  transformation matrices. Therefore, in a perfect world there should be
  ways  implemented to not only find out which data structure to use, but also
  at  what  point to convert from one to the other. This was, however, not the
  aim  of  the  Gauss  package  and  is  just one of many points in which this
  package could be optimized or extended. Take a look at this matrix M:
  
      ┌──   ─   ─   ─   ──┐
      │ 0   0   2   9   0 │ 
      │ 0   5   0   0   0 │ 
      │ 0   0   0   1   0 │ 
      └──   ─   ─   ─   ──┘
  
  The  matrix  M  carries  the same information as the following table, if and
  only if you know how many rows and columns the matrix has. There is also the
  matter of the base ring, but this is not important for now:
  
      ┌──────   ──────┐
      │ (i,j)   Entry │ 
      ├──────   ──────┤
      │ (1,3)     2   │ 
      │ (1,4)     9   │ 
      │ (2,2)     5   │ 
      │ (3,4)     1   │ 
      └──────   ──────┘
  
  This  table  relates each index tuple to its nonzero entry, all other matrix
  entries  are defined to be zero. This only works for known dimensions of the
  matrix,  otherwise trailing zero rows and columns could get lost (notice how
  the table gives no hint about the existence of a 5th column). To convert the
  above  table  into a sparse data structure, one could list the table entries
  in this way:
  
        [ [ 1, 3, 2 ], [ 1, 4, 9 ], [ 2, 2, 5 ], [ 3, 4, 1 ] ]   
  
  However,  this  data structure would not be very efficient. Whenever you are
  interested  in  a  row  i  of  M  (this happens all the time when performing
  Gaussian  elimination) the whole list would have to be searched for 3-tuples
  of  the  form  [  i,  *, * ]. This is why I tried to manage the row index by
  putting the tuples into the corresponding list entry:
  
        [ [ 3, 2 ], [ 4, 9 ] ],   
        [ [ 2, 5 ] ],             
        [ [ 4, 1 ] ] ]            
  
  As you can see, this looks fairly complicated. However, the same information
  can  be stored in this form, which would become the final data structure for
  Gauss sparse matrices:
  
        indices :=   [ [ 3, 4 ],   entries:=   [ [ 2, 9 ],   
                     [ 2 ],                    [ 5 ],        
                     [ 4 ] ]                   [ 1 ] ]       
  
  Although now the number of rows is equal to the Length of both `indices' and
  `entries',  it  is  still stored in the sparse matrix. Here is the full data
  structure (--> SparseMatrix (3.2-1)):
  
    from SparseMatrix.gi  
        DeclareRepresentation( "IsSparseMatrixRep",
             IsSparseMatrix, [ "nrows", "ncols", "indices", "entries", "ring" ] );
        
  
  
  As  you  can see, the matrix stores its ring to be on the safe side. This is
  especially  important for zero matrices, as there is no way to determine the
  base  ring  from  the  sparse  matrix  structure. For further information on
  sparse matrix construction and converting, refer to SparseMatrix (3.2-1).
  
  
  3.1-1 A special case: GF(2)
  
    from SparseMatrix.gi  
        DeclareRepresentation( "IsSparseMatrixGF2Rep",
             IsSparseMatrix, [ "nrows", "ncols", "indices", "ring" ] );
        
  
  
  Because  the nonzero entries of a matrix over GF(2) are all "1", the entries
  of  M are not stored at all. It is of course crucial that all operations and
  algorithms  make  100% sure that all appearing zero entries are deleted from
  the `indices' as well as the `entries' list as they arise.
  
  
  3.2 Methods and functions for sparse matrices
  
  3.2-1 SparseMatrix
  
  SparseMatrix( mat[, R] )  function
  Returns:  a sparse matrix over the ring R
  
  SparseMatrix( nrows, ncols, indices )  function
  Returns:  a sparse matrix over GF(2)
  
  SparseMatrix( nrows, ncols, indices, entries[, R] )  function
  Returns:  a sparse matrix over the ring R
  
  The  sparse  matrix  constructor.  In the one-argument form the SparseMatrix
  constructor  converts  a  GAP matrix to a sparse matrix. If not provided the
  base  ring  R  is found automatically. For the multi-argument form nrows and
  ncols  are  the  dimensions  of the matrix. indices must be a list of length
  nrows  containing  lists  of  the  column indices of the matrix in ascending
  order.
  
    Example  
    gap> M := [ [ 0 , 1 ], [ 3, 0 ] ] * One( GF(2) );
    [ [ 0*Z(2), Z(2)^0 ], [ Z(2)^0, 0*Z(2) ] ]
    gap> SM := SparseMatrix( M );
    <a 2 x 2 sparse matrix over GF(2)>
    gap> IsSparseMatrix( SM );
    true
    gap> Display( SM );
     . 1
     1 .
    gap> SN := SparseMatrix( 2, 2, [ [ 2 ], [ 1 ] ] );
    <a 2 x 2 sparse matrix over GF(2)>
    gap> SN = SM;
    true
    gap> SN := SparseMatrix( 2, 3,
    >                   [ [ 2 ], [ 1, 3 ] ],
    >                   [ [ 1 ], [ 3, 2 ] ] * One( GF(5) ) );
    <a 2 x 3 sparse matrix over GF(5)>
    gap> Display( SN );
     . 1 .
     3 . 2
  
  
  3.2-2 ConvertSparseMatrixToMatrix
  
  ConvertSparseMatrixToMatrix( sm )  method
  Returns:  a GAP matrix, [], or a list of empty lists
  
  This  function  converts  the sparse matrix sm into a GAP matrix. In case of
  nrows(sm)=0  or  ncols(sm)=0 the return value is the empty list or a list of
  empty lists, respectively.
  
    Example  
    gap> M := [ [ 0 , 1 ], [ 3, 0 ] ] * One( GF(3) );
    [ [ 0*Z(3), Z(3)^0 ], [ 0*Z(3), 0*Z(3) ] ]
    gap> SM := SparseMatrix( M );
    <a 2 x 2 sparse matrix over GF(3)>
    gap> N := ConvertSparseMatrixToMatrix( SM );
    [ [ 0*Z(3), Z(3)^0 ], [ 0*Z(3), 0*Z(3) ] ]
    gap> M = N;
    true
  
  
  3.2-3 CopyMat
  
  CopyMat( sm )  method
  Returns:  a shallow copy of the sparse matrix sm
  
  3.2-4 GetEntry
  
  GetEntry( sm, i, j )  method
  Returns:  a ring element.
  
  This returns the entry sm[i,j] of the sparse matrix sm
  
  3.2-5 SetEntry
  
  SetEntry( sm, i, j, elm )  method
  Returns:  nothing.
  
  This sets the entry sm[i,j] of the sparse matrix sm to elm.
  
  3.2-6 AddToEntry
  
  AddToEntry( sm, i, j, elm )  method
  Returns:  true or a ring element
  
  AddToEntry  adds  the  element  elm  to the sparse matrix sm at the (i,j)-th
  position.  This  is  a  Method  with a side effect which returns true if you
  tried  to  add zero or the sum of sm[i,j] and elm otherwise. Please use this
  method whenever possible.
  
  3.2-7 SparseZeroMatrix
  
  SparseZeroMatrix( nrows[, ring] )  function
  Returns:  a sparse <nrows x nrows> zero matrix over the ring ring
  
  SparseZeroMatrix( nrows, ncols[, ring] )  function
  Returns:  a sparse <nrows x ncols> zero matrix over the ring ring
  
  3.2-8 SparseIdentityMatrix
  
  SparseIdentityMatrix( dim[, ring] )  function
  Returns:  a  sparse  <dim  x  dim> identity matrix over the ring ring. If no
            ring  is  specified (one should try to avoid this if possible) the
            Rationals are the default ring.
  
  3.2-9 TransposedSparseMat
  
  TransposedSparseMat( sm )  method
  Returns:  the transposed matrix of the sparse matrix sm
  
  3.2-10 CertainRows
  
  CertainRows( sm, list )  method
  Returns:  the submatrix sm{[list]} as a sparse matrix
  
  3.2-11 CertainColumns
  
  CertainColumns( sm, list )  method
  Returns:  the submatrix sm{[1..nrows(sm)]}{[list]} as a sparse matrix
  
  3.2-12 UnionOfRows
  
  UnionOfRows( A, B )  method
  Returns:  the row union of the sparse matrices A and B
  
  3.2-13 UnionOfColumns
  
  UnionOfColumns( A, B )  method
  Returns:  the column union of the sparse matrices A and B
  
  3.2-14 SparseDiagMat
  
  SparseDiagMat( list )  function
  Returns:  the block diagonal matrix composed of the sparse matrices in list
  
  3.2-15 Nrows
  
  Nrows( sm )  method
  Returns:  the  number  of  rows  of  the  sparse  matrix  sm. This should be
            preferred to the equivalent sm!.nrows.
  
  3.2-16 Ncols
  
  Ncols( sm )  method
  Returns:  the  number  of  columns  of  the sparse matrix sm. This should be
            preferred to the equivalent sm!.ncols.
  
  3.2-17 IndicesOfSparseMatrix
  
  IndicesOfSparseMatrix( sm )  method
  Returns:  the  indices of the sparse matrix sm as a ListList. This should be
            preferred to the equivalent sm!.indices.
  
  3.2-18 EntriesOfSparseMatrix
  
  EntriesOfSparseMatrix( sm )  method
  Returns:  the  entries  of  the  sparse  matrix  sm  as  a  ListList of ring
            elements.  This  should be preferred to the equivalent sm!.entries
            and  has  the  additional advantage of working for sparse matrices
            over GF(2) which do not have any entries.
  
  3.2-19 RingOfDefinition
  
  RingOfDefinition( sm )  method
  Returns:  the base ring of the sparse matrix sm. This should be preferred to
            the equivalent sm!.ring.