Super sparsity

From Glossary

Jump to: navigation, search

The fraction of distinct nonzero values in a matrix. If a matrix has z nonzeros -i.e. z = sparsity × m × n, then the super-sparsity is number of distinct values divided by z. Although related to the idea of sparsity, a matrix can be highly super-sparse yet not sparse. For example if LaTeX: \textstyle A_{(i, j)} = 1 for all LaTeX: i,j, then sparsity is 0 but super-sparsity is LaTeX: 1/mn.

These matrices arise naturally in models with repetitive substructures. For example, a process may be modeled as a linear program with activities that convert raw materials into finished products (like a refinery converting crude oil into petroleum products). The yields are determined by the engineering, so this model would be the same if embedded into a larger linear program that uses it in numerous regions. Then, the yield values are replicated for each region, which makes the resulting linear program matrix super-sparse. Additionally, any network problem in which the coefficient matrix is the incidence matrix is super-sparse. This leads to the special case of only zeros and ones.

Personal tools