演算装置、演算方法および演算プログラム
【課題】２値行列と実数ベクトルとの行列演算を効率的に実行する。
【解決手段】演算装置１００は、Ｍ行Ｎ列（Ｍ、Ｎは整数）の２値行列のデータを入力するデータ入力部と、Ｎ次元の実数ベクトルを入力するベクトル入力部と、前記データ入力部により入力された２値行列のデータを、ゼロサプレス型二分決定グラフ（ＺＤＤ）のデータ構造に変換した変換データを構築する構築部と、前記構築部により構築された変換データと、前記ベクトル入力部により入力された実数ベクトルとの行列演算を実行する演算部と、前記演算部による演算結果を出力する出力部とを有する。
【解決手段】演算装置１００は、Ｍ行Ｎ列（Ｍ、Ｎは整数）の２値行列のデータを入力するデータ入力部と、Ｎ次元の実数ベクトルを入力するベクトル入力部と、前記データ入力部により入力された２値行列のデータを、ゼロサプレス型二分決定グラフ（ＺＤＤ）のデータ構造に変換した変換データを構築する構築部と、前記構築部により構築された変換データと、前記ベクトル入力部により入力された実数ベクトルとの行列演算を実行する演算部と、前記演算部による演算結果を出力する出力部とを有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、演算装置、演算方法および演算プログラムに関する。
【背景技術】
【０００２】
計算機上で動作させることにより、例えば、０（ゼロ）と、０（ゼロ）以外の数を要素に持つＭ行Ｎ列の２値行列と、Ｎ次元の実数ベクトルとの行列演算を行うライブラリが提案されている（非特許文献１参照）。例えば、このライブラリでは、行列が疎な場合、すなわち、非零である要素数をＫとしたときにＫ≪ＭＮである場合には、非零成分のみについて行列計算を行う。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】「SPARSKIT：a basic tool kit for sparse matrix computations（Version2）」．Datasheet．[Online]．Youcef Saad，University of Minnesota，Department of Computer Science and Engineering，June 6 1994，pages 3-12．Retrieved from the Internet：＜URL：http://www-users.cs.umn.edu/~saad/software/SPARSKIT/index.html＞
【発明の概要】
【発明が解決しようとする課題】
【０００４】
一般に、Ｍ行Ｎ列の２値行列と、Ｎ次元の実数ベクトルとの行列演算を行う場合には、「Ｏ（ＭＮ）」の演算量に応じた計算時間および記憶容量とが必要となる。なお、「Ｏ（オー）」は行列演算のオーダーを示し、「ＭＮ」は要素数を示す。一方で、上述したライブラリでは、行列が疎な場合、すなわち、非零である要素数「Ｋ」がＫ≪ＭＮである場合に、非零成分のみについて行列計算を行うので、「Ｏ（Ｋ）」の演算量に応じた計算時間および記憶容量が必要となる。このように、上述したライブラリにより行列演算を行う場合には、非零である要素数「Ｋ」に応じた計算時間および記憶容量が行列演算に必要となる。このため、上述したライブラリにより要素数が膨大な行列について演算を行う場合、演算量も膨大となる結果、演算に必要となる計算時間および記憶容量の規模が大きくなってしまうという問題がある。
【０００５】
本発明は、上記に鑑みてなされたものであって、２値行列と実数ベクトルとの行列演算を効率的に実行することが可能な演算装置、演算方法および演算プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上述した課題を解決し、目的を達成するために、本発明は、２値行列とＮ次元の実数ベクトルとの行列演算を行う演算装置であって、Ｍ行Ｎ列（Ｍ、Ｎは整数）の前記２値行列のデータを入力するデータ入力部と、Ｎ次元（Ｎは整数）の前記実数ベクトルを入力するベクトル入力部と、前記データ入力部により入力された前記２値行列のデータを、二分決定グラフのデータ構造に変換した変換データを構築する構築部と、前記構築部により構築された前記変換データと、前記ベクトル入力部により入力された前記実数ベクトルとの行列演算を実行する演算部と、前記演算部による演算結果を出力する出力部とを有することを特徴とする。
【０００７】
また、本発明は、２値行列とＮ次元の実数ベクトルとの行列演算をコンピュータにより実行される演算方法であって、Ｍ行Ｎ列（Ｍ、Ｎは整数）の前記２値行列のデータを入力するデータ入力工程と、Ｎ次元（Ｎは整数）の前記実数ベクトルを入力するベクトル入力工程と、前記データ入力工程により入力された前記２値行列のデータを、二分決定グラフのデータ構造に変換した変換データを構築する構築工程と、前記構築工程により構築された前記変換データと、前記ベクトル入力部により入力された前記実数ベクトルとの行列演算を実行する演算工程と、前記演算工程による演算結果を出力する出力工程とを実行することを特徴とする。
【０００８】
また、本発明は、２値行列とＮ次元の実数ベクトルとの行列演算を行うコンピュータに実行させるための演算プログラムであって、前記コンピュータに、Ｍ行Ｎ列（Ｍ、Ｎは整数）の前記２値行列のデータを入力するデータ入力手順と、Ｎ次元（Ｎは整数）の前記実数ベクトルを入力するベクトル入力手順と、前記データ入力手順により入力された前記２値行列のデータを、二分決定グラフのデータ構造に変換した変換データを構築する構築手順と、前記構築手順により構築された前記変換データと、前記ベクトル入力手順により入力された前記実数ベクトルとの行列演算を実行する演算手順と、前記演算手順による演算結果を出力する出力手順とを実行させることを特徴とする。
【発明の効果】
【０００９】
本発明によれば、２値行列と実数ベクトルとの行列演算を効率的に実行できるという効果を奏する。
【図面の簡単な説明】
【００１０】
【図１】図１は、実施例１に係る演算装置の構成を示す機能ブロック図である。
【図２】図２は、データ入力部が入力する２値行列の一例を示す図である。
【図３】図３は、ＺＤＤの一例を示す図である。
【図４】図４は、図３に示すＺＤＤに対応するノード表の一例を示す図である。
【図５】図５は、ＺＤＤ構築部１２０により構築されるＺＤＤの一例を示す図である。
【図６】図６は、ＺＤＤ構築部１２０により構築されたＺＤＤに対応するノード表の一例を示す図である。
【図７】図７は、図２に示す行列の１行目のデータについて構築したＺＤＤを示す図である。
【図８】図８は、図７に対応するノード表を示す図である。
【図９】図９は、実施例１に係るＺＤＤ構築処理の流れを示す図である。
【図１０】図１０は、実施例１に係る行列と実数ベクトルとの積の計算処理の流れを示す図である。
【図１１】図１１は、行列演算処理の流れを示す図である。
【図１２】図１２は、演算プログラムを実行する電子機器の一例を示す図である。
【発明を実施するための形態】
【００１１】
以下に、図面を参照しつつ、本願に係る演算装置、演算方法および演算プログラムの各実施例について詳細に説明する。後述する実施例は一例にすぎず、本願に係る演算装置、演算方法および演算プログラムを限定するものではない。また、後述する各実施例は処理内容に矛盾を生じさせない範囲で適宜組み合わせることもできる。
【実施例１】
【００１２】
［演算装置の概要と特徴（実施例１）］
実施例１に係る演算装置は、２値行列と実数ベクトルとの行列演算を行うことを概要とする。そして、実施例１に係る演算装置は、２値行列を所定のデータ構造を用いて圧縮し、圧縮した２値行列を対象として演算を実行する点に特徴がある。
【００１３】
具体的には、実施例１に係る演算装置は、Ｍ行Ｎ列（Ｍ、Ｎは正の整数）の２値行列を、ゼロサプレス型二分決定グラフ（Zero-Suppressed Binary Decision Diagram，以下、適宜ＺＤＤと記載する）を用いたデータ構造に変換する。そして、実施例１に係る演算装置は、ＺＤＤと実数ベクトルとの積の演算を、ＺＤＤ上で再帰的なアルゴリズムとして実行する。すなわち、実施例１に係る演算装置は、２値行列をＺＤＤを用いたデータ構造に変換することにより２値行列のデータを圧縮して表現することができる。そして、実施例１に係る演算装置は、２値行列が有する非零の要素数「Ｋ」に応じた演算を実行するのではなく、２値行列をＺＤＤを用いたデータ構造に変換したときのＺＤＤのノード数「Ｗ」に応じた演算を実行できるようになる。このようなことから、実施例１に係る演算装置は、２値行列と実数ベクトルとの積の演算に必要となる計算時間や記憶容量を減らすことができ、行列演算を効率的に実行できる。
【００１４】
［演算装置の構成（実施例１）］
図１は、実施例１に係る演算装置の構成を示す機能ブロック図である。実施例１に係る演算装置１００は、例えば、所定のプログラムなどに記述された手順に従い、所定の演算処理を行うパーソナルコンピュータやワークステーション、オフコンなどに相当する。なお、図１では、演算装置１００を説明する上で必要となる機能を図示し、中央演算装置や主記憶装置、補助記憶装置などの一般的な機能の図示は省略する。
【００１５】
図１に示すように、実施例１に係る演算装置１００は、データ入力部１１０と、ＺＤＤ構築部１２０と、データ記憶部１３０と、ベクトル入力部１４０と、行列演算実行部１５０と、計算結果出力部１６０とを有する。
【００１６】
データ入力部１１０は、Ｍ行Ｎ列（Ｍ、Ｎは正の整数）の２値行列（要素が０もしくは１の値である行列）を入力する。図２は、データ入力部が入力する２値行列の一例を示す図である。図２に示すように、データ入力部１１０は、例えば、３行３列の２値行列を入力する。なお、データ入力部１１０は、例えば、キーボードやマウスなどのユーザインターフェースや、ＵＳＢ（Universal Serial Bus）やイーサネット（登録商標）などのハードウェアインターフェースなどを介して２値行列を入力する。
【００１７】
ＺＤＤ構築部１２０は、データ入力部１１０により入力されたＭ行Ｎ列の２値行列から、ＺＤＤ（Zero-Suppressed Binary Decision Diagram）を構築する。まず、ＺＤＤ構築部１２０によるＺＤＤの構築手順の説明に先立ち、ＺＤＤについて説明する。
【００１８】
ＺＤＤは、組み合わせ集合を２分グラフの形で保持するデータ構造である。ここで、組み合わせ集合とは、あるアイテムの集合Ａ＝｛ａ１，ａ２，…，｝に対して、ｅ⊆Ａであるようなｅを要素とする集合である。一例を挙げれば、集合Ｂ＝｛ａ，ｂ，ｃ｝がある場合に、集合｛｛ａ，ｂ｝，｛ｂ，ｃ｝，｛ａ，ｃ｝｝は、集合Ｂの組み合わせ集合ということになる。図３は、ＺＤＤの一例を示す図である。なお、図３は、組み合わせ集合｛｛ａ，ｂ｝，｛ｂ｝，｛ｃ｝｝のＺＤＤを表している。図３に示すように、ＺＤＤ「Ｉ１」は指向性を持ったグラフ構造で構成される。また、図３に示すように、ＺＤＤ「Ｉ１」は、「０または１」のラベルが貼り付けられた終端ノード（図３の四角いノード）と、「ａ，ｂまたはｃ」のラベルが貼り付けられた中間ノード（図３の丸いノード）との２種類のノードを有する。また、図３に示すように、中間ノードは、それぞれ、ＨＩリンク（実線矢印）およびＬＯリンク（点線矢印）を有する。中間ノードが有する各リンクは、それぞれが別の子ノードを指す。また、図３に示すように、ＺＤＤには、先頭ノードを表すポインタ「ｆ」が設けられる。このように、ＺＤＤは、終端ノード、中間ノード、ＨＩリンク、ＬＯリンクおよびポインタを有するグラフ構造によって組み合わせ集合を表現する。
【００１９】
例えば、ある組み合わせｅが、ＺＤＤが表す組み合わせ集合に含まれるか否かは、以下に説明する手続きにより判明する。まず、ＺＤＤの先頭ノードを表すポインタに沿って、先頭ノードに遷移する。そこで、先頭ノードのラベルが表すアイテムがｅに含まれているならＨＩリンクが指すノードに遷移し、そうでないならＬＯリンクが指すノードに遷移する。以上の手続きを最終的に終端ノードにたどり着くまで実行し、最終的にラベル１をもつ終端ノードに遷移し、かつｅに含まれるすべてのアイテムに対応するノードを遷移してきているなら、ｅは組み合わせ集合に含まれる。一方、以上の手続きを最終的に終端ノードにたどり着くまで実行し、最終的にラベル１をもつ終端ノードに遷移せず、かつｅに含まれるすべてのアイテムに対応するノードを遷移してきていないなら、ｅは組み合わせ集合に含まれない。
【００２０】
図４は、図３に示すＺＤＤに対応するノード表の一例を示す図である。図４に示すように、ＺＤＤは、コンピュータ上においては、ノードＩＤをインデックスとし、各要素を配列したノード表で表現される。図４に示すように、ノード表には、各要素として、ノードＩＤごとに、ノードのラベル、ＨＩリンク先のノードＩＤ、ＬＯリンク先のノードＩＤがそれぞれ格納されている。
【００２１】
ところで、ある組み合わせをＺＤＤで表現するときには、アイテム間にあらかじめ順序が定められている。具体的には、あるノードのラベルであるアイテムとその子ノードのラベルであるアイテムとを比較したときに、必ず子ノードのアイテムの順序が後になるようにするという制約がある。例えば、上述したＺＤＤ「Ｉ１」（図３）では、ラベル「ａ」、「ｂ」、「ｃ」が貼り付けられたアイテムの間に、「ａ」、「ｂ」、「ｃ」の順で順序が定められている。また、ノードＩＤがｉであるノードのＨＩリンク先となるノードのノードＩＤをＨＩ（ｉ）、ＬＯリンク先となるノードのノードＩＤをＬＯ（ｉ）とした場合に、上述したＺＤＤの配列（図４）では、ｉ＞２のときに、常にＨＩ（ｉ）＜ｉ，ＬＯ（ｉ）＜ｉが成り立つように構成されている。以下、ノードＩＤがｉであるノードのラベルをｖ（ｉ）、ＨＩリンク先のノードのノードＩＤをＨＩ（ｉ）、ＬＯリンク先のノードのノードＩＤをＬＯ（ｉ）と記述する。
【００２２】
ＺＤＤの説明に続いて、ＺＤＤ構築部１２０が、Ｍ行Ｎ列の２値行列からＺＤＤを構築する手順について説明する。ＺＤＤ構築部１２０は、データ入力部１１０からＭ行Ｎ列の２値行列を取得し、行列の各行について、１つの要素のみからなる集合を作成する。行列の各行について、ＺＤＤ構築部１２０により作成される１つの要素のみからなる集合は、例えば、以下に示す式（１）で表される。
【００２３】
【数１】
【００２４】
続いて、ＺＤＤ構築部１２０は、行列の各行について、１つの要素のみからなる集合を作成した後、それらの和集合を作成する。ＺＤＤ構築部１２０により作成される和集合は、例えば、以下に示す式（２）で表される。
【００２５】
【数２】
【００２６】
なお、上述した式（１）および（２）に示すａ（ｉ，ｊ）は、行列のｉ行目のＮ個の要素のうち、値が「１」である列番号を並べたものである。例えば、データ入力部１１０から取得した２値行列が、図２に示すような３行３列の２値行列で与えられたとすると、ａ（１，１）＝１，ａ（１，２）＝３となる。また、上述した式（１）および（２）に示すｂ（ｉ）は、行列のｉ行目のＮ個の要素のうち、値が「１」である要素の個数を示すものである。例えば、データ入力部１１０から取得した２値行列が、図２に示すような３行３列の２値行列で与えられたとすると、ｂ（１）＝２，ｂ（２）＝１，ｂ（３）＝１となる。また、上述した式（１）および（２）に示すＲｉは、行列のｉ行目に対応するシンボルを示すものであり、上述した式（１）および（２）に示すＣｉは、行列のｉ列目に対応するシンボルを示すものである。
【００２７】
このように、ＺＤＤ構築部１２０は、データ入力部１１０により入力された２値行列を、上述した式（２）に示すようにして圧縮して表現できる。
【００２８】
続いて、ＺＤＤ構築部１２０は、上述の式（２）で表わされる和集合を組み合わせ集合Ｆとして、組み合わせ集合ＦのＺＤＤを計算し、データ記憶部１３０に格納する。なお、組み合わせ集合と、その集合に出現するシンボルの順序とが与えられれば、既存の技術を利用して、ＺＤＤを対象とした演算を行うことによりＺＤＤを計算することができる。そこで、ＺＤＤ構築部１２０は、組み合わせ集合Ｆ（式（２））に出現するシンボルＲ１，Ｒ２，…，ＲＭ，Ｃ１，Ｃ２，…，ＣＮに対して、Ｒ１＜Ｒ２＜・・・＜ＲＭ＜Ｃ１＜Ｃ２＜・・・＜ＣＮという順序を与え、既存の技術を利用した演算を行うことにより、組み合わせ集合ＦのＺＤＤを計算する。なお、ＺＤＤを対象とした演算を行う既存の技術としては、例えば、Shin-ichi Minato，「Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems」，DAC’93，pp.272-277などがある。
【００２９】
図５は、ＺＤＤ構築部１２０により構築されるＺＤＤの一例を示す図である。図６は、ＺＤＤ構築部１２０により構築されたＺＤＤに対応するノード表の一例を示す図である。なお、図５および図６は、上述した式（２）で表される組み合わせ集合から構築されるＺＤＤである。ＺＤＤ構築部１２０は、組み合わせ集合Ｆと、組み合わせ集合Ｆに出現するシンボルの順序とが与えられると、既存技術を利用した演算を行うことにより、図５に示すようなＺＤＤ「Ｉ２」を構築できる。図５に示すように、ＺＤＤ「Ｉ２」は、ラベル「Ｒ１」，「Ｒ２」，「Ｒ３」，「Ｃ１」，「Ｃ２」，「Ｃ３」が貼り付けられた中間ノード（丸いノード）と、「０」または「１」のラベルが貼り付けられた終端ノード（四角いノード）とを有する。また、図５に示すように、ＺＤＤ「Ｉ２」は、中間ノードのうち、ポインタ「ｆ」が指すラベル「Ｒ１」が貼り付けられたノードを先頭ノードとする。また、図６に示すように、ＺＤＤ「Ｉ２」は、コンピュータ上において、ノードＩＤをインデックスとし、各要素を配列したノード表で表現される。ノード表のノードＩＤ「１」〜「８」は、図５に示すラベル「０」，「１」，「Ｃ３」，「Ｃ２」，「Ｃ１」，「Ｒ３」，「Ｒ２」，「Ｒ１」のノードにそれぞれ対応する。なお、ＺＤＤ構築部１２０により構築されるＺＤＤは、組み合わせ集合を可能な限り圧縮した形で表現することが可能なデータ構造である。もし、ＺＤＤ構築部１２０が、組み合わせ集合を全く圧縮することなく、ＺＤＤを構築したとする。この場合、ＺＤＤ構築部１２０は、２値行列の行数と、行列中の非零成分の個数分の中間ノードを有するＺＤＤとして、組み合わせ集合を表現することとなる。一方、ＺＤＤ構築部１２０は、組み合わせ集合で表される２値行列の各行をベクトルとして行同士を比較し、共通部分を可能な限り圧縮した構造でＺＤＤを構築したとする。この場合、ＺＤＤ構築部１２０は、共通部分を圧縮せずに構築したＺＤＤよりも、中間ノードの数を減らしたＺＤＤとして、組み合わせ集合を表現することができる。
【００３０】
ベクトル入力部１４０は、データ入力部１１０により入力された２値行列との積の計算対象であるＮ次元（Ｎは正の整数）の実数ベクトルを入力する。なお、ベクトル入力部１４０は、データ入力部１１０と同様に、ユーザインターフェースやハードウェアインターフェースなどを介してＮ次元の実数ベクトルを入力する。
【００３１】
行列演算実行部１５０は、ＺＤＤ構築部１２０により２値行列から構築されたＺＤＤと、ベクトル入力部１４０により入力されたＮ次元の実数ベクトル（以下、適宜Ｎ次元ベクトルと記載する）とを用いて、行列演算を実行する。
【００３２】
具体的には、行列演算実行部１５０は、以下に説明するように、２値行列から構築されたＺＤＤと、実数ベクトルとの積の演算を、ＺＤＤ上で再帰的なアルゴリズムとして実行する。まず、行列演算実行部１５０は、ベクトル入力部１４０からＮ次元ベクトルを取得し、取得したＮ次元ベクトルをｑ、ｉ番目の要素をｑｉと表す。続いて、行列演算実行部１５０は、データ記憶部１３０からＺＤＤを取得し、Ｎ次元ベクトルとの積を演算する。なお、Ｎ次元ベクトル「ｑ」と、ＺＤＤとの演算結果を、Ｍ次元ベクトルｐとする。行列演算実行部１５０は、まず、スコアを格納する要素数（Ｗ−Ｍ）の１次元配列scoreを用意し、すべての要素を０で初期化しておく。ここで、要素数（Ｗ−Ｍ）は、ＺＤＤの中間ノードのうち、列に対応するラベルを持つものの数である。次に、行列演算実行部１５０は、インデックス（ｉ）をｉ＝３に初期化する。続いて、行列演算実行部１５０は、ｖ（ｉ）が、Ｃ１〜ＣＮのいずれかに一致するか否かを判定する。ｖ（ｉ）は、ノードＩＤがｉであるノードのラベルである。ｖ（ｉ）が、Ｃ１〜ＣＮのいずれかに一致する場合には、行列演算実行部１５０は、１次元配列score［ｉ］の値を、ノードＩＤがｉであるノードの子ノードの１次元配列score［ＨＩ（ｉ）］と、ｖ（ｉ）＝Ｃｊとなるｊに対応するパラメータｑｊの和に更新する。ＨＩ（ｉ）は、ノードＩＤがｉであるノードのＨＩリンク先となるノードのノードＩＤである。なお、ノード表については、ＨＩ（ｉ）＜ｉが成り立っているので、score［ｉ］の値の計算は更新されたscore［ＨＩ（ｉ）］の値を利用して行うことができる。
【００３３】
一方、ｖ（ｉ）が、Ｃ１〜ＣＮのいずれにも一致しない場合には、行列演算実行部１５０は、ｐｋにscore［ＨＩ（ｉ）］の値を代入する。なお、ｋは、ｖ（ｉ）＝Ｒｋとなるときの行番号のことである。つまり、ｖ（ｉ）が、Ｃ１〜ＣＮのいずれにも一致しない場合、ｖ（ｉ）は、Ｒ１〜ＲＭのいずれかに一致するためである。
【００３４】
続いて、行列演算実行部１５０は、ＺＤＤの全てのノードについて１次元配列scoreの計算を完了したか（ｉ≦Ｗであるか）否かを判定する。全てのノードについて１次元配列scoreの計算を完了していない場合には、行列演算実行部１５０は、インデックス（ｉ）を１インクリメントして、上述したのと同様の手順で１次元配列scoreの計算を行う。一方、全てのノードについて１次元配列scoreの計算を完了している場合には、行列演算実行部１５０は、行列演算の結果ｐを後述する計算結果出力部１６０に送出して処理を終了する。
【００３５】
上述してきたように、行列演算実行部１５０による行列演算は、以下に示す式（３）のように計算できることを利用し、各ノードに計算途中の値を記憶することによって、最終的な計算結果ｐを得るものである。
【００３６】
【数３】
【００３７】
以下、図７および図８を用いて、行列演算実行部１５０による行列演算について補足説明する。図７は、図２に示す行列の１行目のデータについて構築したＺＤＤを示す図である。図８は、図７に対応するノード表を示す図である。行列演算実行部１５０は、図７に示すＺＤＤ「Ｉ３」を構成するノードのうち、ノードＩＤが３であるノードについて、score［３］＝ｑ３とする。続いて、行列演算実行部１５０は、図７に示すＺＤＤ「Ｉ３」を構成するノードのうち、ノードＩＤが４であるノードについて、score［４］＝ｑ１＋ｑ３とし、最終的に、ｐ１＝ｑ１＋ｑ３を計算する。
【００３８】
上述してきたように、行列演算実行部１５０は、ＺＤＤと実数ベクトルとの積の演算を、ＺＤＤのノード数（Ｗ）に比例する時間で演算の処理を終了することができる。すなわち、行列演算実行部１５０は、演算量「Ｏ（Ｗ）」に応じた計算時間および記憶容量で処理を行うことができ、演算量「Ｏ（ＭＮ）」や演算量「Ｏ（Ｋ）」よりも、必要となる計算時間や記憶容量を削減できる。上述してきた方法により、ＺＤＤと実数ベクトルとの積の演算量を、「Ｏ（Ｗ）」に減らすことができる理由は次のとおりである。再帰的計算において各中間ノードに対応して計算されるscoreの値は、行ベクトルと実数ベクトルqとの乗算の途中までの演算結果を保持している。このとき、ある行ベクトルに対する乗算と、別の行ベクトルに対する乗算において、途中までの計算が同一である場合、その結果が同一のノードに保持されることになるので、計算回数を削減することができる。その結果、ＺＤＤと実数ベクトルとの積の演算量を「Ｏ（Ｗ）」に減らすことができる。
【００３９】
計算結果出力部１６０は、行列演算実行部１５０による演算の結果を外部へ出力する。例えば、計算結果出力部１６０は、ディスプレイやモニタ、プリンタなどの周辺機器へ演算の結果を出力する。
【００４０】
なお、上述してきた演算装置１００の各種処理機能は、例えば、電子回路や集積回路により実装することができる。電子回路としては、例えば、ＣＰＵ（Central Processing Unit）やＭＰＵ（Micro Processing Unit）がある。また、集積回路としては、例えば、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array)などがある。また、データ記憶部１３０は、例えば、ＲＡＭ（Random Access Memory）やフラッシュメモリ(flash memory)などの半導体メモリ素子を用いて実装することができる。
【００４１】
［演算装置による処理（実施例１）］
図９〜図１１を用いて、実施例１に係る演算装置による処理の流れを説明する。図９は、実施例１に係るＺＤＤ構築処理の流れを示す図である。図１０は、実施例１に係る行列と実数ベクトルとの積の計算処理の流れを示す図である。図１１は、行列演算処理の流れを示す図である。実施例１に係る演算装置１００による処理は、図９に示すＺＤＤ構築処理と、図１０および図１１に示す行列と実数ベクトルとの積の計算処理とに２分される。
【００４２】
（ＺＤＤ構築処理）
図９に示すように、データ入力部１１０は、Ｍ行Ｎ列の２値行列を入力する（Ｓ１０１）。続いて、ＺＤＤ構築部１２０は、Ｓ１０１で入力した行列の各行を入力として、組み合わせ集合Ｆを計算する（Ｓ１０２）。そして、ＺＤＤ構築部１２０は、Ｓ１０２で計算した組み合わせ集合Ｆに対応するＺＤＤを構築する（Ｓ１０３）。
【００４３】
具体的には、ＺＤＤ構築部１２０は、データ入力部１１０からＭ行Ｎ列の２値行列を取得し、行列の各行について、１つの要素のみからなる集合を作成する（式（１）参照）。続いて、ＺＤＤ構築部１２０は、行列の各行について、１つの要素のみからなる集合を作成した後、それらの和集合を作成し、組み合わせ集合Ｆを作成する（式（２）参照）。そして、ＺＤＤ構築部１２０は、組み合わせ集合Ｆ（式（２））に出現するシンボルＲ１，Ｒ２，…，ＲＭ，Ｃ１，Ｃ２，…，ＣＮに対して、Ｒ１＜Ｒ２＜・・・＜ＲＭ＜Ｃ１＜Ｃ２＜・・・＜ＣＮという順序を与え、既存の技術を利用した演算を行うことにより、組み合わせ集合Ｆに対応するＺＤＤを構築する。
【００４４】
（行列と実数ベクトルとの積の計算処理）
図１０に示すように、ベクトル入力部１４０は、Ｎ次元の実数ベクトルを入力する（Ｓ２０１）。続いて、行列演算実行部１５０は、ＺＤＤ構築部１２０により２値行列から構築されたＺＤＤと、ベクトル入力部１４０により入力されたＮ次元の実数ベクトルとを用いて、行列演算を実行する（Ｓ２０２）。
【００４５】
（行列演算処理）
行列演算実行部１５０は、図１１に示す処理を実行する前に、ベクトル入力部１４０からＮ次元ベクトルｑを取得し、データ記憶部１３０からＺＤＤを取得して、スコアを格納する要素数（Ｗ−Ｍ）の１次元配列scoreを用意し、すべての要素を０で初期化しておく。以上の準備が完了した後、行列演算実行部１５０は、インデックス（ｉ）をｉ＝３に初期化する（Ｓ３０１）。
【００４６】
続いて、行列演算実行部１５０は、ｖ（ｉ）が、Ｃ１〜ＣＮのいずれかに一致するか否か（ｖ（ｉ）＝Ｃｊ（１≦ｊ≦Ｎ）？）を判定する（Ｓ３０２）。判定の結果、ｖ（ｉ）が、Ｃ１〜ＣＮのいずれかに一致する場合には（Ｓ３０２、Ｙｅｓ）、行列演算実行部１５０は、score［ｉ］の値を、score（ＨＩ（ｉ））＋ｑｊに更新する（Ｓ３０３）。
【００４７】
続いて、行列演算実行部１５０は、ｉ≦Ｗであるか否かを判定する（Ｓ３０４）。判定の結果、ｉ≦Ｗである場合には（Ｓ３０４、Ｙｅｓ）、行列演算実行部１５０は、ＺＤＤの全てのノードについてscoreの計算を完了しているものとして、演算結果ｐを計算結果出力部１５０に送出して（Ｓ３０５）、行列演算処理を終了する。一方、判定の結果、ｉ≦Ｗではない場合には（Ｓ３０４、Ｎｏ）、行列演算実行部１５０は、ＺＤＤの全てのノードについてscoreの計算を完了していないものとして、ｉの値を１インクリメント（ｉ←ｉ＋１）して（ステップＳ３０６）、上述のＳ３０２に戻る。
【００４８】
上述したステップＳ３０２において、判定の結果、ｖ（ｉ）が、Ｃ１〜ＣＮのいずれにも一致しない場合には（Ｓ３０２、Ｎｏ）、行列演算実行部１５０は、ｐｋ←score（ＨＩ（ｉ））として（Ｓ３０７）、上述のＳ３０５に移行する。
【００４９】
［実施例１による効果］
上述してきたように、実施例１に係る演算装置１００は、Ｍ行Ｎ列（Ｍ、Ｎは正の整数）の２値行列を、ＺＤＤを用いたデータ構造に変換する（図５、６等）。そして、実施例１に係る演算装置は、ＺＤＤと実数ベクトルとの積の演算を、ＺＤＤ上で再帰的なアルゴリズムとして実行する（図１１等）。すなわち、実施例１に係る演算装置は、２値行列をＺＤＤを用いたデータ構造に変換することにより２値行列のデータを圧縮して表現することができる。そして、実施例１に係る演算装置は、２値行列が有する非零の要素数「Ｋ」に応じた演算を実行するのではなく、２値行列をＺＤＤを用いたデータ構造に変換したときのＺＤＤのノード数「Ｗ」に応じた演算を実行できるようになる。このようなことから、実施例１に係る演算装置は、２値行列と実数ベクトルとの積の演算に必要となる計算時間を減らすことができ、行列演算を効率的に実行できる。
【００５０】
また、疎な２値行列のデータを圧縮するので、演算に必要となる記憶容量を削減することもできる。
【００５１】
また、上述の実施例１では、図９に示すＺＤＤ構築処理と、図１０および図１１に示す行列と実数ベクトルとの積の計算処理とを２分して説明したが、図９に示すＺＤＤ構築処理と、図１０および図１１に示す行列と実数ベクトルとの積の計算処理とをシリアルに実行してもよい。
【００５２】
なお、上述してきた実施例１に係る演算装置は、各種数値計算や物理的なシミュレーション、各種情報管理などに幅広く適用することができる。特に、ある特定の２値行列が繰り返し利用される状況においては、一旦ＺＤＤによって２値行列を構築すれば、計算量削減の効果が見込まれる。
【実施例２】
【００５３】
以下、本発明にかかる演算装置、演算方法および演算プログラムの他の実施形態として実施例２を説明する。
【００５４】
（１）装置構成等
図１に示した演算装置１００の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、演算装置１００の分散または統合の具体的形態は図１に示すものに限られず、演算装置１００のＺＤＤ構築部１２０、データ記憶部１３０および行列演算実行部１５０を機能的に統合されていてもよい。このように、演算装置１００の各構成要素の全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。
【００５５】
（２）演算プログラム
また、実施例１で説明した演算装置１００の各種の処理（例えば、図９〜１１等参照）は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどの電子機器で実行することによって実現することができる。そこで、以下では、図１２を用いて、実施例１で説明した演算装置１００と同様の機能を有する演算プログラムを実行する電子機器の一例を説明する。図１２は、演算プログラムを実行する電子機器の一例を示す図である。
【００５６】
図１２に示すように、演算装置１００が有する機能と同様の機能を有する電子機器２００は、ＣＰＵ（Central Processing Unit）２１０、入力部２２０、出力部２３０、メモリ２４０およびハードディスク装置２５０を有する。そして、ＣＰＵ２１０、入力部２２０、出力部２３０、メモリ２４０およびハードディスク装置２５０は、バス２６０を介して接続される。
【００５７】
ＣＰＵ２１０は、各種演算処理を実行する。なお、電子機器２００は、ＣＰＵ２１０の代わりに、例えば、ＭＰＵ（Micro Processing Unit）などの電子回路、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ(Field Programmable Gate Array)などの集積回路を用いることもできる。
【００５８】
入力部２２０は２値行列などの各種情報を入力する。また、出力部２３０は行列演算の結果などを出力する。また、メモリ２４０は、２値行列を変換したＺＤＤなどの各種情報を一時的に記憶する。なお、メモリ２４０は、例えば、ＲＡＭ（Random Access Memory）やフラッシュメモリ(flash memory)などの半導体メモリ素子を用いて実装できる。また、ハードディスク装置２５０は、ＣＰＵ２１０による各種処理の実行に必要な情報を記憶する。
【００５９】
ハードディスク装置２５０には、演算装置１００が有する機能と同様の機能を発揮する演算プログラム２５１および演算用データ２５２が記憶されている。なお、この演算プログラム２５１を適宜分散させて、ネットワークを介して通信可能に接続された他のコンピュータの記憶部に記憶させておくこともできる。
【００６０】
そして、ＣＰＵ２１０が、演算プログラム２５１をハードディスク装置２５０から読み出してメモリ２４０に展開することにより、図１２に示すように、演算プログラム２５１は演算プロセス２４１として機能する。演算プロセス２４１は、ハードディスク装置２５０から読み出した演算用データ２５２等の各種データを適宜メモリ２４０上の自身に割当てられた領域に展開し、この展開した各種データに基づいて各種処理を実行する。
【００６１】
なお、演算プロセス２４１は、例えば、上述した演算装置１００のＺＤＤ構築部１２０や行列演算実行部１５０などにより実行される処理、例えば、上述の図９〜１１などを用いて説明した処理を含む。
【００６２】
なお、上述した演算プログラム２５１については、必ずしも最初からハードディスク装置２５０に記憶させておく必要はない。例えば、電子機器２００が、フレキシブルディスク、ＣＤ−ＲＯＭ、ＤＶＤ、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」に予め記憶された演算プログラム２５１を読み出して実行するようにしてもよい。
【００６３】
さらには、電子機器２００が、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介して接続可能な「他のコンピュータ（またはサーバ）」などに格納された演算プログラム２５１を読み出して実行するようにしてもよい。
【００６４】
（３）演算方法
実施例１で説明した演算装置１００により、以下のような演算方法が実現される。
【００６５】
すなわち、２値行列とＮ次元の実数ベクトルとの行列演算を演算装置１００としてのコンピュータが実行する演算方法であって、コンピュータは、Ｍ行Ｎ列（Ｍ、Ｎは整数）の２値行列のデータを入力するデータ入力工程と（図９、Ｓ１０１）、Ｎ次元（Ｎは整数）の実数ベクトルを入力するベクトル入力工程と（図１０、Ｓ２０１）、データ入力工程により入力された２値行列のデータを、二分決定グラフのデータ構造に変換した変換データを構築する構築工程と（図９、Ｓ１０３）、構築工程により構築された変換データと、ベクトル入力部により入力された実数ベクトルとの行列演算を実行する演算工程と（図１０、Ｓ２０２、図１１）、演算工程による演算結果を出力する出力工程とを実行することを特徴とする演算方法が実現される。
【符号の説明】
【００６６】
１００ 演算装置
１１０ データ入力部
１２０ ＺＤＤ構築部
１３０ データ記憶部
１４０ ベクトル入力部
１５０ 行列演算実行部
１６０ 計算結果出力部
２００ 電子機器
２１０ ＣＰＵ
２２０ 入力部
２３０ 出力部
２４０ メモリ
２５０ ハードディスク装置
２６０ バス
【技術分野】
【０００１】
本発明は、演算装置、演算方法および演算プログラムに関する。
【背景技術】
【０００２】
計算機上で動作させることにより、例えば、０（ゼロ）と、０（ゼロ）以外の数を要素に持つＭ行Ｎ列の２値行列と、Ｎ次元の実数ベクトルとの行列演算を行うライブラリが提案されている（非特許文献１参照）。例えば、このライブラリでは、行列が疎な場合、すなわち、非零である要素数をＫとしたときにＫ≪ＭＮである場合には、非零成分のみについて行列計算を行う。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】「SPARSKIT：a basic tool kit for sparse matrix computations（Version2）」．Datasheet．[Online]．Youcef Saad，University of Minnesota，Department of Computer Science and Engineering，June 6 1994，pages 3-12．Retrieved from the Internet：＜URL：http://www-users.cs.umn.edu/~saad/software/SPARSKIT/index.html＞
【発明の概要】
【発明が解決しようとする課題】
【０００４】
一般に、Ｍ行Ｎ列の２値行列と、Ｎ次元の実数ベクトルとの行列演算を行う場合には、「Ｏ（ＭＮ）」の演算量に応じた計算時間および記憶容量とが必要となる。なお、「Ｏ（オー）」は行列演算のオーダーを示し、「ＭＮ」は要素数を示す。一方で、上述したライブラリでは、行列が疎な場合、すなわち、非零である要素数「Ｋ」がＫ≪ＭＮである場合に、非零成分のみについて行列計算を行うので、「Ｏ（Ｋ）」の演算量に応じた計算時間および記憶容量が必要となる。このように、上述したライブラリにより行列演算を行う場合には、非零である要素数「Ｋ」に応じた計算時間および記憶容量が行列演算に必要となる。このため、上述したライブラリにより要素数が膨大な行列について演算を行う場合、演算量も膨大となる結果、演算に必要となる計算時間および記憶容量の規模が大きくなってしまうという問題がある。
【０００５】
本発明は、上記に鑑みてなされたものであって、２値行列と実数ベクトルとの行列演算を効率的に実行することが可能な演算装置、演算方法および演算プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上述した課題を解決し、目的を達成するために、本発明は、２値行列とＮ次元の実数ベクトルとの行列演算を行う演算装置であって、Ｍ行Ｎ列（Ｍ、Ｎは整数）の前記２値行列のデータを入力するデータ入力部と、Ｎ次元（Ｎは整数）の前記実数ベクトルを入力するベクトル入力部と、前記データ入力部により入力された前記２値行列のデータを、二分決定グラフのデータ構造に変換した変換データを構築する構築部と、前記構築部により構築された前記変換データと、前記ベクトル入力部により入力された前記実数ベクトルとの行列演算を実行する演算部と、前記演算部による演算結果を出力する出力部とを有することを特徴とする。
【０００７】
また、本発明は、２値行列とＮ次元の実数ベクトルとの行列演算をコンピュータにより実行される演算方法であって、Ｍ行Ｎ列（Ｍ、Ｎは整数）の前記２値行列のデータを入力するデータ入力工程と、Ｎ次元（Ｎは整数）の前記実数ベクトルを入力するベクトル入力工程と、前記データ入力工程により入力された前記２値行列のデータを、二分決定グラフのデータ構造に変換した変換データを構築する構築工程と、前記構築工程により構築された前記変換データと、前記ベクトル入力部により入力された前記実数ベクトルとの行列演算を実行する演算工程と、前記演算工程による演算結果を出力する出力工程とを実行することを特徴とする。
【０００８】
また、本発明は、２値行列とＮ次元の実数ベクトルとの行列演算を行うコンピュータに実行させるための演算プログラムであって、前記コンピュータに、Ｍ行Ｎ列（Ｍ、Ｎは整数）の前記２値行列のデータを入力するデータ入力手順と、Ｎ次元（Ｎは整数）の前記実数ベクトルを入力するベクトル入力手順と、前記データ入力手順により入力された前記２値行列のデータを、二分決定グラフのデータ構造に変換した変換データを構築する構築手順と、前記構築手順により構築された前記変換データと、前記ベクトル入力手順により入力された前記実数ベクトルとの行列演算を実行する演算手順と、前記演算手順による演算結果を出力する出力手順とを実行させることを特徴とする。
【発明の効果】
【０００９】
本発明によれば、２値行列と実数ベクトルとの行列演算を効率的に実行できるという効果を奏する。
【図面の簡単な説明】
【００１０】
【図１】図１は、実施例１に係る演算装置の構成を示す機能ブロック図である。
【図２】図２は、データ入力部が入力する２値行列の一例を示す図である。
【図３】図３は、ＺＤＤの一例を示す図である。
【図４】図４は、図３に示すＺＤＤに対応するノード表の一例を示す図である。
【図５】図５は、ＺＤＤ構築部１２０により構築されるＺＤＤの一例を示す図である。
【図６】図６は、ＺＤＤ構築部１２０により構築されたＺＤＤに対応するノード表の一例を示す図である。
【図７】図７は、図２に示す行列の１行目のデータについて構築したＺＤＤを示す図である。
【図８】図８は、図７に対応するノード表を示す図である。
【図９】図９は、実施例１に係るＺＤＤ構築処理の流れを示す図である。
【図１０】図１０は、実施例１に係る行列と実数ベクトルとの積の計算処理の流れを示す図である。
【図１１】図１１は、行列演算処理の流れを示す図である。
【図１２】図１２は、演算プログラムを実行する電子機器の一例を示す図である。
【発明を実施するための形態】
【００１１】
以下に、図面を参照しつつ、本願に係る演算装置、演算方法および演算プログラムの各実施例について詳細に説明する。後述する実施例は一例にすぎず、本願に係る演算装置、演算方法および演算プログラムを限定するものではない。また、後述する各実施例は処理内容に矛盾を生じさせない範囲で適宜組み合わせることもできる。
【実施例１】
【００１２】
［演算装置の概要と特徴（実施例１）］
実施例１に係る演算装置は、２値行列と実数ベクトルとの行列演算を行うことを概要とする。そして、実施例１に係る演算装置は、２値行列を所定のデータ構造を用いて圧縮し、圧縮した２値行列を対象として演算を実行する点に特徴がある。
【００１３】
具体的には、実施例１に係る演算装置は、Ｍ行Ｎ列（Ｍ、Ｎは正の整数）の２値行列を、ゼロサプレス型二分決定グラフ（Zero-Suppressed Binary Decision Diagram，以下、適宜ＺＤＤと記載する）を用いたデータ構造に変換する。そして、実施例１に係る演算装置は、ＺＤＤと実数ベクトルとの積の演算を、ＺＤＤ上で再帰的なアルゴリズムとして実行する。すなわち、実施例１に係る演算装置は、２値行列をＺＤＤを用いたデータ構造に変換することにより２値行列のデータを圧縮して表現することができる。そして、実施例１に係る演算装置は、２値行列が有する非零の要素数「Ｋ」に応じた演算を実行するのではなく、２値行列をＺＤＤを用いたデータ構造に変換したときのＺＤＤのノード数「Ｗ」に応じた演算を実行できるようになる。このようなことから、実施例１に係る演算装置は、２値行列と実数ベクトルとの積の演算に必要となる計算時間や記憶容量を減らすことができ、行列演算を効率的に実行できる。
【００１４】
［演算装置の構成（実施例１）］
図１は、実施例１に係る演算装置の構成を示す機能ブロック図である。実施例１に係る演算装置１００は、例えば、所定のプログラムなどに記述された手順に従い、所定の演算処理を行うパーソナルコンピュータやワークステーション、オフコンなどに相当する。なお、図１では、演算装置１００を説明する上で必要となる機能を図示し、中央演算装置や主記憶装置、補助記憶装置などの一般的な機能の図示は省略する。
【００１５】
図１に示すように、実施例１に係る演算装置１００は、データ入力部１１０と、ＺＤＤ構築部１２０と、データ記憶部１３０と、ベクトル入力部１４０と、行列演算実行部１５０と、計算結果出力部１６０とを有する。
【００１６】
データ入力部１１０は、Ｍ行Ｎ列（Ｍ、Ｎは正の整数）の２値行列（要素が０もしくは１の値である行列）を入力する。図２は、データ入力部が入力する２値行列の一例を示す図である。図２に示すように、データ入力部１１０は、例えば、３行３列の２値行列を入力する。なお、データ入力部１１０は、例えば、キーボードやマウスなどのユーザインターフェースや、ＵＳＢ（Universal Serial Bus）やイーサネット（登録商標）などのハードウェアインターフェースなどを介して２値行列を入力する。
【００１７】
ＺＤＤ構築部１２０は、データ入力部１１０により入力されたＭ行Ｎ列の２値行列から、ＺＤＤ（Zero-Suppressed Binary Decision Diagram）を構築する。まず、ＺＤＤ構築部１２０によるＺＤＤの構築手順の説明に先立ち、ＺＤＤについて説明する。
【００１８】
ＺＤＤは、組み合わせ集合を２分グラフの形で保持するデータ構造である。ここで、組み合わせ集合とは、あるアイテムの集合Ａ＝｛ａ１，ａ２，…，｝に対して、ｅ⊆Ａであるようなｅを要素とする集合である。一例を挙げれば、集合Ｂ＝｛ａ，ｂ，ｃ｝がある場合に、集合｛｛ａ，ｂ｝，｛ｂ，ｃ｝，｛ａ，ｃ｝｝は、集合Ｂの組み合わせ集合ということになる。図３は、ＺＤＤの一例を示す図である。なお、図３は、組み合わせ集合｛｛ａ，ｂ｝，｛ｂ｝，｛ｃ｝｝のＺＤＤを表している。図３に示すように、ＺＤＤ「Ｉ１」は指向性を持ったグラフ構造で構成される。また、図３に示すように、ＺＤＤ「Ｉ１」は、「０または１」のラベルが貼り付けられた終端ノード（図３の四角いノード）と、「ａ，ｂまたはｃ」のラベルが貼り付けられた中間ノード（図３の丸いノード）との２種類のノードを有する。また、図３に示すように、中間ノードは、それぞれ、ＨＩリンク（実線矢印）およびＬＯリンク（点線矢印）を有する。中間ノードが有する各リンクは、それぞれが別の子ノードを指す。また、図３に示すように、ＺＤＤには、先頭ノードを表すポインタ「ｆ」が設けられる。このように、ＺＤＤは、終端ノード、中間ノード、ＨＩリンク、ＬＯリンクおよびポインタを有するグラフ構造によって組み合わせ集合を表現する。
【００１９】
例えば、ある組み合わせｅが、ＺＤＤが表す組み合わせ集合に含まれるか否かは、以下に説明する手続きにより判明する。まず、ＺＤＤの先頭ノードを表すポインタに沿って、先頭ノードに遷移する。そこで、先頭ノードのラベルが表すアイテムがｅに含まれているならＨＩリンクが指すノードに遷移し、そうでないならＬＯリンクが指すノードに遷移する。以上の手続きを最終的に終端ノードにたどり着くまで実行し、最終的にラベル１をもつ終端ノードに遷移し、かつｅに含まれるすべてのアイテムに対応するノードを遷移してきているなら、ｅは組み合わせ集合に含まれる。一方、以上の手続きを最終的に終端ノードにたどり着くまで実行し、最終的にラベル１をもつ終端ノードに遷移せず、かつｅに含まれるすべてのアイテムに対応するノードを遷移してきていないなら、ｅは組み合わせ集合に含まれない。
【００２０】
図４は、図３に示すＺＤＤに対応するノード表の一例を示す図である。図４に示すように、ＺＤＤは、コンピュータ上においては、ノードＩＤをインデックスとし、各要素を配列したノード表で表現される。図４に示すように、ノード表には、各要素として、ノードＩＤごとに、ノードのラベル、ＨＩリンク先のノードＩＤ、ＬＯリンク先のノードＩＤがそれぞれ格納されている。
【００２１】
ところで、ある組み合わせをＺＤＤで表現するときには、アイテム間にあらかじめ順序が定められている。具体的には、あるノードのラベルであるアイテムとその子ノードのラベルであるアイテムとを比較したときに、必ず子ノードのアイテムの順序が後になるようにするという制約がある。例えば、上述したＺＤＤ「Ｉ１」（図３）では、ラベル「ａ」、「ｂ」、「ｃ」が貼り付けられたアイテムの間に、「ａ」、「ｂ」、「ｃ」の順で順序が定められている。また、ノードＩＤがｉであるノードのＨＩリンク先となるノードのノードＩＤをＨＩ（ｉ）、ＬＯリンク先となるノードのノードＩＤをＬＯ（ｉ）とした場合に、上述したＺＤＤの配列（図４）では、ｉ＞２のときに、常にＨＩ（ｉ）＜ｉ，ＬＯ（ｉ）＜ｉが成り立つように構成されている。以下、ノードＩＤがｉであるノードのラベルをｖ（ｉ）、ＨＩリンク先のノードのノードＩＤをＨＩ（ｉ）、ＬＯリンク先のノードのノードＩＤをＬＯ（ｉ）と記述する。
【００２２】
ＺＤＤの説明に続いて、ＺＤＤ構築部１２０が、Ｍ行Ｎ列の２値行列からＺＤＤを構築する手順について説明する。ＺＤＤ構築部１２０は、データ入力部１１０からＭ行Ｎ列の２値行列を取得し、行列の各行について、１つの要素のみからなる集合を作成する。行列の各行について、ＺＤＤ構築部１２０により作成される１つの要素のみからなる集合は、例えば、以下に示す式（１）で表される。
【００２３】
【数１】
【００２４】
続いて、ＺＤＤ構築部１２０は、行列の各行について、１つの要素のみからなる集合を作成した後、それらの和集合を作成する。ＺＤＤ構築部１２０により作成される和集合は、例えば、以下に示す式（２）で表される。
【００２５】
【数２】
【００２６】
なお、上述した式（１）および（２）に示すａ（ｉ，ｊ）は、行列のｉ行目のＮ個の要素のうち、値が「１」である列番号を並べたものである。例えば、データ入力部１１０から取得した２値行列が、図２に示すような３行３列の２値行列で与えられたとすると、ａ（１，１）＝１，ａ（１，２）＝３となる。また、上述した式（１）および（２）に示すｂ（ｉ）は、行列のｉ行目のＮ個の要素のうち、値が「１」である要素の個数を示すものである。例えば、データ入力部１１０から取得した２値行列が、図２に示すような３行３列の２値行列で与えられたとすると、ｂ（１）＝２，ｂ（２）＝１，ｂ（３）＝１となる。また、上述した式（１）および（２）に示すＲｉは、行列のｉ行目に対応するシンボルを示すものであり、上述した式（１）および（２）に示すＣｉは、行列のｉ列目に対応するシンボルを示すものである。
【００２７】
このように、ＺＤＤ構築部１２０は、データ入力部１１０により入力された２値行列を、上述した式（２）に示すようにして圧縮して表現できる。
【００２８】
続いて、ＺＤＤ構築部１２０は、上述の式（２）で表わされる和集合を組み合わせ集合Ｆとして、組み合わせ集合ＦのＺＤＤを計算し、データ記憶部１３０に格納する。なお、組み合わせ集合と、その集合に出現するシンボルの順序とが与えられれば、既存の技術を利用して、ＺＤＤを対象とした演算を行うことによりＺＤＤを計算することができる。そこで、ＺＤＤ構築部１２０は、組み合わせ集合Ｆ（式（２））に出現するシンボルＲ１，Ｒ２，…，ＲＭ，Ｃ１，Ｃ２，…，ＣＮに対して、Ｒ１＜Ｒ２＜・・・＜ＲＭ＜Ｃ１＜Ｃ２＜・・・＜ＣＮという順序を与え、既存の技術を利用した演算を行うことにより、組み合わせ集合ＦのＺＤＤを計算する。なお、ＺＤＤを対象とした演算を行う既存の技術としては、例えば、Shin-ichi Minato，「Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems」，DAC’93，pp.272-277などがある。
【００２９】
図５は、ＺＤＤ構築部１２０により構築されるＺＤＤの一例を示す図である。図６は、ＺＤＤ構築部１２０により構築されたＺＤＤに対応するノード表の一例を示す図である。なお、図５および図６は、上述した式（２）で表される組み合わせ集合から構築されるＺＤＤである。ＺＤＤ構築部１２０は、組み合わせ集合Ｆと、組み合わせ集合Ｆに出現するシンボルの順序とが与えられると、既存技術を利用した演算を行うことにより、図５に示すようなＺＤＤ「Ｉ２」を構築できる。図５に示すように、ＺＤＤ「Ｉ２」は、ラベル「Ｒ１」，「Ｒ２」，「Ｒ３」，「Ｃ１」，「Ｃ２」，「Ｃ３」が貼り付けられた中間ノード（丸いノード）と、「０」または「１」のラベルが貼り付けられた終端ノード（四角いノード）とを有する。また、図５に示すように、ＺＤＤ「Ｉ２」は、中間ノードのうち、ポインタ「ｆ」が指すラベル「Ｒ１」が貼り付けられたノードを先頭ノードとする。また、図６に示すように、ＺＤＤ「Ｉ２」は、コンピュータ上において、ノードＩＤをインデックスとし、各要素を配列したノード表で表現される。ノード表のノードＩＤ「１」〜「８」は、図５に示すラベル「０」，「１」，「Ｃ３」，「Ｃ２」，「Ｃ１」，「Ｒ３」，「Ｒ２」，「Ｒ１」のノードにそれぞれ対応する。なお、ＺＤＤ構築部１２０により構築されるＺＤＤは、組み合わせ集合を可能な限り圧縮した形で表現することが可能なデータ構造である。もし、ＺＤＤ構築部１２０が、組み合わせ集合を全く圧縮することなく、ＺＤＤを構築したとする。この場合、ＺＤＤ構築部１２０は、２値行列の行数と、行列中の非零成分の個数分の中間ノードを有するＺＤＤとして、組み合わせ集合を表現することとなる。一方、ＺＤＤ構築部１２０は、組み合わせ集合で表される２値行列の各行をベクトルとして行同士を比較し、共通部分を可能な限り圧縮した構造でＺＤＤを構築したとする。この場合、ＺＤＤ構築部１２０は、共通部分を圧縮せずに構築したＺＤＤよりも、中間ノードの数を減らしたＺＤＤとして、組み合わせ集合を表現することができる。
【００３０】
ベクトル入力部１４０は、データ入力部１１０により入力された２値行列との積の計算対象であるＮ次元（Ｎは正の整数）の実数ベクトルを入力する。なお、ベクトル入力部１４０は、データ入力部１１０と同様に、ユーザインターフェースやハードウェアインターフェースなどを介してＮ次元の実数ベクトルを入力する。
【００３１】
行列演算実行部１５０は、ＺＤＤ構築部１２０により２値行列から構築されたＺＤＤと、ベクトル入力部１４０により入力されたＮ次元の実数ベクトル（以下、適宜Ｎ次元ベクトルと記載する）とを用いて、行列演算を実行する。
【００３２】
具体的には、行列演算実行部１５０は、以下に説明するように、２値行列から構築されたＺＤＤと、実数ベクトルとの積の演算を、ＺＤＤ上で再帰的なアルゴリズムとして実行する。まず、行列演算実行部１５０は、ベクトル入力部１４０からＮ次元ベクトルを取得し、取得したＮ次元ベクトルをｑ、ｉ番目の要素をｑｉと表す。続いて、行列演算実行部１５０は、データ記憶部１３０からＺＤＤを取得し、Ｎ次元ベクトルとの積を演算する。なお、Ｎ次元ベクトル「ｑ」と、ＺＤＤとの演算結果を、Ｍ次元ベクトルｐとする。行列演算実行部１５０は、まず、スコアを格納する要素数（Ｗ−Ｍ）の１次元配列scoreを用意し、すべての要素を０で初期化しておく。ここで、要素数（Ｗ−Ｍ）は、ＺＤＤの中間ノードのうち、列に対応するラベルを持つものの数である。次に、行列演算実行部１５０は、インデックス（ｉ）をｉ＝３に初期化する。続いて、行列演算実行部１５０は、ｖ（ｉ）が、Ｃ１〜ＣＮのいずれかに一致するか否かを判定する。ｖ（ｉ）は、ノードＩＤがｉであるノードのラベルである。ｖ（ｉ）が、Ｃ１〜ＣＮのいずれかに一致する場合には、行列演算実行部１５０は、１次元配列score［ｉ］の値を、ノードＩＤがｉであるノードの子ノードの１次元配列score［ＨＩ（ｉ）］と、ｖ（ｉ）＝Ｃｊとなるｊに対応するパラメータｑｊの和に更新する。ＨＩ（ｉ）は、ノードＩＤがｉであるノードのＨＩリンク先となるノードのノードＩＤである。なお、ノード表については、ＨＩ（ｉ）＜ｉが成り立っているので、score［ｉ］の値の計算は更新されたscore［ＨＩ（ｉ）］の値を利用して行うことができる。
【００３３】
一方、ｖ（ｉ）が、Ｃ１〜ＣＮのいずれにも一致しない場合には、行列演算実行部１５０は、ｐｋにscore［ＨＩ（ｉ）］の値を代入する。なお、ｋは、ｖ（ｉ）＝Ｒｋとなるときの行番号のことである。つまり、ｖ（ｉ）が、Ｃ１〜ＣＮのいずれにも一致しない場合、ｖ（ｉ）は、Ｒ１〜ＲＭのいずれかに一致するためである。
【００３４】
続いて、行列演算実行部１５０は、ＺＤＤの全てのノードについて１次元配列scoreの計算を完了したか（ｉ≦Ｗであるか）否かを判定する。全てのノードについて１次元配列scoreの計算を完了していない場合には、行列演算実行部１５０は、インデックス（ｉ）を１インクリメントして、上述したのと同様の手順で１次元配列scoreの計算を行う。一方、全てのノードについて１次元配列scoreの計算を完了している場合には、行列演算実行部１５０は、行列演算の結果ｐを後述する計算結果出力部１６０に送出して処理を終了する。
【００３５】
上述してきたように、行列演算実行部１５０による行列演算は、以下に示す式（３）のように計算できることを利用し、各ノードに計算途中の値を記憶することによって、最終的な計算結果ｐを得るものである。
【００３６】
【数３】
【００３７】
以下、図７および図８を用いて、行列演算実行部１５０による行列演算について補足説明する。図７は、図２に示す行列の１行目のデータについて構築したＺＤＤを示す図である。図８は、図７に対応するノード表を示す図である。行列演算実行部１５０は、図７に示すＺＤＤ「Ｉ３」を構成するノードのうち、ノードＩＤが３であるノードについて、score［３］＝ｑ３とする。続いて、行列演算実行部１５０は、図７に示すＺＤＤ「Ｉ３」を構成するノードのうち、ノードＩＤが４であるノードについて、score［４］＝ｑ１＋ｑ３とし、最終的に、ｐ１＝ｑ１＋ｑ３を計算する。
【００３８】
上述してきたように、行列演算実行部１５０は、ＺＤＤと実数ベクトルとの積の演算を、ＺＤＤのノード数（Ｗ）に比例する時間で演算の処理を終了することができる。すなわち、行列演算実行部１５０は、演算量「Ｏ（Ｗ）」に応じた計算時間および記憶容量で処理を行うことができ、演算量「Ｏ（ＭＮ）」や演算量「Ｏ（Ｋ）」よりも、必要となる計算時間や記憶容量を削減できる。上述してきた方法により、ＺＤＤと実数ベクトルとの積の演算量を、「Ｏ（Ｗ）」に減らすことができる理由は次のとおりである。再帰的計算において各中間ノードに対応して計算されるscoreの値は、行ベクトルと実数ベクトルqとの乗算の途中までの演算結果を保持している。このとき、ある行ベクトルに対する乗算と、別の行ベクトルに対する乗算において、途中までの計算が同一である場合、その結果が同一のノードに保持されることになるので、計算回数を削減することができる。その結果、ＺＤＤと実数ベクトルとの積の演算量を「Ｏ（Ｗ）」に減らすことができる。
【００３９】
計算結果出力部１６０は、行列演算実行部１５０による演算の結果を外部へ出力する。例えば、計算結果出力部１６０は、ディスプレイやモニタ、プリンタなどの周辺機器へ演算の結果を出力する。
【００４０】
なお、上述してきた演算装置１００の各種処理機能は、例えば、電子回路や集積回路により実装することができる。電子回路としては、例えば、ＣＰＵ（Central Processing Unit）やＭＰＵ（Micro Processing Unit）がある。また、集積回路としては、例えば、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array)などがある。また、データ記憶部１３０は、例えば、ＲＡＭ（Random Access Memory）やフラッシュメモリ(flash memory)などの半導体メモリ素子を用いて実装することができる。
【００４１】
［演算装置による処理（実施例１）］
図９〜図１１を用いて、実施例１に係る演算装置による処理の流れを説明する。図９は、実施例１に係るＺＤＤ構築処理の流れを示す図である。図１０は、実施例１に係る行列と実数ベクトルとの積の計算処理の流れを示す図である。図１１は、行列演算処理の流れを示す図である。実施例１に係る演算装置１００による処理は、図９に示すＺＤＤ構築処理と、図１０および図１１に示す行列と実数ベクトルとの積の計算処理とに２分される。
【００４２】
（ＺＤＤ構築処理）
図９に示すように、データ入力部１１０は、Ｍ行Ｎ列の２値行列を入力する（Ｓ１０１）。続いて、ＺＤＤ構築部１２０は、Ｓ１０１で入力した行列の各行を入力として、組み合わせ集合Ｆを計算する（Ｓ１０２）。そして、ＺＤＤ構築部１２０は、Ｓ１０２で計算した組み合わせ集合Ｆに対応するＺＤＤを構築する（Ｓ１０３）。
【００４３】
具体的には、ＺＤＤ構築部１２０は、データ入力部１１０からＭ行Ｎ列の２値行列を取得し、行列の各行について、１つの要素のみからなる集合を作成する（式（１）参照）。続いて、ＺＤＤ構築部１２０は、行列の各行について、１つの要素のみからなる集合を作成した後、それらの和集合を作成し、組み合わせ集合Ｆを作成する（式（２）参照）。そして、ＺＤＤ構築部１２０は、組み合わせ集合Ｆ（式（２））に出現するシンボルＲ１，Ｒ２，…，ＲＭ，Ｃ１，Ｃ２，…，ＣＮに対して、Ｒ１＜Ｒ２＜・・・＜ＲＭ＜Ｃ１＜Ｃ２＜・・・＜ＣＮという順序を与え、既存の技術を利用した演算を行うことにより、組み合わせ集合Ｆに対応するＺＤＤを構築する。
【００４４】
（行列と実数ベクトルとの積の計算処理）
図１０に示すように、ベクトル入力部１４０は、Ｎ次元の実数ベクトルを入力する（Ｓ２０１）。続いて、行列演算実行部１５０は、ＺＤＤ構築部１２０により２値行列から構築されたＺＤＤと、ベクトル入力部１４０により入力されたＮ次元の実数ベクトルとを用いて、行列演算を実行する（Ｓ２０２）。
【００４５】
（行列演算処理）
行列演算実行部１５０は、図１１に示す処理を実行する前に、ベクトル入力部１４０からＮ次元ベクトルｑを取得し、データ記憶部１３０からＺＤＤを取得して、スコアを格納する要素数（Ｗ−Ｍ）の１次元配列scoreを用意し、すべての要素を０で初期化しておく。以上の準備が完了した後、行列演算実行部１５０は、インデックス（ｉ）をｉ＝３に初期化する（Ｓ３０１）。
【００４６】
続いて、行列演算実行部１５０は、ｖ（ｉ）が、Ｃ１〜ＣＮのいずれかに一致するか否か（ｖ（ｉ）＝Ｃｊ（１≦ｊ≦Ｎ）？）を判定する（Ｓ３０２）。判定の結果、ｖ（ｉ）が、Ｃ１〜ＣＮのいずれかに一致する場合には（Ｓ３０２、Ｙｅｓ）、行列演算実行部１５０は、score［ｉ］の値を、score（ＨＩ（ｉ））＋ｑｊに更新する（Ｓ３０３）。
【００４７】
続いて、行列演算実行部１５０は、ｉ≦Ｗであるか否かを判定する（Ｓ３０４）。判定の結果、ｉ≦Ｗである場合には（Ｓ３０４、Ｙｅｓ）、行列演算実行部１５０は、ＺＤＤの全てのノードについてscoreの計算を完了しているものとして、演算結果ｐを計算結果出力部１５０に送出して（Ｓ３０５）、行列演算処理を終了する。一方、判定の結果、ｉ≦Ｗではない場合には（Ｓ３０４、Ｎｏ）、行列演算実行部１５０は、ＺＤＤの全てのノードについてscoreの計算を完了していないものとして、ｉの値を１インクリメント（ｉ←ｉ＋１）して（ステップＳ３０６）、上述のＳ３０２に戻る。
【００４８】
上述したステップＳ３０２において、判定の結果、ｖ（ｉ）が、Ｃ１〜ＣＮのいずれにも一致しない場合には（Ｓ３０２、Ｎｏ）、行列演算実行部１５０は、ｐｋ←score（ＨＩ（ｉ））として（Ｓ３０７）、上述のＳ３０５に移行する。
【００４９】
［実施例１による効果］
上述してきたように、実施例１に係る演算装置１００は、Ｍ行Ｎ列（Ｍ、Ｎは正の整数）の２値行列を、ＺＤＤを用いたデータ構造に変換する（図５、６等）。そして、実施例１に係る演算装置は、ＺＤＤと実数ベクトルとの積の演算を、ＺＤＤ上で再帰的なアルゴリズムとして実行する（図１１等）。すなわち、実施例１に係る演算装置は、２値行列をＺＤＤを用いたデータ構造に変換することにより２値行列のデータを圧縮して表現することができる。そして、実施例１に係る演算装置は、２値行列が有する非零の要素数「Ｋ」に応じた演算を実行するのではなく、２値行列をＺＤＤを用いたデータ構造に変換したときのＺＤＤのノード数「Ｗ」に応じた演算を実行できるようになる。このようなことから、実施例１に係る演算装置は、２値行列と実数ベクトルとの積の演算に必要となる計算時間を減らすことができ、行列演算を効率的に実行できる。
【００５０】
また、疎な２値行列のデータを圧縮するので、演算に必要となる記憶容量を削減することもできる。
【００５１】
また、上述の実施例１では、図９に示すＺＤＤ構築処理と、図１０および図１１に示す行列と実数ベクトルとの積の計算処理とを２分して説明したが、図９に示すＺＤＤ構築処理と、図１０および図１１に示す行列と実数ベクトルとの積の計算処理とをシリアルに実行してもよい。
【００５２】
なお、上述してきた実施例１に係る演算装置は、各種数値計算や物理的なシミュレーション、各種情報管理などに幅広く適用することができる。特に、ある特定の２値行列が繰り返し利用される状況においては、一旦ＺＤＤによって２値行列を構築すれば、計算量削減の効果が見込まれる。
【実施例２】
【００５３】
以下、本発明にかかる演算装置、演算方法および演算プログラムの他の実施形態として実施例２を説明する。
【００５４】
（１）装置構成等
図１に示した演算装置１００の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、演算装置１００の分散または統合の具体的形態は図１に示すものに限られず、演算装置１００のＺＤＤ構築部１２０、データ記憶部１３０および行列演算実行部１５０を機能的に統合されていてもよい。このように、演算装置１００の各構成要素の全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。
【００５５】
（２）演算プログラム
また、実施例１で説明した演算装置１００の各種の処理（例えば、図９〜１１等参照）は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどの電子機器で実行することによって実現することができる。そこで、以下では、図１２を用いて、実施例１で説明した演算装置１００と同様の機能を有する演算プログラムを実行する電子機器の一例を説明する。図１２は、演算プログラムを実行する電子機器の一例を示す図である。
【００５６】
図１２に示すように、演算装置１００が有する機能と同様の機能を有する電子機器２００は、ＣＰＵ（Central Processing Unit）２１０、入力部２２０、出力部２３０、メモリ２４０およびハードディスク装置２５０を有する。そして、ＣＰＵ２１０、入力部２２０、出力部２３０、メモリ２４０およびハードディスク装置２５０は、バス２６０を介して接続される。
【００５７】
ＣＰＵ２１０は、各種演算処理を実行する。なお、電子機器２００は、ＣＰＵ２１０の代わりに、例えば、ＭＰＵ（Micro Processing Unit）などの電子回路、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ(Field Programmable Gate Array)などの集積回路を用いることもできる。
【００５８】
入力部２２０は２値行列などの各種情報を入力する。また、出力部２３０は行列演算の結果などを出力する。また、メモリ２４０は、２値行列を変換したＺＤＤなどの各種情報を一時的に記憶する。なお、メモリ２４０は、例えば、ＲＡＭ（Random Access Memory）やフラッシュメモリ(flash memory)などの半導体メモリ素子を用いて実装できる。また、ハードディスク装置２５０は、ＣＰＵ２１０による各種処理の実行に必要な情報を記憶する。
【００５９】
ハードディスク装置２５０には、演算装置１００が有する機能と同様の機能を発揮する演算プログラム２５１および演算用データ２５２が記憶されている。なお、この演算プログラム２５１を適宜分散させて、ネットワークを介して通信可能に接続された他のコンピュータの記憶部に記憶させておくこともできる。
【００６０】
そして、ＣＰＵ２１０が、演算プログラム２５１をハードディスク装置２５０から読み出してメモリ２４０に展開することにより、図１２に示すように、演算プログラム２５１は演算プロセス２４１として機能する。演算プロセス２４１は、ハードディスク装置２５０から読み出した演算用データ２５２等の各種データを適宜メモリ２４０上の自身に割当てられた領域に展開し、この展開した各種データに基づいて各種処理を実行する。
【００６１】
なお、演算プロセス２４１は、例えば、上述した演算装置１００のＺＤＤ構築部１２０や行列演算実行部１５０などにより実行される処理、例えば、上述の図９〜１１などを用いて説明した処理を含む。
【００６２】
なお、上述した演算プログラム２５１については、必ずしも最初からハードディスク装置２５０に記憶させておく必要はない。例えば、電子機器２００が、フレキシブルディスク、ＣＤ−ＲＯＭ、ＤＶＤ、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」に予め記憶された演算プログラム２５１を読み出して実行するようにしてもよい。
【００６３】
さらには、電子機器２００が、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介して接続可能な「他のコンピュータ（またはサーバ）」などに格納された演算プログラム２５１を読み出して実行するようにしてもよい。
【００６４】
（３）演算方法
実施例１で説明した演算装置１００により、以下のような演算方法が実現される。
【００６５】
すなわち、２値行列とＮ次元の実数ベクトルとの行列演算を演算装置１００としてのコンピュータが実行する演算方法であって、コンピュータは、Ｍ行Ｎ列（Ｍ、Ｎは整数）の２値行列のデータを入力するデータ入力工程と（図９、Ｓ１０１）、Ｎ次元（Ｎは整数）の実数ベクトルを入力するベクトル入力工程と（図１０、Ｓ２０１）、データ入力工程により入力された２値行列のデータを、二分決定グラフのデータ構造に変換した変換データを構築する構築工程と（図９、Ｓ１０３）、構築工程により構築された変換データと、ベクトル入力部により入力された実数ベクトルとの行列演算を実行する演算工程と（図１０、Ｓ２０２、図１１）、演算工程による演算結果を出力する出力工程とを実行することを特徴とする演算方法が実現される。
【符号の説明】
【００６６】
１００ 演算装置
１１０ データ入力部
１２０ ＺＤＤ構築部
１３０ データ記憶部
１４０ ベクトル入力部
１５０ 行列演算実行部
１６０ 計算結果出力部
２００ 電子機器
２１０ ＣＰＵ
２２０ 入力部
２３０ 出力部
２４０ メモリ
２５０ ハードディスク装置
２６０ バス
【特許請求の範囲】
【請求項１】
２値行列とＮ次元の実数ベクトルとの行列演算を行う演算装置であって、
Ｍ行Ｎ列（Ｍ、Ｎは整数）の前記２値行列のデータを入力するデータ入力部と、
Ｎ次元の前記実数ベクトルを入力するベクトル入力部と、
前記データ入力部により入力された前記２値行列のデータを、二分決定グラフのデータ構造に変換した変換データを構築する構築部と、
前記構築部により構築された前記変換データと、前記ベクトル入力部により入力された前記実数ベクトルとの行列演算を実行する演算部と、
前記演算部による演算結果を出力する出力部と
を有することを特徴とする演算装置。
【請求項２】
２値行列とＮ次元の実数ベクトルとの行列演算を行うコンピュータにより実行される演算方法であって、
Ｍ行Ｎ列（Ｍ、Ｎは整数）の前記２値行列のデータを入力するデータ入力工程と、
Ｎ次元の前記実数ベクトルを入力するベクトル入力工程と、
前記データ入力工程により入力された前記２値行列のデータを、二分決定グラフのデータ構造に変換した変換データを構築する構築工程と、
前記構築工程により構築された前記変換データと、前記ベクトル入力部により入力された前記実数ベクトルとの行列演算を実行する演算工程と、
前記演算工程による演算結果を出力する出力工程と
を含むことを特徴とする演算方法。
【請求項３】
２値行列とＮ次元の実数ベクトルとの行列演算を行うコンピュータに実行させるための演算プログラムであって、
前記コンピュータに、
Ｍ行Ｎ列（Ｍ、Ｎは整数）の前記２値行列のデータを入力するデータ入力手順と、
Ｎ次元の前記実数ベクトルを入力するベクトル入力手順と、
前記データ入力手順により入力された前記２値行列のデータを、二分決定グラフのデータ構造に変換した変換データを構築する構築手順と、
前記構築手順により構築された前記変換データと、前記ベクトル入力手順により入力された前記実数ベクトルとの行列演算を実行する演算手順と、
前記演算手順による演算結果を出力する出力手順と
を実行させることを特徴とする演算プログラム。
【請求項１】
２値行列とＮ次元の実数ベクトルとの行列演算を行う演算装置であって、
Ｍ行Ｎ列（Ｍ、Ｎは整数）の前記２値行列のデータを入力するデータ入力部と、
Ｎ次元の前記実数ベクトルを入力するベクトル入力部と、
前記データ入力部により入力された前記２値行列のデータを、二分決定グラフのデータ構造に変換した変換データを構築する構築部と、
前記構築部により構築された前記変換データと、前記ベクトル入力部により入力された前記実数ベクトルとの行列演算を実行する演算部と、
前記演算部による演算結果を出力する出力部と
を有することを特徴とする演算装置。
【請求項２】
２値行列とＮ次元の実数ベクトルとの行列演算を行うコンピュータにより実行される演算方法であって、
Ｍ行Ｎ列（Ｍ、Ｎは整数）の前記２値行列のデータを入力するデータ入力工程と、
Ｎ次元の前記実数ベクトルを入力するベクトル入力工程と、
前記データ入力工程により入力された前記２値行列のデータを、二分決定グラフのデータ構造に変換した変換データを構築する構築工程と、
前記構築工程により構築された前記変換データと、前記ベクトル入力部により入力された前記実数ベクトルとの行列演算を実行する演算工程と、
前記演算工程による演算結果を出力する出力工程と
を含むことを特徴とする演算方法。
【請求項３】
２値行列とＮ次元の実数ベクトルとの行列演算を行うコンピュータに実行させるための演算プログラムであって、
前記コンピュータに、
Ｍ行Ｎ列（Ｍ、Ｎは整数）の前記２値行列のデータを入力するデータ入力手順と、
Ｎ次元の前記実数ベクトルを入力するベクトル入力手順と、
前記データ入力手順により入力された前記２値行列のデータを、二分決定グラフのデータ構造に変換した変換データを構築する構築手順と、
前記構築手順により構築された前記変換データと、前記ベクトル入力手順により入力された前記実数ベクトルとの行列演算を実行する演算手順と、
前記演算手順による演算結果を出力する出力手順と
を実行させることを特徴とする演算プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１２−２４３０４０（Ｐ２０１２−２４３０４０Ａ）
【公開日】平成２４年１２月１０日（２０１２．１２．１０）
【国際特許分類】
【出願番号】特願２０１１−１１１８１２（Ｐ２０１１−１１１８１２）
【出願日】平成２３年５月１８日（２０１１．５．１８）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年１２月１０日（２０１２．１２．１０）
【国際特許分類】
【出願日】平成２３年５月１８日（２０１１．５．１８）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]