ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 23 Dec 2018 23:17:02 -0600NEW VERSION: Sparse matrix stores something for each row?http://ask.sagemath.org/question/44709/new-version-sparse-matrix-stores-something-for-each-row/**NEW VERSION. This is what this question has boiled down to upon further investigation. Everything below this paragraph in boldface and the subsequent code is the old version and serves purely historical purposes =) I hope this was the right thing to do rather than creating a new question. The issue is that the amount of memory occupied by a sparse matrix seems to depend linearly on the number of rows in the matrix. In particular, my setup wont even let me create a zero $10^9\times 1$ sparse matrix but has no problem with a zero $1\times 10^9$ sparse matrix. This can all be illustrated by running the below code (and it's hardly the way things are supposed to be).**
print get_memory_usage()
B=matrix(QQ, 1, 1000000000, {})
print get_memory_usage()
B=matrix(QQ, 10000000, 1, {})
print get_memory_usage()
B=matrix(QQ, 1000000000, 1, {})
print get_memory_usage()
---------------------------------------------------------------------------------------------------------------------------------
I'm running the following code. Here I create a sparse $10^5\times 10^5$ identity matrix and then apply it repeatedly to a vector in $\mathbb R^{10^5}$ with 100 nonzero coordinates (which is stored as $10^5\times 1$ sparse matrix). Each time I add the result to a list until I run out of 2 GB of memory.
A=matrix(QQ, 100000, 100000, {(i,i):1. for i in range(100000)})
print get_memory_usage()
B=[matrix(QQ, 100000, 1, {(i,0):1. for i in range(100)})]
while (get_memory_usage()<2000): B.append(A*B[-1])
print len(B)
print get_memory_usage()
del B
del A
print get_memory_usage()
I'm receiving (on a freshly started kernel)
204.54296875
196
2003.51953125
1399.0234375
This raises two questions.
1. Why is there so much memory (1.4 GB) still in use after I successfully ran the code and deleted both objects I've created? That's a leak, right?
2. Why does deleting a list of 196 sparse matrices with 100 nonzero elements each free up 600 MB? Each such matrix should only take up a few KB, right?
I'm on Windows 8.1/SAGE 8.4.
**UPDATE**. Transposing the matrices, i.e. writing
...
B=[matrix(QQ, 1, 100000, {(0,i):1. for i in range(100)})]
for i in range(200): B.append(B[-1]*A)
...
seems to work well memory-wise, it returns
214.50390625
201
215.53125
186.62109375
However, it takes up much more time than the first version. This is probably due to the implementation of sparse matrix multiplication unfortunately containing a [loop over the columns of the right matrix](https://github.com/sagemath/sage/blob/6187d261eca3c980e575b53d1a31f580ba8cfdfd/src/sage/matrix/matrix_rational_sparse.pyx#L184). Is there any simple way around this high memory/low speed dilemma?
**UPDATE 2.** This might not be a memory leak and have more to do with the implementation of sparse matrices in general rather than their multiplication in particular. Apparently, a sparse matrix stores something for *each* of its rows as shown by
print get_memory_usage()
B=matrix(QQ, 1, 10000000, {})
print get_memory_usage()
B=matrix(QQ, 10000000, 1, {})
print get_memory_usage()
165.45703125
165.51953125
1082.68359375
This has got to be a known issue. I was not able to find a discussion, however. (This might be what is known as `csr_matrix` in `scipy` but why this would be chosen as the general standard here is beyond me.)Tue, 18 Dec 2018 18:20:27 -0600http://ask.sagemath.org/question/44709/new-version-sparse-matrix-stores-something-for-each-row/Answer by tmonteil for <p><strong>NEW VERSION. This is what this question has boiled down to upon further investigation. Everything below this paragraph in boldface and the subsequent code is the old version and serves purely historical purposes =) I hope this was the right thing to do rather than creating a new question. The issue is that the amount of memory occupied by a sparse matrix seems to depend linearly on the number of rows in the matrix. In particular, my setup wont even let me create a zero $10^9\times 1$ sparse matrix but has no problem with a zero $1\times 10^9$ sparse matrix. This can all be illustrated by running the below code (and it's hardly the way things are supposed to be).</strong></p>
<pre><code>print get_memory_usage()
B=matrix(QQ, 1, 1000000000, {})
print get_memory_usage()
B=matrix(QQ, 10000000, 1, {})
print get_memory_usage()
B=matrix(QQ, 1000000000, 1, {})
print get_memory_usage()
</code></pre>
<hr>
<p>I'm running the following code. Here I create a sparse $10^5\times 10^5$ identity matrix and then apply it repeatedly to a vector in $\mathbb R^{10^5}$ with 100 nonzero coordinates (which is stored as $10^5\times 1$ sparse matrix). Each time I add the result to a list until I run out of 2 GB of memory.</p>
<pre><code>A=matrix(QQ, 100000, 100000, {(i,i):1. for i in range(100000)})
print get_memory_usage()
B=[matrix(QQ, 100000, 1, {(i,0):1. for i in range(100)})]
while (get_memory_usage()<2000): B.append(A*B[-1])
print len(B)
print get_memory_usage()
del B
del A
print get_memory_usage()
</code></pre>
<p>I'm receiving (on a freshly started kernel)</p>
<pre><code>204.54296875
196
2003.51953125
1399.0234375
</code></pre>
<p>This raises two questions. </p>
<ol>
<li><p>Why is there so much memory (1.4 GB) still in use after I successfully ran the code and deleted both objects I've created? That's a leak, right? </p></li>
<li><p>Why does deleting a list of 196 sparse matrices with 100 nonzero elements each free up 600 MB? Each such matrix should only take up a few KB, right?</p></li>
</ol>
<p>I'm on Windows 8.1/SAGE 8.4.</p>
<p><strong>UPDATE</strong>. Transposing the matrices, i.e. writing</p>
<pre><code>...
B=[matrix(QQ, 1, 100000, {(0,i):1. for i in range(100)})]
for i in range(200): B.append(B[-1]*A)
...
</code></pre>
<p>seems to work well memory-wise, it returns</p>
<pre><code>214.50390625
201
215.53125
186.62109375
</code></pre>
<p>However, it takes up much more time than the first version. This is probably due to the implementation of sparse matrix multiplication unfortunately containing a <a href="https://github.com/sagemath/sage/blob/6187d261eca3c980e575b53d1a31f580ba8cfdfd/src/sage/matrix/matrix_rational_sparse.pyx#L184">loop over the columns of the right matrix</a>. Is there any simple way around this high memory/low speed dilemma?</p>
<p><strong>UPDATE 2.</strong> This might not be a memory leak and have more to do with the implementation of sparse matrices in general rather than their multiplication in particular. Apparently, a sparse matrix stores something for <em>each</em> of its rows as shown by </p>
<pre><code>print get_memory_usage()
B=matrix(QQ, 1, 10000000, {})
print get_memory_usage()
B=matrix(QQ, 10000000, 1, {})
print get_memory_usage()
165.45703125
165.51953125
1082.68359375
</code></pre>
<p>This has got to be a known issue. I was not able to find a discussion, however. (This might be what is known as <code>csr_matrix</code> in <code>scipy</code> but why this would be chosen as the general standard here is beyond me.)</p>
http://ask.sagemath.org/question/44709/new-version-sparse-matrix-stores-something-for-each-row/?answer=44720#post-id-44720This might be related to [this ask question](https://ask.sagemath.org/question/43979/multiplying-sparse-matrices/), and is tracked on [trac ticket 26532](https://trac.sagemath.org/ticket/26532).
Thu, 20 Dec 2018 14:39:30 -0600http://ask.sagemath.org/question/44709/new-version-sparse-matrix-stores-something-for-each-row/?answer=44720#post-id-44720Comment by imakhlin for <p>This might be related to <a href="https://ask.sagemath.org/question/43979/multiplying-sparse-matrices/">this ask question</a>, and is tracked on <a href="https://trac.sagemath.org/ticket/26532">trac ticket 26532</a>.</p>
http://ask.sagemath.org/question/44709/new-version-sparse-matrix-stores-something-for-each-row/?comment=44758#post-id-44758@nbruin I am certainly no expert on sparse matrix algorithms but I still feel like this is a questionable choice for the default (and only) format.
**with apologies of nbruin**: It looks like I edited this comment when I was intending to reply. If someone can find the history of this comment and restore it in its old form, that would be great.Sun, 23 Dec 2018 10:10:20 -0600http://ask.sagemath.org/question/44709/new-version-sparse-matrix-stores-something-for-each-row/?comment=44758#post-id-44758Comment by nbruin for <p>This might be related to <a href="https://ask.sagemath.org/question/43979/multiplying-sparse-matrices/">this ask question</a>, and is tracked on <a href="https://trac.sagemath.org/ticket/26532">trac ticket 26532</a>.</p>
http://ask.sagemath.org/question/44709/new-version-sparse-matrix-stores-something-for-each-row/?comment=44768#post-id-44768Oops. Indeed, it seems I did edit your comment. My apologies, I my intention was just to reply to your comment. I don't see any history or version control either, so I don't know how to undo the damage.
Comment I meant to write:
Not really. You need at least one of CSR or CSC to be able to do matrix operations relatively efficiently. If you can't do matrix operations with the object, you might as well use a default dictionary where you use (i,j) as keys and default to returning a 0. Note that the matrix operations are currently not even implemented with a reasonable efficiency, so clearly this code has not received a lot of love (yet). The fact that it was started with just CSR seems reasonably to me.
If you can make do with the scipy data types, then that might be a solution.Sun, 23 Dec 2018 23:17:02 -0600http://ask.sagemath.org/question/44709/new-version-sparse-matrix-stores-something-for-each-row/?comment=44768#post-id-44768Comment by imakhlin for <p>This might be related to <a href="https://ask.sagemath.org/question/43979/multiplying-sparse-matrices/">this ask question</a>, and is tracked on <a href="https://trac.sagemath.org/ticket/26532">trac ticket 26532</a>.</p>
http://ask.sagemath.org/question/44709/new-version-sparse-matrix-stores-something-for-each-row/?comment=44767#post-id-44767@nbruin OK, thank you for the insight (as you can see though, I really need matrix multiplication, so it is not clear how I'd make use of the polynomials trick)... But am I crazy or did you just edit my comment, deleting most of it (including my response to @rburing) and replacing the deleted part with a response to me? No offense taken, but could you please undo that?Sun, 23 Dec 2018 20:29:45 -0600http://ask.sagemath.org/question/44709/new-version-sparse-matrix-stores-something-for-each-row/?comment=44767#post-id-44767Comment by nbruin for <p>This might be related to <a href="https://ask.sagemath.org/question/43979/multiplying-sparse-matrices/">this ask question</a>, and is tracked on <a href="https://trac.sagemath.org/ticket/26532">trac ticket 26532</a>.</p>
http://ask.sagemath.org/question/44709/new-version-sparse-matrix-stores-something-for-each-row/?comment=44761#post-id-44761Another way to get a sparse data structure mimicking a sparse matrix is to use a bivariate polynomial sum a[i,j]*x^i*y^j. Addition should work pretty well on that (there might be limitation on the exponent size, though).Sun, 23 Dec 2018 13:08:36 -0600http://ask.sagemath.org/question/44709/new-version-sparse-matrix-stores-something-for-each-row/?comment=44761#post-id-44761Comment by rburing for <p>This might be related to <a href="https://ask.sagemath.org/question/43979/multiplying-sparse-matrices/">this ask question</a>, and is tracked on <a href="https://trac.sagemath.org/ticket/26532">trac ticket 26532</a>.</p>
http://ask.sagemath.org/question/44709/new-version-sparse-matrix-stores-something-for-each-row/?comment=44732#post-id-44732Sounds like OP/Sage may want to follow this advice from the scipy `coo_matrix` documentation: "COO is a fast format for constructing sparse matrices. Once a matrix has been constructed, convert to CSR or CSC format for fast arithmetic and matrix vector operations."Sat, 22 Dec 2018 10:12:36 -0600http://ask.sagemath.org/question/44709/new-version-sparse-matrix-stores-something-for-each-row/?comment=44732#post-id-44732Comment by nbruin for <p>This might be related to <a href="https://ask.sagemath.org/question/43979/multiplying-sparse-matrices/">this ask question</a>, and is tracked on <a href="https://trac.sagemath.org/ticket/26532">trac ticket 26532</a>.</p>
http://ask.sagemath.org/question/44709/new-version-sparse-matrix-stores-something-for-each-row/?comment=44731#post-id-44731I think it is quite common to implement matrices with sparse rows or sparse columns, with the idea that a completely zero row or column probably doesn't need to be stored at all, see e.g. https://docs.scipy.org/doc/scipy/reference/sparse.html#sparse-matrices-scipy-sparse
That's just the implementation sage offers right now. Perhaps it will grow other sparse forms if someone feels the need to provide them.Sat, 22 Dec 2018 02:58:06 -0600http://ask.sagemath.org/question/44709/new-version-sparse-matrix-stores-something-for-each-row/?comment=44731#post-id-44731Comment by imakhlin for <p>This might be related to <a href="https://ask.sagemath.org/question/43979/multiplying-sparse-matrices/">this ask question</a>, and is tracked on <a href="https://trac.sagemath.org/ticket/26532">trac ticket 26532</a>.</p>
http://ask.sagemath.org/question/44709/new-version-sparse-matrix-stores-something-for-each-row/?comment=44730#post-id-44730@tmonteil Yes, I've seen the question and the ticket and they are somewhat related. This is a separate issue though, a memory efficiency issue rather than time efficiency. Plus it concerns not only multiplication but construction of sparse matrices in general, which I realized after posting and tried to explain in the second update. Maybe I should make that clear at the very top.Fri, 21 Dec 2018 19:04:34 -0600http://ask.sagemath.org/question/44709/new-version-sparse-matrix-stores-something-for-each-row/?comment=44730#post-id-44730