(57)【要約】【課題】計算リソースに限りがある場合であっても、比較的大きいサイズの行列を扱うことができる逆行列計算装置を提供することを目的とする。【解決手段】  逆行列計算装置１は、Ｎ行Ｎ列の入力行列Ａにおける拡大行列（Ａ｜Ｉ）に対してガウスの消去法に基づき行基本変形を行うプロセッサ１０２と、Ｎ行Ｎ列行列を記憶するメモリ１３とを備え、プロセッサ１０２は、拡大行列の（ｉ＋１）行（ｉ＋１）列（ｉ＝０，１，・・・，Ｎ−１）成分の正規化計算を行う毎に、計算後の拡大行列のうち１行（ｉ＋２）列成分を１行１列成分とするＮ行Ｎ列行列をメモリ１３に記憶させるとともに、メモリ１３に記憶されたＮ行Ｎ列行列に基づいて、計算後の拡大行列の（ｉ＋２）行（ｉ＋２）列成分について正規化計算を繰り返し、第１行から第Ｎ行まで計算が終了したときにメモリ１３が記憶するＮ行Ｎ列行列を逆行列Ａ-1として出力する。【選択図】  図１
2020091691.tif 000002
【特許請求の範囲】
【請求項１】
Ｎ次正方行列（Ｎは２以上の整数）の入力行列を入力とし、この入力行列の逆行列を出力する逆行列計算回路であって、
前記入力行列にＮ次の単位行列を行方向に結合した拡大行列に対して、ガウスの消去法に基づき、行基本変形の処理を行うプロセッサと、
Ｎ行Ｎ列行列を記憶する読み書き可能なメモリと、
を備え、
前記プロセッサは、前記拡大行列の（ｉ＋１）行（ｉ＋１）列（ｉ＝０，１，・・・，Ｎ−１）成分について正規化計算を行うごとに、正規化計算後の拡大行列のうち、１行（ｉ＋２）列成分を１行１列成分とするＮ行Ｎ列行列を前記メモリに記憶させるとともに、このメモリに記憶された前記Ｎ行Ｎ列行列に基づいて、前記正規化計算後の拡大行列の（ｉ＋２）行（ｉ＋２）列成分について正規化計算を行う処理を繰り返し、第１行から第Ｎ行まで正規化計算が終了したときの前記メモリに記憶されているＮ行Ｎ列行列を前記逆行列として出力する
ことを特徴とする逆行列計算装置。
【請求項２】
請求項１に記載の逆行列計算装置において、
前記プロセッサは、
前記入力行列の対角成分である（ｉ＋１）行（ｉ＋１）列（ｉ＝０，１，・・・，Ｎ−１）成分の値の逆数を前記拡大行列の（ｉ＋１）行目の各成分に乗算して第１計算結果を出力する係数計算回路と、
前記第１計算結果を用いて、前記拡大行列の（ｉ＋１）行目の各成分を正規化して第２計算結果を出力する正規化計算回路と、
を有し、
前記プロセッサは、
前記第２計算結果に含まれる１行（ｉ＋２）列目を１行１列成分とするＮ行Ｎ列の成分を前記メモリに書き込み、前記メモリに記憶されているＮ行Ｎ列行列を更新する
ことを特徴とする逆行列計算装置。
【請求項３】
請求項２に記載の逆行列計算装置において、
前記係数計算回路は、
前記入力行列の対角成分である（ｉ＋１）行（ｉ＋１）列の値の逆数を求める逆数回路と、
前記逆数を前記拡大行列の（ｉ＋１）行目の各成分に乗算する第１乗算回路と、
を有し、
前記係数計算回路は、
前記拡大行列の行ごとに計算された前記第１計算結果を出力する
ことを特徴とする逆行列計算装置。
【請求項４】
請求項３に記載の逆行列計算装置において、
前記係数計算回路には、前記第１乗算回路が並列に計算可能に複数具備されていることを特徴とする逆行列計算装置。
【請求項５】
請求項２から４のいずれか１項に記載の逆行列計算装置において、
前記正規化計算回路は、
前記第１計算結果に前記入力行列の行ごとの（ｉ＋１）列目の成分の値を乗算する第２乗算回路と、
前記第２乗算回路による乗算結果から、前記第２乗算回路が計算の対象とした前記入力行列の行に対応する前記拡大行列の行に含まれる各成分を減算する減算回路と、
を有し、
前記正規化計算回路は、
乗算および減算を繰り返し行ってＮ行分の前記第２計算結果を出力する
ことを特徴とする逆行列計算装置。
【請求項６】
請求項５に記載の逆行列計算装置において、
前記正規化計算回路には、前記第２乗算回路および前記減算回路が並列に計算可能に複数具備されていることを特徴とする逆行列計算装置。
【請求項７】
請求項２から６のいずれか１項に記載の逆行列計算装置において、
前記正規化計算回路は、並列に計算可能に複数具備されていることを特徴とする逆行列計算装置。
【請求項８】
Ｎ次正方行列（Ｎは２以上の整数）の入力行列を入力とし、この入力行列の逆行列を出力する逆行列計算処理方法であって、
前記入力行列にＮ次の単位行列を行方向に結合した拡大行列に対して、ガウスの消去法に基づき、行基本変形の処理を行うプロセッサが、
前記拡大行列の（ｉ＋１）行（ｉ＋１）列（ｉ＝０，１，・・・，Ｎ−１）成分について正規化計算を行うごとに、正規化計算後の拡大行列のうち、１行（ｉ＋２）列成分を１行１列成分とするＮ行Ｎ列行列を読み書き可能なメモリに記憶させる第１ステップと、
前記第１ステップで前記メモリに記憶された前記Ｎ行Ｎ列行列に基づいて、前記正規化計算後の拡大行列の（ｉ＋２）行（ｉ＋２）列成分について正規化計算を行う第２ステップと、
前記第１ステップと前記第２ステップとを繰り返して、第１行から第Ｎ行までの正規化計算が終了したときの前記メモリに記憶されているＮ行Ｎ列行列を前記逆行列として出力する第３ステップと
を備えることを特徴とする逆行列計算処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、逆行列計算装置および逆行列計算処理方法に関する。
【背景技術】
【０００２】
スマートフォンの普及に伴って、通信速度の向上や利用帯域の増大など、無線ネットワークに対する社会的な要請が大きくなっている。このような状況を背景として、ＬＴＥ（Ｌｏｎｇ  Ｔｅｒｍ  Ｅｖｏｌｕｔｉｏｎ）と呼ばれる移動通信方式の無線インターフェース仕様を適用した無線ネットワークシステムが普及しつつある。
【０００３】
このＬＴＥでは、無線アクセス技術の１つとして、複数の送信ポイント（ＴＰ：基地局）が協調してユーザ端末（ＵＥ：ユーザ無線端末）と信号を送受信するＣｏＭＰ（Ｃｏｏｒｄｉｎａｔｅｄ  Ｍｕｌｔｉ−ｐｏｉｎｔ  ｔｒａｎｓｍｉｓｓｉｏｎ／ｒｅｃｅｐｔｉｏｎ：セル間協調送受信）が採用されている（非特許文献１参照）。
【０００４】
ＣｏＭＰ技術は、周波数利用効率やセル端ユーザスループットを向上させる重要な技術の１つである。例えば、下り方向の通信（ＴＰからＵＥへの送信）において、同時に複数の送信ポイントが同一周波数帯を用いて、各ＵＥに送信することで無線リソースの利用効率を高めることができる。しかし、各送信ポイントが異なるＵＥに対して送信した場合、複数の送信ポイントから信号を受信可能なＵＥにとっては、他の送信ポイントからの信号が所望の受信信号の干渉となって、かえってスループットの低下を招く恐れがある。したがって、このような干渉を抑制しつつ通信速度を向上させるためにＣｏＭＰは必要不可欠な技術となっている。
【０００５】
さらに、ＬＴＥを発展させた次世代移動通信方式の研究開発が行われており、ＣｏＭＰを拡張した概念として協調無線リソース制御方式、およびその処理を高速化するための専用回路構成が提案されている（非特許文献２参照）。協調無線リソース制御方式では、１ミリ秒からサブミリ秒程度の短時間の間に逆行列計算を数百回程度以上行う必要があり、その処理の高速化が必要不可欠である。
【０００６】
そこで、例えば、特許文献１には、ｎ次正方行列（ｎは２以上の整数。）の逆行列をｎ並列で求める逆行列計算装置が開示されている。特許文献１に記載の逆行列計算装置は、比較的小さいサイズの行列をターゲットとしており、行列サイズｎに対して回路規模がｎ倍以上になる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００６−０１１７０６号公報
【非特許文献】
【０００８】
【非特許文献１】田岡  他「ＬＴＥ−ＡｄｖａｎｃｅｄにおけるＭＩＭＯおよびセル間協調送受信技術」，ＮＴＴ  ＤＯＣＯＭＯ  テクニカル・ジャーナル，Ｖｏｌ．１８，Ｎｏ．２，ｐｐ．２２−３０，２０１０年７月，［ｏｎｌｉｎｅ］＜ｈｔｔｐｓ：／／ｗｗｗ．ｎｔｔｄｏｃｏｍｏ．ｃｏ．ｊｐ／ｂｉｎａｒｙ／ｐｄｆ／ｃｏｒｐｏｒａｔｅ／ｔｅｃｈｎｏｌｏｇｙ／ｒｄ／ｔｅｃｈｎｉｃａｌ＿ｊｏｕｒｎａｌ／ｂｎ／ｖｏｌ１８＿２／ｖｏｌ１８＿２＿０２２ｊｐ．ｐｄｆ＞
【非特許文献２】Ｙ．Ａｒｉｋａｗａ，Ｔ．Ｓａｋａｍｏｔｏ  ａｎｄ  Ｓ．Ｋｉｍｕｒａ，“Ｈａｒｄｗａｒｅ  ａｃｃｅｌｅｒａｔｏｒ  ｆｏｒ  ｃｏｏｒｄｉｎａｔｅｄ  ｒａｄｉｏ−ｒｅｓｏｕｒｃｅ  ｓｃｈｅｄｕｌｉｎｇ  ｉｎ  ５Ｇ  ｕｌｔｒａ−ｈｉｇｈ−ｄｅｎｓｉｔｙ  ｄｉｓｔｒｉｂｕｔｅｄ  ａｎｔｅｎｎａ  ｓｙｓｔｅｍｓ，”２０１７  ２７ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｎｅｔｗｏｒｋｓ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ  Ｃｏｎｆｅｒｅｎｃｅ（ＩＴＮＡＣ），Ｍｅｌｂｏｕｒｎｅ，  ｐｐ．  １−６，Ｎｏｖｅｍｂｅｒ  ２０１７．
【発明の概要】
【発明が解決しようとする課題】
【０００９】
特許文献１に記載の技術において、比較的大きいサイズの行列を扱う場合、回路規模が増大してしまい、ロジック規模の比較的大きいＦＰＧＡなどを用いたとしても、計算リソースの制限を受けるため、逆行列計算装置を実現することが困難となる。
【００１０】
本発明は、上述した課題を解決するためになされたものであり、計算リソースに限りがある場合であっても、比較的大きいサイズの行列を扱うことができる逆行列計算装置を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上述した課題を解決するために、本発明に係る逆行列計算装置は、Ｎ次正方行列（Ｎは２以上の整数）の入力行列を入力とし、この入力行列の逆行列を出力する逆行列計算回路であって、前記入力行列にＮ次の単位行列を行方向に結合した拡大行列に対して、ガウスの消去法に基づき、行基本変形の処理を行うプロセッサと、Ｎ行Ｎ列行列を記憶する読み書き可能なメモリと、を備え、前記プロセッサは、前記拡大行列の（ｉ＋１）行（ｉ＋１）列（ｉ＝０，１，・・・，Ｎ−１）成分について正規化計算を行うごとに、正規化計算後の拡大行列のうち、１行（ｉ＋２）列成分を１行１列成分とするＮ行Ｎ列行列を前記メモリに記憶させるとともに、このメモリに記憶された前記Ｎ行Ｎ列行列に基づいて、前記正規化計算後の拡大行列の（ｉ＋２）行（ｉ＋２）列成分について正規化計算を行う処理を繰り返し、第１行から第Ｎ行まで正規化計算が終了したときの前記メモリに記憶されているＮ行Ｎ列行列を前記逆行列として出力することを特徴とする。
【００１２】
また、本発明に係る逆行列計算装置において、前記プロセッサは、前記入力行列の対角成分である（ｉ＋１）行（ｉ＋１）列（ｉ＝０，１，・・・，Ｎ−１）成分の値の逆数を前記拡大行列の（ｉ＋１）行目の各成分に乗算して第１計算結果を出力する係数計算回路と、前記第１計算結果を用いて、前記拡大行列の（ｉ＋１）行目の各成分を正規化して第２計算結果を出力する正規化計算回路と、を有し、前記プロセッサは、前記第２計算結果に含まれる１行（ｉ＋２）列目を１行１列成分とするＮ行Ｎ列の成分を前記メモリに書き込み、前記メモリに記憶されているＮ行Ｎ列行列を更新してもよい。
【００１３】
また、本発明に係る逆行列計算装置において、前記係数計算回路は、前記入力行列の対角成分である（ｉ＋１）行（ｉ＋１）列の値の逆数を求める逆数回路と、前記逆数を前記拡大行列の（ｉ＋１）行目の各成分に乗算する第１乗算回路と、を有し、前記係数計算回路は、前記拡大行列の行ごとに計算された前記第１計算結果を出力してもよい。
【００１４】
また、本発明に係る逆行列計算装置において、前記係数計算回路には、前記第１乗算回路が並列に計算可能に複数具備されていてもよい。
【００１５】
また、本発明に係る逆行列計算装置において、前記正規化計算回路は、前記第１計算結果に前記入力行列の行ごとの（ｉ＋１）列目の成分の値を乗算する第２乗算回路と、前記第２乗算回路による乗算結果から、前記第２乗算回路が計算の対象とした前記入力行列の行に対応する前記拡大行列の行に含まれる各成分を減算する減算回路と、を有し、前記正規化計算回路は、乗算および減算を繰り返し行ってＮ行分の前記第２計算結果を出力してもよい。
【００１６】
また、本発明に係る逆行列計算装置において、前記正規化計算回路には、前記第２乗算回路および前記減算回路が並列に計算可能に複数具備されていてもよい。
【００１７】
また、本発明に係る逆行列計算装置において、前記正規化計算回路は、並列に計算可能に複数具備されていてもよい。
【００１８】
上述した課題を解決するために、本発明に係る逆行列計算処理方法は、Ｎ次正方行列（Ｎは２以上の整数）の入力行列を入力とし、この入力行列の逆行列を出力する逆行列計算処理方法であって、前記入力行列にＮ次の単位行列を行方向に結合した拡大行列に対して、ガウスの消去法に基づき、行基本変形の処理を行うプロセッサが、前記拡大行列の（ｉ＋１）行（ｉ＋１）列（ｉ＝０，１，・・・，Ｎ−１）成分について正規化計算を行うごとに、正規化計算後の拡大行列のうち、１行（ｉ＋２）列成分を１行１列成分とするＮ行Ｎ列行列を読み書き可能なメモリに記憶させる第１ステップと、前記第１ステップで前記メモリに記憶された前記Ｎ行Ｎ列行列に基づいて、前記正規化計算後の拡大行列の（ｉ＋２）行（ｉ＋２）列成分について正規化計算を行う第２ステップと、前記第１ステップと前記第２ステップとを繰り返して、第１行から第Ｎ行までの正規化計算が終了したときの前記メモリに記憶されているＮ行Ｎ列行列を前記逆行列として出力する第３ステップとを備えることを特徴とする。
【発明の効果】
【００１９】
本発明によれば、行基本変形された拡大行列のうち、入力行列と同一のサイズの所定の行列成分をメモリに記憶するので、計算リソースに限りがある場合であっても、比較的大きいサイズの行列を扱うことができる。
【図面の簡単な説明】
【００２０】
【図１】図１は、本発明の第１の実施の形態に係る逆行列計算装置の構成を示すブロック図である。
【図２】図２は、第１の実施の形態に係る係数計算回路の構成を示すブロック図である。
【図３】図３は、第１の実施の形態に係る正規化計算回路の構成を示すブロック図である。
【図４】図４は、第１の実施の形態に係る逆行列計算装置を実現するコンピュータの一例を示すブロック図である。
【図５】図５は、第１の実施の形態に係る逆行列計算装置によって実行されるプログラムの一例を示す図である。
【図６】図６は、第１の実施の形態に係る逆行列計算装置の動作を説明するためのフローチャートである。
【図７】図７は、第１の実施の形態に係るメモリに格納されるデータ構造の一例を説明する図である。
【図８】図８は、第２の実施の形態に係る逆行列計算装置の構成を示すブロック図である。
【図９】図９は、第３の実施の形態に係る正規化計算回路の構成を示すブロック図である。
【図１０】図１０は、第４の実施の形態に係る係数計算回路の構成を示すブロック図である。
【図１１】図１１は、従来例に係る逆行列計算装置の構成を示すブロック図である。
【発明を実施するための形態】
【００２１】
以下、本発明の好適な実施の形態について、図１から図１１を参照して詳細に説明する。
［発明の概要］
はじめに、本発明の実施の形態に係る逆行列計算装置の概要について説明する。逆行列計算装置は、入力行列Ａを入力とし、よく知られたガウスの消去法に基づいて、入力行列Ａの逆行列Ａ-1を計算し出力する。ガウスの消去法は掃き出し法とも呼ばれる。本実施の形態では、入力行列ＡはＮ次正方行列（Ｎは２以上の整数）であり、また、出力される逆行列Ａ-1もＮ次正方行列である。
【００２２】
ここで、入力行列Ａが正則であるとき、入力行列Ａは逆行列Ａ-1を持つ。ＩをＮ行Ｎ列の単位行列としたとき、入力行列Ａとの積が単位行列Ｉとなる行列が、本実施の形態に係る逆行列計算装置が求める逆行列Ａ-1である。
【００２３】
従来の技術では、入力行列Ａ、および入力行列Ａを単位行列Ｉにするように変形した階段行列の２つのＮ行Ｎ列の行列を記憶領域に保持して逆行列Ａ-1の計算処理を実行していた。これに対し、本実施の形態に係る逆行列計算装置は、拡大行列（Ａ｜Ｉ）に対して入力行列Ａを単位行列Ｉにするように行基本変形を行って、階段行列（最終的に逆行列Ａ-1となる行列）を求める計算過程に応じて、拡大行列（Ａ｜Ｉ）に含まれる所定のＮ行Ｎ列分の成分のみを記憶領域に格納する。
【００２４】
［第１の実施の形態］
まず、本発明の第１の実施の形態に係る逆行列計算装置１の構成を説明する。逆行列計算装置１は、図１に示すように、係数計算回路１１、正規化計算回路１２、およびメモリ１３を備える。
【００２５】
係数計算回路１１は、入力行列Ａの対角成分である（ｉ＋１）行（ｉ＋１）列（ｉ＝０，１，・・・，Ｎ−１）の値の逆数を求め、（ｉ＋１）行目の各成分に対して、求めた逆数を乗算し、その計算結果Ａ11’（第１計算結果）を出力する。
【００２６】
係数計算回路１１は、図２に示すように、逆数回路１１０と乗算回路（第１乗算回路）１１１とを備える。
逆数回路１１０は、入力行列Ａの対角成分である（ｉ＋１）行（ｉ＋１）列の値の逆数を求めて出力する。逆数回路１１０が求めた対角成分の値の逆数は、拡大行列（Ａ｜Ｉ）における単位行列Ｉの（ｉ＋１）行（ｉ＋１）列の値としてメモリ１３に記憶される。
【００２７】
乗算回路１１１は、逆数回路１１０が計算した入力行列Ａの対角成分である（ｉ＋１）行（ｉ＋１）列の値の逆数を用いて、拡大行列（Ａ｜Ｉ）の（ｉ＋１）行目の各成分ごとの乗算を行い、計算結果Ａ11’を出力する。より詳細には、乗算回路１１１は、メモリ１３に予め記憶されている入力行列Ａの（ｉ＋１）行の成分を読み出して、入力行列Ａの（ｉ＋１）行目の各成分に逆数を乗算する。
【００２８】
例えば、ｉ＝０とすると、乗算回路１１１は、メモリ１３に予め記憶されている入力行列Ａの１行目の成分を読み出して、拡大行列（Ａ｜Ｉ）の１行目に入力行列Ａの１行１列成分の逆数を乗算する計算を行う。Ｎ行Ｎ列の入力行列Ａの場合、乗算回路１１１は、１行分の乗算を行うにあたり、Ｎ個の成分ごとに合計Ｎ回の乗算を行う。
【００２９】
また、乗算回路１１１は乗算処理を行ごとにＮ行分の乗算を行い、行ごとの係数計算の計算結果Ａ11’を得る。例えば、計算結果Ａ11’には、入力行列Ａの１行分の各成分の乗算結果と、逆数回路１１０によって求められた逆数の値とが含まれる。逆数回路１１０によって求められた逆数は、単位行列Ｉの対角成分に逆数が乗算された値として用いることができる。
【００３０】
次に、正規化計算回路１２について説明する。正規化計算回路１２は、図３に示すように、係数計算回路１１による計算結果Ａ11’を用いて、拡大行列（Ａ｜Ｉ）の（ｉ＋１）行（ｉ＋１）列成分を正規化し、計算結果Ａ12’（第２計算結果）を出力する。
正規化計算回路１２は、乗算回路（第２乗算回路）１２０と減算回路１２１とを備える。
【００３１】
乗算回路１２０は、係数計算回路１１による計算結果Ａ11’に、メモリ１３から読み出した入力行列Ａの行ごとの（ｉ＋１）列目の成分の値を乗算する。
【００３２】
例えば、ｉ＝０の場合において、係数計算回路１１から出力された計算結果Ａ11’として、拡大行列（Ａ｜Ｉ）の１行目の各成分に入力行列Ａの１行１列目の成分の逆数を乗算した値が得られる。乗算回路１２０は、計算結果Ａ11’に対して入力行列Ａの２行１列目の成分の値を乗算する。乗算回路１２０は、拡大行列（Ａ｜Ｉ）の３行目から３２行目（Ｎ行目）についても同様の計算を繰り返して行う。このように、１行１列成分の正規化を行うときに、乗算回路１２０は、合計Ｎ−１回（Ｎ−１行分）の乗算を行う。
【００３３】
減算回路１２１は、乗算回路１２０による乗算結果から、乗算回路１２０が計算の対象とした入力行列Ａの行に対応する拡大行列（Ａ｜Ｉ）の行に含まれる各成分を減算して計算結果Ａ12’を出力する。
【００３４】
具体的には、ｉ＝０の場合、減算回路１２１は、乗算回路１２０が求めた入力行列Ａの２行１列成分と拡大行列（Ａ｜Ｉ）の１行目における計算結果Ａ11’との乗算結果から、拡大行列（Ａ｜Ｉ）の２行目の各成分を減算する。減算回路１２１は、同様の計算を拡大行列（Ａ｜Ｉ）の３行目から３２行目（Ｎ行目）まで行う。
【００３５】
このように、ｉ＝０の場合に、減算回路１２１が２行目から３２行目までの減算処理を行うと、拡大行列（Ａ｜Ｉ）において、入力行列Ａの１列目が階段化されることになる。減算回路１２１によってＮ−１回（Ｎ−１行分）の減算処理が繰り返し行われる結果、階段化された列を含む拡大行列（Ａ｜Ｉ）が計算結果Ａ12’として得られる。
【００３６】
メモリ１３は、読み書き可能なメモリであり、外部から入力されるＮ行Ｎ列の入力行列Ａを記憶する。より詳細には、メモリ１３には、入力行列Ａのサイズに応じた記憶領域が確保されており、常にＮ行Ｎ列分だけの成分を記憶することができる。
【００３７】
後述するプロセッサ１０２は、拡大行列（Ａ｜Ｉ）の（ｉ＋１）行（ｉ＋１）列成分について正規化計算が行われるごとに、正規化計算後の拡大行列（Ａ｜Ｉ）のうち、１行（ｉ＋２）列成分を１行１列成分とするＮ行Ｎ列行列をメモリ１３に記憶させる。さらに、プロセッサ１０２は、メモリ１３に記憶されたＮ行Ｎ列行列に基づいて、正規化計算後の拡大行列（Ａ｜Ｉ）の（ｉ＋２）行（ｉ＋２）列成分について正規化計算を行う処理を繰り返す。
【００３８】
より詳細には、プロセッサ１０２は、メモリ１３に予め入力行列Ａを記憶させ、係数計算回路１１および正規化計算回路１２による計算結果Ａ11’、Ａ12’を書き込んでいって、入力行列Ａの情報を更新する。
【００３９】
具体的には、プロセッサ１０２は、正規化計算回路１２による計算結果Ａ12’のうち、拡大行列（Ａ｜Ｉ）における入力行列Ａが階段化された列より後の（ｉ＋２）以降のＮ行Ｎ列分の成分について、有意な値を有する行列Ａ’として、メモリ１３に記憶させる。
【００４０】
係数計算回路１１および正規化計算回路１２による上述した繰り返し計算が全て完了したとき、すなわち拡大行列（Ａ｜Ｉ）に対する行基本変形が完了したときに、メモリ１３には、所望のＮ行Ｎ列の逆行列Ａ-1が記憶されていることになる。
【００４１】
プロセッサ１０２は、１行目からＮ行目までの正規化計算が終了したときにメモリ１３が記憶しているＮ行Ｎ列行列を、入力行列Ａの逆行列Ａ-1として出力する。
【００４２】
［逆行列計算装置のコンピュータ構成］
次に、上述した構成を有する逆行列計算装置１を実現するコンピュータ構成の一例について図４を参照して説明する。
図４に示すように、逆行列計算装置１は、例えば、バス１０１を介して接続されるプロセッサ１０２、主記憶装置１０３、通信インターフェース１０４、補助記憶装置１０５、入出力装置１０６を備えるコンピュータと、これらのハードウェア資源を制御するプログラムによって実現することができる。逆行列計算装置１は、例えば、表示装置１０７がバス１０１を介して接続され、表示画面に計算結果などを表示してもよい。
【００４３】
主記憶装置１０３は、例えば、ＳＲＡＭ、ＤＲＡＭ、およびＲＯＭなどの半導体メモリによって実現される。主記憶装置１０３は、図１で説明したメモリ１３を実現する。
プロセッサ１０２は、図１で説明したメモリ１３の制御を行う。
【００４４】
主記憶装置１０３には、プロセッサ１０２が各種制御や演算を行うためのプログラムが予め格納されている。プロセッサ１０２と主記憶装置１０３とによって、図１から図３に示した係数計算回路１１や正規化計算回路１２を含む逆行列計算装置１の各機能が実現される。
【００４５】
通信インターフェース１０４は、通信ネットワークＮＷを介して各種外部電子機器との通信を行うためのインターフェース回路である。逆行列計算装置１は、通信インターフェース１０４を介して外部から入力行列Ａを受信したり、求めた逆行列Ａ-1を外部に送出してもよい。
【００４６】
通信インターフェース１０４としては、例えば、ＬＴＥ、３Ｇ、無線ＬＡＮ、Ｂｌｕｅｔｏｏｔｈ（登録商標）などの無線データ通信規格に対応した演算インターフェースおよびアンテナが用いられる。通信ネットワークＮＷは、例えば、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）やＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネット、専用回線、無線基地局、プロバイダなどを含む。
【００４７】
補助記憶装置１０５は、読み書き可能な記憶媒体と、その記憶媒体に対してプログラムやデータなどの各種情報を読み書きするための駆動装置とで構成されている。補助記憶装置１０５には、記憶媒体としてハードディスクやフラッシュメモリなどの半導体メモリを使用することができる。
【００４８】
補助記憶装置１０５は、逆行列計算装置１が逆行列Ａ-1を求める計算処理を行うためのプログラムを格納するプログラム格納領域を有する。さらには、補助記憶装置１０５は、例えば、上述したデータやプログラムやなどをバックアップするためのバックアップ領域などを有していてもよい。補助記憶装置１０５は、例えば、図５に示す逆行列計算プログラムを記憶することができる。
【００４９】
入出力装置１０６は、表示装置１０７など外部機器からの信号を入力したり、外部機器へ信号を出力したりするＩ／Ｏ端子により構成される。
【００５０】
なお、逆行列計算装置１は、１つのコンピュータによって実現される場合だけでなく、互いに通信ネットワークＮＷで接続された複数のコンピュータによって分散されていてもよい。また、プロセッサ１０２は、ＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）、ＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ）、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）等のハードウェアによって実現されていてもよい。
【００５１】
［逆行列計算装置の動作］
次に、上述した構成を有する逆行列計算装置１の動作について、図６および図７を参照して説明する。Ｎ行Ｎ列の入力行列Ａは、外部から逆行列計算装置１に入力され、予めメモリ１３に記憶されているものとする。例えば、メモリ１３は、図７の上段に示すように、入力行列Ａの各成分を記憶している。
【００５２】
まず、プロセッサ１０２は、メモリ１３に記憶されているＮ行Ｎ列の入力行列Ａにおいて、ｉ＝０と設定して（ｉ＋１）行目を計算の対象として選択する（ステップＳ１）。より詳細には、プロセッサ１０２はｉ＝０、すなわち入力行列Ａの１行目を計算の対象として選択して処理を開始する。このとき、プロセッサ１０２は、拡大行列（Ａ｜Ｉ）を生成する。
【００５３】
次に、係数計算回路１１は、入力行列Ａの１行目についての係数計算を行う（ステップＳ２）。より詳細には、逆数回路１１０が、メモリ１３から入力行列Ａを読み出し、１行１列成分の逆数を求める。求められた逆数は、乗算回路１１１に入力され、入力行列Ａの１行目の各成分と乗算される。例えば、乗算回路１１１は、合計Ｎ回の乗算を行う。
【００５４】
係数計算回路１１は、入力行列Ａの１行目の乗算結果と１行１列成分の逆数を有する計算結果Ａ11’を出力する。プロセッサ１０２は、計算結果Ａ11’に含まれる入力行列Ａの１行目の乗算結果を、図７の上段に示すメモリ１３の１行目に反映させる。なお、逆数に関する情報は、メモリ１３の別領域に一時的に保持することができる。
【００５５】
その後、正規化計算回路１２は、係数計算回路１１によって求められた計算結果Ａ11’に基づいて、拡大行列（Ａ｜Ｉ）の（ｉ＋１）行（ｉ＋１）列成分、すなわち１行１列成分の正規化を行う（ステップＳ３）。具体的には、乗算回路１２０は、ステップＳ２で係数計算処理された入力行列Ａの１行目の各成分（計算結果Ａ11’）をメモリ１３から読み出して、入力行列Ａの２行１列成分の値を乗算する。
【００５６】
その後、減算回路１２１は、乗算回路１２０による１行目に対する乗算結果から２行目の各成分を減算した計算結果Ａ12’を出力する。乗算回路１２０および減算回路１２１は、同様の処理を、ステップＳ２で得られた１行目の計算結果Ａ11’に基づいて、３行目から３２行目（Ｎ行）まで繰り返して行い、入力行列Ａの１列目が階段化された拡大行列（Ａ｜Ｉ）である計算結果Ａ12’を出力する。
【００５７】
プロセッサ１０２は、正規化計算回路１２から出力された計算結果Ａ12’に含まれるＮ行Ｎ列の行列Ａ’をメモリ１３に格納する（ステップＳ４）。例えば、図７の中段に示すように、プロセッサ１０２は、正規化計算回路１２による計算結果Ａ12’のうち、有意な値を有するＮ行Ｎ列の成分からなる行列Ａ’をメモリ１３に書き込み、メモリ１３に記憶されているＮ行Ｎ列行列を更新する。
【００５８】
なお、図７の中段に示すように、メモリ１３が格納する行列Ａ’の例では、入力行列Ａの１行２列目から３２列目および単位行列Ｉの１行１列成分の計算結果Ａ11’からなる合計３２個（＝Ｎ個）の成分は、矢印ａで示すように、メモリ１３におけるＮ行目に相当する領域に格納されている。また、入力行列Ａの２行目は、次の処理で正規化される行として第１行目に相当する領域に格納され（矢印ｂ）、これに続いて３行目以降の成分が順番に格納される（矢印ｃ）。
【００５９】
以上の手順により、入力行列Ａの１列目が階段化され、ｉ＝０、すなわち入力行列Ａの１行目の成分に基づいた係数計算および正規化計算が完了する。
【００６０】
次に、プロセッサ１０２は、ｉをインクリメントさせる（ステップＳ５）。上記の例では、プロセッサ１０２は、ｉ＝１にインクリメントして、入力行列Ａの（ｉ＋１）行目、すなわち２行目を計算の対象として選択する。
【００６１】
その後、ｉ＝Ｎ−１となるまで（ステップＳ６：ＮＯ）、ステップＳ２からステップＳ５までの処理が繰り返し実行される。上記の例では、係数計算回路１１は、メモリ１３からｉ＝１、すなわち入力行列Ａの２行目に相当するデータを読み出して、係数計算を行う（ステップＳ２）。その後、正規化計算回路１２は、係数計算回路１１による計算結果Ａ11’に基づいて、入力行列Ａの第２列目を階段化するために正規化計算を行う（ステップＳ３）。
【００６２】
その後、プロセッサ１０２は、入力行列Ａの第２列目の階段化が完了すると、正規化計算の計算結果Ａ12’のうち、有意な値を含むＮ行Ｎ列分の成分からなる行列Ａ’をメモリ１３に記憶させる（ステップＳ４）。より詳細には、プロセッサ１０２は、行基本変形されている拡大行列（Ａ｜Ｉ）の３列目以降のＮ行Ｎ列の成分を行列Ａ’としてメモリ１３に格納する。
【００６３】
その後、ｉ＝Ｎ−１までの計算が行われると（ステップＳ６：ＹＥＳ）、処理は終了する。図７の下段に示すように。例えば、ｉ＝３１にインクリメントされた場合に、プロセッサ１０２がメモリ１３に格納するＮ行Ｎ列分の行列Ａ’は、所望とされる逆行列Ａ-1に相当する行列となる。このように、係数計算（ステップＳ２）および正規化計算（ステップＳ３）がＮ行分繰り返されることで、最終的にメモリ１３に記憶されている行列Ａが逆行列Ａ-1として出力される。
【００６４】
以上説明したように、第１の実施の形態に係る逆行列計算装置１によれば、Ｎ行Ｎ列の入力行列Ａに対して、ガウスの消去法に基づいて、Ｎ行Ｎ列の逆行列Ａ-1を出力する計算処理において、Ｎ行Ｎ列分の行列のみをメモリ１３に記憶する。そのため、従来の技術では、メモリにおいて、入力行列Ａと単位行列Ｉに相当する２つのＮ行Ｎ列の行列データを保持する領域が必要であったのに対して、メモリ量が削減され、その回路規模を半分に抑えることができる。
【００６５】
また、第１の実施の形態に係る逆行列計算装置１によれば、メモリアクセスに要する時間が削減できるため、係数計算処理および正規化計算を含む計算処理をより高速化することができる。
【００６６】
ここで、本実施の形態に係る逆行列計算装置１との比較例として、図１１に、例えば特許文献１に記載されている従来例に係る逆行列計算装置の構成を示す。図１１に示す従来例に係る逆行列計算装置では、Ｎ次正方行列の入力行列Ａの逆行列Ａ-1をＮ個の係数計算部と、Ｎ個の正規化計算部とを用いて、Ｎ並列で求めている。
【００６７】
このような従来例の逆行列計算装置は、比較的小さいサイズの行列をターゲットとしており、行列サイズＮに対して、回路規模がＮ倍以上となる。そのため、比較的大きいサイズの行列を対象とした逆行列計算装置は、ロジック規模が大きいＦＰＧＡを用いたとしても、リソースが不足してしまう場合がある。
【００６８】
これに対して、本実施の形態に係る逆行列計算装置１は、回路規模が削減されるので、計算リソースに限りがある場合であっても、比較的大きいサイズの行列を扱うことができる。
【００６９】
［第２の実施の形態］
次に、本発明の第２の実施の形態について説明する。なお、以下の説明では、上述した第１の実施の形態と同じ構成については同一の符号を付し、その説明を省略する。
【００７０】
第１の実施の形態では、逆行列計算装置１は１つの正規化計算回路１２を備える場合について説明した。これに対し、第２の実施の形態に係る逆行列計算装置１Ａは、複数の正規化計算回路１２ａ、１２ｂを備え、正規化計算を並列に行う。例えば、図５で説明したサンプルコードにおいて、点線の枠５ａに示す正規化計算を並列に行う。以下、第１の実施の形態と異なる構成を中心に説明する。
【００７１】
図８に示すように、逆行列計算装置１Ａは、係数計算回路１１、複数の正規化計算回路１２ａ、１２ｂ、およびメモリ１３を備える。逆行列計算装置１Ａは、Ｎ行Ｎ列の入力行列Ａを入力として、ガウスの消去法に基づいて、Ｎ行Ｎ列の逆行列Ａ-1を出力する。
【００７２】
逆行列計算装置１Ａは、Ｍ個（例えば、Ｍは２以上かつＮ−１以下の整数）の正規化計算回路１２ａ、１２ｂを具備する。複数の正規化計算回路１２ａ、１２ｂは、並列に接続されている。図８の例では、逆行列計算装置１Ａは、２つの正規化計算回路１２ａ、１２ｂを備えている。正規化計算回路１２ａ、１２ｂのそれぞれは、図３で示したように、乗算回路１２０と減算回路１２１とを有する。
【００７３】
正規化計算回路１２ａ、１２ｂは、係数計算回路１１による計算結果Ａ11’を用いて、入力行列Ａの（ｉ＋１）行（ｉ＋１）列成分を正規化する。本実施の形態では、Ｍ個の正規化計算回路１２ａ、１２ｂでＮ行分の正規化計算を並列に処理する。したがって、例えば、図８の例に示すように、Ｍ＝２の場合、各正規化計算回路１２ａ、１２ｂは、（Ｎ−１）／２行分の正規化計算を繰り返すことで、Ｎ行Ｎ列の入力行列Ａにおける正規化計算を完了することができる。Ｍ＝Ｎ−１の場合には、正規化計算は１回で完了することになる。特にＮが３以上の場合に有効である。
【００７４】
プロセッサ１０２は、正規化計算回路１２ａ、１２ｂのそれぞれから出力されて得られた計算結果Ａ12’に含まれる、拡大行列（Ａ｜Ｉ）の入力行列Ａが階段化された列以降のＮ行Ｎ列分の行列Ａ’をメモリ１３に記憶させる。これによって、メモリ１３記憶されていたＮ行Ｎ列行列が更新される。
【００７５】
このように、第２の実施の形態に係る逆行列計算装置１Ａは、Ｍ個の正規化計算回路１２ａ、１２ｂが並列に正規化計算を行うので、Ｎ行Ｎ列の入力行列Ａに対しては、Ｎ行分の正規化計算が不要となる。その結果として、逆行列計算装置１Ａでは、逆行列Ａ-1を求める計算処理を高速化することができる。
【００７６】
なお、正規化計算回路１２ａ、１２ｂのＭ個の数については、例えば、入力行列Ａのサイズ、使用するＦＰＧＡなどのハードウェアのリソースや所望とされる処理速度などに鑑み、最適な個数を設定すればよい。
【００７７】
［第３の実施の形態］
次に、本発明の第３の実施の形態について説明する。なお、以下の説明では、上述した第１および第２の実施の形態と同じ構成については同一の符号を付し、その説明を省略する。
【００７８】
第１の実施の形態では、正規化計算回路１２は、１つの乗算回路１２０と１つの減算回路１２１を備える場合について説明した。また、第２の実施の形態では、逆行列計算装置１Ａは、複数の正規化計算回路１２ａ、１２ｂを備え、並列に正規化計算を行う場合について説明した。
【００７９】
これに対して、第３の実施の形態に係る逆行列計算装置１は、複数の乗算回路１２０ａ、１２０ｂと、減算回路１２１ａ、１２１ｂとが１つの正規化計算回路１２Ｂに具備されている。第３の実施の形態に係る逆行列計算装置１は、例えば、図５で説明したサンプルコードにおいて、点線の枠５ｂに示す正規化計算の内部処理を並列に行う。第３の実施の形態に係る逆行列計算装置１が備えるその他の構成は、第１の実施の形態と同様である（図１、図２、図４）。
【００８０】
正規化計算回路１２Ｂは、係数計算回路１１による計算結果Ａ11’を入力とし、１行ごとの各成分の乗算処理と減算処理とからなる正規化計算を行い、計算結果Ａ12’を出力する。例えば、Ｎ行Ｎ列の入力行列Ａにおいては、１行あたりＮ個の成分を有し、Ｎ回の乗算および減算処理が必要となる。正規化計算回路１２Ｂは、例えば、１行あたりの計算に必要とされる乗算および減算を並列に処理する。
【００８１】
図９に示すように、正規化計算回路１２Ｂは、Ｍ個（Ｍは２以上かつＮ以下の整数）の乗算回路１２０ａ、１２０ｂと減算回路１２１ａ、１２１ｂとを備え、１行分の正規化計算をＭ並列で行う。そのため、Ｎ／Ｍ回の計算を繰り返すことで、１行分の正規化計算の結果を得ることができる。例えば、図９に示すように、Ｍ＝２の場合、Ｎ／２回の乗算処理および減算処理を繰り返すことで、１行分の正規化計算の処理を完了することができる。Ｍ＝Ｎの場合、１回の乗算および減算処理によって１行分の正規化計算を完了する。
【００８２】
正規化計算回路１２Ｂは、Ｎ行分の正規化計算を行い、計算結果Ａ12’を出力する。
プロセッサ１０２はそれぞれの減算回路１２１ａ、１２１ｂから出力される減算結果に基づく計算結果Ａ12’のうち、有意な値を含むＮ行Ｎ列の行列Ａ’でメモリ１３に記憶されている行列を更新する。
【００８３】
このように、第３の実施の形態によれば、正規化計算回路１２Ｂは、Ｍ個の乗算回路１２０ａ、１２０ｂおよび減算回路１２１ａ、１２１ｂにより乗算および減算を並列に処理するので、１行分の正規化計算処理における繰り返しの計算回数を削減することができる。１行分の正規化計算処理をより高速化できるため、結果として、逆行列Ａ-1を求めるための計算処理を高速化することができる。
【００８４】
なお、説明した第３の実施の形態に係る正規化計算回路１２Ｂは、第２の実施の形態に係るＭ個の正規化計算回路１２ａ、１２ｂと組み合わせることも可能である。このとき、乗算回路１２０ａ、１２０ｂおよび減算回路１２１ａ、１２１ｂのＭ個の数については、例えば、入力行列Ａのサイズ、使用するＦＰＧＡなどのハードウェアのリソースや所望とされる処理速度などに鑑み、最適な個数を設定すればよい。
【００８５】
［第４の実施の形態］
次に、本発明の第４の実施の形態について説明する。なお、以下の説明では、上述した第１から第３の実施の形態と同じ構成については同一の符号を付し、その説明を省略する。
【００８６】
第１の実施の形態では、係数計算回路１１が逆数回路１１０と１つの乗算回路１１１とを備える場合について説明した。また、第３の実施の形態では、正規化計算回路１２Ｂが複数の乗算回路１２０ａ、１２０ｂおよび減算回路１２１ａ、１２１ｂを備え、１行分の正規化計算を並列に処理する場合について説明した。
【００８７】
これに対し、第４の実施の形態では、係数計算回路１１Ａが複数の乗算回路１１１ａ、１１１ｂを備える。第４の実施の形態に係る逆行列計算装置１は、例えば、図５で説明したサンプルコードにおいて、点線の枠５ｃに示す係数計算の内部処理を並列に行う。なお、第４の実施の形態に係る逆行列計算装置１のその他の構成は第１の実施の形態と同様である（図１、図３、図４）。
【００８８】
図１０に示すように、係数計算回路１１Ａは、逆数回路１１０とＭ個（Ｍは２以上かつＮ以下の整数）の乗算回路１１１ａ、１１１ｂを備える。
逆数回路１１０は、例えば、Ｎ行Ｎ列の入力行列Ａが入力された場合に、対角成分である（ｉ＋１）行（ｉ＋１）列成分の値の逆数を求める。
【００８９】
乗算回路１１１ａ、１１１ｂは、（ｉ＋１）行目の各成分に対して逆数回路１１０が求めた対角成分の逆数を乗算する。より詳細には、Ｍ個の乗算回路１１１ａ、１１１ｂのそれぞれは、入力行列Ａの（ｉ＋１）行に含まれるＮ個の成分に対して行う乗算処理を並列に実行する。例えば、図１０に示すように、Ｍ＝２の場合、各乗算回路１１１ａ、１１１ｂのそれぞれは、Ｎ／２回の乗算処理を行う。このように、Ｎ回の繰り返しが必要な１行分の乗算処理について、本実施の形態に係るＭ個の乗算回路１１１ａ、１１１ｂを用いることで、係数計算をＭ並列で行う。
【００９０】
プロセッサ１０２は、それぞれの乗算回路１１１ａ、１１１ｂによる乗算結果および逆数を計算結果Ａ11’としてメモリ１３に書き込む。
【００９１】
このように、第４の実施の形態によれば、係数計算回路１１ＡがＭ個の乗算回路１１１ａ、１１１ｂを備え、係数計算における乗算処理を並列に処理するので、１行分の各成分に対する係数計算の回数を削減して、係数計算処理をより高速化することができる。
【００９２】
また、第４の実施の形態に係る係数計算回路１１Ａを備えた逆行列計算装置１は、逆行列Ａ-1を求める計算処理をより高速化することができる。
【００９３】
なお、乗算回路１１１ａ、１１１ｂのＭ個の数については、例えば、入力行列Ａのサイズ、使用するＦＰＧＡなどのハードウェアのリソースや所望とされる処理速度などに鑑み、最適な個数を設定すればよい。
【００９４】
また、第４の実施の形態に係る係数計算回路１１Ａは、第２から第３の実施の形態と適宜組み合わせることも可能である。
【００９５】
以上、本発明の逆行列計算装置、および逆行列計算処理方法における実施の形態について説明したが、本発明は説明した実施の形態に限定されるものではなく、請求項に記載した発明の範囲において当業者が想定し得る各種の変形を行うことが可能である。
【００９６】
例えば、説明した実施の形態に係る逆行列計算装置は、実数を成分とする行列を扱う場合について説明したが、複素数を成分とする行列を扱うこともできる。
【００９７】
また、説明した実施の形態に係る逆行列計算装置は、協調無線リソース制御方式を採用した複数のＵＥおよびアンテナを含む無線ネットワークシステムのスケジューラに搭載され、システムのスループットや送信重み行列を計算する専用のアクセラレータとして用いることができる（非特許文献２参照）。本実施の形態に係る逆行列計算回路を用いることで、協調無線リソース制御方式の処理を高速化することができる。
【符号の説明】
【００９８】
１…逆行列計算装置、１１…係数計算回路、１２…正規化計算回路、１３…メモリ、１０１…バス、１０２…プロセッサ、１０３…主記憶装置、１０４…通信インターフェース、１０５…補助記憶装置、１０６…入出力装置、１０７…表示装置、１１０…逆数回路、１１１、１２０…乗算回路、１２１…減算回路、ＮＷ…通信ネットワーク。
【図１】
2020091691.tif 000003
【図２】
2020091691.tif 000004
【図３】
2020091691.tif 000005
【図４】
2020091691.tif 000006
【図５】
2020091691.tif 000007
【図６】
2020091691.tif 000008
【図７】
2020091691.tif 000009
【図８】
2020091691.tif 000010
【図９】
2020091691.tif 000011
【図１０】
2020091691.tif 000012
【図１１】
2020091691.tif 000013