疎行列の表現方法 その1 Matrix Market

現在疎行列ベクトル積のプログラムを書く途中なので、よく使われる疎行列の表現形式の一つである（らしい）Matrix Market形式(略してMMらしい)のリファレンス*1を参照しつつ適当に翻訳っぽいものをしてみる。

Introduction

疎行列の座標形式(Coordinate Format)

行列の座標形式は非ゼロ成分だけを座標を明示的に示しつつ列挙するもので、疎行列の表現に適している。下に一般の実疎行列の例をあげる。

これをMM座標形式では次のように表す。

%%MatrixMarket matrix coordinate real general
% A 5x5 sparse matrix with 8 nonzeros
5 5  8
1 1     1.0
2 2    10.5
4 2   250.5
3 3     0.015
1 4     6.0
4 4  -280.0
4 5    33.32
5 5    12.0

最初の行はいくつかのキーワードとその前のヘッダを示す文字列%%MatrixMarketからなる。この例では以下の行列が座標形式の行列であることを示し、さらに各要素が実数(real)で、行列全体がgeneralであることを示す。generalとは行列の表現が対称性などに依存しないことを示す。2行目はコメントで、%から始まっている。ここは任意の行数コメントを入れることができる。

その次の行は3つの整数からなり、それぞれ行数、列数、非ゼロ要素数を示す。この後に値valの(i,j)要素が

i j val

の形式で、上で示した非ゼロ要素数だけ続く。valは実数なので浮動小数として表される。また、(i,j)はFortran的に1から始まる。

Matrix Market形式は柔軟で、大文字と小文字は区別せず、各要素は1つ以上のスペース*2で区切られていればよい。また非ゼロ要素の登場する順序は一意ではない。そのためある行列に対するMM形式での表現は一意ではない。先ほどの行列も下のように書き表すことができる。

%%MatrixMarket  MATRIX    Coordinate    Real General
% --------------------------------------------------------------
%                Same matrix as previous example
% --------------------------------------------------------------
%
%  See http://math.nist.gov/MatrixMarket for more information.

    5  5        8

1 1  1.0
2 2       10.5
3 3             1.5e-2
4 4                     -2.8E2
5 5                              12.
     1      4      6
     4      2      250.5
     4      5      33.32

座標形式は複素行列(complex)・整数行列(integer)と位置のみを表す行列(pattern)に対しても定義されている。また、対称行列(symmetric)・交代行列(skew-symmetric)・エルミート行列(Hermitian)は対称性を利用して記述量を削減できる。その場合、下三角成分だけを記述する。（交代行列においては対角成分は0になるため当然記述されない。）以下に複素エルミート疎行列の例を示す。

これをMM形式では次のように表せる。

%%MatrixMarket matrix coordinate complex hermitian
5 5  7
1 1    1.0      0
2 2   10.5      0
4 2  250.5     22.2
3 3    1.5e-2   0
4 4   -2.8e2    0
5 5   12.       0
5 4    0       33.3

なんかCRS(Compressed Row Storage)に向いてないんじゃないかなという気もしたけど（ソートされてないからね）、いいのかな。

*1: http://math.nist.gov/MatrixMarket/formats.html

*2:タブとかもいいんですかね？