A separate type is provided for sparse matrices to allow the user to construct such matrices and apply algorithms which take advantage of sparsity. Sparse matrices are distinct from normal matrices in Magma, which have a dense representation. This chapter describes the operations available for creating and working with sparse matrices.
The operations provided for sparse matrices include dynamic construction, simple properties, and the calculation of a number of non-trivial and important invariants (such as rank, determinant, or computing a non-zero vector in the nullspace). In particular, this datatype supports the class of index-calculus algorithms which involve generating a very large sparse system and then solving the system or finding the elementary divisors of the corresponding matrix (for example, to compute the abelian group structure). An extended example presented at the end of the chapter (H28E3) illustrates how an index-calculus method may be implemented in practice in the Magma language using the sparse matrix facilities.
The type name for the category of sparse matrices is MtrxSprs. All sparse matrices over a given ring R lie in the same sparse matrix structure, whose type name is MtrxSprsStr. The user will, in practice, rarely need to refer explicitly to the parent structure.