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 tag instead.