I am having trouble to know what is the formal mathematical way to in which we define what is a sparse matrix. I know that a sparse matrix, is a matrix in which most of the elements are zero. But by most are we saying 50% of the elements are zero?

  • 2
    $\begingroup$ That's not really how people use sparsity. It is really an asymptotic notion: we are considering $n \times n$ matrices with, say, $o(n^2)$ nonzero entries as $n \to \infty$. $\endgroup$ – Qiaochu Yuan Dec 5 '17 at 1:13
  • $\begingroup$ I know that. I just thought that by now someone had come with a formal definition of sparsity of sparse matrix. $\endgroup$ – Pedro Martins Dec 5 '17 at 1:18
  • $\begingroup$ @QiaochuYuan: Your comment makes me curious -- as far as I know, sparse matrices arising from scientific computing problems (usually finite difference and finite element methods) have only $O(n)$ nonzero entries. Do you know of situations where sparse matrices with a superlinear number of nonzeros, say $O(n\log n)$, are of interest? $\endgroup$ – user856 Dec 5 '17 at 3:43
  • $\begingroup$ No, I just wanted to say the largest thing that made sense. $O(n)$ also made sense but I didn't want to preclude the possibility of, as you say, $O(n \log n)$ or something like that also making sense. $\endgroup$ – Qiaochu Yuan Dec 5 '17 at 4:00

I don't think there is an 'official' or 'formal' break point where a graph becomes sparse. You generally speak of a sparse matrix when the sparsity of the matrix is noteworthy, and especially if it allows you to apply special computational techniques that only work on matrices with many zero entries.

  • 1
    $\begingroup$ Technically, computational techniques designed for sparse matrices will still work on dense matrices, they will just work very very slowly. $\endgroup$ – user856 Dec 5 '17 at 2:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.