(57)【要約】【課題】クロネッカー積を含む行列演算の計算量を低減すること。【解決手段】本発明の演算方法は、行列Ａ，Ｂのクロネッカー積とベクトルｘとの乗算結果であるベクトルｙを演算する場合において、行列Ａ，Ｂのクロネッカー積を直接計算せずに、ベクトルｘとの内積計算を行う。【選択図】図２
2011086148.tif 000002
【特許請求の範囲】
【請求項１】
クロネッカー積を含む行列演算を行う演算装置であって、
行数がｎA、列数がｍAである行列Ａと、行数がｎB、列数がｍBである行列Ｂと、が与えられたときのクロネッカー積を
【数１】
2011086148.tif 000035
とし、
【数２】
2011086148.tif 000036
を大きさｎAｎB、
【数３】
2011086148.tif 000037
を大きさｍAｍBのベクトルとし、
【数４】
2011086148.tif 000038
を演算する場合において、
【数５】
2011086148.tif 000039
の第ｉ成分を、／を整数の除算の商、％を剰余と表記して
【数６】
2011086148.tif 000040
と変形する変形手段と、
【数７】
2011086148.tif 000041
を計算し、
【数８】
2011086148.tif 000042
とおく第１の演算手段と、
ＡとＣから
【数９】
2011086148.tif 000043
を計算し、
【数１０】
2011086148.tif 000044
を求める第２の演算手段と、を有する演算装置。
【請求項２】
行列Ａを、所定の速度以上にアクセスできる領域に格納し得る行列に制限し、行列Ａの残りを行列Ｂとする、請求項１に記載の演算装置。
【請求項３】
クロネッカー積を含む行列演算を行う演算方法であって、
行数がｎA、列数がｍAである行列Ａと、行数がｎB、列数がｍBである行列Ｂと、が与えられたときのクロネッカー積を
【数１１】
2011086148.tif 000045
とし、
【数１２】
2011086148.tif 000046
を大きさｎAｎB、
【数１３】
2011086148.tif 000047
を大きさｍAｍBのベクトルとし、
【数１４】
2011086148.tif 000048
を演算する場合において、
【数１５】
2011086148.tif 000049
の第ｉ成分を、／を整数の除算の商、％を剰余と表記して
【数１６】
2011086148.tif 000050
と変形する変形ステップと、
【数１７】
2011086148.tif 000051
を計算し、
【数１８】
2011086148.tif 000052
とおく第１の演算ステップと、
ＡとＣから
【数１９】
2011086148.tif 000053
を計算し、
【数２０】
2011086148.tif 000054
を求める第２の演算ステップと、を有する演算方法。
【請求項４】
行列Ａを、所定の速度以上にアクセスできる領域に格納し得る行列に制限し、行列Ａの残りを行列Ｂとする、請求項３に記載の演算方法。
【請求項５】
クロネッカー積を含む行列演算を行う演算装置に、
行数がｎA、列数がｍAである行列Ａと、行数がｎB、列数がｍBである行列Ｂと、が与えられたときのクロネッカー積を
【数２１】
2011086148.tif 000055
とし、
【数２２】
2011086148.tif 000056
を大きさｎAｎB、
【数２３】
2011086148.tif 000057
を大きさｍAｍBのベクトルとし、
【数２４】
2011086148.tif 000058
を演算する場合において、
【数２５】
2011086148.tif 000059
の第ｉ成分を、／を整数の除算の商、％を剰余と表記して
【数２６】
2011086148.tif 000060
と変形する変形手順と、
【数２７】
2011086148.tif 000061
を計算し、
【数２８】
2011086148.tif 000062
とおく第１の演算手順と、
ＡとＣから
【数２９】
2011086148.tif 000063
を計算し、
【数３０】
2011086148.tif 000064
を求める第２の演算手順と、を実行させる演算プログラム。
【請求項６】
行列Ａを、所定の速度以上にアクセスできる領域に格納し得る行列に制限し、行列Ａの残りを行列Ｂとする、請求項５に記載の演算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クロネッカー積で表現できる行列に関する行列演算を行うアルゴリズムに関する。
【背景技術】
【０００２】
従来、クロネッカー積で表現できる行列に関する行列演算を行うアルゴリズムにおいては、クロネッカー積を最初に計算し、その結果（結果行列と呼ぶ）を保持しアルゴリズムを実行する演算方法が存在した（非特許文献１参照。以下、「従来手法」と称す）。
【０００３】
クロネッカー積で表現できるアルゴリズムのほとんどは、クロネッカー積を計算した後にベクトル演算を含む行列演算を行う。
【０００４】
例えば、再構築計算における反復ベイズ手法では結果行列とベクトル間で乗算を行う。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】五十嵐  大、千田  浩司、高橋  克己、「多値属性に適用可能な効率的プライバシー保護クロス集計」、コンピュータセキュリティシンポジウム２００８（ＣＳＳ２００８）、２００８年１０月８日〜１０日
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、上記の従来手法では、全体のクロネッカー積を計算しないことでメモリの消費を抑えているが、計算量が増加するという問題に対し、メモリの削減という実装方式からの高速化を提案するに留まっており、根本的な計算量は低減されていなかった。
【０００７】
そこで、本発明の目的は、クロネッカー積を含む行列演算の計算量を低減することができる演算装置、演算方法、演算プログラムを提供することにある。
【課題を解決するための手段】
【０００８】
本発明の演算装置は、
クロネッカー積を含む行列演算を行う演算装置であって、
行数がｎA、列数がｍAである行列Ａと、行数がｎB、列数がｍBである行列Ｂと、が与えられたときのクロネッカー積を
【０００９】
【数１】
2011086148.tif 000003
【００１０】
とし、
【００１１】
【数２】
2011086148.tif 000004
【００１２】
を大きさｎAｎB、
【００１３】
【数３】
2011086148.tif 000005
【００１４】
を大きさｍAｍBのベクトルとし、
【００１５】
【数４】
2011086148.tif 000006
【００１６】
を演算する場合において、
【００１７】
【数５】
2011086148.tif 000007
【００１８】
の第ｉ成分を、／を整数の除算の商、％を剰余と表記して
【００１９】
【数６】
2011086148.tif 000008
【００２０】
と変形する変形手段と、
【００２１】
【数７】
2011086148.tif 000009
【００２２】
を計算し、
【００２３】
【数８】
2011086148.tif 000010
【００２４】
とおく第１の演算手段と、
ＡとＣから
【００２５】
【数９】
2011086148.tif 000011
【００２６】
を計算し、
【００２７】
【数１０】
2011086148.tif 000012
【００２８】
を求める第２の演算手段と、を有する。
【発明の効果】
【００２９】
本発明によれば、クロネッカー積を含む行列演算の計算量を低減することができ、クロネッカー積を含む行列演算の高速化が図れるという効果が得られる。
【図面の簡単な説明】
【００３０】
【図１】本発明の一実施形態の演算装置の構成を示すブロック図である。
【図２】図１に示した演算装置による、クロネッカー積を含む行列演算の演算方法を説明するフローチャートである。
【発明を実施するための形態】
【００３１】
以下に、本発明を実施するための形態について図面を参照して説明する。
【００３２】
図１に示すように、本実施形態の演算装置１０は、変形手段１１と、第１の演算手段１２と、第２の演算手段１３と、を有し、クロネッカー積を含む行列演算を行う。
【００３３】
最初に用語を定義する。
【００３４】
今、行列をＡ，Ｂ，・・・、ベクトルを
【００３５】
【数１１】
2011086148.tif 000013
【００３６】
のように表記する。また、行列の行数を
【００３７】
【数１２】
2011086148.tif 000014
【００３８】
、列を
【００３９】
【数１３】
2011086148.tif 000015
【００４０】
とする。行列Ａの場合、ｎA×ｍAの大きさの行列と言える。
【００４１】
クロネッカー積
【００４２】
【数１４】
2011086148.tif 000016
【００４３】
とは、行列Ａ，Ｂが与えられたとき次のように定義される。
【００４４】
【数１５】
2011086148.tif 000017
【００４５】
以下、本発明における
【００４６】
【数１６】
2011086148.tif 000018
【００４７】
の演算方法について、図２を参照して説明する。ここで、
【００４８】
【数１７】
2011086148.tif 000019
【００４９】
は大きさｎAｎB、
【００５０】
【数１８】
2011086148.tif 000020
【００５１】
は大きさｍAｍBのベクトルである。
【００５２】
【数１９】
2011086148.tif 000021
【００５３】
の第ｉ成分を
【００５４】
【数２０】
2011086148.tif 000022
【００５５】
、／を整数の除算の商、％を剰余と表記すると
【００５６】
【数２１】
2011086148.tif 000023
【００５７】
と書ける。さらにこの式は、変形手段１１により、
【００５８】
【数２２】
2011086148.tif 000024
【００５９】
と変形でき（ステップＳ１）、
【００６０】
【数２３】
2011086148.tif 000025
【００６１】
の外に出すことが可能である。
【００６２】
結果、乗算回数を減らすことができる。この乗算回数の減少は、以下のようなアルゴリズムにしたがい、
【００６３】
【数２４】
2011086148.tif 000026
【００６４】
を直接計算せずに、ベクトル
【００６５】
【数２５】
2011086148.tif 000027
【００６６】
との内積計算を行うが故に可能となる。
［アルゴリズム］
まず、第１の演算手段１２により、
【００６７】
【数２６】
2011086148.tif 000028
【００６８】
を計算する（ステップＳ２）。
【００６９】
ここで、ｋは０からｎA−１の間の値を、（ｉ％ｍB）は０からｍB−１の間の値をとるため、ｋを行番号、（ｉ％ｍB）を列番号として行列表現すると、以下のようになる。
【００７０】
【数２７】
2011086148.tif 000029
【００７１】
とおく。
【００７２】
次に、第２の演算手段１３により、
ＡとＣから
【００７３】
【数２８】
2011086148.tif 000030
【００７４】
を計算する（ステップＳ３）。
【００７５】
【数２９】
2011086148.tif 000031
【００７６】
となる。
【００７７】
【数３０】
2011086148.tif 000032
【００７８】
を大きさｍB×ｍAの行列として見てやると、
【００７９】
【数３１】
2011086148.tif 000033
【００８０】
と行列の積で書ける。ここで、ｔは転置をさす。
【００８１】
ここで、非特許文献１の従来手法と本発明の提案手法とで乗算回数を比較すると、従来手法における乗算回数は、クロネッカー積の計算にｎAｍAｎBｍB、その後の
【００８２】
【数３２】
2011086148.tif 000034
【００８３】
との内積計算にｎAｍAｎBｍBとなり、合計２ｎAｍAｎBｍBとなる。
【００８４】
一方、本発明の提案手法における乗算回数は、ステップＳ２でｎBｍBｎA回、ステップＳ３でｍBｍAｎA回となるため、合計（ｎAｍB）（ｎB＋ｍA）となり、従来手法よりも計算量の次数が下がっていることが分かる。
【実施例１】
【００８５】
行列Ａ，Ｂが正方行列の場合、つまり、ｎA＝ｍAかつｎB＝ｍBの場合に、ｎAｎB＝Ｎとおくと、非特許文献１の従来手法における乗算回数は２Ｎ2となるのに対し、本発明の提案手法における乗算回数はＮ（ｎA＋ｎB）となり、
ｎA＜＜Ｎ，
ｎB＜＜Ｎ，
が成立しているような場合、計算量は２次から１次に下がる。
【実施例２】
【００８６】
非特許文献１などに開示された再構築計算における再構築処理アルゴリズム、特に反復ベイズ手法に対して本発明を適用することで、高速に統計分析を行うことが可能である。
【実施例３】
【００８７】
ＧＰＵ（Graphics Processing Unit）など並列計算デバイスを用いる場合、行列Ａを、演算装置の所定の速度以上に高速にアクセスできる領域に格納する。言い換えれば、行列Ａはこの領域に入る程度の行列に制限し、行列Ａの残りを行列Ｂとすることで、行列Ａは、低速なアクセス領域と高速なアクセス領域との間の通信を削減でき、実装からも高速化が可能である。
【実施例４】
【００８８】
クロネッカー積と演算を行うのが、ベクトルではなく、行列であっても本発明を適用できる。
【実施例５】
【００８９】
結果行列のサイズが大きくなる場合、３つ以上のクロネッカー積で表現し、例えば、Ａ，Ｂ，Ｃ行列とする。３つ以上の場合も、本発明を適用することが可能である。このときサイズが一番大きいものをＣとすることで、実施例３にある実装が有効になる。
【００９０】
上述したように本発明によれば、クロネッカー積を含む行列演算が非常に高速となる。
【００９１】
例えば、非特許文献１の反復ベイズ手法の計算において、ｎA＝ｍA＝ｎB＝ｍB＝１００００の場合を例に挙げる。
【００９２】
この場合、非特許文献１の従来手法における乗算回数は２×１００００4＝２×１０16となり、メモリ制約なしで１ＴＦＬＯＰＳ（Tera Floating point number Operations Per Second）と仮定して計算したとしても５時間程度かかってしまう。
【００９３】
一方、本発明の提案手法における乗算回数は、（ｎAｍB）（ｎB＋ｍA）であるから、２×１０12であり、２秒程度で計算できることとなり、１万倍の高速化が図れる。
【００９４】
実際、非特許文献１の従来手法をレコメンデーションなどに適用した場合は、行列サイズはこの程度、またはそれ以上になるため、本発明は大きな効果を発揮する。
【００９５】
なお、本発明の演算装置にて行われる演算方法は、コンピュータに実行させるための演算プログラムに適用してもよい。また、その演算プログラムを記憶媒体に格納することも可能であり、ネットワークを介して外部に提供することも可能である。
【産業上の利用可能性】
【００９６】
本発明は、行列演算を含み、かつクロネッカー積で記述できるアルゴリズムであれば、適用可能である。
【符号の説明】
【００９７】
１０    演算装置
１１    変形手段
１２    第１の演算手段
１３    第２の演算手段
【図１】
2011086148.tif 000065
【図２】
2011086148.tif 000066