|
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.
Kernel(A) : MtrxSprs -> ModTupRng, Map
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.
KernelMatrix(A) : MtrxSprs -> Mtrx
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.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|