稀疏矩阵的填充非常慢，并且本征中没有存储增益 [英] Very slow filling of sparse matrix and no memory gain in Eigen
问题描述
我正在尝试实现本征中给出的示例教程作为伪代码。据我了解，它说明了填充稀疏矩阵的推荐方法，只要知道每列的非零条目数即可。
I am trying to implement an example that is given in the Eigen tutorial as pseudocode. As far as I understand, it illustrates the recommended method for filling a sparse matrix, provided that the number of non zero entries per column is known.
伪代码位于标题 填充稀疏矩阵，其内容如下：
The pseudocode is found under the Header "Filling a sparse Matrix"and is written as follows:
1: SparseMatrix<double> mat(rows,cols); // default is column major
2: mat.reserve(VectorXi::Constant(cols,6));
3: for each i,j such that v_ij != 0
4: mat.insert(i,j) = v_ij; // alternative: mat.coeffRef(i,j) += v_ij;
5: mat.makeCompressed(); // optional
我尝试将其转换为C。我（希望如此）编写了vee（），这样它将在每列中创建2500个非零元素。因此，示例中的2500应该对应于6。我将其设置为3000，以测试make。也将其压缩。
My attempt to transform it into C is found below. I have (hopefully) written vee() such, that it will create 2500 non-zero elements per column. Therefore 2500 should correspond to 6 in the example. I set it to 3000 to test make.Compressed as well.
不幸的是，我不了解该程序的行为。它在几秒钟内完成i = 0 ... 3000，然后停留了几分钟。然后达到6000，并再次卡住几分钟。为什么会这样以及如何获得更好的性能？
Unfortunately, I don't understand the behaviour of the programme. It does i=0...3000 in seconds, then is stuck for minutes. Then it goes to 6000 and is stuck again for minutes. Why is that and how to get better performance?
此外，内存使用情况很奇怪。您会发现，有时Eigen会使用比GSL中相应的密集矩阵所需的内存更多的内存，而且所使用的内存也会剧烈波动。步长大于100MB
Furthermore, the memory usage is very strange. You can see that at times toward the end Eigen uses significantly more memory than needed for the corresponding dense matrix in GSL.The memory used also fluctuates wildly. in steps bigger than 100MB
我这样编译并运行：
ludi @ ludi-M17xR4：〜/台式机/测试$ g ++ -o eigenfill.x eigenfill.cc -L / usr / local / lib -lgsl -lgslcblas&& ./eigenfill.x
ludi@ludi-M17xR4:~/Desktop/tests$ g++ -o eigenfill.x eigenfill.cc -L/usr/local/lib -lgsl -lgslcblas && ./eigenfill.x
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <Eigen/Sparse>
#include <gsl/gsl_matrix.h>
#define rows 1e4
#define cols 1e4
/*-- DECLARATIONES --*/
int FillMatrix(Eigen::SparseMatrix<double> mat);
double vee(int i, int j);
int main()
{
printf("---> Watch gsl matrix memory usage!\n");
gsl_matrix *testmat = gsl_matrix_calloc(rows, cols);
sleep(20);
gsl_matrix_free(testmat);
printf("---> Watch eigen matrix memory usage!\n");
Eigen::SparseMatrix<double> mat(rows,cols); // default is column major
FillMatrix(mat);
printf("------------------------DONE");
return(0);
}
/*-- --*/
int FillMatrix(Eigen::SparseMatrix<double> mat)
{
int i, j;
Eigen::VectorXd Vres;
mat.reserve(Eigen::VectorXi::Constant(cols,3000));
for(i=0;i<rows;i++)
{
if(i%500==0){printf("i= %i\n", i);}
for(j=0;j<cols;j++)
{
if (vee(i,j) != 0){mat.insert(i,j) = vee(i,j); /*alternative: mat.coeffRef(i,j) += v_ij;*/ }
}
}
printf("--->starting compression");
mat.makeCompressed();
return(0);
}
/*-- --*/
double vee(int i, int j)
{
double result = 0.0;
if(j%4 == 0){result =1.0;}
return result;
}
/*-- --*/
编辑
一个答案提醒我我需要使用地址，因为FillMatrix（）的局部变量在运行时将消失。我尝试了以下无法编译的内容：
One answer reminded me I needed to use addresses, because the local variables of FillMatrix() will be gone when it runs through. I tried the following, which does not compile:
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <Eigen/Sparse>
#include <gsl/gsl_matrix.h>
#define rows 1e4
#define cols 1e4
/*-- DECLARATIONES --*/
int FillMatrix(Eigen::SparseMatrix<double> & mat);
double vee(int i, int j);
int main()
{
printf("---> Watch gsl matrix memory usage!\n");
gsl_matrix *testmat = gsl_matrix_calloc(rows, cols);
sleep(20);
gsl_matrix_free(testmat);
printf("---> Watch eigen matrix memory usage!\n");
Eigen::SparseMatrix<double> mat(rows,cols); // default is column major
FillMatrix(& mat);
printf("------------------------>DONE\n");
return(0);
}
/*-- --*/
int FillMatrix(Eigen::SparseMatrix<double> &mat)
{
int i, j;
Eigen::VectorXd Vres;
mat.reserve(Eigen::VectorXi::Constant(cols,3000));
for(i=0;i<rows;i++)
{
if(i%500==0){printf("i= %i\n", i);}
for(j=0;j<cols;j++)
{
if (vee(i,j) != 0){mat.insert(i,j) = vee(i,j); /*alternative: mat.coeffRef(i,j) += v_ij;*/ }
}
}
printf("--->starting compression\n");
mat.makeCompressed();
return(0);
}
/*-- --*/
double vee(int i, int j)
{
double result = 0.0;
if(i%4 == 0){result =1.0;}
return result;
}
/*-- --*/
错误消息是：
ludi@ludi-M17xR4:~/Desktop/tests$ g++ -o eigenfill.x eigenfill.cc -L/usr/local/lib -lgsl -lgslcblas && ./eigenfill.x
eigenfill.cc: In function ‘int main()’:
eigenfill.cc:24:17: error: invalid initialization of non-const reference of type ‘Eigen::SparseMatrix<double>&’ from an rvalue of type ‘Eigen::SparseMatrix<double>*’
FillMatrix(& mat);
^
eigenfill.cc:12:5: error: in passing argument 1 of ‘int FillMatrix(Eigen::SparseMatrix<double>&)’
int FillMatrix(Eigen::SparseMatrix<double> & mat);
^
ludi@ludi-M17xR
编辑 >
并且如果我写了，它将编译：
EDIT And it compiles if I write:
FillMatrix（mat）;
FillMatrix(mat);
而不是
FillMatrix（& mat）;
FillMatrix(&mat);
我不明白。最后一个难道不正确吗？
I don't understand. Should not the last one be correct?
推荐答案
这是因为您要在四列中填满一列。看起来像这样：
This is because you are entirely filling one column over four. It looks like the following:
1 0 0 0 1 0 0 0 1 ...
1 0 0 0 1 0 0 0 1 ...
1 0 0 0 1 0 0 0 1 ...
1 0 0 0 1 0 0 0 1 ...
...
用<$ c替换 j％4 == 0 $ c> i％4 == 0 就可以了。内存使用情况将完全是： 2500 * cols *（sizeof（double）+ sizeof（int））+ cols * sizeof（int）。
Replacing j%4 == 0 by i%4 == 0 will do the job. The memory usage will be exactly: 2500*cols*(sizeof(double)+sizeof(int)) + cols*sizeof(int).
还必须修复 FillMatrix 的原型，以便填充真实矩阵而不是临时矩阵：
You must also fix the prototype of FillMatrix so that you fill the real matrix and not a temporary:
int FillMatrix(Eigen::SparseMatrix<double> &mat);
最后，如果您的目标是真正使用稀疏矩阵，且其非零值约为1/4，那么密集表示可能会更快。
Finally, if your goal is really to work with sparse matrices having about 1/4 of non zeros, then a dense representation will likely be faster.
这篇关于稀疏矩阵的填充非常慢，并且本征中没有存储增益的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
