[Script Info]
Title:
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.03,0:00:05.06,Default,,0000,0000,0000,,So the traditional way to represent a sparse matrix is what we call compressed sparse row.
Dialogue: 0,0:00:05.06,0:00:08.16,Default,,0000,0000,0000,,So here's a small matrix of 9 elements.
Dialogue: 0,0:00:08.16,0:00:11.76,Default,,0000,0000,0000,,Three of them are zeroes, and so we want some sort of representation
Dialogue: 0,0:00:11.76,0:00:13.93,Default,,0000,0000,0000,,that's going to squeeze out those zeroes
Dialogue: 0,0:00:13.93,0:00:16.69,Default,,0000,0000,0000,,and only represent the values that are non-zero.
Dialogue: 0,0:00:16.69,0:00:19.30,Default,,0000,0000,0000,,And it seems a little silly on a small matrix like this,
Dialogue: 0,0:00:19.30,0:00:23.05,Default,,0000,0000,0000,,but, trust me, as you get to very large matrices with lots and lots of zeroes,
Dialogue: 0,0:00:23.05,0:00:27.70,Default,,0000,0000,0000,,this representation is going to save you a lot of space and save you a lot of computation.
Dialogue: 0,0:00:27.70,0:00:34.95,Default,,0000,0000,0000,,So in CSR format we require 3 vectors that together are going to represent this sparse matrix.
Dialogue: 0,0:00:34.95,0:00:37.45,Default,,0000,0000,0000,,So the first one is what we call the value vector,
Dialogue: 0,0:00:37.45,0:00:41.28,Default,,0000,0000,0000,,and it is simply going to represent all the non-zero data.
Dialogue: 0,0:00:41.28,0:00:46.45,Default,,0000,0000,0000,,So here we're simply going to list all the data that are not zero as 1 long array.
Dialogue: 0,0:00:46.45,0:00:51.20,Default,,0000,0000,0000,,The second array that we need is recording which column each of these data came from.
Dialogue: 0,0:00:51.20,0:01:00.43,Default,,0000,0000,0000,,So for instance, a is in column 0, b is in column 2, c is in column 0, and so on.
Dialogue: 0,0:01:00.43,0:01:05.71,Default,,0000,0000,0000,,And finally we have to indicate at which element each one of these 3 rows begin.
Dialogue: 0,0:01:05.71,0:01:12.76,Default,,0000,0000,0000,,So the 3 rows begin with value a and value c and value f.
Dialogue: 0,0:01:12.76,0:01:18.06,Default,,0000,0000,0000,,So what we're going to write in the row pointer is that value a is at index 0,
Dialogue: 0,0:01:18.06,0:01:23.30,Default,,0000,0000,0000,,value c is at index 2, and value f is at index 5.
Dialogue: 0,0:01:23.30,0:01:29.36,Default,,0000,0000,0000,,And now we can reconstruct this sparse matrix with these 3 arrays.