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)):
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).
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.
‣ 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.
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
‣ 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.
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
‣ CopyMat( sm ) | ( method ) |
Returns: a shallow copy of the sparse matrix sm
‣ GetEntry( sm, i, j ) | ( method ) |
Returns: a ring element.
This returns the entry sm[i,j] of the sparse matrix sm
‣ SetEntry( sm, i, j, elm ) | ( method ) |
Returns: nothing.
This sets the entry sm[i,j] of the sparse matrix sm to elm.
‣ 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.
‣ 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
‣ 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.
‣ TransposedSparseMat( sm ) | ( method ) |
Returns: the transposed matrix of the sparse matrix sm
‣ CertainRows( sm, list ) | ( method ) |
Returns: the submatrix sm{[list]} as a sparse matrix
‣ CertainColumns( sm, list ) | ( method ) |
Returns: the submatrix sm{[1..nrows(sm)]}{[list]} as a sparse matrix
‣ SparseUnionOfRows( L ) | ( function ) |
Returns: a sparse matrix
Stack the sparse matrices in the non-empty list L.
‣ SparseUnionOfColumns( L ) | ( function ) |
Returns: a sparse matrix
Augment the sparse matrices in the non-empty list L.
‣ SparseDiagMat( list ) | ( function ) |
Returns: the block diagonal matrix composed of the sparse matrices in list
‣ Nrows( sm ) | ( method ) |
Returns: the number of rows of the sparse matrix sm. This should be preferred to the equivalent sm!.nrows.
‣ Ncols( sm ) | ( method ) |
Returns: the number of columns of the sparse matrix sm. This should be preferred to the equivalent sm!.ncols.
‣ IndicesOfSparseMatrix( sm ) | ( method ) |
Returns: the indices of the sparse matrix sm as a ListList. This should be preferred to the equivalent sm!.indices.
‣ 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.
‣ RingOfDefinition( sm ) | ( method ) |
Returns: the base ring of the sparse matrix sm. This should be preferred to the equivalent sm!.ring.
generated by GAPDoc2HTML