# Sparsity

### From Glossary

The fraction of zeroes in a matrix. If is and for of its elements, its sparsity is 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 constraints and variables. Each column, however, has exactly 2 nonzeroes since A is the incidence matrix of the network, so its sparsity is 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.