秩亏矩阵的压缩列格式示例

Question

这是我第一次处理列压缩存储（CCS）格式来存储矩阵。谷歌搜索了一下，如果我是对的，在一个有 n 个非零元素的矩阵中，CCS 如下：

-we define a vector A_v of dimensions n x 1 storing the n non-zero elements 
 of the matrix

- we define a second vector A_ir of dimensions n x 1 storing the rows of the 
  non-zero elements of the matrix

-we finally define a third vector A_jc whose elements are the indices of the 
 elements of A_v which corresponds to the beginning of new column, plus a 
 final value which is by convention equal t0 n+1, and identifies the end of 
 the matrix (pointing theoretically to a virtual extra-column).

例如，如果

M = [1 0 4 0 0;
     0 3 5 2 0;
     2 0 0 4 6;
     0 0 7 0 8]

我们得到

A_v = [1 2 3 4 5 7 2 4 6 8];

A_ir = [1 3 2 1 2 4 2 3 3 4];

A_jc = [1 3 4 7 9 11];

我的问题是

我）是我写的对，还是我理解错了什么？

II) 如果我想用一些列为零的矩阵来表示怎么办，例如

   M2 = [0 1 0 0 4 0 0; 
         0 0 3 0 5 2 0;
         0 2 0 0 0 4 6;
         0 0 0 0 7 0 8]

M2在CCS中的表示不会和M一样吗？

感谢您的帮助！

Answer 1

I) is what I wrote correct, or I misunderstood anything?

你完全正确。但是，您必须注意，如果您使用 C 或 C++ 库，偏移量和索引 应该从 0 开始。在这里，我猜你读了一些索引从 1 开始的 Fortran 文档。要清楚，这里是 C 版本，它只是翻译了你的 Fortran 风格正确答案的索引:

A_v  = unmodified

A_ir = [0 2 1 0 1 3 1 2 2 4] (in short [1 3 2 1 2 4 2 3 3 4] - 1)

A_jc = [0 2 3 6 8 10] (in short [1 3 4 7 9 11] - 1)

II) what if I want to represent a matri with some columns which are zeroes, e.g., M2 = [0 1 0 0 4 0 0; 0 0 3 0 5 2 0; 0 2 0 0 0 4 6; 0 0 0 0 7 0 8]

wouldn't the representation of M2 in CCS be identical to the one of M?

我有一个空列，只需在偏移量 table A_jc 中添加一个新条目即可。由于此列不包含任何元素，因此此新条目值只是前一个条目的值。例如对于 M2（索引从 0 开始）你有：

A_v  = unmodified
A_ir = unmodified
A_jc = [0 0 2 3 6 8 10]   (to be compared to [0 2 3 6 8 10])

因此这两种表示是不同的。

如果您刚开始学习稀疏矩阵，这里有一本很棒的免费书籍：http://www-users.cs.umn.edu/~saad/IterMethBook_2ndEd.pdf

秩亏矩阵的压缩列格式示例

Example of compress column format for rank-deficient matrices

matrix

sparse-matrix

suitesparse