¿La velocidad de llenar la matriz escasa en Eigen depende de la cantidad de nodos o bordes? -- ++ campo con arrays campo con sparse-matrix campo con eigen camp Relacionados El problema

The speed of filling sparse matrix in Eigen depends on number of nodes or edges?


1
vote

problema

Español

Llené los bordes de dos redes.

uno es de aproximadamente 4000 nodos y 80000 bordes.

Otro sobre los nodos 80000 y 1300000 bordes.

El código está escrito como a continuación:

  SparseMatrix<int,Eigen::RowMajor> mat(nodenumber,nodenumber); //nodenumber is 4000 or 80000 mat.reserve(VectorXi::Constant(nodenumber,50)); //preserve 50 non-nero elements for (i,j) in edges:     mat.insert(i,j) = 1;     mat.insert(j,i) = 1; }   

(4000 nodos, 80000 bordes) se realiza con 1,5 seg.

(80000 nodos, 1300000 bordes) se realiza con 600 seg.

Pero creo que la velocidad de la matriz de llenado debe depender de los bordes.

que debe ser 1.5 * 1300000/80000 para (80000 nodos, 1300000 bordes) red.

¿Estoy en lo correcto o equivocado?

¿Cómo puedo mejorar la velocidad de llenar la matriz?

¡Gracias!

Original en ingles

I filled edges of two network.

One is about 4000 nodes and 80000 edges.

Another one about is 80000 nodes and 1300000 edges.

The code is written like below:

SparseMatrix<int,Eigen::RowMajor> mat(nodenumber,nodenumber); //nodenumber is 4000 or 80000 mat.reserve(VectorXi::Constant(nodenumber,50)); //preserve 50 non-nero elements for (i,j) in edges:     mat.insert(i,j) = 1;     mat.insert(j,i) = 1; } 

(4000 nodes,80000 edges) is done with 1.5 sec.

(80000 nodes,1300000 edges) is done with 600 sec.

But I think the speed of filling matrix should depend on edges.

That should be 1.5*1300000/80000 for (80000 nodes,1300000 edges) network.

Am I right or wrong?

How can I improve the speed of filling the matrix?

Thanks!

           
 
 

Lista de respuestas

1
 
vote
vote
La mejor respuesta
 

Vea esta línea: mat.reserve(VectorXi::Constant(nodenumber,50)); y este punto de la Documentación de Eigen en la matriz escasa :

Tenga en cuenta que al llamar a la reserva (), no se requiere que NNZ sea el número exacto de elementos distintos de cero en la matriz final. Sin embargo, una estimación exacta evitará múltiples reasignaciones durante la fase de inserción.

Por lo tanto, Considere cambiar 50 por algo más grande que el número de bordes para reducir la asignación repetida. Sin embargo, solo reducirá ligeramente el tiempo del reloj de pared, como se detalla en la sección Llenando una matriz escasa

Debido al esquema de almacenamiento especial de un SPARSEMATRIX, se debe tener especial cuidado al agregar nuevas entradas no cero. Por ejemplo, El costo de una inserción única puramente aleatoria en un SPARSEMATRIX es O (NNZ), donde NNZ es el número actual de coeficientes no cero.

Como consecuencia, llenar toda la matriz por inserciones aleatorias es O (nnz ^ 2/2). De hecho, si calcula 80000 ^ 2 y 1300000 ^ 2, la relación no estará demasiado lejos de 1.5 / 600, estas cifras son los tiempos de ejecución que informó.

