ITKeyword,专注技术干货聚合推荐

注册 | 登录

解决matlab - Is there overhead of accessing elements in a sparse matrix

itPublisher 分享于

2020腾讯云双十一活动,全年最低!!!(领取3500元代金券),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1073

【阿里云】双十一活动,全年抄底价,限时3天!(老用户也有),
入口地址https://www.aliyun.com/1111/home

推荐:matlab-sparse函数和full函数-sparse matrix和full matrix

sparse函数 功能:Create sparse matrix-创建稀疏矩阵 用法1:S=sparse(X)——将矩阵X转化为稀疏矩阵的形式,即矩阵X中任何零元素去除,非零元素及其下标(索引

Let's say I have a sparse matrix A. I want to do heavy calculations on it. The calculations do not modify A, only accessing its elements e.g. take a row of A then multiply with something. I wonder whether I should convert A to a full matrix before doing any calculation, or just do it directly?
In other words, is accessing elements in a sparse matrix slower than a full matrix?

matlab matrix sparse-matrix overhead
|
  this question
edited Oct 14 '14 at 11:35 Stewie Griffin 12.4k 8 22 55 asked Oct 14 '14 at 9:50 Tu Bui 443 1 6 18      If you have enough memory to convert A to full, why do you need sparse at all? –  Luis Mendo Oct 14 '14 at 9:51 1   slicing sparse matrices across columns is much faster than by rows, which is understood given how the data is stored internally –  Amro Oct 14 '14 at 9:58      @Luis: The server which i am working on has enough memory for it, but other users are using it as well so I think it would be nicer to use as less resource as possible. Also I did save that matrix (in sparse mode) into a mat file (it does save me some space). Now I load it back and wonder should I convert it to a full matrix. –  Tu Bui Oct 14 '14 at 9:58      @Amro +1: this is interesting. I just found the similar info in this link: mathengineering.com/understanding-sparse-matrix-storage –  Tu Bui Oct 14 '14 at 10:05 1   You might find this question and this answer, including the linked reference interesting. –  Stewie Griffin Oct 14 '14 at 11:28

 | 

1 Answers
1

解决方法

Slicing sparse matrices across columns is much faster than slicing across rows in MATLAB. So you should prefer accessing M(:,i) over M(i,:).

Internally MATLAB uses the Compressed Sparse Column (CSC) storage:

  • the non-zero elements are stored in a 1-D double array of length nzmax arranged in column-major order (pr for real part and pi for imaginary part if matrix is complex)
  • ir an array of integers with corresponding row indices
  • jc an integer array of length n+1 (where n is the number of columns) containing column index information. By definition, the last value of jc contains nnz (number of non-zeros stored).

As an example, take the following sparse matrix:

>> M = sparse([1 3 5 3 4 1 5], [1 1 1 2 2 4 4], [1 7 5 3 4 2 6], 5, 4);

This is what it looks like stored in memory (I'm using 0-based indices for ir and jc):

1 . . 2
. . . .
7 3 . .
. 4 . .
5 . . 6

pr = 1 7 5 3 4 2 6
ir = 0 2 4 2 3 0 4
jc = 0 3 5 5 7

nzmax = at least 7
nnz = 7
m = 5
n = 4

To retrieve the i-th column of the sparse matrix M(:,i), it suffices to do: pr(jc(i):jc(i+1)-1) (to keep it simple, I'm not paying attention to 0- vs 1-based indexing). On the other hand, accessing a matrix row involves more calculations and array traversals (it is no longer spatial-locality friendly).

Here are some links to the MATLAB documentation for more info: Sparse Matrices, Manipulating Sparse Matrices

It's worth checking out the original paper by John R. Gilbert, Cleve Moler, and Robert Schreiber: "Sparse Matrices In Matlab: Design and Implementation", (SIAM Journal on Matrix Analysis and Applications , 13:1, 333–356 (1992)).

Here are some quotes from the above paper to answer your question about the overhead of sparse storage:

The computational complexity of simple array operations should be proportional to nnz, and perhaps also depend linearly on m or n, but be independent of the product m*n. The complexity of more complicated operations involves such factors as ordering and fill-in, but an objective of a good sparse matrix algorithm should be:

推荐:solve stiffness matrix in matlab

note: this passage serves for the analysis of Alec Jacobson’s thesis 1.what’s stiffness matrix According to (2.16), stiffness matrix is given by: Li

The time required for a sparse matrix operation should be proportional to number of arithmetic operations on nonzero quantities.

We call this the "time is proportional to flops" rule; it is a fundamental tenet of our design.

and

This (column-oriented sparse matrix) scheme is not efficient for manipulating matrices on element at a time: access to a single element takes time at least proportional to the logarithm of the length of its column; inserting or removing a nonzero may require extensive data movement. However, element-by-element manipulation is rare in MATLAB (and is expensive even in full MATLAB). Its most common application would be to create a sparse matrix, but this is more efficiently done by building a list [i,j,s] of matrix elements in arbitrary order and then using sparse(i,j,s) to create the matrix.

The sparse data structure is allowed to have unused elements after the end of the last column of the matrix. Thus an algorithm that builds up a matrix one column at a time can be implemented efficiently by allocating enough space for all the expected nonzeros at the outset.

Also section 3.1.4 "asymptotic complexity analysis" should be of interest (it's too long to quote here).


|
  this answer
edited Oct 15 '14 at 7:45 answered Oct 14 '14 at 10:16 Amro 105k 19 171 314      although it does not answer my question (my question is to compare sparse matrix vs full matrix in term of retrieving elements), I am happy with this one. –  Tu Bui Oct 14 '14 at 10:56      To follow on from Amro's answer - if it really is rows you want from the sparse matrix - transpose it and extract columns from the transposed form. Or better still - use the profiler to see what's actually going on! –  Edric Oct 14 '14 at 22:02

 | 

推荐:matlab中的sparse和full以及ground truth matrix

sparse和full的用法都不止一种,我说下目前我用到的,看doc总是觉得不怎么明白: M = sparse(r, c, v) 得到的是一个稀疏矩阵M,用r(i)代表r中的第i个元素,c(i)


相关阅读排行


相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。