sp2adj

引数

A

m行n列の実数または複素数の疎行列 (nz 個の非ゼロエントリ)

xadj

(n+1)行1列の浮動小数点整数の行列で, 各列のiadjとvの先頭の添字を指します. j=1:nの場合, 浮動小数点整数 xadj(j+1)-xadj(j) は j列の非ゼロエントリの数になります.

iadj

nz行1列の浮動小数点整数の行列, 非ゼロエントリの行添字. j=1:nおよび, k = xadj(j):xadj(j+1)-1に関して, 浮動小数点整数 i = iadj(k) は 非ゼロエントリ #k の行添字です.

v

nz行1列の浮動小数点整数の行列, Aの非ゼロエントリ. j=1:nおよび, k = xadj(j):xadj(j+1)-1に関して, 浮動小数点整数Aij = v(k)は 非ゼロエントリ #k の値です.

説明

sp2adjは,疎行列を隣接形式に変換します. 隣接形式の値は列毎に保存されています. これは,この形式がしばしば "Compressed sparse column" または CSCと呼ばれる理由です.

例

以下の例では,1から10のエントリを有する通常の行列を作成します. 次に,これを疎行列に変換し,ゼロを除きます. 最後に,この行列の隣接形式を計算します. 行列bはAの非ゼロ要素のみを有します.

A = [
0 0 4 0 9
0 0 5 0 0
1 3 0 7 0
0 0 6 0 10
2 0 0 8 0
];
B=sparse(A);
[xadj,iadj,v]=sp2adj(B)
expected_xadj = [1 3 4 7 9 11]';
expected_adjncy = [3 5 3 1 2 4 3 5 1 4]';
expected_anz = [1 2 3 4 5 6 7 8 9 10]';
and(expected_xadj == xadj) // Should be %t
and(expected_adjncy == iadj) // Should be %t
and(expected_anz == v) // Should be %t
// j is the column index
for j = 1 : size(xadj,"*")-1
  irows = iadj(xadj(j):xadj(j+1)-1);
  vcolj = v(xadj(j):xadj(j+1)-1);
  mprintf("Column #%d:\n",j)
  mprintf("  Rows  = %s:\n",sci2exp(irows))
  mprintf("  Values= %s:\n",sci2exp(vcolj))
end

前のスクリプトは以下の出力を生成します.

Column #1:
  Rows  = [3;5]:
  Values= [1;2]:
Column #2:
  Rows  = 3:
  Values= 3:
Column #3:
  Rows  = [1;2;4]:
  Values= [4;5;6]:
Column #4:
  Rows  = [3;5]:
  Values= [7;8]:
Column #5:
  Rows  = [1;4]:
  Values= [9;10]:

列 #1について考えてみましょう. 等式 xadj(2)-xadj(1)=2 は列 #1に非ゼロ要素が2個あることを示します. 行添字は iadjに保存され, 列 #1 の非ゼロエントリは 行 #3 および #5であることを示します. 行列 v は実際のエントリが 1および2であることを示します.

以下の例では,疎行列の非ゼロエントリを隣接構造でループ処理を することにより,調べます.

A = [
0 0 0 0 0 6 0 0 0 0
3 0 5 0 0 0 0 5 0 0
0 0 0 3 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 7 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 3
0 0 0 0 0 0 0 0 2 0
];
B=sparse(A);
[xadj,iadj,v]=sp2adj(B)
expected_xadj = [1 2 3 4 5 5 6 6 7 8 9]';
expected_adjncy = [2 5 2 3 1 2 7 6]';
expected_anz = [3 7 5 3 6 5 2 3]';
and(expected_xadj == xadj) // Should be %t
and(expected_adjncy == iadj) // Should be %t
and(expected_anz == v) // Should be %t

以下の例では,sp2adjおよびadj2sp関数が逆関数であることを 確認します.

// Templates for the Solution of Algebraic Eigenvalue Problems: a Practical Guide
// Edited by Zhaojun Bai, James Demmel, Jack Dongarra, Axel Ruhe, and Henk van der Vorst
// "Sparse Matrix Storage Formats", J. Dongarra
// http://web.eecs.utk.edu/~dongarra/etemplates/book.html

A = [
10 0 0 0 -2 0
3 9 0 0 0 3
0 7 8 7 0 0
3 0 8 7 5 0
0 8 0 9 9 13
0 4 0 0 2 -1
];
A = sparse(A)

// To get the Compressed Sparse Column (CSC) :
[col_ptr,row_ind,val]=sp2adj(A)
// To convert back to sparse:
AAsp=adj2sp(col_ptr,row_ind,val)
// Check the conversion
AAsp - A

// To get the Compressed Sparse Row (CSR) :
[row_ptr,col_ind,val]=sp2adj(A')
// To convert back to sparse:
AAsp=adj2sp(row_ptr,col_ind,val)'
// Check the conversion
AAsp - A

参照

• adj2sp — 隣接形式を疎行列に変換.
• sparse — 疎行列を定義
• spcompack — 圧縮隣接表現に変換する
• spget — 疎行列のエントリを取得

参考文献

"Implementation of Lipsol in Scilab", Hector E. Rubio Scola, INRIA, Decembre 1997, Rapport Technique No 0215

"Solving Large Linear Optimization Problems with Scilab : Application to Multicommodity Problems", Hector E. Rubio Scola, Janvier 1999, Rapport Technique No 0227

"Toolbox Scilab : Detection signal design for failure detection and isolation for linear dynamic systems User's Guide", Hector E. Rubio Scola, 2000, Rapport Technique No 0241

"Computer Solution of Large Sparse Positive Definite Systems", A. George, Prentice-Hall, Inc. Englewood Cliffs, New Jersey, 1981.