Critical matrix sparsity

6 messages
Open this post in threaded view
|

Critical matrix sparsity

 Hello People, If I have a two-dimensional matrix with double elements. Is there a sparsity threshold which let me know if it is convenient to save such matrix as sparse or as dense? Is there any general formula to compute this decision? Thanks
Open this post in threaded view
|

Re: Critical matrix sparsity

 dariodematties wrote Hello People, If I have a two-dimensional matrix with double elements. Is there a sparsity threshold which let me know if it is convenient to save such matrix as sparse or as dense? Is there any general formula to compute this decision? Thanks For me there is no "golden rule" to use sparse matrices. If you know your matrices are really sparse you definitely should work with them. Otherwise I would consider the following things: 1. Do I face memory limitations? a) A dense m*n-matrix requires about  m*n*sizeof(double) Bytes of memory [1] b) A sparse m*n* matrix about [(n+1) + nnz(matrix)]*sizeof(int) + nnz(matrix)*sizeof(double) Bytes of memory [2,3] => So the number of nonzero matrix entries should at least be below 50%. If your matrix is really sparse, then the number of columns n should be smaller than the number of rows m (transpose if not). Otherwise you waste space for storing zero columns. 2. Do I often extract parts of the matrix or insert elements? Randomly extracting or adding parts of a sparse matrix might be a real performance killer! If you only intent to call system functions on the sparse matrices (like factorizations or solving systems of equations, which are optimized for those data structures) you'll face the desired effect. Otherwise you wisely have to profile your code to detect operations that slow down the calculation by improper memory access. HTH, Kai [1]: sizeof(double) usually 8 Byte [2]: nnz(matrix) is the number of nonzero matrix elements, sizeof(int) usually 4 or 8 Byte [3]: Read more at https://arxiv.org/abs/cs/0604006
Open this post in threaded view
|

Re: Critical matrix sparsity

 Thanks siko1056, Up to now, my concern is about taking the decision of whether to save the matrix in sparse or dense format (in hard disk). I am working with dense matrices in my code. Yet, ram memory shortages can come soon, then I think all your advises are very handy. Thank you very much, Dario
Open this post in threaded view
|

Re: Critical matrix sparsity

 In reply to this post by siko1056 On Jun 8, 2017 5:52 PM, "siko1056" <[hidden email]> wrote:dariodematties wrote If your matrix is really sparse, then the number of columns n should be smaller than the number of rows m (transpose if not). Otherwise you waste space for storing zero columns.Maybe a naive side question, but wouldn't it make sense to have the transposition automatic and transparent as part of the storage class? A "transposed?" flag and the check would be the only overhead. _______________________________________________ Help-octave mailing list [hidden email] https://lists.gnu.org/mailman/listinfo/help-octave