データ構造入門：スパース行列（疎行列）とは？メモリ上の効率的な表現方法

スパース行列（疎行列）とは

このセクションでは、スパース行列（疎行列）とは何か、そしてそれをコンピュータのメモリ上でどのように表現すればよいかについて解説します。スパース行列とは、行列を構成する要素の大部分が0である行列のことです。別の定義としては、非ゼロ要素が最大でも全体の1/3程度（m×n の約30%）しか含まない行列をスパース行列と呼ぶこともあります。

なぜ特別な格納方法が必要なのか

コンピュータのメモリ上で行列を扱うのは、各種の演算を効率的に実行するためです。しかし、行列がスパースな性質を持っている場合、演算の効率化には役立つ一方で、メモリ空間を大きく消費してしまうという問題があります。値が0の部分は意味を持たないため、その分の領域は完全に無駄になってしまいます。そこで、スパース行列を格納する際には、通常の二次元配列とは異なるデータ構造を採用するのが有効です。

スパース行列の具体例

例として、次のようなスパース行列を考えてみましょう。

この行列には非ゼロ要素が8個含まれ、残りの28個はすべて0です。この行列をそのまま格納すると、6×6 = 36 個分のメモリ領域を消費することになります。行列のサイズが大きくなればなるほど、無駄になる領域も比例して増えていきます。

トリプル（三つ組）形式による表現

スパース行列の情報は、表構造を使って効率的に格納できます。ここでは「X」という名前の表を作成してみましょう。

この表では、第1列に行番号、第2列に列番号、第3列に M[row, col] の位置に存在するデータをそれぞれ格納します。各行は3つのパラメータを持つことから、「トリプル（triplet：三つ組）」と呼ばれます。

最初のトリプルには行列全体のサイズ情報が記録されます。「行 = 6、列 = 6」という情報から、行列 M が 6×6 の行列であることが分かります。また、value フィールドには、配列内に存在する非ゼロ要素の総数が格納されます。

空間計算量の比較

一見すると、この表自体も 9 × 3 = 36 個分の領域を消費しており、メリットがないように思えるかもしれません。しかし、ここに大きな利点があります。仮に行列のサイズが 8×8 = 64 で、非ゼロ要素が8個しか存在しなかったとしても、表 X が必要とする領域は36単位のまま変わりません。

ポイントは、この表の列数が常に3列で固定されており、行数だけが非ゼロ要素の個数に応じて変化するという点です。したがって、非ゼロ要素の数を T とおくと、空間計算量は O(3×T) = O(T) で表されます。一方、元の行列をそのまま格納する場合に必要な空間計算量は O(m×n) です。非ゼロ要素が少ないスパース行列に対しては、このトリプル形式の手法を用いることで、大幅なメモリ削減を実現できるのです。