Matlab Indexing Sparse Matrix

Question

Let's say we have the following sparse matrix defined by this 3 vectors:

[lines, columns, values] = find(A)

lines =

     1
     2
     3
     5
     1
     3
     3
     5
     4
     5


columns =

     1
     2
     2
     2
     3
     3
     4
     4
     5
     5


values =

     3
     4
     7
     3
     1
     5
     9
     6
     2
     5

What I am trying to achieve is to access the element at the position (2, 2)

I know you can do values(lines == 2) (values(columns == 2)) which will return all the values from second row (column).

My question is how can you do something like values(lines == 2 && columns == 2) to get the value at A(2,2)?

I'm not sure 'Q(qi == 2)' does what you think it does; 'qi == 2' is a 1D vector, and so it will index into the unrolled matrix. — Isaac, Apr 01 '14 at 14:51
@RobertP. Check http://www.mathworks.com/help/matlab/math/accessing-sparse-matrices.html - Indexing in Sparse Matrix Operations section The best way is to work with the 3 vectors and build the sparse matrix in the end. — Dragos Rizescu, Apr 01 '14 at 16:46
Yes, but you're not building them are you? According to your question you are trying to "access the element at the position qi = 2 and qj = 2". If this is _not_ what you're trying to do, then please try to explain more carefully. *Accessing* sparse matrices is definitely fastest the way I suggested (if not, please prove me wrong). Btw, do you get your desired result when doing it the way I suggest (if not, I have obviously missed something)? — Stewie Griffin, Apr 01 '14 at 17:01
@RobertP. No. I am not getting expected results on matrixes bigger that 1000x1000. Also, you are not supposed to access sparse like that. Let's say you have a matrix `A` with the dimension 10000x10000 defined as sparse with only one element `(231, 781) -> 1`. As you say if you want to add a new element, you do `A(213, 41) = 7`. This is very wrong!!! Because: `A(213, 41) = 7` => `A = full(A)` => `A(213, 41) = 7` => `A = sparse(A)`. About my question, yes, I've formulated it a bit stupid, but I will fix that now. — Dragos Rizescu, Apr 02 '14 at 06:02
I have never said that you should **add** elements this way. **Accessing** elements is something completely different! I very much agree that you should *not* add elements this way, but this is not what you're asking for in the question (as far as I can tell). — Stewie Griffin, Apr 02 '14 at 06:50
@RobertP. Accessing element on row 2 and column 2 the way you said, `A(2,2)` does the same as adding a new element: `var = A(2,2) => A = full(A) => var = A(2,2) => A = sparse(A) => 4`. — Dragos Rizescu, Apr 02 '14 at 07:17
What? If you want to **see** or **use** the element in position (2,2), it most definitely does not convert it to a full matrix when doing the operation. It's the **only** sensible way to do it. `var = A(2,2)` has **no overhead whatsoever**. Please have a look at my answer. Does it answer your question? — Stewie Griffin, Apr 02 '14 at 07:36
Dragos, you might want to have a look at the answers to [this question](http://stackoverflow.com/questions/22817806/best-practice-when-working-with-sparse-matrices). =) — Stewie Griffin, Apr 19 '14 at 14:55

score 1 · Accepted Answer · edited Jun 20 '20 at 09:12

1

If you want to access elements in a sparse matrix, or any other matrix for that matter. This has no overhead whatsoever. If anyone can prove me wrong on this one, I would very much like to see a benchmark of it, because then I have missed something very important!

a = Q(2,2);

If you want to add elements to a sparse matrix, this is also very simple. I don't think there are any faster ways to do this either. Again, if anyone can prove me wrong, please share your benchmark results!

If you have:

lines = [ 1
     2
     3
     5
     1];


columns = [1
     2
     2
     2
     3];


values = [3
     4
     7
     3
     1];
 
 Q = sparse(lines, columns, values)
  (1, 1) ->  3
  (2, 2) ->  4
  (3, 2) ->  7
  (5, 2) ->  3
  (1, 3) ->  1

 [linesF, columnsF, valuesF] = find(Q)
 
 %% Now add the value 12 to position (3,1)
 linesF = [linesF; 3];
 columnsF = [columnsF; 1];
 valuesF = [valuesF; 12];
 
 Q = sparse(linesF, columnsF, valuesF)
 
  (1, 1) ->  3
  (3, 1) ->  12
  (2, 2) ->  4
  (3, 2) ->  7
  (5, 2) ->  3
  (1, 3) ->  1

This works because there is nothing saying the row and column vectors must be sorted in any way.

Benchmark

S = sprand(10000,10000,0.0005);
tic
for ii = 1:1000
    var = S(r,c);
end
toc
Elapsed time is 0.010705 seconds.

[i,j,s] = find(S);
tic
for ii = 1:1000
    var = s((i == r & j == c);  % (r,c) is a random non-zero element in s
end
toc
Elapsed time is 0.296547 seconds.

edited Jun 20 '20 at 09:12

Community

1
1

answered Apr 02 '14 at 07:17

Stewie Griffin

14,889
11
39
70

`a = Q(qi(2), qj(2))` works but won't always return the correct value. For example if I want the value from `(2,3)`, according to that, I would do `a = Q(qi(2), qj(3))`, which based on your example `qi(2) = 2` and `qj(3) = 2`, => `a = Q(2,3)`. Just remove that part and it's alright. Thank you very much! – Dragos Rizescu Apr 02 '14 at 09:39
Will do =) I included it in case you wanted to elements in `qi(2)` and `qj(3)`, which is not necessarily (2,3). – Stewie Griffin Apr 02 '14 at 10:00
I am sorry, but I can not accept the answer as it is misleading and incorrect to be used on sparse matrix. – Dragos Rizescu Apr 02 '14 at 14:40
@DragosRizescu, please explain further. I've been working a lot with sparse matrices and I'm pretty confident this is correct. If it's not, I would love to know what is correct. What exactly is wrong? Can you prove it? Do you have benchmark results? Do you get your desired results? – Stewie Griffin Apr 02 '14 at 15:19
1

@DragosRizescu This is the correct answer. To access any element all you need is `Q(2,3)`. No need to go through `find()` and its row and column subscripts at all. – Oleg Apr 11 '14 at 21:51

score 1 · Answer 2 · edited May 23 '17 at 12:32

1

In support of Robert's answer , here's a snapshot that proves that no conversion to full happens in accessing elements of a sparse matrix

enter image description here

I create a sparse matrix that would occupy 1e5^2 * 8bytes ~ 74.5 GB in RAM if it were full. Then I retrieve the subscripts to nonzero elements of S and access the first element (without loss of generality).

On the right side of the pic, nowhere the memory jumps to > 16 GB. The only (hardly) noticeable bump happens when I create S.

edited May 23 '17 at 12:32

Community

1
1

answered Apr 11 '14 at 21:57

Oleg

10,406
3
29
57

That was a nice and simple way of showing that there is no conversion. And I liked your `wssize`, haven't seen it before. For others, the function can be found [here](http://www.mathworks.com/matlabcentral/fileexchange/26250-display-ws-variables-size-in-kb-mb-or-gb/content/wssize.m). – Stewie Griffin Apr 11 '14 at 22:08
One thing just occurred to me: Shouldn't `S` be bigger (in MB)? The sparse matrix is represented by three vectors, rows, columns and values. If you did `[r, c, v] = find(S)`. `v` would be a vector with the same size as `r` and `c`. `S` must naturally contain this information already, thus it should be approximately 3x76.26, not 2x76.27 MB. Am I missing something here? I don't have MATLAB here so unfortunately I can't test this. – Stewie Griffin Apr 13 '14 at 10:55
2

@RobertP. According to the [paper on page 3](http://www.mathworks.com/help/pdf_doc/otherdocs/simax.pdf), they store the row indices and the position of the first element of each column in the vector of row indices. If `nnz()` is the number of nonzero elements and `n` the number of columns, then a sparse matrix requires `nnz*(8 bytes) + nnz*(4 bytes) + n*(4 bytes) = nnz*(12 bytes) + n * (4 bytes)` – Oleg Apr 13 '14 at 20:33

Matlab Indexing Sparse Matrix

2 Answers2

Benchmark

Linked