Para ganar algún tiempo, puede estar interesado en inserción por lotes , que está insertando todos los bordes a la vez. Lea esta parte de la documentación de Eigen: ¡Realmente lo vale la pena! De hecho, la pieza de código proporcionada en esta página web probablemente lo ayudará.

  typedef Eigen::Triplet<double> T; std::vector<T> tripletList; tripletList.reserve(nnz); for(...) {     // ...     tripletList.push_back(T(i,j,v_ij)); } SparseMatrixType mat(rows,cols); mat.setFromTriplets(tripletList.begin(), tripletList.end());   

Como alternativa, también puede reservar espacio de almacenamiento para cada columna, si conoce el número máximo de elementos no nulos por columna y si no es demasiado grande:

  mat.reserve(VectorXi::Constant(cols,6));   
 

See this line: mat.reserve(VectorXi::Constant(nodenumber,50)); and this point of the documentation of Eigen on sparse matrix:

Note that when calling reserve(), it is not required that nnz is the exact number of nonzero elements in the final matrix. However, an exact estimation will avoid multiple reallocations during the insertion phase.

Hence, consider changing 50 by something larger than the number of edges so as to reduce repeated allocation. Nevertheless, it will only slightly reduce wall clock time, as detailed in the section Filling a sparse matrix

Because of the special storage scheme of a SparseMatrix, special care has to be taken when adding new nonzero entries. For instance, the cost of a single purely random insertion into a SparseMatrix is O(nnz), where nnz is the current number of non-zero coefficients.

As a consequence, filling the whole matrix by random insertions is O(nnz^2/2). Indeed, if you compute 80000^2 and 1300000^2, the ratio will not be too far from 1.5/600, these figures being the execution times you reported.

To gain some time, you may be interested in batch insertion, that is inserting all edges at once. Read this part of the documentation of Eigen: it really worths it! Indeed, the piece of code provided on this webpage will likely help you.

typedef Eigen::Triplet<double> T; std::vector<T> tripletList; tripletList.reserve(nnz); for(...) {     // ...     tripletList.push_back(T(i,j,v_ij)); } SparseMatrixType mat(rows,cols); mat.setFromTriplets(tripletList.begin(), tripletList.end()); 

As an alternative, you can also reserve storage space for each column, if you know the maximum number of non-null elements per column and if it is not too big:

mat.reserve(VectorXi::Constant(cols,6)); 
 
 
 
 

Relacionados problema

6  Multiplicación de matriz de elementos: R contra RCPP (¿Cómo acelerar este código?)  ( Elementwise matrix multiplication r versus rcpp how to speed this code up ) 
Soy nuevo en C++ Programación (usando Rcpp para una integración perfecta en R ), y apreciaría algunos consejos sobre cómo acelerar algunos cálculos. Co...

1  ¿Cómo calcular SVD utilizando CIMG (o tal vez OPENCV o Biblioteca Eigen)?  ( How to compute svd using cimg or maybe opencv or eigen library ) 
¿Puede alguien darme una guía rápida sobre cómo usar CIMG para calcular SVD para una matriz de 3 dimensiones? Solo quiero obtener la descomposición de la matr...

59  Convierta la matriz Eigen a C Array  ( Convert eigen matrix to c array ) 
The La biblioteca de Eigen puede asignar la memoria existente en MATRICES EIGEN. float array[3]; Map<Vector3f>(array, 3).fill(10); int data[4] = 1, 2, 3,...

4  ¿Cómo devolveré un Eigen :: Matrix de un método, de modo que no copie los datos al regresar  ( How do i return a eigenmatrix from a method such it do not copy the data when ) 
Tengo: Eigen::MatrixXf load_from_gpu() { Eigen::MatrixXf mat(m_rows,m_cols); clEnqueueReadBuffer(m_manager->m_gpu_queue_loader, m_buffer, CL_TRUE, ...

8  Implementación de una función de densidad de probabilidad gaussiana multivariable para> 2 dimensiones en C ++  ( Implementing a multivariate gaussian probability density function for 2 dimensi ) 
Estoy trabajando en la implementación de una función de densidad de probabilidad de un gaussiano multivariado en C ++, y estoy atascado en cómo manejar mejor ...

1  Multiplicando las escasas sub-matrices en Eigen  ( Multiplying sparse sub matrices in eigen ) 
Estoy tratando de multiplicar sub-matrices como bloques, columnas y filas de Eigen :: SPARSEMATRIX. Sin embargo, cada vez que se involucran múltiples sub-matr...

4  Agregue la fila y la columna en la posición cero en Matrix Eigen  ( Add row and column at zero position in matrix eigen ) 
Tengo la matriz por ejemplo: C (400,400) y me gustaría hacer crecer esta matriz con un vector: fila y columna de esta matriz en el índice de inicio 0 de la ...

17  Resolviendo grandes sistemas lineales con matrices escasas de bloques  ( Solving large linear systems with block sparse matrices ) 
Quiero resolver Ax = b DONDE A es una matriz de bloques simétricos definitiva positiva muy grande y x y b son vectores. Cuando digo grande, quiero dec...

0  ¿Se beneficia con Cholesky de Eigen de MP?  ( Does eigens cholesky benefit from mp ) 
Me pregunto si el uso de múltiples hilos (usando FOPENMP) aceleraría la descomposición de Cholesky de Eigen https://eigen.tuxfamily.org/dox/classeigen_1_1l...

1  Extendiendo Eigen con Cwisenularyop: no se puede reproducir Ejemplo  ( Extending eigen with cwisenullaryop cannot reproduce example ) 
Estoy tratando de reproducir el segundo ejemplo en esta página de la documentación de Eigen , pero no puede compilar mi programa mínimo. Estoy usando Eigen ...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos