07解説：SQLで行列積の計算???
CodeIQの設問「SQLで行列積の計算???」の解説をします。
問題文
下記のような4×3の疎行列Aがあります。多くの要素が0となっている行列を疎行列(sparse matrix)といいます。
0 1 -3 2 0 0 0 0 0 -1 0 4この行列Aは列と行の情報で取り出すと、以下のように表現できます。
row_id col_id val_nr 1 2 1 1 3 -3 2 1 2 4 1 -1 4 3 4行列を疎行列の表として表すことができます。
問１ 基本問題
行列AとBが与えれたとすると、AとBの行列の積はどのようにSQLクエリーで表現できるかを考え、行列積ABを表すSQLクエリーをselect文で答えてください。
行列A, Bは以下のようなフィールドの行として表現できます。
(row_id, col_id, val_nr)答えの行列積の表は (row_id, col_id, val_nr)という形式となります。
AとBの行列の積はAとBの表の結合として表せます。ただし、JOIN文は使いません。
データの表示順は(row_id, col_id)の昇順にしてください。行列積Cの行列の各要素(i,k)をC(i,k)と表すと、下記の式が成り立ちますので、参考にしてください。
C(i,k) = Σ (j=1 to end) { A(i,j) * B(j,k) }計算結果の数値は必要ありません。データは確認用に使ってください。
添付ファイルはこちらからダウンロードしてください。multiply.txtはpostgreSQLのスクリプトになっていますので、下記のように実行してください。
$ psql yourdb < multiply.txt前半部分は表作成とデータのロードとなっています。
mysqlやOracle等他のデータベースをお使いの場合は適宜修正して、データを読み込んでください。
問２ 発展問題
表Aと表Bにはimg_nrという値が含まれており、下記のようなフィールド形式になっています。
(row_id, col_id, val_nr, img_nr)val_nrを複素数の実数部、img_nrを複素数の虚数部とみなして、複素数行列A、Bの行列積を計算するSQLクエリーを作ってください。行列積の結果もA, Bと同じフィールド形式になります。
問１と同じく、multiply.txt内に書き込む部分がありますので、書き込んだらmultiply.txtを送ってください。
複素数x, yをx = a + bi, y = c + di （a, b, c, d ∈R, iは虚数）とすると以下の式が成り立つことに注意。
x y = (ac - bd) + (bc + ad)i練習問題
問題が難しいようでしたら、下記の練習問題がありますので、その練習問題を解いてからこの問題に再挑戦してみてください。
解説
問１ 基本問題
解答は以下の通りです。
select A.row_id, B.col_id, sum(A.val_nr * B.val_nr) as val_nr
from A, B
where A.col_id = B.row_id
group by A.row_id, B.col_id
order by A.row_id, B.col_id;
表AとBの結合として表現します。制約条件を与えないと、結果がAの全行とBの全行の組み合わせとなってしまうので、制約条件を与えます。結果となる行列の要素C(i,k)について考えると以下の式が成り立ちます。
C(i,k) = Σ (j=1 to end) { A(i,j) * B(j,k) }
= A(i,1)*B(1,k) + A(i,2)*B(2,k) + ... + A(i,m)*B(m,k)
j は 1,2,...,m の値を取りますが、C(i,k)はAの要素A(i,j)とBの要素B(j,k)を取り出して、かけたものの和になっています。
各項A(i,j)*B(j,k)ではjが共通しており、Aの列jとBの行jが共通しているので、SQLで書くと以下のような条件となります。
where A.col_id = B.row_id
C(i,k)の要素はA(i,j)*B(j,k)の和になっているので、集計関数sum()で和を計算します。
制約条件だけではなく、Cの(i,k)要素毎に結果を求める必要があるので、下記のグループ句が必要となります。
group by A.row_id, B.col_id
最後に計算結果を(i,k)順に表示するため、下記のオーダー句が書き加えます。
order by A.row_id, B.col_id
どうでしょうか。面倒くさそうな計算がSQLの結合を使うと意外と簡単に書けますね。
SQLの出力は以下のようになっていれば、うまく行っています。
row_id | col_id | val_nr
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- -
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
問２ 発展問題
解答は以下の通りです。
select A.row_id, B.col_id,
sum(A.val_nr * B.val_nr - A.img_nr * B.img_nr) as val_nr,
sum(A.val_nr * B.img_nr + A.img_nr * B.val_nr) as img_nr
from A, B
where A.col_id = B.row_id
group by A.row_id, B.col_id
order by A.row_id, B.col_id;
Aの要素の実数部、虚数部をそれぞれReA, ImAとして、Bの要素の実数部、虚数部をReB, ImBとすると次の式が成り立ちます。
(ReA + ImA i) * (ReB + ImB i) = (ReA * ReB - ImA * ImB) + (ReA * ImB + ImA * ReB) i
実数部の間にマイナスがあるので、注意。
従って、行列積要素の実数部と虚数部をSQLで書くと下記の通りになります。
sum(A.val_nr * B.val_nr - A.img_nr * B.img_nr) sum(A.val_nr * B.img_nr + A.img_nr * B.val_nr)
この問題は、複素数の虚数の扱いを知っていれば、応用なので、簡単ですね。
SQLの出力は以下のようになっていれば、うまく行っています。
row_id | col_id | val_nr | img_nr
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- -
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
まとめ
集計関数sum()を使うことを思いつかないとなかなか解答に辿り着くのが難しかったようです。
一旦、気づいてしまうとエレガントに解けて、面白いかと思います。
もう少し簡単にした問題も作成しましたので、予備練習としてこちらの方も解いてみてください。
エレガントにベクトル内積計算
