Problems in which an operator or function can be represented with asymptotically less data than the naive representation. Not limited to sparse matrices.

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 matrices (in which most entries are zero, thus not stored)
  • 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
history | excerpt history