|
|
6#
大 中
小 發表於 2015-10-18 14:46 只看該作者
\( A=\left[\matrix{0&0&1&0\cr0&1&0&1\cr1&0&0&1\cr1&0&0&0}\right] \)
\(A\)矩陣中大部分的元素都是0，故\(A\)矩陣又稱為稀疏矩陣(Sparse Matrix)，只要儲存非0元素的位置及其元素値，不僅可以節省記憶體空間，還可以節省不必要的運算。
以下介紹三種基本稀疏矩陣的儲存格式及其對應的矩陣乘法
(1)Coordinate-wise(COO)
就是將\(A\)矩陣中非零元素的行、列、値儲存起來
\( \matrix{第3行第1列値為1 \cr 第2行第2列値為1 \cr 第4行第2列値為1 \cr 第1行第3列値為1 \cr 第4行第3列値為1 \cr 第1行第4列値為1} \) 轉換成 \( \matrix{Col=[\;3,2,4,1,4,1]\; \cr Row=[\;1,2,2,3,3,4]\; \cr Val=[\;1,1,1,1,1,1]\;} \)
COO稀疏矩陣以列或以列存取元素同樣簡單
再乘上\(b\)矩陣\( =[\;1,2,3,4]\;^T \)
\( \left[\matrix{0&0&1&0\cr0&1&0&1\cr1&0&0&1\cr1&0&0&0}\right] \cdot \left[ \matrix{1\cr 2 \cr 3 \cr 4} \right]=\left[ \matrix{1\times 3 \cr 1 \times 2+1 \times 4 \cr 1 \times 1+1 \times 4 \cr 1 \times 4} \right] \) 轉換成 \( \left[ \matrix{Val[1]\cdot b[Col[1]] \cr Val[2]\cdot b[Col[2]]+Val[3]\cdot b[Col[3]] \cr Val[4]\cdot b[Col[4]]+Val[5]\cdot b[Col[5]] \cr Val[6]\cdot b[Col[6]]} \right] \)
程式碼為
for (i = 0; i < N; i = i + 1)
result[ i ] = 0;
for (i = 1; i <= nnz; i = i + 1)
result[Row[ i ]] = result[Row[ i ]] + Val[ i ]*b[Col[ i ]];
\(N\)代表\(A\)矩陣列個數
\(nnz\)代表\(A\)矩陣非零元素的個數
(%i1)
A:matrix([0,0,1,0],
[0,1,0,1],
[1,0,0,1],
[1,0,0,0]);
(%o1) \( \left[\matrix{0&0&1&0\cr0&1&0&1\cr1&0&0&1\cr1&0&0&0}\right] \)
A矩陣轉換成COO稀疏矩陣
(%i5)
Col:[]$
Row:[]$
Val:[]$
for i:1 thru length(A) do
(for j:1 thru length(A[1]) do
(if A[i,j]#0 then
(print("第",j,"行第",i,"列値為",A[i,j]),
Row:append(Row,[ i ]),
Col:append(Col,[j]),
Val:append(Val,[A[i,j]])
)
)
)$
第3行第1列値為1
第2行第2列値為1
第4行第2列値為1
第1行第3列値為1
第4行第3列値為1
第1行第4列値為1
行,列,値
(%i8)
Col;
Row;
Val;
(%o6) \( [\;3,2,4,1,4,1]\; \)
(%o7) \( [\;1,2,2,3,3,4]\; \)
(%o8) \( [\;1,1,1,1,1,1]\; \)
(%i9) b:[1,2,3,4];
(%o9) \( [\;1,2,3,4]\; \)
COO稀疏矩陣相乘，可以發現0元素都不會被乘到
(%i13)
N:apply(max,Row)$
result:create_list(0,i,1,N)$
for i:1 thru length(Val) do
(print("result[",Row[ i ],"]再加上",Val[ i ],"*",b[Col[ i ]]),
result[Row[ i ]]:result[Row[ i ]]+Val[ i ]*b[Col[ i ]]
)$
result[1]再加上1*3
result[2]再加上1*2
result[2]再加上1*4
result[3]再加上1*1
result[3]再加上1*4
result[4]再加上1*1
COO稀疏矩陣相乘結果
(%i14) result;
(%o14) \( [\;3,6,5,1]\; \)
和矩陣實際相乘結果相同
(%i15) A.b;
(%o15) \( \left[ \matrix{3 \cr 6 \cr 5 \cr 1} \right] \)
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
(2)Compressed Sparse Row (CSR)
就是將\(Row\)陣列壓縮成\(RowPtr\)陣列
\( \matrix{Col=[\;3,2,4,1,4,1]\; \cr Row=[\;1,2,2,3,3,4]\; \cr Val=[\;1,1,1,1,1,1]\;} \) 轉換成 \( \matrix{Col=[\;3,2,4,1,4,1]\; \cr RowPtr=[\;1,2,4,6,7]\; \cr Val=[\;1,1,1,1,1,1]\;} \)
\(RowPtr\)意思是
第1列包含値\(Val[1]\)
第2列包含値\(Val[2],Val[3]\)
第3列包含値\(Val[4],Val[5]\)
第4列包含値\(Val[6]\)
若稀疏矩陣行>列則\(RowPtr\)壓縮率較高，CSR格式以列存取元素非常簡單，以行存取元素非常困難
故矩陣乘法以\( A.b \)表示，其中\( b=\left[ \matrix{1 \cr 2 \cr 3 \cr 4} \right] \)
\( \left[\matrix{0&0&1&0\cr0&1&0&1\cr1&0&0&1\cr1&0&0&0}\right] \cdot \left[ \matrix{1\cr 2 \cr 3 \cr 4} \right]=\left[ \matrix{1\times 3 \cr 1 \times 2+1 \times 4 \cr 1 \times 1+1 \times 4 \cr 1 \times 4} \right] \) 轉換成 \( \left[ \matrix{Val[1]\cdot b[Col[1]] \cr Val[2]\cdot b[Col[2]]+Val[3]\cdot b[Col[3]] \cr Val[4]\cdot b[Col[4]]+Val[5]\cdot b[Col[5]] \cr Val[6]\cdot b[Col[6]]} \right] \)
程式碼為
for (i = 0; i < N; i = i + 1)
result[ i ] = 0;
for (i = 1; i < N; i = i + 1)
{for (j = RowPtr[ i ]; j < RowPtr[i+1]; j = j + 1)
result[ i ] = result[ i ] + Val[j]*b[Col[j]];
}
\(N\)代表\(RowPtr\)陣列長度
(%i1)
A:matrix([0,0,1,0],
[0,1,0,1],
[1,0,0,1],
[1,0,0,0]);
(%o1) \( \left[\matrix{0&0&1&0\cr0&1&0&1\cr1&0&0&1\cr1&0&0&0}\right] \)
A矩陣轉換成CSR稀疏矩陣
(%i6)
Col:[]$
RowPtr:[1]$
Val:[]$
index:1$
for i:1 thru length(A) do
(for j:1 thru length(A[1]) do
(if A[i,j]#0 then
(print("第",j,"行値為",A[i,j]),
Col:append(Col,[j]),
Val:append(Val,[A[i,j]]),
index:index+1
)
),
RowPtr:append(RowPtr,[index]),
print("第",i,"列包含Val[",RowPtr[ i ],"~",RowPtr[i+1]-1,"]")
)$
第3行値為1
第1列包含Val[1~1]
第2行値為1
第4行値為1
第2列包含Val[2~3]
第1行値為1
第4行値為1
第3列包含Val[4~5]
第1行値為1
第4列包含Val[6~6]
行,列壓縮,値
(%i9)
Col;
RowPtr;
Val;
(%o7) \( [\;3,2,4,1,4,1]\; \)
(%o8) \( [\;1,2,4,6,7]\; \)
(%o9) \( [\;1,1,1,1,1,1]\; \)
(%i10) b:[1,2,3,4];
(%o10) \( [\;1,2,3,4]\; \)
CSR稀疏矩陣相乘，可以發現0元素都不會被乘到
(%i13)
N:length(RowPtr)-1$
result:create_list(0,i,1,N)$
for i:1 thru length(RowPtr)-1 do
(for j:RowPtr[ i ] thru RowPtr[i+1]-1 do
(print("result[",i,"]再加上",Val[j],"*",b[Col[j]]),
result[ i ]:result[ i ]+Val[j]*b[Col[j]]
)
)$
result[1]再加上1*3
result[2]再加上1*2
result[2]再加上1*4
result[3]再加上1*1
result[3]再加上1*4
result[4]再加上1*1
CSR稀疏矩陣相乘結果
(%i14) result;
(%o14) \( [\;3,6,5,1]\; \)
和矩陣實際相乘結果相同
(%i15) A.b;
(%o15) \( \left[ \matrix{3 \cr 6 \cr 5 \cr 1}\right] \)
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
(2)Compressed Sparse Column (CSC)
就是將\(Col\)陣列壓縮成\(ColPtr\)陣列
\( \matrix{Col=[\;1,1,2,3,4,4]\; \cr Row=[\;3,4,2,1,2,3]\; \cr Val=[\;1,1,1,1,1,1]\;} \) 轉換成 \( \matrix{ColPtr=[\;1,3,4,5,7]\; \cr Row=[\;3,4,2,1,2,3]\; \cr Val=[\;1,1,1,1,1,1]\;} \)
\(ColPtr\)意思是
第1行包含値\(Val[1],Val[2]\)
第2行包含値\(Val[3]\)
第3行包含値\(Val[4]\)
第4行包含値\(Val[5],Val[6]\)
若稀疏矩陣列>行則\(RowPtr\)壓縮率較高，CSC格式以行存取元素非常簡單，以列存取元素非常困難
故矩陣乘法以\( b.A \)表示，其中\( b=\left[ 1,2,3,4 \right] \)
\( \left[ 1,2,3,4 \right] \cdot \left[\matrix{0&0&1&0\cr0&1&0&1\cr1&0&0&1\cr1&0&0&0}\right]=\left[ 3 \cdot 1+4 \cdot 1 , 2 \cdot 1 , 1 \cdot 1 , 2 \cdot 1+3 \cdot 1 \right] \) 轉換成 \( \left[ b[Row[1]]\cdot Val[1]+b[Row[2]]\cdot Val[2] , b[Row[3]]\cdot Val[3] , b[Row[4]] \cdot Val[4] , b[Row[5]]\cdot Val[5]+b[Row[6]]\cdot Val[6] \right] \)
程式碼為
for (i = 0; i < N; i = i + 1)
result[ i ] = 0;
for (i = 1; i < N; i = i + 1)
{for (j = ColPtr[ i ]; j < ColPtr[i+1]; j = j + 1)
result[ i ] = result[ i ] + b[Row[j]]*Val[j];
}
\(N\)代表\(ColPtr\)陣列長度
(%i1)
A:matrix([0,0,1,0],
[0,1,0,1],
[1,0,0,1],
[1,0,0,0]);
(%o1) \( \left[\matrix{0&0&1&0\cr0&1&0&1\cr1&0&0&1\cr1&0&0&0}\right] \)
A矩陣轉換成CSC稀疏矩陣
(%i6)
ColPtr:[1]$
Row:[]$
Val:[]$
index:1$
for j:1 thru length(A[1]) do
(for i:1 thru length(A) do
(if A[i,j]#0 then
(print("第",j,"行値為",A[i,j]),
Row:append(Row,[ i ]),
Val:append(Val,[A[i,j]]),
index:index+1
)
),
ColPtr:append(ColPtr,[index]),
print("第",j,"行包含Val[",ColPtr[j],"~",ColPtr[j+1]-1,"]")
)$
第1行値為1
第1行値為1
第1行包含Val[1~2]
第2行値為1
第2行包含Val[3~3]
第3行値為1
第3行包含Val[4~4]
第4行値為1
第4行値為1
第4行包含Val[5~6]
行壓縮,列,値
(%i9)
ColPtr;
Row;
Val;
(%o7) \( [\;1,3,4,5,7]\; \)
(%o8) \( [\;3,4,2,1,2,3]\; \)
(%o9) \( [\;1,1,1,1,1,1]\; \)
(%i10) b:[1,2,3,4];
(%o10) \( [\;1,2,3,4]\; \)
CSC稀疏矩陣相乘，可以發現0元素都不會被乘到
(%i12)
N:length(ColPtr)-1$
result:create_list(0,i,1,N)$
for i:1 thru length(ColPtr)-1 do
(for j:ColPtr[ i ] thru ColPtr[i+1]-1 do
(print("result[",i,"]再加上",b[Row[j]],"*",Val[j]),
result[ i ]:result[ i ]+b[Row[j]]*Val[j]
)
)$
result[1]再加上3*1
result[1]再加上4*1
result[2]再加上2*1
result[3]再加上1*1
result[4]再加上2*1
result[4]再加上3*1
CSC稀疏矩陣相乘結果
(%i13) result;
(%o13) \( [\;7,2,1,5]\; \)
和矩陣實際相乘結果相同
(%i14) b.A;
(%o14) \( [\;7,2,1,5]\; \)
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
將以上程式改寫成副程式
(%i1)
A:matrix([0,0,1,0],
[0,1,0,1],
[1,0,0,1],
[1,0,0,0]);
(%o1) \( \left[\matrix{0&0&1&0\cr0&1&0&1\cr1&0&0&1\cr1&0&0&0}\right] \)
(%i2) b:[1,2,3,4];
(%o2) \( [1,2,3,4] \)
A矩陣轉換成COO稀疏矩陣
(%i3)
COO(A):=block
([Col:[],Row:[],Val:[]],
for i:1 thru length(A) do
(for j:1 thru length(A[1]) do
(if A[i,j]#0 then
(Row:append(Row,[ i ]),
Col:append(Col,[j]),
Val:append(Val,[A[i,j]])
)
)
),
return([Col,Row,Val])
)$
行,列,値
(%i4) [Col,Row,Val]:COO(A);
(%o4) \( [[3,2,4,1,4,1],[1,2,2,3,3,4],[1,1,1,1,1,1]] \)
COO稀疏矩陣相乘
(%i5)
COOmul(Col,Row,Val,b):=block
([N,result],
N:apply(max,Row),
result:create_list(0,i,1,N),
for i:1 thru length(Val) do
(result[Row[ i ]]:result[Row[ i ]]+Val[ i ]*b[Col[ i ]]
),
return(result)
)$
COO稀疏矩陣相乘結果
(%i6) COOmul(Col,Row,Val,b);
(%o6) \( [3,6,5,1] \)
和矩陣實際相乘結果相同
(%i7) A.b;
(%o7) \( \left[ \matrix{3 \cr 6 \cr 5 \cr 1} \right] \)
A矩陣轉換成CSR稀疏矩陣
(%i8)
CSR(A):=block
([Col:[],RowPtr:[1],Val:[],index:1],
for i:1 thru length(A) do
(for j:1 thru length(A[1]) do
(if A[i,j]#0 then
(Col:append(Col,[j]),
Val:append(Val,[A[i,j]]),
index:index+1
)
),
RowPtr:append(RowPtr,[index])
),
return([Col,RowPtr,Val])
)$
行,列壓縮,値
(%i9) \( [[3,2,4,1,4,1],[1,2,4,6,7],[1,1,1,1,1,1]] \)
CSR稀疏矩陣相乘
(%i10)
CSRmul(Col,RowPtr,Val,b):=block
([N,result],
N:length(RowPtr)-1,
result:create_list(0,i,1,N),
for i:1 thru length(RowPtr)-1 do
(for j:RowPtr[ i ] thru RowPtr[i+1]-1 do
(result[ i ]:result[ i ]+Val[j]*b[Col[j]]
)
),
return(result)
)$
CSR稀疏矩陣相乘結果
(%i11) CSRmul(Col,RowPtr,Val,b);
(%o11) \( [3,6,5,1] \)
和矩陣實際相乘結果相同
(%i12) A.b;
(%o12) \( \left[ \matrix{3 \cr 6 \cr 5 \cr 1} \right] \)
A矩陣轉換成CSC稀疏矩陣
(%i13)
CSC(A):=block
([ColPtr:[1],Row:[],Val:[],index:1],
for j:1 thru length(A[1]) do
(for i:1 thru length(A) do
(if A[i,j]#0 then
(Row:append(Row,[ i ]),
Val:append(Val,[A[i,j]]),
index:index+1
)
),
ColPtr:append(ColPtr,[index])
),
return([ColPtr,Row,Val])
)$
行壓縮,列,値
(%i14) [ColPtr,Row,Val]:CSC(A);
(%o14) \( [[1,3,4,5,7],[3,4,2,1,2,3],[1,1,1,1,1,1]] \)
CSC稀疏矩陣相乘
(%i15)
CSCmul(b,ColPtr,Row,Val):=block
([N,result],
N:length(ColPtr)-1,
result:create_list(0,i,1,N),
for i:1 thru length(ColPtr)-1 do
(for j:ColPtr[ i ] thru ColPtr[i+1]-1 do
(result[ i ]:result[ i ]+b[Row[j]]*Val[j]
)
),
return(result)
)$
CSC稀疏矩陣相乘結果
(%i16) CSCmul(b,ColPtr,Row,Val);
(%o16) \( [7,2,1,5] \)
CSC稀疏矩陣相乘結果
(%i17) b.A;
(%o17) \( [7,2,1,5] \)
參考資料
有COO,CSR矩陣相乘程式碼
http://www.mathcs.emory.edu/~che ... bus/3-C/sparse.html
|
