4

我想测试一些较新的稀疏线性求解器，我想知道是否有一种快速填充矩阵的方法。我感兴趣的格式是 CSR (http://goo.gl/hLXYd)。假设 CSR 格式的矩阵由下式给出：

values(num non-zero elements)
columns(num non-zero elements)
rowIndex(num rows + 1)

所考虑的稀疏矩阵来自网络。所以，我有数千个节点，其中一些节点通过线连接。因此，矩阵在结构上是对称的。每个连接 (i,j) 向对角项 (i,i) 和 (j,j) 以及非对角项 (i,j) 和 (j,i) 添加一些内容。我可以在相同的节点 (i,j,1)、(i,j,2) 之间有多个连接...因此，我可能需要多次重新访问 2 个对角线和 2 个非对角线元素。

我知道我可以通过执行 rowIndex(i) 来获得行的开头。然后，我必须遍历元素 columns(rowIndex(i):rowIndex(i+1)-1) 才能找到 j 的位置。

问题：

有没有一种方法可以在 CSR 格式中更快地访问元素，而无需每次我想更新元素时​​都进行搜索？

一些澄清：我只需要从头开始填写矩阵。矩阵在结构上是对称的，并不是真正对称的。保存的值与网络数据（阻抗、电阻等）有关，它们具有真实值。一般来说，价值（i，j）<>价值（j，i）。我有 (name1,i1,j1,value1), (name2,i2,j2,value2) 等形式的元组。这些元组没有排序，2 个元组可以引用相同的 i,j 值，这意味着它们需要被添加

提前致谢！

4

2 回答 2

2

你所拥有的是所谓的三元组稀疏格式。CRS的创建，包括删除重复条目和对值求和，可以非常有效地实现。在自己编程之前，请查看SuiteSparse 库。它是用 C 编写的，但我相信你会理解其中的原理。您感兴趣的是cholmod_triplet.c文件，它实现了您需要的功能。

本质上，转换是在行和列索引上使用两阶段桶排序执行的。该算法具有线性复杂性，如果您对处理大型数据集感兴趣，这一点很重要。

编辑如果要一起跳过显式创建三元组格式，可以通过动态生成(row, col)连接并将它们添加到动态稀疏结构来实现。我通常使用插入排序和排序列表来做到这一点，这实际上是最快的。它也比三元组到 CRS 的转换更快，并且使用更少的内存。方法如下：

  • 如果您大约知道，每行中有多少个非零条目，对于每一行，您预先分配一个（空）列索引数组，以及一个单独的值数组（不是链表，而是一个简单的数组）那个大小。就像是

    static_lists_cols[row] = malloc(sizeof(int)*expected_number_of_non_zeros) static_lists_vals[row] = malloc(sizeof(double)*expected_number_of_non_zeros)

  • 如果您不知道这一点，您可以选择一个初始大小并在行列表已满时根据需要重新分配（使用一些足够大的块大小以避免重新分配开销）。

  • 对于每一(row, col)对，您将 插入到与使用插入排序col相对应的排序列表中。row对于每行小的（最多几百个）非零，线性搜索是最快的。对于每行更多的非零，您可以使用二分法来定位插入col索引的正确位置。
  • colrow通过在排序列表中移动具有较高列索引的非零条目来将其插入到排序列表中。这是缓存友好的，因为实际上这些行足够小，可以放入现在的任何缓存中。
  • 完成后，您需要通过将各个行列表复制到最终的columns. 价值观也是一样。
  • 如果您确定某些行可以有零条目，您实际上可以通过预先分配一个静态的“列表数组”来避免最后一步。因此，每行的条目数是恒定的，其中一些可能为零。有时这没关系。

这种方法比使用三元组到稀疏转换要快，至少对于我使用它的 FEM 模型来说是这样。一般的原因是内存带宽是这里的瓶颈，而上面的方案使用的内存要少得多：

  • 创建三元组格式需要时间，您需要将三元组写入内存
  • 转换为 CRS 需要至少一次读取和写入三元组以对它们进行排序（实际上不止一次，如果您查看算法。您排序两次，并且您需要辅助数据结构。）
  • 根据连接结构的不同，您最终可能会获得大量(row, col)三元组格式的重复项，这些重复项在组装过程中通过添加相应的值来删除。上述方法中不存在此开销 - 如果col行列表中已存在，则只需更新相应的值。
  • 如果您将行范围分配给各个工作人员，则可以并行更新排序列表。不需要通信，也不需要同步。确保负载平衡是另一回事......

看看使用这两种方法（图 1）对 2D 中的三角形元素进行的性能比较。请注意，性能差异取决于三元组中的条目数与组装稀疏矩阵格式的比率（表 2）。但总的来说，该方法永远不会比三元组到crs的转换差，并且需要首先创建三元组。您还可以下载一个 MATLAB MEX 函数sparse_create，它是mutils包的一部分（请参阅下载部分）。

于 2012-10-23T12:04:53.373 回答
1

您的问题似乎混淆了 2 个完全不同的问题：

  1. 以 CSR 形式创建矩阵的快速方法是什么？
  2. 有没有更快的方法从已经以 CSR 形式存储的矩阵中读取值？（比您描述的直接方法更快）

所以这里有2个答案：

  1. 一般来说，将网络数据从它的任何形式读取到诸如键字典之类的东西中（其他中间形式可用，并且由于速度或其他原因可能对您更有吸引力）；然后将该中间结构转换为矩阵的 CSR 形式。更多关于这下面。
  2. 我不相信，不是以 CSR 形式存储的矩阵。这种相对较慢的访问速度是您为节省空间付出的代价的一部分。你已经用时间换空间，或者用空间换时间，这取决于你的观点。

您对输入数据的描述表明您应该考虑设计自己的中间形式来编组原始数据。由于您的邻接矩阵是对称的，您只需要以任何形式存储它的一半。此外，您可能不需要沿主对角线存储元素——我猜该节点要么i总是连接到节点i，要么永远不会，因此网络的性质决定了存储在(i,i). 我有点不确定要在矩阵的每个节点上存储的信息，是iand之间的连接数j还是其他？

于 2012-10-23T09:27:26.013 回答