Problems in which an operator or function can be represented with asymptotically less data than the naive representation. For questions that are specifically related to sparse matrices use [sparse-matrix] tag instead.
In principle, any problem with enough structure to have asymptotically less data (in an information-theoretical sense) than the naive representation is a candidate for sparsity. Finding new sparse representations and methods for manipulating those sparse representations efficiently is an active research area. Some common examples:
- sparse grids (for representing high-dimensional functions with decaying mixed derivatives)
- hierarchical representations of operators (Fourier transforms, fast multipole method, butterfly method for Fourier integral operators)
- tensor product operators
Questions that deal with sparse matrices should be tagged with a sparse-matrix tag instead.