解决matlab  Is there overhead of accessing elements in a sparse matrix
2020腾讯云双十一活动，全年最低！！！（领取3500元代金券），
地址：https://cloud.tencent.com/act/cps/redirect?redirect=1073
【阿里云】双十一活动，全年抄底价，限时3天！(老用户也有)，
入口地址：https://www.aliyun.com/1111/home
推荐：matlabsparse函数和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?

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/understandingsparsematrixstorage –
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 nonzero elements are stored in a 1D double array of length
nzmax
arranged in columnmajor order (pr
for real part andpi
for imaginary part if matrix is complex) ir
an array of integers with corresponding row indicesjc
an integer array of lengthn+1
(wheren
is the number of columns) containing column index information. By definition, the last value ofjc
containsnnz
(number of nonzeros 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 0based 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 ith 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 1based indexing). On the other hand, accessing a matrix row involves more calculations and array traversals (it is no longer spatiallocality 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 onm
orn
, but be independent of the productm*n
. The complexity of more complicated operations involves such factors as ordering and fillin, 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 (columnoriented 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, elementbyelement 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 usingsparse(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)
相关阅读排行
 1白话NMF（Nonnegative Matrix Factorization）——Matlab 实现
 2matlabsparse函数和full函数sparse matrix和full matrix
 3matlab Error using ==> mtimes Inner matrix dimensions must agree.
 4matlab matrix的可视化 彩色矩阵 imagesec
 5matlab 计算大型距离方阵，distance matrix