Help With Search Form

The following is a list of the search fields present on the Matrix Market Search Form, along with a brief explanation of their purpose.

Linear Algebra Problem Type

This indicates the general linear algebraic problem for which the matrix was originally generated. The choices are as follows. (In this discussion, A and B denote matrices, x a vector, and z a scalar.)

• Linear System ... The solution of systems of linear equations.
• Eigenvalue ... The computation of eigenvalues and/or eigenvectors of matrices. Both simple eigenproblems (Ax = zx) and generalized eigenproblems (e.g., Ax = zBx) are included.
• Least Squares ... The solution to overdetermined systems of linear equations in the least squares sense, that is, minimize || Ax-b || over x where ||.|| denotes the Euclidian norm.
• Structure ... Studies of the nonzero structure of sparse matrices under various transformations.

Included in each of these problems are the study of matrix factorizations peculiar to those problems.

Number Field

This indicates the scalar field from which the matrix elements are drawn. The choices are as follows.

• Real ... The real number field.
• Complex ... The complex number field.
• Pattern ... In this case the numerical values for the matrix elements are not supplied, only their nonzero pattern.

Numerical Symmetry Property

This indicates one of several numerical symmetry properties of the matrix. The choices are as follows.

• Symmetric ... aij = aji.
• Symmetric positive definite ... see below.
• Symmetric indefinite ... see below.
• Hermitian ... A complex matrix for which aji is the complex conjugate of aij. This implies a real diagonal.
• Skew symmetric ... aij = -aji. This implies a zero diagonal.
• Unsymmetric ... None of the above.

A matrix A is positive definite if and only if xTAx > 0 for all nonzero vectors x. A symmetric positive definite matrix has all positive real eigenvalues. A is negative definite if and only if -A is positive definite. For semidefiniteness, the inequality above is relaxed to admit equality; a semidefinite matrix has at least one zero eigenvalue. An indefinite matrix has none of these special properties.

Only half the elements of symmetric, Hermitian and skew symmetric matrices are present in the matrices downloaded from Matrix Market.

Nonzero Structure

This is used to informally characterize the nonzero structure of the matrix. Note that a given matrix may have more than one of these properties. Additional properties will be added to this list as the Matrix Market collection grows. The choices are as follows.

• Dense ... A matrix with no special nonzero structure, i.e. none of its elements are presumed zero a priori.
• Sparse ... A matrix which contains only a few nonzero elements in each row or column.
• Sparse symmetric ... A sparse matrix with a symmetric nonzero pattern. That is, aji is nonzero whenever aij is nonzero. Note that this does not imply that the matrix is numerically symmetric.
• Sparse unsymmetric ... A sparse matrix with an unsymmetric nonzero pattern. That is, for some i and j, aij is nonzero while aji=0.
• Banded ... A sparse matrix in which all the nonzeros are clustered about the main diagonal. The bandwidth is the largest |i-j| such that aSUBij is nonzero.
• Diagonal ... A matrix of bandwidth 0, i.e., its only nonzeros lie along the main diagonal.
• Tridiagonal ... A matrix of bandwidth 1, i.e., only the elements ai,i-1, aii, ai,i+1 can be nonzero in row i.
• Block Tridiagonal ... A matrix which can be partitioned into blocks such that the only blocks containing nonzeros in each block row are the diagonal block, its predecessor, and its successor. Finite difference discretizations of 2D elliptic operators typically give rise to block tridiagonal matrices in which each of the nonzero blocks are themselves tridiagonal.
• Triangular ... A matrix is upper triangular if all elements below the diagonal are zero, i.e. if aij=0 for all i > j. A matrix is lower triangular if all elements above the diagonal are zero, i.e. if aij=0 for all i < j.

Storage Mode

Applies only to matrices, i.e. not to generators.

Indicates the general text file storage format used to represent the matrix. The choices are as follows.

• Sparse Assembled ... The nonzero elements are represented directly. That is, the indices and nonzero values of individual nonzero matrix elements are provided. Such matrices are available in both Harwell-Boeing exchange format and in coordinate text file format.
• Sparse Elemental ... These matrices are represented as a set of small "elemental" matrices which must be summed to get the normal, assembled form. Finite element matrices are often represented in this form. Elemental matrices are only available in Harwell-Boeing exchange format.

Details on the text file formats are also available.

Shape

Indicates the general shape of the matrix. The choices are as follows.

