The following functions compute non-trivial properties of sparse matrices.
The following functions compute nullspaces (solving equations of the form V.A=0) or rowspaces of sparse matrices.
Given an m x n sparse matrix A over a ring R, return the nullspace of A (or the kernel of A, considered as a linear transformation or map), which is the R-space consisting of all vectors v of length m such that v.A = 0. Since the result will be given in the dense representation, both the nullity of A and the number of rows of A must both be reasonably small.The algorithm first performs sparse elimination using Markowitz pivoting ([DEJ84, Sec. 9.2]) to obtain a smaller dense matrix, then the nullspace algorithm for dense-representation matrices is applied to this matrix.
Given an m x n sparse matrix A over a ring R, return a (dense-representation) basis matrix of the nullspace of A. This is a matrix N having m columns and the maximal number of independent rows subject to the condition that N.A = 0. This function has the advantage that the nullspace is not returned as a R-space, so echelonization of the resulting nullspace may be avoided.
This function is equivalent to Nullspace(Transpose(A)), but will be more efficient in space for large matrices, since the transpose may not have to be explicitly constructed to compute the nullspace.
Given an m x n sparse matrix A over a ring R, return the rowspace of A, which is the R-space generated by the rows of A. Since the result will be given in the dense representation, the rank and the number of columns of A must both be reasonably small.
Given an m x n sparse matrix A over a ring R, return the rank of A. The algorithm first performs sparse elimination using Markowitz pivoting ([DEJ84, Sec. 9.2]) to obtain a smaller dense matrix, then the rank algorithm for dense-representation matrices is applied to this matrix.