Sparsity

From Glossary

Jump to: navigation, search

The fraction of zeroes in a matrix. If LaTeX: \textstyle A is LaTeX: \textstyle m \times n, and LaTeX: \textstyle A_{(i, j)} \ne 0 for LaTeX: k of its elements, its sparsity is LaTeX: \textstyle \frac{k}{mn}. Large linear programs tend to be very sparse, increasingly so as the dimensions grow. For example, consider the standard transportation problem with s sources and d destinations. This has LaTeX: \textstyle m = (s+d) constraints and LaTeX: \textstyle n = sd variables. Each column, however, has exactly 2 nonzeroes since A is the incidence matrix of the network, so its sparsity is LaTeX: \textstyle \frac{2n}{mn} = \frac{2}{m}, which decreases as the number of sources and/or destinations grows large.

The sparsity of a simple graph (or network) is the sparsity of its adjacency matrix. More generally, the sparsity of a multigraph refers to the average degree of its nodes.

See super sparsity for extensions of this idea.


Views
Personal tools