• Square ... A matrix with the same number of rows and columns.
• More Rows Than Columns ... Represents an overdetermined system of linear equations. Least squares problems are of this type.
• More Columns Than Rows ... Represents an underdetermined linear system. Constraint matrices from linear programming problems are typically of this type.

Size

Applies only to matrices, i.e. not to generators.

This allows you to indicate constraints on the size of the matrix, including

• Minimum number of rows
• Maximum number of rows
• Minimum number of columns
• Maximum number of columns
• Minimum number of entries
• Maximum number of entries
• Minimum percentage of entries
• Maximum percentage of entries
The desired bounds are indicated by typing the appropriate numbers into the text fields displayed on the form.

Note that entries corresponds to matrix elements stored in Matrix Market or Harwell-Boeing files. Typically this is the same as the number of nonzeros in the matrix. However, in some cases explicit zero entries are stored in the files; in these cases there may be more entries than nonzeros.

Associated Materials Required

Applies only to matrices, i.e. not to generators.

This allows you to demand that certain associated material be available to supplement the matrix data, including

• Right hand side vectors for the associated linear system of equations.
• Solution vectors for the associated linear system of equations.
• Initial vectors to be used as starting guesses for iterative methods for solving the associated linear system of equations.

Language

Applies only to generators, i.e. not to individual matrices.

Indicates the language in which the matrix generator is coded. The choices are as follows.

• Fortran
• Matlab
• Java applet ... This indicates that the generator may be downloaded and run in a Java-enabled Web browser.

Output Type

Applies only to generators, i.e. not to individual matrices.

Indicates the form in which the genertor supplies the matrix. The choices are as follows.

• Column major dense ... The matrix is returned as an internal data structure based on a dense two-dimensional array in column major order (i.e., as in Fortran).
• Column major dense packed ... The matrix is returned as an internal data structure based on a one-dimensional array in column major order with only lower-triangular elements stored. (Suitable for symmetric or Hermitian matrices.)
• Compressed Row ... The matrix is returned as an internal data structure based on compressed row format.
• Compressed Column ... The matrix is returned as an internal data structure based on compressed column format.
• Matrix-vector multiply ... The matrix is provided implicitly via a subprogram which computes the product of the matrix and a given input vector.
• Matrix Market ... The matrix is written to a file in Matrix Market format.

Text Field

The text field in the Matrix Market Search Tool specifies a pattern to search for in the Matrix Market meta-database. This database contains, in ASCII form, all of the words visible on the various matrix and set home pages. We suggest that you browse through set and matrix pages to familiarize yourself with the type of information found there.

If the pattern is matched in a matrix entry, then that matrix will be retireved; if the pattern is matched in a set entry, then all matrices in the set will be retrieved.

Most patterns acceptable to egrep are acceptable, with the following restrictions:

• all patterns are case insensitive
• the single quote character (') is prohibited.
For those who are not Unix afficionados, the following synopsis covers the main points.

Special Characters

The following characters have special meanings in patterns: .+*\$()\{}^|\. In general, they should be avoided, except for the few cases we give below.

Simple Patterns

A simple pattern is a string of characters that does not contain one of the special characters given above. This pattern must be matched exactly. Note that it can contain blanks, and that it can be only part of a word. For example, oil pan will match both oil pan and foil panda, but not oily pan.

Wild Cards

The period character (.) matches any single character. Thus, p.t matches pat, pot, put, and even computation.

A one-character pattern followed by an asterisk (*) matches zero or more occurrences of the single character preceeding it. Thus, be*t matches bet, beet as well as subtle.

Combining the two wildcards above yields the following pattern: .* This matches zero or more arbitrary characters, i.e. anything. It is useful in cases where you want to specify the beginning and end of the pattern, but not the middle. For example, b.*t will match any string beginning with b and ending with t, e.g., bat, boat, or even big grey cat. As you can see, such wildcards can give unexpected results.

Examples

Here are some examples of search patterns and the matrices they retrieve.

• petroleum

Finds about 10 matrices related to petroleum engineering.

• saylor

Finds the 3 matrices in the set named SAYLOR.

• saylor3

Finds the matrix named SAYLOR3.

• least squares

Finds about 6 matrices related to least squares problems.

The Matrix Market is a service of the Mathematical and Computational Sciences Division / Information Technology Laboratory / National Institute of Standards and Technology

[ Home ] [ Search ] [ Browse ] [ Resources ]