The following functions and procedures enable the user to access or set individual entries of sparse matrices.
Given a sparse matrix A over a ring R having m rows and n columns, and an integer i such that 1 ≤i ≤m, return the i-th row of A, as a dense vector of length n (lying in Rn).
Given a sparse matrix A over a ring R having m rows and n columns, integers i and j such that 1 ≤i ≤m and 1 ≤j ≤n, return the (i, j)-th entry of A, as an element of the ring R.
Given a sparse matrix A over a ring R having m rows and n columns, integers i and j such that 1 ≤i ≤m and 1 ≤j ≤n, and a ring element x coercible into R, modify the (i, j)-th entry of A to be x. Here i and j must be within the ranges given by the current dimensions of A; see SetEntry below for a procedure to automatically extend A if necessary.
(Procedure.) Given a sparse matrix A over a ring R, integers i, j≥1, and a ring element x coercible into R, modify the (i, j)-th entry of A to be x. The entry specified by i and j is allowed to be beyond the current dimensions of A; if so, A is automatically extended to have at least i rows and j columns.This procedure will be commonly used in situations where the final size of the matrix is not known as an algorithm proceeds (e.g., in index-calculus methods). One can create the 0 x 0 sparse matrix over Z, say, and then call SetEntry to build up the matrix dynamically. See the example H28E3 below, which uses this technique.
Note that extending the dimensions of A with a very large i or j will not in itself consume much memory, but if A then becomes dense or is passed to some algorithm, then the memory needed may of course be proportional to the dimensions of A.
> A := SparseMatrix(2, 3, [<1,2,3>, <2,3,-1>]); > A; Sparse matrix with 2 rows and 3 columns over Integer Ring > Matrix(A); [ 0 3 0] [ 0 0 -1] > A[1]; (0 3 0) > A[1, 3]:=5; > A[1]; (0 3 5)We next extend A using the procedure SetEntry.
> SetEntry(~A, 1, 5, -7); > A; Sparse matrix with 2 rows and 5 columns over Integer Ring > Matrix(A); [ 0 3 5 0 -7] [ 0 0 -1 0 0]A common situation is to start with the empty 0 x 0 matrix over Z and then to extend it dynamically.
> A := SparseMatrix(); > A; Sparse matrix with 0 rows and 0 columns over Integer Ring > SetEntry(~A, 1, 4, -2); > A; Sparse matrix with 1 row and 4 columns over Integer Ring > SetEntry(~A, 2, 3, 8); > A; Sparse matrix with 2 rows and 4 columns over Integer Ring > Matrix(A); [ 0 0 0 -2] [ 0 0 8 0] > SetEntry(~A, 200, 319, 1); > SetEntry(~A, 200, 3876, 1); > A; Sparse matrix with 200 rows and 3876 columns over Integer Ring > Nrows(A); 200 > Ncols(A); 3876 > NNZEntries(A); 4 > Density(A); 0.000005159958720330237358101135190 > Support(A, 200); [ 319, 3876 ]
The following functions enable the extraction of certain rows, columns or general submatrices, or the replacement of a block by another sparse matrix.
Given an m x n sparse matrix A and integers i, j, p and q such that 1≤i ≤i + p ≤m + 1 and 1 ≤j ≤j + q ≤n + 1, return the p x q submatrix of A rooted at (i, j). Either or both of p and q may be zero, while i may be m + 1 if p is zero and j may be n + 1 if q is zero.
Given an m x n sparse matrix A and integers i, j, r and s such that 1≤i, i - 1 ≤r ≤m, 1 ≤j, and j - 1 ≤s ≤n, return the r - i + 1 x s - j + 1 submatrix of A rooted at the (i, j)-th entry and extending to the (r, s)-th entry, inclusive. r may equal i - 1 or s may equal j - 1, in which case a sparse matrix with zero rows or zero columns, respectively, will be returned.
Given an m x n sparse matrix A and integer sequences I and J, return the submatrix of A given by the row indices in I and the column indices in J.
Given an m x n sparse matrix A over a ring R, a p x q sparse matrix B over R, and integers i and j such that 1≤i ≤i + p ≤m + 1 and 1 ≤j ≤j + q ≤n + 1, insert B at position (i, j) in A. In the functional version (A is a value argument), this function returns the new sparse matrix and leaves A untouched, while in the procedural version (~A is a reference argument), A is modified in place so that the p x q submatrix of A rooted at (i, j) is now equal to B.
Given an m x n sparse matrix A and integers i and k such that 1 ≤i ≤i + k ≤m + 1, return the k x n submatrix of X consisting of rows [i ... i + k - 1] inclusive. The integer k may be zero and i may also be m + 1 if k is zero, but the result will always have n columns.
Given an m x n sparse matrix A and an integer i such that 0 ≤i ≤m, return the i x n submatrix of X consisting of the first i rows. The integer i may be 0, but the result will always have n columns.
Given an m x n sparse matrix A and integers i and j such that 1 ≤i and i - 1 ≤j ≤m, return the j - i + 1 x n submatrix of X consisting of rows [i ... j] inclusive. The integer j may equal i - 1, in which case a sparse matrix with zero rows and n columns will be returned.
Given an m x n sparse matrix A and integers i and k such that 1 ≤i ≤i + k ≤n + 1, return the m x k submatrix of X consisting of columns [i ... i + k - 1] inclusive. The integer k may be zero and i may also be n + 1 if k is zero, but the result will always have m rows.
Given an m x n sparse matrix A and an integer i such that 0 ≤i ≤n, return the m x i submatrix of X consisting of the first i columns. The integer i may be 0, but the result will always have m rows.
Given an m x n sparse matrix A and integers i and j such that 1 ≤i and i - 1 ≤j ≤n, return the m x j - i + 1 submatrix of X consisting of columns [i ... j] inclusive. The integer j may equal i - 1, in which case a sparse matrix with zero columns and n rows will be returned.
The following functions and procedures provide elementary row or column operations on sparse matrices. For each operation, there is a corresponding function which creates a new sparse matrix for the result (leaving the input sparse matrix unchanged), and a corresponding procedure which modifies the input sparse matrix in place.
Given an m x n sparse matrix A and integers i and j such that 1 ≤i≤m and 1 ≤j ≤m, swap the i-th and j-th rows of A.
Given an m x n sparse matrix A and integers i and j such that 1 ≤i≤n and 1 ≤j ≤n, swap the i-th and j-th columns of A.
Given a sparse matrix A, reverse all the rows of A.
Given a sparse matrix A, reverse all the columns of A.
Given an m x n sparse matrix A over a ring R, a ring element c coercible into R, and integers i and j such that 1 ≤i≤m and 1 ≤j ≤m, add c times row i of A to row j of A.
Given an m x n sparse matrix A over a ring R, a ring element c coercible into R, and integers i and j such that 1 ≤i≤n and 1 ≤j ≤n, add c times column i of A to column j.
Given an m x n sparse matrix A over a ring R, a ring element c coercible into R, and an integer i such that 1 ≤i≤m, multiply row i of A by c (on the left).
Given an m x n sparse matrix A over a ring R, a ring element c coercible into R, and an integer i such that 1 ≤i≤n, multiply column i of A by c (on the left).
Given an m x n sparse matrix A and an integer i such that 1 ≤i≤m, remove row i from A (leaving an (m - 1) x n sparse matrix).
Given an m x n sparse matrix A and an integer j such that 1 ≤j≤n, remove column j from A (leaving an m x (n - 1) sparse matrix).
Given an m x n sparse matrix A and integers i and j such that 1 ≤i≤m and 1 ≤j≤n, remove row i and column j from A (leaving an (m - 1) x (n - 1) sparse matrix).
Given a sparse matrix A, remove all the zero rows of A.