Eigen中的SparseMatrix构造

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中构建稀疏矩阵同时仍能多次更新其系数的最有效方法是什么？

谢谢

[编辑:示例用例:10x10矩阵,10个非零.为简单起见,矩阵是对角的]

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运算符()慢几个数量级(对于更大的矩阵和当然更真实的设置).

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

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

如果你可以轻松计算稀疏模式,那么另一种方法是填充一个唯一三元组的向量,其值为0,然后coeffRef将很快.