読者です 読者をやめる 読者になる 読者になる

web系な備忘録

私が忘れてもブログがあるもの

疎行列計算ライブラリ UJMP

疎行列とは

 修論で初めて行列計算が必要になりました(遅い!)。
 まず,今回Twitterデータを扱う関係上,便利なTwitter4jと併用できると楽なのでJavaのライブラリを探しました。
 JAMA: Java Matrix Packageというのがなかなか簡単に書けてよさそうだったのですが,試しにデータ数を増やして10000×10000ぐらいのMatrixを作った瞬間OutOfMemory。そりゃそうか。要素数1億ですからね……。
 この10000×10000な行列は,ほとんどが0で,ごくたまに数値が入る,いわゆる疎行列です。疎行列が具体的にはどんなものかといいますと、
 普通の行列が以下のように、要素全てを持っている形であるのに対して、

|0 0 0|
|3 0 0|
|0 0 2|

 疎行列は、0でない要素だけを持っている行列です。
 ほとんど0ばかりな行列を扱う場合にデータ量が少なくてすむという利点があります。

(3, 1, 0),(2, 2, 2)

↑(1, 0)に3を入れる,という感じのデータだけを渡せばいい

 が,JAMAは疎行列計算ができないということに、ここで気が付きました。ガッデム。

UJMPの紹介

 いくつかライブラリを迷走した結果(PythonのScipyにも手を出しました。書けたけど,遅い気がするのと,JavaプログラムとPythonプログラムの間を行ったりきたりするのに疲れたので,Javaのライブラリを改めて探しました),Universal Java Matrix Package | Free Development software downloads at SourceForge.netというJavaライブラリに落ち着きましたので、使い方を紹介します。
 日本語ドキュメントが全然見つからなかったので、疎行列を扱いたい日本語Javaユーザさんの参考になれば幸いです。

普通の行列
int row = 100;
int column = 1;
Matrix m1 = Matrix.factory.zeros(row, column); // 全部ゼロな行列
Matrix m2 = Matrix.factory.ones(row, column);   // 全部1な行列
疎行列を扱う
int row = 10000;
int column = 10000;
SparseMatrix sm = SparseMatrix.factory.zeros(row, column);// 疎行列はこの全部ゼロな行列でしか初期化できない模様(使い方からして当然だけど)
sm.setAsInt(3, 1, 0);// 1行目0列目に3をセット。setAsIntとかsetAsStringとかいろいろあります。どんな風に入れても,取り出し型に合わせてよしなに返してくれます。
転置行列

 transposeという関数があるものの,SparseMatrixには使えないらしいので,書いてみました。availableCoordinates()という,非ゼロ要素の座標を取ってきてくれる関数がとても便利です。(本当は実装されているのに気がついていないだけかも、という気がしてなりませんが……)

SparseMatrix st = SparseMatrix.factory.zeros(row, column);// 転置後の行列
for(long [] cd : sm.availableCoordinates()){      // 非ゼロ要素のみ座標をイテレータで転置位置にセット
    st.setAsDouble(sm.getAsDouble(cd[0], cd[1]), cd[1], cd[0]);
}
四則演算
加 a.plus(b)
減 a.minus(b)
乗 a.mtimes(b)
除 a.divideMatrix(b)  or  a.divideScalar(b)

 各関数は,ReturnTypeを引数に設定できるようにもなっていて,Ret.ORGを設定すれば行列aを計算後の状態に変更し,Ret.NEWを設定すれば行列aはそのままで、返り値が計算結果の新規行列になります。用途によって計算結果の出し方を使い分けられるのは便利そうです。

ノルム(要素の絶対値の和とか,自乗の和とか)も一通り計算できます。

w.norm1();

固有ベクトルも計算できます。

Matrix[] eig = w.eig();

eig[0]がV,eig[1]がDです。VとDについては専門のページを参照してください。

行列の一部を切り出すことも可能です。

m.submatrix(ReturnType, startRow, startCol, endRow, endCol);

 そのうち、PageRankの計算プログラムを紹介しようと思います。上記の組み合わせで出来てしまいますが。
 なんとなく難しい印象のある行列計算ですが、UJMPではとても簡単に、そして高速なコードが書けるので、ぜひ試してみてください!

 ※間違い等ありましたらご教授くださいm(_ _)m