The following functions compute non-trivial properties of sparse matrices.
The following functions compute nullspaces of matrices (solving equations of the form V.A=0).
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 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.
Given an m x n matrix A over the Euclidean ring or field R, return the elementary divisors of A. These are simply the non-zero diagonal entries of the Smith form of A, in order.The divisors are returned as a sequence Q = [e_1, ..., e_d], e_i | e_(i + 1) (i=1, ..., d - 1) of d elements of R (which may include ones), where d is the rank of A. If R is a field, the result is always a sequence of r ones, where r is the rank of A.
A function for computing the Smith normal form is not supplied for sparse matrices since the form may be trivially derived from the elementary divisors, and the sequence Q containing the divisors is often more convenient (and takes less memory). As transformation matrices are dense in general, they are not supported for the sparse representation.
The algorithm first performs sparse elimination using Markowitz pivoting to obtain a smaller dense matrix ([DEJ84, Sec. 9.2]; this is similar to the techniques described in [HHR93]). Then it invokes the dense Smith normal form algorithm for normal (dense-representation) matrices (SmithForm).
(Procedure.) Set the verbose printing level for all sparse matrix algorithms to be v. Currently the legal values for v are true, false, 0, 1, 2, and 3 (false has the same effect as 0, and true has the same effect as 1).[Next][Prev] [Right] [Left] [Up] [Index] [Root]