Sparse Linear Function(Under Construction!)

Sparse Matrix

「稀疏矩陣」。非零元素很少的矩陣。

元素幾乎都是零。非零元素稀稀落落零零散散淒淒慘慘戚戚。

經典的矩陣運算,諸如反矩陣、QR分解、特徵分解,時間複雜度O(N³)以上,速度太慢不實用。因此數學家旁敲側擊,鑽研稀疏矩陣,精簡計算步驟,以投入實用。

Low-rank Matrix

「低秩矩陣」。rank很少的矩陣。

基底幾乎都是零向量。非零基底稀稀落落。

稀疏矩陣多是低秩矩陣,低秩矩陣多是稀疏矩陣。這個領域的專家只講稀疏矩陣、不講低秩矩陣,講了一個就等於兩個都講了。

Sparse Matrix資料結構

不記錄零,節省時間空間。即是圖的資料結構。

edge list:非零元素,逐一列出。

adjacency lists:以橫條歸類,非零元素,逐一列出。

adjacency lists銜接在一起:MATLAB即採用此方式。

Eigenbasis(Under Construction!)

Eigenbasis

請見專著《Numerical Methods for Large Eigenvalue Problems》