压缩稀疏行（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之间的差异？我们使用负整数来表示间距吗？

谢谢。

- Stephen Lasky

---

你有什么语言/工具在脑海中？ - Tim Biegeleisen

我在询问一般的理论问题，如果有帮助的话，C语言可以。 - Stephen Lasky

Answer 1

请看维基百科页面。向量IA（或者像您称呼的“行”）被定义为：

数组IA的长度为m+1。它由以下递归定义得出：

• IA [0] = 0
• IA [i] = IA [i-1]+（原始矩阵第（i-1）行的非零元素数量）
• 因此，IA的前m个元素存储M每行中第一个非零元素在A中的索引 [ed：但仅适用于至少有一个这样的元素的行，即IA [i +1]> IA [i]] ，并且最后一个元素IA[m]存储NNZ A中元素的数量，也可以视为矩阵M末尾之外的虚拟行的第一个元素在A中的索引。原始矩阵的第i行的值从元素A [IA [i]]到A [IA [i +1] -1]读取（两端都包含），即从一行的开始到下一行的起始索引的上一个索引。

因此，在矩阵1中： row = [0 1 2 3] 在矩阵2中： row = [0 3 3 3] 在矩阵3中： row = [0 0 3 3]

- Arash

Answer 2

提供的答案接近完美解释，但需要稍加澄清:

前两个要点清晰地说明了IA中条目的规定。

但接下来的部分是这样的：

"因此，IA的前m个元素存储了M矩阵每行第一个非零元素在A矩阵中的索引，而最后一个元素IA[m]存储了A矩阵中元素的数量NNZ，也可以看作是超出矩阵M末尾的幻象行的第一个元素在A中的索引。对于原始矩阵的第i行的值从元素A[IA[i]]到A[IA[i+1]-1]（两端都包括）读取，也就是从一行开始到下一行开始之前的最后一个索引。"

这段话很难理解，因为未定义"IA"，“m”，“NNZ”，“M”和“A”的引用。

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

您能否提供 "IA"、"m"、"NNZ"、"M" 和 "A" 的定义，以便完成解释呢？

非常感谢您的帮助！

- jcatanza