English subtitles

← Sparse Matrices - Intro to Parallel Programming

Get Embed Code
2 Languages

Showing Revision 4 created 05/25/2016 by Udacity Robot.

  1. So the traditional way to represent a sparse matrix is what we call compressed sparse row.
  2. So here's a small matrix of 9 elements.
  3. Three of them are zeroes, and so we want some sort of representation
  4. that's going to squeeze out those zeroes
  5. and only represent the values that are non-zero.
  6. And it seems a little silly on a small matrix like this,
  7. but, trust me, as you get to very large matrices with lots and lots of zeroes,
  8. this representation is going to save you a lot of space and save you a lot of computation.
  9. So in CSR format we require 3 vectors that together are going to represent this sparse matrix.
  10. So the first one is what we call the value vector,
  11. and it is simply going to represent all the non-zero data.
  12. So here we're simply going to list all the data that are not zero as 1 long array.
  13. The second array that we need is recording which column each of these data came from.
  14. So for instance, a is in column 0, b is in column 2, c is in column 0, and so on.
  15. And finally we have to indicate at which element each one of these 3 rows begin.
  16. So the 3 rows begin with value a and value c and value f.
  17. So what we're going to write in the row pointer is that value a is at index 0,
  18. value c is at index 2, and value f is at index 5.
  19. And now we can reconstruct this sparse matrix with these 3 arrays.