University of Florida Sparse Matrix Collection: Legend

• structural rank, sprank(A)

  The structural rank of a matrix is the number of entries in the maximum transversal of the bipartite graph of A. It is an upper bound on the numeric rank of the matrix. With probability one, sprank(A) is equal to rank(S), where S=sprand(A) has the same nonzero pattern as A, but with random numerical values. A matrix has structural full rank if it can be permuted so that the diagonal has no zero entries.

• # of blocks from dmperm

  This is the number of blocks obtained from the Dulmage-Mendelsohn decomposition. For a square matrix with full structural rank, it is the number of diagonal blocks after A is permuted into upper block triangular form. One if the matrix is strong Hall (not reducible via dmperm).

• # of strongly connected components

  For a square matrix, this is the number of strongly components of the graph. If the matrix has a zero-free diagonal, this is the same as the # of blocks from dmperm.

  For a rectangular matrix, this is the number of connected components in the undirected bipartite graph.

• entries not in dmperm blocks

  The number of entries outside the diagonal blocks, from the Dulmage-Mendelsohn decomposition. Zero if the matrix is not reducible via dmperm. Not reported if the matrix is not structurally full rank.

• explicit zero entries

  Matrices may include numerically zero entries that are present in the data structure for the matrix. MATLAB always removes these entries, but they can represent important information, such as entries that will become nonzero later on in a subsequent interation of a nonlinear solver. Except for the nonzero pattern symmetry, all matrix statistics exclude these entries.

• nonzero pattern symmetry

  Let S be the nonzero pattern of A, excluding the diagonal, but including explicit zero entries. Then this statistic is nnz(S & S')/nnz(S). It is one (100%) the pattern is perfectly symmetric, and zero if it is completely unsymmetric.

• numeric value symmetry

  The number of matched offdiagonal nonzeros over the total number of offdiagonal entries. A real entry A(i,j), i not equal to j, is matched if A(j,i) == A(i,j), but this is only counted if both A(j,i) and A(i,j) are nonzero. This metric is not affected by explicit zero entries. If A is complex, then the above test is modified; A(i,j) is matched if conj (A(j,i)) == A(i,j). This statistic is one (100%) if A == A', and zero if it is completely unsymmetric.

• type

  Real, complex, integer, or binary.

• structure

  Rectangular, unsymmetric, symmetric, Hermitian, or skew-symmetric.

• Cholesky candidate?

  "Yes" if the matrix is real symmetric, or complex Hermitian, and all entries on the diagonal are real, with values greater than zero. "No" otherwise.

• positive definite?

  Whether or not the matrix is positive definite.

• author

  The matrix creator.

• editor

  The matrix editor/collector, who first placed it in a widely-available collection.

• date

  The date the matrix was created, or added to a widely-available collection if the creation date is unknown.

• kind

  The kind of problem this matrix is from.

• 2D/3D problem?

  Whether or not the matrix comes from a problem with underlying 2D/3D geometry. This is based on the kind field, above.

• Additional fields

  This table displays the contents of the aux item in the problem structure. Its contents are problem dependent.

• ordering statistics

  These are computed in MATLAB. AMD is the approximate minimum degree algorithm. For rectangular matrices, this column of the table reports the COLAMD ordering. METIS is George Karypis' METIS_NodeND. For rectangular matrices, METIS_NodeND is applied to A'*A.

  The DMPERM+ column is an ordering obtained by first permuting the matrix via cs_dmperm (in CSparse) followed by AMD or METIS for each diagonal block (whichever obtains the best ordering for that block). No fillin occurs in the off-diagonal blocks. DMPERM+ results are not reported if the matrix consists of of a single irreducible block.

• nnz(chol(P*(A+A'+s*I)*P'))

  If s is selected so that C=P*(A+A'+s*I)*P' is positive definite, then this is the number of entries in L, for the Cholesky factorization of L*L'=C, where P is obtained from the ordering method. This statistic is not reported for rectangular matrices. Excludes the entries outside the diagonal blocks for DMPERM+.

• Cholesky flop count

  The floating-point operation count for the Cholesky factorization of C, described above. This statistic is not reported for rectangular matrices.

• nnz(L+U), no partial pivoting

  The number of nonzeros in L+U of the LU factorization of C, described above, but with no partial pivoting. For DMPERM, is the LU factorization of just the diagonal blocks, plus the number of entries not in the diagonal blocks. If the matrix has a symmetric nonzero pattern and a "healthy" diagonal, no partial pivoting is necessary, and LU factorization can often obtain this ordering quality. If the matrix is unsymmetric, the actual number of nonzeros in L+U can be less than this (with no pivoting), or it can be much more (with arbitrary pivoting). This statistic is not reported for AMD or METIS for rectangular matrices.

• nnz(V) for QR, upper bound nnz(L) for LU

  This is the number of entries in the Householder matrix V, consisting of the set of Householder reflections for a QR factorization of A (with columns permuted first via COLAMD, METIS(A'*A), or DMPERM+). It is also an upper bound on the number of entries in L, for an LU factorization with partial pivoting (with arbitrary row interchanges). This upper bound on nnz(L) can be very loose.

• nnz(R) for QR, upper bound nnz(U) for LU

  This is the number of entries in the factor R for a QR factorization of A (with columns permuted first via COLAMD, METIS(A'*A), or DMPERM+). It is also an upper bound on the number of entries in U, for an LU factorization with partial pivoting (with arbitrary row interchanges). This upper bound on nnz(U) can be very loose.

SVD-based stats

• norm(A)

  The largest singular value.

• min(svd(A))

  The smallest singular value.

• cond(A)

  The 2-norm condition number (max(svd(A)) / min(svd(A))).

• rank(A)

  The numerical rank, as found by rank(A) in MATLAB. It is the number of singular values great than the tolerance of max(size(A)) * eps * norm(A).

• sprank(A)

  This is not an SVD-based statistic, but it is listed here for comparison with rank(A). See sprank(A) at the top of this document. For all matrices, rank(A) is less than or equal to sprank(A).

• null space dimension

  The dimension of the null space, min(m,n)-rank(A) if A is m-by-n.

• gap

  If the matrix is rank deficient, let k = rank(A). The gap is the ratio s(k) / s(k+1).