matlab稀疏矩陣使用的是什麼數據結構？

01-07

我在用matlab做一個圖像處理程序時需要求解個稀疏矩陣的方程，在建立稀疏矩陣的時候我發現如果先聲明矩陣規模，比如a=sparse(10e5,10e5);再用索引賦值的方式（a（1,2）=1這種）效率會非常低（matlab也提示我了），如果按照他的提示把橫縱坐標的索引以及非零元數值存成三個一維向量，效率就會提高很多，於是我很好奇的就是matlab是用什麼數據結構存儲的稀疏矩陣，如果是用像Eigen里那種三元組的存儲應該不會出現這樣的問題啊？望大牛解答

無論是Matlab、SuiteSparse，還是CSparse，他們的稀疏矩陣的數據結構實現都是相同的。

/* --- primary CSparse routines and data structures ------------------------- */ typedef struct cs_sparse /* matrix in compressed-column or triplet form */ { csi nzmax ; /* maximum number of entries */ csi m ; /* number of rows */ csi n ; /* number of columns */ csi *p ; /* column pointers (size n+1) or col indices (size nzmax) */ csi *i ; /* row indices, size nzmax */ double *x ; /* numerical values, size nzmax */ csi nz ; /* # of entries in triplet matrix, -1 for compressed-col */ } cs ;

簡單解釋一下，就是存儲row和column的行數，然後有三個malloc出來的空間，其中p是每個column的有效起始元素的序號，i是對應的每個column對應的有效row的序號，x存儲的是每個i指向的元素的值。其中p的長度是n+1，而i和x的長度都是nz。

舉個例子，稀疏矩陣如下：

1，2，0，0；

7，0，0，4；

0，0，0，1；

0，9，8，1。

那麼數據結構里的p,i,x的結構分別為：

p：0，2，4，5，8；

i：0，1，0，3，3，1，2，3；

x：1，7，2，9，8，4，1，1。

其中p的含義是，第一col從i[0]開始，第二col從i[2]開始，第三col從i[4]開始，第四col從i[5]開始，i最大index為8-1=7。而i和x分別對應著每個column中row的index和值。

還有一種是triplet方法，就是p和i分別村col和row的index，x存數值，這時候p、i、x三者size是相同的，也就是nz，就不贅述了。

參考header file：

CSparse/include/cs.h, Timothy Davis

看一下這篇文章：Sparse Matrices in MATLAB: Design and Implementation

作者 John R. Gilbert, Cleve Moler, and Robert Schreiber

三元數組的形式，分別表示行列和值，不過在我印象里matlab的數據結構是從1開始的@立黨其他說的都很詳細了

書被我畫的有點亂…別介意！