2021-10-13 17:19:11 +0200 | received badge | ● Popular Question (source) |
2018-12-24 03:29:45 +0200 | commented answer | NEW VERSION: Sparse matrix stores something for each row? @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? |
2018-12-23 17:10:20 +0200 | commented answer | NEW VERSION: Sparse matrix stores something for each row? @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. |
2018-12-22 02:04:34 +0200 | commented answer | NEW VERSION: Sparse matrix stores something for each row? @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. |
2018-12-19 13:32:21 +0200 | received badge | ● Editor (source) |
2018-12-19 11:17:53 +0200 | received badge | ● Student (source) |
2018-12-19 11:15:03 +0200 | asked a question | 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). 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. I'm receiving (on a freshly started kernel) This raises two questions.
I'm on Windows 8.1/SAGE 8.4. UPDATE. Transposing the matrices, i.e. writing seems to work well memory-wise, it returns 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. 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 This has got to be a known issue. I was not able to find a discussion, however. (This might be what is known as |