erotavlas
October 25th, 2013, 02:11 PM
Hi,
I have to implement in C/C++ a symmetric sparse matrix. I have read of various storage format and the most popular is this one CSR http://netlib.org/linalg/html_templates/node91.html#SECTION00931100000000000000. This method is efficient from the memory requirement perspective, but it is no efficient in my case. In fact, I have three constraints: the first is that the dimensions and the matrix are not known in advance but the matrix is dynamically built, the second is that the elements of the matrix are updated during the computation and finally the matrix-vector and matrix-matrix operations must be efficient.
For the first and second constraint I think that something like this struct{double val; size_t i; size_t j;} vector<struct entry> myMatrix; is not efficient. In fact I have to search over a vector to find the right position for the elements and this require O(n) where n is the size of the vector.
I have thought about two possibilities: the first is to use a vector<map<int, double> > myMatrix; where the vector is row-wise and each map stores only non zero elements in the column. The first and second constraints are easily handled thank to the fast search over a map O(log ci) where ci are the number of non zero elements in the row ri. Also the matrix-vector and matrix-matrix multiplication is fast as in the case of vector<struct entry>. This representation is also more efficient in term of memory with respect to vector<struct entry>, but less with respect to CSR. The second is map<struct entry> myMatrix. This is similar to vector<struct entry> but allows faster searches.
I think that the best is vector<map<int, double> > but I worried about the following fact: in case of symmetric matrix is necessary to store only upper(lower)-triangular part of the matrix. So the first row is full and has n elements, the second row has n-1 elements and the last row has 1 element. In this case the last map has only one element. In the case of symmetric sparse matrix this is also more important.
I cannot use the solution of vector<vector<double> > since that the search is still O(n) even if moving down to the matrix the n decreases up to 1. Another important problem that is practical, instead of theoretical, is the cache coherence. A vector can be contiguously allocated, is it possible with a map? Of course I can use an unordered_map instead of map. The search become constant but the constant can be high. So the game is worth the candle?!
Do you have more clever idea? Any suggestion is welcome.
Thank you
I have to implement in C/C++ a symmetric sparse matrix. I have read of various storage format and the most popular is this one CSR http://netlib.org/linalg/html_templates/node91.html#SECTION00931100000000000000. This method is efficient from the memory requirement perspective, but it is no efficient in my case. In fact, I have three constraints: the first is that the dimensions and the matrix are not known in advance but the matrix is dynamically built, the second is that the elements of the matrix are updated during the computation and finally the matrix-vector and matrix-matrix operations must be efficient.
For the first and second constraint I think that something like this struct{double val; size_t i; size_t j;} vector<struct entry> myMatrix; is not efficient. In fact I have to search over a vector to find the right position for the elements and this require O(n) where n is the size of the vector.
I have thought about two possibilities: the first is to use a vector<map<int, double> > myMatrix; where the vector is row-wise and each map stores only non zero elements in the column. The first and second constraints are easily handled thank to the fast search over a map O(log ci) where ci are the number of non zero elements in the row ri. Also the matrix-vector and matrix-matrix multiplication is fast as in the case of vector<struct entry>. This representation is also more efficient in term of memory with respect to vector<struct entry>, but less with respect to CSR. The second is map<struct entry> myMatrix. This is similar to vector<struct entry> but allows faster searches.
I think that the best is vector<map<int, double> > but I worried about the following fact: in case of symmetric matrix is necessary to store only upper(lower)-triangular part of the matrix. So the first row is full and has n elements, the second row has n-1 elements and the last row has 1 element. In this case the last map has only one element. In the case of symmetric sparse matrix this is also more important.
I cannot use the solution of vector<vector<double> > since that the search is still O(n) even if moving down to the matrix the n decreases up to 1. Another important problem that is practical, instead of theoretical, is the cache coherence. A vector can be contiguously allocated, is it possible with a map? Of course I can use an unordered_map instead of map. The search become constant but the constant can be high. So the game is worth the candle?!
Do you have more clever idea? Any suggestion is welcome.
Thank you