Ask Your Question
0

is it a sparse matrix or dense matrix?

asked 2013-09-20 03:52:26 -0500

radhika agrawal gravatar image

if the number of non zero elements in a matrix is equal to the number of zeros than what should we call this matrix -- a sparse matrix or a dense matrix?

edit retag flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted
2

answered 2013-09-20 04:39:46 -0500

tmonteil gravatar image

updated 2013-09-28 10:19:18 -0500

You should understand that a matrix is not sparse or dense by itself. It depends on how you define it.

For example:

sage: M = matrix(ZZ,[[1,1,1],[1,1,1],[1,1,1]],sparse=True)
sage: M
[1 1 1]
[1 1 1]
[1 1 1]
sage: M.is_sparse()
True
sage: M.is_dense()
False

But

sage: sage: M = matrix(ZZ,3,sparse=False)                       
sage: M
[0 0 0]
[0 0 0]
[0 0 0]
sage: M.is_sparse()
False
sage: M.is_dense()
True

The difference about sparse matrices and dense matrices is about how it is stored in memory (and therefore which algorithm are used to handle them).

Basically, in a dense matrix, every entry are stored in memory, even if it is zero. In a sparse matrix, only the non-zero entries are stored in a dictionary mapping an index $(i,j)$ to its entry.

So, you should define a matrix as a sparse matrix only if the number of non-zero elements is very small compared to the total number of entries. This is typically useful if the non-zero entries are located along the diagonal (there are about $n$ non-zero entries compared to about $n^2$ zero entries). However, for very small matrices (e.g. 5x5), even with a lot of zero entries, defining dense matrices is usually faster.

In your case, $n^2/2$ non-zero entries is too much for the sparse-matrix algorithms to work efficiently. Hence, you should better define dense matrices.

Note that, given a matrix M, you can transform it into a dense matrix or a sparse matrix with the methods .dense_matrix() and .sparse_matrix(). This can be usefull for example if, after a computation, a lot of entries become non-zero.

edit flag offensive delete link more
0

answered 2013-09-20 04:21:44 -0500

Mark gravatar image

For a matrix $M$ of rank $N\times N$, the number of non-zero elements should scale $\sim N$ or, at most, $\sim N \log(N)$ for $M$ to be sparse, otherwise most sparse matrix algorithms are of rather little help. (You can surely refine this statement for $N\times M$ matrices with $N\neq M$ ...)

In turn, I would not call 'your' matrix sparse.

edit flag offensive delete link more

Comments

@whomeveritmayconcern: I'd dare to disagree with the notion that a matrix is not sparse or dense by itself. I'd rather go with the majority of mathematical definitions on that, which can also be found publicly, e.g. http://en.wikipedia.org/wiki/Sparse_matrix, or http://www.phy.ornl.gov/csep/la/node14.html, or many others. Also, the 'difference' between sparse and dense matrices ist not how you store them ... I believe matrices exist even without computer RAM ;-) . Rather, once a matrix has been identified to be sparse, then you may want to consider storing it into various existing sparse matrix formats and may want to use various sparse matrix algorithms ... yet, even if you would stay away from doing so, the matrix would still remain sparse by itself.

Mark gravatar imageMark ( 2013-09-20 05:05:43 -0500 )edit

The links you provide do not support your point of view, they both deal with storage and algorithmics, and none of them provide a mathematical definition. - A huge majority of the wikipedia article is its first paragraph : "Storing a sparse matrix". - The second link states: "A good operational definition is that a matrix is sparse if it contains enough zero entries to be worth taking advantage of them to reduce both the storage and work required in solving a linear system." But no mathematical definition is given... Could you please provide a mathematical definition of a sparse matrix ?

tmonteil gravatar imagetmonteil ( 2013-09-27 11:55:38 -0500 )edit

Also, ask.sagemath.org tend to handle topics from a Sage perspective, and even mathematically defined objects could lead to not well defined Sage objects. For example, to the question "is $\sqrt{2}$ an algebraic number?", it might be worth saying that `sqrt(2)` will lead to a symbolic expression, `sqrt(2.0)` will lead to a floating-point number (hence a rational approximation), and `sqrt(QQbar(2))` will lead to an algebraic number. sage: sqrt(2).parent() Symbolic Ring sage: sqrt(2.0).parent() Real Field with 53 bits of precision sage: sqrt(QQbar(2)).parent() Algebraic Field This is somehow related to your point: I agree that "matrices exist even without computer RAM", but sparse and dense matrices are two implementations of the same mathematical object.

tmonteil gravatar imagetmonteil ( 2013-09-27 11:59:00 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2013-09-20 03:52:26 -0500

Seen: 2,221 times

Last updated: Sep 28 '13