使用 C 计算稀疏矩阵每一列的总和

Question

我有一个大小为 (8 x 8) 的矩阵，如下所示，我必须将其转换为一种稀疏矩阵形式，并使用 C 语言计算每一列的非零元素之和。

 Matrix =   [1 2 0 4 0 0 0 0;
             0 1 3 0 2 0 0 0;
             1 0 4 7 0 0 0 0;
             0 6 0 0 1 8 0 0;
             0 0 0 0 4 0 0 0;
             0 0 0 0 8 1 1 0;
             0 0 0 0 9 0 2 0;
             0 0 0 0 0 0 7 1]

有人可以建议如何处理这个问题吗？请注意，这是一个样本矩阵，实际上我有大约（15,000 行 x 25,000 列）

的巨大维度矩阵

Answer 1

Could someone please advise on how to proceed on this problem?

你创建了一个列表来存储矩阵的非零元素。为此，您需要一个结构来定义此类列表的元素的外观：

struct sparseElement{
    int n;
    int m;
    int value;
}

然后通过循环遍历矩阵，计算非零元素，将矩阵转换为这种稀疏形式。既然知道有多少，就可以分配内存了：

sparseElement* sparse = malloc(n * sizeof(sparseElement))

其中 n 是非零元素的数量。然后就可以填写列表了。

compute the sum of non-zero elements for each column using C language.

您遍历列表并对列索引等于您为其计算总和的行的所有元素求和。如果您想一次性对所有列执行此操作，您可以制作一个列表，每列一个条目，然后将每个元素添加到相应的索引中。

当然，这只是一种可能的实现方式。大型、成熟的图书馆使用更精细和高效的 structures/algorithms.

Answer 2

Could someone please advise on how to proceed on this problem?

找出稀疏矩阵上的所有必需和可选操作。

许多操作需要按行或按列访问数据。一些操作（如高效的朴素矩阵乘法）需要两者；特定的取决于矩阵在乘法运算符的哪一侧。一些操作受益于简单的转置。收集操作并根据它们的要求对它们进行排序，为您提供了可用于选择 "best"（最接近您的用例的最佳）实施的标准。
选择合适的类型来描述矩阵中的值。

特别是，我建议考虑 float、double、unsigned char、signed char、uintN_t 和 intN_t 类型（对于 N = 8、16、32 或 64）。

您需要精度和范围来描述您拥有的值，而不是为了您不需要的精度或范围而浪费内存。
选择您将用于实现稀疏矩阵的数据结构。

sparse matrix 上的维基百科文章描述了一些典型的结构（DOK、LIL、COO、CSR、CSC、Yale）。如果您实现多个，则不仅需要为每个编写所有低级操作，还需要为算术运算编写所有组合。（例如，如果您的稀疏矩阵使用压缩稀疏行 (CSR) 或压缩稀疏列 (CSC) 格式，那么根据两个参数矩阵的类型（CSR×CSR， CSC×CSR, CSR×CSC, CSC×CSC), 因为矩阵乘法不可交换。)

如果性能很重要，则应仔细考虑各种数据结构的缓存效果。您需要在一个或多个数组中按顺序检查内存，以利用 CPU 预取和缓存。如果有大量数据，您将希望 "pack" 一切都尽可能紧凑（因为内存带宽往往是矩阵运算的限制瓶颈），但将处理每个矩阵元素所需的运算保持在最低限度.
编写基本矩阵 input/output 例程和单元测试以检查您的数据结构是否正常工作。

通常，您需要读取和写入这些矩阵 from/to 文件或流（如标准输入和输出）。先写这些。然后，编写一些描述矩阵数据存储方式的调试函数。至少，您需要编写一个测试程序来读取矩阵（从标准输入）、打印它（到标准输出）和存储格式（到标准错误）；您可以为它提供一些测试用例输入（至少一个带有随机数据）以查看往返是否保留了正确的数据。我经常使用 awk 来生成测试数据集，并将数值输出与预期的数值输出进行比较。
写一个给定稀疏矩阵M，returns一个行向量v的函数，其中v_i = ∑M_j,i

也就是说v中的元素i是M[=68=所有元素的和] 在列 i.

为你的功能编写一个测试程序，并进行测试。

通常，您会希望程序读取矩阵（从标准输入），并将向量写入标准输出。

使用 C 计算稀疏矩阵每一列的总和

Calculate the sum of each column of a sparse matrix using C

c

sparse-matrix