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.
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.
@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.
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 ?
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.
Asked: 2013-09-20 10:52:26 +0100
Seen: 4,467 times
Last updated: Sep 28 '13
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
