Understanding Sparse Matrices (Multicore Analysis and Sparse Matrix Toolkit)

A matrix that represents a large-scale application can contain many zero elements. A matrix primarily populated by zero elements is known as a sparse matrix. Conversely, a matrix primarily populated by nonzero elements is known as a dense matrix.

To compute a dense matrix, you must store all matrix elements in memory explicitly. The computational complexity of matrix operations is proportional to the matrix size. For example, if you multiply two n-by-n matrices on a computer, where n is the number of rows and columns, the memory usage is O(n²) and the computational complexity is O(n³).

Therefore, working with dense matrices can be a memory-consuming and time-consuming task on a typical computer because of the potentially large size of the matrices. On the other hand, sparse matrices can use up less memory by taking advantage of the zero elements in a sparse matrix. You use a specialized data structure to store the nonzero elements in the sparse matrix. Sparse matrix algorithms also contribute to faster computation.

Sparse matrices have the following attributes:

• Nonzeros—The nonzero elements in a sparse matrix.
  
  In general, the elements in a sparse matrix are nonzero elements. However, the sparse matrix in LabVIEW may store zero elements. Storing zero elements can occur in one of the following ways:
  • You explicitly set elements in a sparse matrix to zero. This is useful when you want to create a symmetrically structured sparse matrix.
  • Zero elements appear when numerical cancellation occurs in matrix operations, such as addition or subtraction. The existence of zero elements in a sparse matrix does not affect the results of matrix operations.
• Number of nonzeros—The number of nonzero elements in a sparse matrix.
  
  In LabVIEW, the number of nonzeros includes the number of zero elements if LabVIEW stores the zero elements in the sparse matrix.
• Maximum number of nonzeros—The maximum number of nonzeros elements that a sparse matrix can store.
  
  Because LabVIEW manages an internal workspace to store elements in a sparse matrix, the maximum number of nonzeros specifies the maximum number of elements that the workspace can accommodate. The maximum number of nonzeros always is no less than the number of nonzeros, such that the workspace has additional space available for inserting more elements into the sparse matrix. LabVIEW automatically enlarges the internal workspace if the number of nonzeros exceeds the maximum number of nonzeros.
  
  You can use the Set Max Number of Nonzeros VI to set the maximum number of nonzeros in a sparse matrix. If the sparse matrix allows a large number of elements, specify a large value for the maximum number of nonzeros to get better performance when inserting elements.
• Density—A measure of nonzero elements in a sparse matrix. Density is equal to the ratio of the number of nonzeros to the number of rows multiplied by the number of columns.
• Pattern—The distribution of nonzero elements in a sparse matrix. Pattern, or sparsity pattern, considers the coordinates, the row and column indices, of nonzero elements more than the actual values. Two sparse matrices can have the same sparsity pattern but not the same element values.