Chapter 02

はじめに

Hishinuma_t
Hishinuma_t
2021.09.17に更新

はじめに

毎年のように研究室で疎行列ベクトル積の解説をしている気がしており, いい加減きちんとまとめて,Publicなものとして形にしたいという思いから,本書の作成を始めました.

本書では,C/C++およびマルチスレッドプログラミングの基礎知識があることを前提とします.なお,本書ではマルチスレッドプログラミングにOpenMPを用います.

なお,参考までに著者の環境は,

  • Ubuntu 20.10
  • gcc/g++ 10.3.0

ですが,特殊なコンパイラの機能などは使わないので,他の環境でも大丈夫だと思っています.

疎行列ベクトル積とはどのような演算か

疎行列ベクトル積 (SpMV, Sparse Matrix and Vector Product)は,疎行列 A とベクトル x を掛け算してベクトル y に格納する y = Ax という演算です (BLASのGEMV準拠でy+=Axを対象にしている論文やソフトもあるので注意してください).

本書における行列ベクトル積はNN列の正方実数行列 A と長さNの実数ベクトル x の積の結果を長さNの実数ベクトル y にストアする演算を指すことにし,長方形の行列は対象としません.

疎行列 (sparse matrix)とは,要素がほとんどゼロの行列のことです.反対に値がほとんど埋まっている行列のことを密行列 (dense matrix)といいます.

疎行列は,数学的に特殊な意味や性質があるわけではありません.そのため,厳密に何%の要素がゼロなら疎行列なのかという定義はありません.

では,なぜ密行列と区別して疎行列を扱うのか?それは,ゼロ要素を含むということは,疎行列ベクトル積において無駄な演算やデータ保持が生じるからです (え,なんで無駄が生じるの?と思った人はページ下部の補足の章を読んでください).

そのため,

  1. ゼロ要素を含まないようなデータ形式
  2. ゼロがスキップされていることを考慮した疎行列ベクトル積のプログラム

を用意することで,演算量やメモリデータ量を減らすことを考えます.

データ形式の例を挙げると,汎用的かつ最も単純に非零要素のみを保持する方法に,COO形式 (Coordinate形式,座標形式)と呼ばれるx座標 (行番号),y座標 (列番号),値の2つの値のペアで疎行列を格納する形式があります.これはその名の通り座標の表現によく使われるものと同じなのでイメージしやすいでしょう.

このようにデータ形式が違うのだから密行列と同じように扱えるはずもなく,「疎行列」という別の名前で呼ばれます.

言ってしまえば,疎行列とは計算を効率的に行うためのテクニックです.

後の章で詳しく述べるが,1.のデータ形式を決めた時点で,2.の計算プログラムはほとんど決まります.行列を計算しやすいように事前に加工するというのがこの演算に対する研究の主眼であり,疎行列ベクトル積は,「計算しやすい」という状態を考えるためにメモリやコンピュータアーキテクチャ,並列化の知識が求められる演算です.

本書で取り扱う疎行列の格納形式について

本書では,事前情報のない任意の行列に対する一般的な疎行列の格納形式について取り扱い,行列構造の非零要素の配置 (非零パターン,非零プロファイルと呼ばれる)が既に分かっている場合については考えません.

非零プロファイルが既に分かっている場合というのは,最も簡単に言えば対角成分にしか非零要素のない対角行列のようなものです.

事前に対角行列だと分かっているのであれば,その事前情報に基づいて長さ N の配列として対角要素だけを保持すればよいが,当然ながらこれは全ての行列には対応できません.

このように事前情報から行列の非零プロファイルが一意に定まる場合,本書で取り上げる一般的な格納形式でなく,事前情報に基づいたプログラムを実装することで,より無駄のない演算を行うことが可能でしょう.

用語,略語,英語表記等

  • 疎行列
    • Sparse Matrix
  • 密行列
    • Dense Matrix
  • 疎行列ベクトル積 (SpMV)
    • Sparse Matrix and Vector Multiplication
    • Sparse Matrix and Vector Product
  • COO 形式
    • Coodinate形式,座標形式
    • ijv形式,triplet形式と呼ばれることもある
  • CRS 形式
    • Compressed Row Storage形式
    • 圧縮行格納形式と日本語で書いてあることもある(あまり見ない)
    • CSR形式と呼ばれることもある

CRS形式の名称の問題点とCSR形式

COOやCRSは行列をメモリ上に保持するための格納形式 (Storage format)です.つまりCOO格納形式はCoodinate Storgae formatと書いて良いわけであるが,CRSはCompressed Row Storageの略なのでCompressed Row Storage Storage formatとなってStorageが重複します.

このような初期の命名ミスが原因(だと思う,出典はない)で,CRS形式はCSR (Compressed Sparse Row)形式とも呼ばれます.というか,現在はCSR形式のほうが普及しつつあり,IntelやNVIDIAのライブラリでもCSRと表記されています.筆者は老害なのでCRSと呼びますが,若者はCSRと呼んだほうが良いのかもしれないです.

補足) 疎な行列を密行列として扱うと無駄な計算が生じる理由

それは,ゼロ要素を含むということは,疎行列ベクトル積において無駄な演算やデータ保持が生じるからです.

この理由が良くわからない人は,以下を読んでください(分かる人は飛ばしてOK)

理由1 計算量が多い

以下に6x6の疎行列とベクトルの積の例を示します.この行列では,青色の部分以外がゼロです.
このとき,青色の部分を非零要素 (non-zeros)と呼び,非零要素の数をthe number of non-zerosの頭文字を取って nnz と書きます.
この行列は,nnz=16の行列です.

spmv.png

この行列とベクトルの掛け算の1行目の計算結果 y_1 は密行列としてAを扱った場合は,

y_1 = a * x_1 + b * x_2 + 0 * x_3 + 0 * x_4 + 0 * x_5 + 0 * x_6

となり,6つの要素全てを計算する必要があるが,実際にはほとんどゼロの計算なので x_1x_2 の2つの計算以外は無駄です.

密行列における計算量は,各要素に対する足し算と掛け算が一回ずつなので,行数を N としたとき,

密行列の計算量:2*N^2

一方,疎行列では,非零要素に対する計算しかしなくてよいので,

疎行列の計算量:2*nnz

ということになります.
値がゼロばかりなのであれば,密行列として扱いたくない理由がわかって頂けたでしょうか.

理由2 メモリデータ量が多い

このように,密行列としてデータを扱うと計算量の無駄であるため,ゼロをスキップして計算したい.

ほとんどの人は,行列を扱う場合,100x100の行列であれば double A[100][100]double A[100*100] などとすることで,倍精度の100x100の行列を確保してきたことだと思います.
このとき,倍精度は8 byteであるので,8 * 100 * 100 = 80,000 Byte (80 KB)のメモリを必要とします.

しかし,例えば先程の例のような1行に非零要素が3個しかないとわかっている行列であれば,8 * 3 * 100 = 2,400 Byte しか使わないことになります.

実際には非零実際には零要素だけを抜き出すのではなく,行番号や列番号を保持するためのインデックスが必要になるが,それでも十分にメモリデータ量を削減することができます.