c++ - Eigen 中的稀疏矩阵构造

Question

我正在构建一个具有多个(软)约束的稀疏线性系统。我正在将一些用于使用 boost::ublas 构建矩阵的代码转换为 Eigen。 boost:ublas 有一种方便的方法来创建具有已知(或估计)数量的非零值的稀疏矩阵，并且具有相当快的运算符(int row，int col)来更新其元素。

问题如下:

• 使用 SparseMatrix::setFromTriplets:
  我的系统有很多限制。作为一个天真的、“稍微”夸大的例子，假设我有一个 100x100 的稀疏矩阵，具有 500 nnz 但有 10 亿个冗余约束(即，非零系数被修改了十亿次)。 setFromTriplets 要求我存储 10 亿个系数，其中大部分将被加起来形成我的 500 个非零系数集。这不是很有效，也不利于内存。当然，我可以用 std::map 替换我的 std::vector，并手动执行约束的累积，但这不知何故错过了拥有稀疏矩阵类的要点，而且效率也不高。

• 使用 SparseMatrix::insert(i,j,val):
  如果元素已经存在则不起作用。我的问题是能够累加已经存在的系数。

• 使用 SparseMatrix::coeffRef(i, j):
  那确实有效，并且将是我正在寻找的功能。然而，它比 boost::ublas 慢了几个数量级。我很惊讶我没有看到更好的功能。我认为这是由于事先不知道非零的数量，并强制进行多次重新分配(这在实践中会发生)。但是，使用 SparseMatrix::reserve() 没有任何效果，因为它是一个仅适用于压缩矩阵的函数(源代码中的注释在断言之前说““此函数在非压缩模式下没有意义”)。 .. 并且，正如文档所说，“将新元素插入 SparseMatrix 之后会将其转换为未压缩模式”。

在 Eigen 中构建稀疏矩阵同时仍能够多次更新其系数的最有效方法是什么？

谢谢

[编辑:示例用例:具有 10 个非零值的 10x10 矩阵。为简单起见，矩阵是对角线]

SparseMatrix<double> mat(10, 10);
for (int i=0; i<10; i++) {
  for (int j=0; j<1000000; j++) {
    mat.coeffRef(i, i) += rand()%10;
  }
}

=> 有效，但比 ublas operator() 慢几个数量级(当然对于更大的矩阵和更现实的设置)。

std::vector<Eigen::Triplet<double> > triplets(10000000);
int k=0;
for (int i=0; i<10; i++) {
  for (int j=0; j<1000000; j++) {
    triplets[k++] = Eigen::Triplet<double>(i,i,rand()%10);
  }
}
SparseMatrix<double> mat(10, 10);
mat.setFromTriplets(triplets.begin(), triplets.end());

=> 内存不友好...

Answer 1

要使 coeffRef 的insert 高效，您需要使用 mat.reserve(nnz) 保留足够的空间，其中 nnz 是一个 Eigen::VectorXi 包含每列的非零的估计数量。最好稍微高估这些数字以避免大量重新分配/复制。另一个补充技巧是确保您第一次访问元素 (i,j) 时，该元素是 j 列的最后一个。

如果您可以轻松计算稀疏模式，那么另一种方法是用 0 作为值填充唯一三元组的 vector ，然后 coeffRef 会很快。