压缩稀疏行 (CSR)：如何存储空行？

Question

如何在 CSR 中表示空行？

假设我们有以下矩阵：

* MATRIX 1 *
a 0 0
0 b 0
0 0 c

val = [ a b c ]
col = [ 0 1 2 ]
row = [ 0 1 2 ] <- makes sense!

—————————————————————   

* MATRIX 2 *
a b c
0 0 0
0 0 0

val = [ a b c ]
col = [ 0 1 2 ]
row = [ 0 ] <— makes sense…? but how about…

—————————————————————

* MATRIX 3 *
0 0 0
a b c
0 0 0

val = [ a b c ]
col = [ 0 1 2 ]
row = [ 0 ] <— wait… how do we differentiate between MATRIX 2 and MATRIX 3?

MATRIX 1很直观，但是我们如何表示MATRIX 2和MATRIX 3之间的区别呢？我们是否使用负整数作为间距？

谢谢

Answer 1

看看The Wikipedia page。 IA 向量（或您称之为“行”）定义为：

The array IA is of length m + 1. It is defined by this recursive definition:

IA[0] = 0

IA[i] = IA[i − 1] + (number of nonzero elements on the (i − 1)-th row in the original matrix)

Thus, the first m elements of IA store the index into A of the first nonzero element in each row of M, and the last element IA[m] stores NNZ, the number of elements in A, which can be also thought of as the index in A of first element of a phantom row just beyond the end of the matrix M. The values of the i-th row of the original matrix is read from the elements A[IA[i]] to A[IA[i + 1] − 1] (inclusive on both ends), i.e. from the start of one row to the last index just before the start of the next.

因此，在矩阵 1 中：

row = [0 1 2 3]

在矩阵 2 中：

row = [0 3 3 3]

矩阵 3

row = [0 0 3 3]

Answer 2

提供的答案接近于很好的解释，但需要稍微澄清一下：

前两个要点对 IA 中的条目给出了明确的说明。

但是下一部分，

”因此，IA的前m个元素将索引存储到M的每一行中第一个非零元素的A中，最后一个元素IA[m] 存储 NNZ，A 中的元素数，也可以认为是 A 中虚线末尾第一个元素的索引矩阵 M。原始矩阵的 i-th row 的值是从元素 A[IA[i]] to A[IA[i + 1] − 1] 中读取的（包括两端），即从一行的开始到下一行开始之前的最后一个索引。”

很难解析，因为引用"IA", "m", "NNZ", "M",和"A"没有定义。

"IA"的长度是否等于一加全矩阵中非零元素的个数？。我认为 "A" 和 "M" 指的是全矩阵和稀疏矩阵，但没有足够的信息来确定哪个是哪个。 "NNZ" 可能指的是全矩阵中非零元素的数量。而 "m" 可能与 "NNZ".

相同

您介意提供 "IA", "m", "NNZ", "M" 和 "A" 的定义来完成解释吗？

在此先致谢，将不胜感激！

压缩稀疏行 (CSR)：如何存储空行？

Compressed Sparse Row (CSR): How do you store empty rows?

algorithm

matrix

sparse-matrix

data-structures