(57)【要約】      （修正有）【課題】処理演算量を少なくし、回路規模を小型化し、消費電力を削減するQL分解アルゴリズムの行列における数値分解方法を提供する。【解決手段】入力される行列Hを行列Qと下三角行列Lとに分解するQL分解に関し、行列Hと該行列の複素共役転置行列HＨと行列Hとを乗算して求めた正方行列Gを入力し、行列Hの各要素を、空行列Qに対して付与して行列Qとし、正方行列Gの下三角部分の各要素を空三角行列Lに対して付与して下三角行列Lとする過程と、下三角行列Lを読み出し、行ベクトル単位に、各行ベクトルにおける非ゼロ要素のみの部分行列に対して演算を行い、行列Lの各行ベクトルを算出する過程と、記憶部から行列Qを読み出し、列ベクトル単位に演算を行い、行列Qの各列ベクトルを求める過程と、行列L，Qを求める程を同一ループ内で、行列Hの列数に対応する回数繰り返す過程とを有する。【選択図】図１
2008129861.tif 000002
【特許請求の範囲】
【請求項１】
入力される行列Ｈを行列Ｑと下三角行列Ｌとに分解するＱＬ分解を行う数値分解方法であって、
初期化手段が、記憶部に記憶されている分解対象である行列Ｈ、及び該行列の複素共役転置行列ＨＨと行列Ｈとを乗算して求めた正方行列Ｇを入力し、行列Ｈの各要素を、空行列Ｑに対して付与して仮の行列Ｑとし、正方行列Ｇの下三角部分の各要素を空三角行列Ｌに対して付与して仮の下三角行列Ｌとする初期化過程と、
行列Ｌ演算部が前記記憶部から前記仮の下三角行列Ｌを読み出し、この仮の下三角行列Ｌを行ベクトル単位に、下部から上部方向に、各行ベクトルにおける非ゼロ要素のみの部分行列に対して、対応する行ベクトルより下部の要素を所定の割合にて順次減算する演算を行い、算出された行列Ｌの各行ベクトルを記憶部に記憶する行列Ｌ演算過程と、
行列Ｑ演算部が前記記憶部から前記仮の行列Ｑを読み出し、この仮の行列Ｑを列ベクトル単位に、列ベクトルの各要素より、所定の列ベクトルの要素を順次減算する演算を行い、算出された行列Ｑの各列ベクトルを記憶部に記憶する行列Ｑ演算過程と、
演算処理部が前記行列Ｌ演算過程及び行列Ｑ演算過程を同一の処理ループ内にて行い、この処理ループを行列Ｈの列数に対応する回数繰り返し、行列Ｈを分解した行列Ｑ及び下三角行列Ｌを、記憶部から読み出して出力する演算処理過程と
を有することを特徴とする行列における数値分解方法。
【請求項２】
入力される行列Ｈを行列Ｑと下三角行列Ｌとに分解するＱＬ分解を行う数値分解方法であって、
初期化手段が、記憶部に記憶されている分解対象である行列Ｈ、及び該行列の複素共役転置行列ＨＨと行列Ｈとを乗算して求めた正方行列Ｇを入力し、行列Ｈの各要素を、空行列Ｑに対して付与して仮の行列Ｑとし、正方行列Ｇの下三角部分の各要素を空三角行列Ｌに対して付与して仮の下三角行列Ｌとする初期化過程と、
行列Ｌ演算部が前記記憶部から前記仮の下三角行列Ｌを読み出し、この仮の下三角行列Ｌを行ベクトル単位に、下部から上部方向に、各行ベクトルにおける非ゼロ要素のみの部分行列に対して、対応する行ベクトルより上部の要素を所定の割合にて順次減算する演算を行い、算出された行列Ｌの各行ベクトルを記憶部に記憶する行列Ｌ演算過程と、
行列Ｑ演算部が前記記憶部から前記仮の行列Ｑを読み出し、この仮の行列Ｑを列ベクトル単位に、列ベクトルの各要素より、所定の列ベクトルの要素を順次減算する演算を行い、算出された行列Ｑの各列ベクトルを記憶部に記憶する行列Ｑ演算過程と、
演算処理部が前記行列Ｌ演算過程及び行列Ｑ演算過程を、各々独立した処理ループ内にて行い、この各処理ループを行列Ｈの列数に対応する回数繰り返し、行列Ｈを分解した行列Ｑ及び下三角行列Ｌを、記憶部から読み出して出力する演算処理過程と
を有し、
前記演算処理部が行列Ｌ演算過程の繰り返しループが終了した後に、行列Ｑ演算過程の繰り返しループを実行することを特徴とする行列における数値分解方法。
【請求項３】
入力される行列Ｈを行列Ｑと下三角行列Ｌとに分解するＱＬ分解を行う数値分解方法であって、
初期化手段が、記憶部に記憶されている分解対象である行列Ｈ、及び該行列の複素共役転置行列ＨＨと行列Ｈとを乗算して求めた正方行列Ｇを入力し、行列Ｈの各要素を、空行列Ｑに対して付与して仮の行列Ｑとし、正方行列Ｇの上三角部分の各要素を空三角行列Ｕに対して付与して上三角行列Ｕとする初期化過程と、
行列Ｌ演算部が前記記憶部から前記仮の上三角行列Ｕを読み出し、この上三角行列Ｕを列ベクトル単位に、右端から左端方向に、各列ベクトルにおける非ゼロ要素のみの部分行列に対して演算を行い、算出された行列Ｕの各列ベクトルを記憶部に記憶する行列Ｕ演算過程と、
行列Ｌ演算部が所定の回数の処理ループの繰り返しの終了の後、前記行列Ｕを読み出し、この行列Ｕに対して複素共役転置処理を行い、この演算結果を下三角行列Ｌとして、記憶部に記憶する複素共役転置処理過程と、
行列Ｑ演算部が前記記憶部から前記仮の行列Ｑを読み出し、この仮の行列Ｑを列ベクトル単位に、列ベクトルの各要素より、所定の列ベクトルの要素を順次減算する演算を行い、算出された行列Ｑの各列ベクトルを記憶部に記憶する行列Ｑ演算過程と、
演算処理部が前記行列Ｕ演算過程及び行列Ｑ演算過程を同一の処理ループ内にて行い、この処理ループを行列Ｈの列数に対応する回数繰り返し、行列Ｈを分解した行列Ｑ及び下三角行列Ｌを、記憶部から読み出して出力する演算処理過程と
を有することを特徴とする行列における数値分解方法。
【請求項４】
入力される行列Ｈを行列Ｑと下三角行列Ｌとに分解するＱＬ分解を行う数値分解方法であって、
初期化手段が、記憶部に記憶されている分解対象である行列Ｈ、及び該行列の複素共役転置行列ＨＨと行列Ｈとを乗算して求めた正方行列Ｇを入力し、行列Ｈの各要素を、空行列Ｑに対して付与して仮の行列Ｑとし、正方行列Ｇの上三角部分の各要素を空三角行列Ｕに対して付与して上三角行列Ｕとする初期化過程と、
行列Ｌ演算部が前記記憶部から前記仮の上三角行列Ｕを読み出し、この上三角行列Ｕを列ベクトル単位に、右端から左端方向に、各列ベクトルにおける非ゼロ要素のみの部分行列に対して演算を行い、算出された行列Ｕの各列ベクトルを記憶部に記憶する行列Ｕ演算過程と、
行列Ｌ演算部が所定の回数の処理ループの繰り返しの終了の後、前記行列Ｕを読み出し、この行列Ｒに対して複素共役転置処理を行い、この演算結果を下三角行列Ｌとして、記憶部に記憶する複素共役転置処理過程と、
行列Ｑ演算部が前記記憶部から前記仮の行列Ｑを読み出し、この仮の行列Ｑを列ベクトル単位に、列ベクトルの各要素より、所定の列ベクトルの要素を順次減算する演算を行い、算出された行列Ｑの各列ベクトルを記憶部に記憶する行列Ｑ演算過程と、
演算処理部が前記行列Ｌ演算過程及び行列Ｑ演算過程を、各々異なった処理ループ内にて行い、この各処理ループを行列Ｈの列数に対応する回数繰り返し、行列Ｈを分解した行列Ｑ及び下三角行列Ｌを、記憶部から読み出して出力する演算処理過程と
を有することを特徴とする行列における数値分解方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、数値計算分野における行列のＱＬ分解計算方法に属し、あらゆるデジタル信号処理分野（例えば、デジタル通信，画像処理，音声処理，ソナーシステム，レーザシステムなど）において、ある行列Ｈを、行列Ｑと下三角行列Ｌとの２つに分解することに適用する行列における数値分解方法に関する。
【背景技術】
【０００２】
数値計算の分野において、行列Ｈを、行列Ｑと下三角行列Ｌとの２つに分解する計算アルゴリズムがあり、その計算イメージを図７に示す。
図７において、従来のＱＲ分解アルゴリズムにより、以下に示す（１）式に基づき、行列Ｈを行列Ｑと下三角行列Ｌとの２つの行列に分解される。ここで、行列ＨはＲ行，Ｔ列の行列を表し、行列ＱはＲ行，Ｔ列の行列を表し、下三角行列ＬはＴ行，Ｔ列の行列を表している。
【０００３】
【数１】
2008129861.tif 000003
【０００４】
上記（１）式に示すように、行列Ｑ及び下三角行列Ｌに分解するアルゴリズムとして、Classical Gram-Schmidt QR分解法，Modified Gram-Schmidt QR分解法，Householder QR分解法，Given QR分解法などがある（例えば、非特許文献１参照）。
【非特許文献１】Gene H.Golub, Charles F.Van Loan、Matrix Computations ThirdEdition. Hohns Hopkins published
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、非特許文献１に示すＱＲ分解方法にあっては、ＧＲアルゴリズムにおける行列のＱＲ分解の繰り返しにより行われるため、所要処理演算量が大きいという問題がある。
また、従来例にあっては、アルゴリズムを実際の物理的な回路により実現する場合、回路規模が上記所要処理演算量に比例するため、必要な回路規模も大きくなり、装置を小型化することが困難である。
また、従来例にあっては、上述したように、回路規模が大きくなることにより、消費電力も比例して増加することとなり、バッテリで動作する携帯機器等で使用した場合、電力の消耗が早く、長時間使用することができなくなる。
【０００６】
本発明は、このような事情に鑑みてなされたもので、入力される行列Ｇ及びＨが既知である場合、従来のＱＲ分解のアルゴリズムに比較して、所要処理演算量を少なくし、回路規模を小型化し、消費電力を削減することができるＱＬ分解のアルゴリズムの行列における数値分解方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の行列における数値分解方法は、入力される行列Ｈを行列Ｑと下三角行列Ｌとに分解するＱＬ分解を行う数値分解方法であって、初期化手段が、記憶部に記憶されている分解対象である行列Ｈ、及び該行列の複素共役転置行列ＨＨと行列Ｈとを乗算して求めた正方行列Ｇを入力し、行列Ｈの各要素を、空行列Ｑに対して付与して仮の行列Ｑとし、正方行列Ｇの下三角部分の各要素を空三角行列Ｌに対して付与して仮の下三角行列Ｌとする初期化過程と、行列Ｌ演算部が前記記憶部から前記仮の下三角行列Ｌを読み出し、この仮の下三角行列Ｌを行ベクトル単位に、下部から上部方向に、各行ベクトルにおける非ゼロ要素のみの部分行列に対して、対応する行ベクトルより下部の要素を所定の割合にて順次減算する演算（例えば、第１の実施形態における処理（３）〜処理（５）における（３）式の演算）を行い、算出された行列Ｌの各行ベクトルを記憶部に記憶する行列Ｌ演算過程と、行列Ｑ演算部が前記記憶部から前記仮の行列Ｑを読み出し、この仮の行列Ｑを列ベクトル単位に、列ベクトルの各要素より、所定の列ベクトルの要素を順次減算する演算を行い、算出された行列Ｑの各列ベクトルを記憶部に記憶する行列Ｑ演算過程と、演算処理部が前記行列Ｌ演算過程及び行列Ｑ演算過程を同一の処理ループ内にて行い、この処理ループを行列Ｈの列数に対応する回数繰り返し（第１の実施形態における処理（２）から処理（１１）のＴ回の演算ループ）、行列Ｈを分解した行列Ｑ及び下三角行列Ｌを、記憶部から読み出して出力する演算処理過程とを有することを特徴とする。
【０００８】
本発明の行列における数値分解方法は、入力される行列Ｈを行列Ｑと下三角行列Ｌとに分解するＱＬ分解を行う数値分解方法であって、初期化手段が、記憶部に記憶されている分解対象である行列Ｈ、及び該行列の複素共役転置行列ＨＨと行列Ｈとを乗算して求めた正方行列Ｇを入力し、行列Ｈの各要素を、空行列Ｑに対して付与して仮の行列Ｑとし、正方行列Ｇの下三角部分の各要素を空三角行列Ｌに対して付与して仮の下三角行列Ｌとする初期化過程と、行列Ｌ演算部が前記記憶部から前記仮の下三角行列Ｌを読み出し、この仮の下三角行列Ｌを行ベクトル単位に、下部から上部方向に、各行ベクトルにおける非ゼロ要素のみの部分行列に対して、対応する行ベクトルより下部の要素を所定の割合にて順次減算する演算（例えば、第２の実施形態における処理（３）〜処理（５）における（３）式の演算）を行い、算出された行列Ｌの各行ベクトルを記憶部に記憶する行列Ｒ演算過程（第２の実施形態における処理（２）から処理（７）のＴ回の演算ループ）と、行列Ｑ演算部が前記記憶部から前記仮の行列Ｑを読み出し、この仮の行列Ｑを列ベクトル単位に、列ベクトルの各要素より、所定の列ベクトルの要素を順次減算する演算を行い、算出された行列Ｑの各列ベクトルを記憶部に記憶する行列Ｑ演算過程（第２の実施形態における処理（８）から処理（１２）のＴ回の演算ループ）と、演算処理部が前記行列Ｌ演算過程及び行列Ｑ演算過程を、各々独立した処理ループ内にて行い、この各処理ループを行列Ｈの列数に対応する回数繰り返し、行列Ｈを分解した行列Ｑ及び下三角行列Ｌを、記憶部から読み出して出力する演算処理過程とを有し、前記演算処理部が行列Ｌ演算過程の繰り返しループが終了した後に、行列Ｑ演算過程の繰り返しループを実行することを特徴とする。
【０００９】
本発明の行列における数値分解方法は、入力される行列Ｈを行列Ｑと下三角行列Ｌとに分解するＱＬ分解を行う数値分解方法であって、初期化手段が、記憶部に記憶されている分解対象である行列Ｈ、及び該行列の複素共役転置行列ＨＨと行列Ｈとを乗算して求めた正方行列Ｇを入力し、行列Ｈの各要素を、空行列Ｑに対して付与して仮の行列Ｑとし、正方行列Ｇの上三角部分の各要素を空三角行列Ｕに対して付与して上三角行列Ｕとする初期化過程と、行列Ｌ演算部が前記記憶部から前記仮の上三角行列Ｕを読み出し、この上三角行列Ｕを列ベクトル単位に、右端から左端方向に、各列ベクトルにおける非ゼロ要素のみの部分行列に対して演算を行い、算出された行列Ｕの各列ベクトルを記憶部に記憶する行列Ｕ演算過程（第３の実施形態における処理（３）から処理（５）の演算ループ）と、行列Ｌ演算部が所定の回数の処理ループの繰り返しの終了の後、前記行列Ｕを読み出し、この行列Ｕに対して複素共役転置処理を行い、この演算結果を下三角行列Ｌとして、記憶部に記憶する複素共役転置処理過程と、行列Ｑ演算部が前記記憶部から前記仮の行列Ｑを読み出し、この仮の行列Ｑを列ベクトル単位に、列ベクトルの各要素より、所定の列ベクトルの要素を順次減算する演算を行い、算出された行列Ｑの各列ベクトルを記憶部に記憶する行列Ｑ演算過程と、演算処理部が前記行列Ｕ演算過程及び行列Ｑ演算過程を同一の処理ループ（第３の実施形態における処理（２）から処理（１１）の演算ループ）内にて行い、この処理ループを行列Ｈの列数に対応する回数繰り返し、行列Ｈを分解した行列Ｑ及び下三角行列Ｌを、記憶部から読み出して出力する演算処理過程とを有することを特徴とする。
【００１０】
本発明の行列における数値分解方法は、入力される行列Ｈを行列Ｑと下三角行列Ｌとに分解するＱＬ分解を行う数値分解方法であって、初期化手段が、記憶部に記憶されている分解対象である行列Ｈ、及び該行列の複素共役転置行列ＨＨと行列Ｈとを乗算して求めた正方行列Ｇを入力し、行列Ｈの各要素を、空行列Ｑに対して付与して仮の行列Ｑとし、正方行列Ｇの上三角部分の各要素を空三角行列Ｕに対して付与して上三角行列Ｕとする初期化過程と、行列Ｌ演算部が前記記憶部から前記仮の上三角行列Ｕを読み出し、この上三角行列Ｕを列ベクトル単位に、右端から左端方向に、各列ベクトルにおける非ゼロ要素のみの部分行列に対して演算を行い、算出された行列Ｕの各列ベクトルを記憶部に記憶する行列Ｕ演算過程（第４の実施形態における処理（２）から処理（７）の演算ループ）と、行列Ｌ演算部が所定の回数の処理ループの繰り返しの終了の後、前記行列Ｕを読み出し、この行列Ｒに対して複素共役転置処理を行い、この演算結果を下三角行列Ｌとして、記憶部に記憶する複素共役転置処理過程と、行列Ｑ演算部が前記記憶部から前記仮の行列Ｑを読み出し、この仮の行列Ｑを列ベクトル単位に、列ベクトルの各要素より、所定の列ベクトルの要素を順次減算する演算を行い、算出された行列Ｑの各列ベクトルを記憶部に記憶する行列Ｑ演算過程と、演算処理部が前記行列Ｌ演算過程及び行列Ｑ演算過程（第４の実施形態における処理（９）から処理（１４）の演算ループ）を、各々異なった処理ループ内にて行い、この各処理ループを行列Ｈの列数に対応する回数繰り返し、行列Ｈを分解した行列Ｑ及び下三角行列Ｌを、記憶部から読み出して出力する演算処理過程とを有することを特徴とする。
【発明の効果】
【００１１】
以上説明したように、本発明のアルゴリズムによれば、部分行列毎に行列全体を演算していくため、所要処理演算量が従来アルゴリズム（Classical Gram-Schmidt QR分解法，Modified Gram-Schmidt QR分解法，Householder QR分解法，Given QR分解法など）に比較して少なくなる。
また、本発明のアルゴリズムによれば、ＱＬ分解法のための回路を小さい規模で実現できる。すなわち、回路規模は所要演算量に比例するため、従来例に比較して演算量が少なくなるため、行列のＱＬ分解の所要回路規模も従来に比較して小さくなり、従来装置に比較して小型化及び低製造コスト化を実現できる。
【００１２】
また、本発明のアルゴリズムによれば、上述したように、ＱＬ分解における所要演算量が少ないため、構成した回路における消費電流が従来に比較して低減されるため、携帯機器に用いた場合に、携帯機器のバッテリの寿命を延ばし、携帯性を向上させることができるという効果が得られる。
また、本発明のアルゴリズムによれば、上述したように、回路規模が小さくなり、低消費電力化、低製造コスト化が可能となり、大量生産に適している。
【発明を実施するための最良の形態】
【００１３】
本発明の行列における数値分解方法は、分解対象の行列Ｈに対する複素共役転置の行列ＨＨを数値演算により求め、行列Ｈと行列ＨＨとを乗算することにより、正方行列Ｇを算出し、この行列Ｈと正方行列Ｇとを用いて、行列Ｈを行列Ｑと下三角行列Ｌとに分解するアルゴリズである。後述するように、行列Ｈから作られる行列Ｇ（Ｇ＝ＨＨＨ＋γ：γは雑音標準分散／信号標準分散などのパラメータ）を入力し、Ｔ回（Ｔは行列Ｈの列ベクトル数）の巡回（ループ演算）によりＨ＝ＱＬとなる行列Ｑ，Ｌ（下三角行列）を生成する。
【００１４】
本願発明は、複素領域（あるいは実数領域）にある行列Ｈに対して、Ｇ＝ＨＨＨ＋γが既知であることを前提に、行列Ｈを２つの行列Ｑと下三角行列Ｌに分解する。
すなわち、本発明は行列Ｈのみを用いて、この行列Ｈを行列Ｑ及び行列Ｌの２つの行列に分解する従来のアルゴリズムにおける所要演算量が大きい、所要回路規模が大きい、消費電力が大きいなどの欠点を解決するものである。
すなわち、計算のイメージは、図１に示すような流れで行われ、行列Ａと行列Ｇとを入力し、以下の（２）式に示すように、行列Ｌを各行毎に、最下部の行から、最上部の行まで順次算出し、行列Ｑを各列毎に、右側から左側まで順次算出する。この（２）式において、ｑｔ（１≦ｔ≦Ｔ）は行列Ｑのｔ番目の列ベクトルを示しており、ｌｔ（１≦ｔ≦Ｔ）は行列Ｌのｔ番目の行ベクトルを示している。
【００１５】
【数２】
2008129861.tif 000004
【００１６】
＜第１の実施形態＞
以下、本発明の第１の実施形態による数値分解システムを図面を参照して説明する。図２は同実施形態による数値分解システムの構成例を示すブロック図である。
第１の実施形態による数値分解システムは、入力部１，初期化部４，行列Ｌ演算部５，行列Ｑ演算部６，記憶部７及び演算制御部８を有している。
【００１７】
入力部１は、分解対象のＲ行，Ｔ列の行列Ｈ及びＴ行，Ｔ列の正方行列Ｇが既知の値を、記憶部７に記憶する。すなわち、行列Ｈ及び行列Ｇ（＝ＨＨＨ）が既知であるとし、これらの行列が外部機器から入力されるとして、以下の説明を行う。また、入力部１が入力される行列Ｈ及び行列Ｇを、直接に初期化部４へ出力するようにしてもよい。
初期化部４は、行列Ｌ演算部５及び行列Ｑ演算部６にて用いる仮の行列を設定する。すなわち、初期化部４は、空行列Ｑに対して、分解対象の行列Ｈを付与して（行列Ｈの要素を、空行列Ｑの対応する要素の位置（行及び列で指定される）に要素のデータを上書きして）、行列Ｑとし、空行列Ｌに対して正方行列の下三角行列を付与して（対応する位置に要素のデータを上書きして）、行列Ｌとして初期化を行う。
【００１８】
行列Ｌ演算部５は、設定された数値ｉにより、記憶部７に記憶されている対応するｉ行目の行ベクトルＬ（i,１:i）、すなわち行ベクトルｌｉのデータを読み出すとともに、行列Ｌのｋ行，ｉ列目の要素ｌｋ，ｉからスカラーｌｋ，ｉ＊を算出し、以下の（３）式により、新たな行ベクトルを算出して、記憶部７の読み出した位置（すなわちアドレス）に上書きを行い、行ベクトルのデータの変更を行う。
ここで、行ベクトルＬ（i,1:i）は、ｉ行目の行ベクトルにおける１番目の列成分からｉ番目までの列成分までの部分行列を示し、スカラーｌｋ，ｉ＊は行列Ｌのｋ行，ｉ列目の要素の複素共役を示している。すなわち、各列ベクトル単位にて、非ゼロ要素の部分からなる部分行列のみの演算を行っている。
Ｌ（i,1:i）：＝Ｌ（i,1:i）−ｌｋ，ｉ＊・Ｌ（ｋ,1:i）…（３）
【００１９】
すなわち、行列Ｌ演算部５は、行ベクトルＬ（ｋ,1:i）に対して、スカラーｌｋ，ｉ＊を乗算し、乗算結果をこの行ベクトルから減算して、この減算結果を新たな行ベクトルＬ（i,1:i）として、記憶部７に対して、読み出した位置に上書きする。
このとき、行列Ｒ演算部４は、ｋをデクリメントして、上記（３）式を、Ｔからｉ＋１の間、すなわちｉ＋１≦ｋ≦Ｔの範囲において繰り返して行う。
【００２０】
また、行列Ｌ演算部５は、以下の（４）式に示すように、最終的に得られた行ベクトルＬ（i,1:i）を記憶部７から読み出し、スカラーｌｉ，ｉの平方根である（ｌｉ，ｉ）１／２により除算し、この除算結果を最終的な行ベクトルＬ（i,1:i）を演算結果として、記憶部７に記憶する。このスカラーｌｉ，ｉは、行列Ｌのｉ行番目，ｉ列番目の要素を示している。
Ｌ（i,1:i）：＝Ｌ（i,1:i）／（ｌｉ，ｉ）１／２       …（４）
【００２１】
行列Ｑ演算部６は、設定された数値ｉにより、記憶部７から行列Ｑのｉ番目の列ベクトルＱ（：,ｉ）を読み出し、以下の（５）式に示すように、スカラーｌｉ，ｉにより除算し、除算結果を新たな列ベクトルＱ（：,ｉ）として、記憶部７において読み出した位置に書き込む。このスカラーは、行列Ｌにおけるｉ行，ｉ列目の要素である。
Ｑ（：,ｉ）：＝Ｑ（：,ｉ）／ｌｉ，ｉ              …（５）
また、行列Ｑ演算部６は、記憶部７から列ベクトルＱ（：,ｊ）を読み出し、以下の（６）式により、新たな列ベクトルＱ（：，ｊ）を算出し、記憶部７の読み出した位置に記憶する。ここで、スカラーｌｉ，ｊは、行列Ｌにおけるｉ行目，ｊ列目の要素である。
Ｑ（：,ｊ）：＝Ｑ（：,ｊ）−ｌｉ，ｊ・Ｑ（：,ｉ） …（６）
【００２２】
すなわち、行列Ｑ演算部６は、列ベクトルＱ（：,ｉ）の要素に対して、スカラーを乗算し、この乗算結果を列ベクトルＱ（：,ｊ）から減算し、この減算結果を新たな列ベクトルＱ（：,ｊ）として、記憶部７の読み出した位置に書き込み、データの更新を行う。
このとき、行列Ｑ演算部６は、ｊを初期値ｉ＋１とし、処理を１回行う毎にインクリメントしつつ、上記（６）式を、ｉ＋１≦ｊ≦Ｔの間で繰り返して行う。
演算制御部８は、行列Ｒ演算部５及び行列Ｑ演算部６における演算処理の順序制御と、各演算部における演算処理の回数の制御、すなわち演算ループの制御とを行っている。
【００２３】
次に、図２及び図３を参照して、第１の実施形態による数値分解システムの動作を説明する。図３は、第１の実施形態の数値分解システムのアルゴリズムにおける各部の処理を示したテーブルであり、（１）〜（１１）の処理が順次行われる。ここで、入力部１，複素共役転置行列生成部２及び正方行列生成部３の動作は省略され、行列Ｈ及び正方行列Ｇが各々求められ、すでに記憶部７に記憶されているとする。
処理（１）において、初期化部４は、記憶部７から分割対象の行列Ｈを読み出し、空行列Ｑに対し、この行列Ｈの各要素を、対応する行番号及び列番号で指定される位置に書き込み、すなわち空行列Ｑに対して行列Ｈの値を付与し、空行列ＱをＲ行，Ｔ列の行列とする。
また、初期化部４は、記憶部７から行列Ｇを読み出し、この行列Ｇから下三角部分を抽出し、空行列Ｌの対応する行番号及び列番号で指定される位置に書き込み、すなわち空行列Ｌに対して行列Ｇの下三角部分の要素を付与し、行列Ｌを下三角部分が非ゼロ要素である下三角行列である行列Ｌとする。
【００２４】
次に、処理（２）において、演算制御部８は、正方行列である行列Ｌの列数及び行数の数値Ｔを抽出し、行列Ｌ演算部５と行列Ｑ演算回路６とにおける繰り返し演算回数をＴとし、数値ｉを「１」に初期化して、処理（２）〜処理（１１）までの、行列Ｌ演算部５と行列Ｑ演算回路６とにおける演算処理を、数値ｉが１≦ｉ≦Ｔの間繰り返して行う。
ここで、例えば、１回の演算ループの処理が終了した後、処理（１１）にて数値ｉをデクリメント（１を減算）し、処理（２）にて数値ｉが１≦ｉ≦Ｔの範囲内であるか否かを検出し、範囲内であることを検出した場合、次の処理（３）へ処理を移し、一方、数値ｉが数値１を下回ったこと、すなわち０となったこと（範囲外であること）を検出すると、処理（２）〜処理（１１）の演算ループ（行列分割の演算ループ）を終了し、その時点で記憶部７に記憶されている行列Ｌ及び行列Ｑを、それぞれ行列Ｈを分解した下三角行列Ｌと行列Ｑとして出力する。
【００２５】
次に、処理（３）において、行列Ｌ演算部５は、演算制御部８から数値ｉを入力し、数値ｋを「Ｔ」に初期化して、処理（３）〜処理（５）までの演算ループを、１回の演算ループ終了毎に数値ｋをデクリメントし、数値ｋがＴからｉ＋１（すなわち、ｉ＋１≦ｋ≦Ｔ）の間繰り返して行い、演算ループ毎に（３）式により、（２）式の最左辺の行ベクトルｌ１〜行ベクトルｌＴの各行ベクトル（部分行列）を、行列の最下部の行ベクトルから最上部の行ベクトルの順に、すなわち行ベクトルｌＴから行ベクトルｌ１の向かい、順に行ベクトルを演算する。ここで、行ベクトルｌ１は、Ｌ（１，１：Ｔ）と同様である。
【００２６】
ここで、上記ｉ＋１≦ｋ≦Ｔの範囲にて、ｉ＝１の場合においても、ｋ＝１が成り立たないため、１行目の行ベクトルｌ１は行列Ｇの１行目の行ベクトルのままとする。
したがって、数値ｋ＝１以降において、行列Ｌ演算部５は、数値ｋがｉ＋１≦ｋ≦Ｔの範囲内にあることを検出すると、処理（４）へ処理を進める。
【００２７】
次に、処理（４）において、行列Ｌ演算部５は、数値ｉの示す行ベクトルｌｉにおける部分行列Ｌ（ｉ,１：ｉ）を、記憶部７に記憶されている行列Ｌから読み出す。
そして、行列Ｌ演算部５は、この部分行列Ｌ（ｉ,１：ｉ）に対し、（３）式の演算を行い、記憶部７における読み出した位置に書き込み、処理を処理（５）へ進める。
次に、処理（５）において、行列Ｌ演算部５は、１回の演算ループの毎に数値ｋをデクリメントし、処理を処理（３）へ進める。
【００２８】
次に、行列Ｌ演算部５は、処理（３）にて数値ｋがｉ＋１≦ｋ≦Ｔの範囲内であるか否かを検出し、範囲内であることを検出した場合、次の処理（４）へ処理を移し、一方、数値ｋが数値ｉ＋１を下回ったこと（範囲外であること）を検出すると、処理（３）〜処理（５）の演算ループ（行列Ｒ生成の演算ループ）を終了させ、処理を処理（６）へ移す。
【００２９】
次に、処理（６）において、行列Ｒ演算部５は、この時点の数値ｉに対応した行ベクトルにおける部分行列Ｌ（ｉ,１：ｉ）を、記憶部７に記憶された行列Ｌから読み出し、（４）式の演算処理を行い、演算結果を記憶部７の読み出した位置に上書きし、データの変更を行い、処理を処理（７）へ移す。
【００３０】
次に、処理（７）において、行列Ｑ演算部６は、演算制御部８から数値ｉを入力し、記憶部７に記憶された行列Ｑから、数値ｉに対応した列ベクトルｑｉ（すなわち、Ｑ（：，ｉ））を読み出し、（５）式に示す処理を行い、すなわちスカラーｌｉ，ｉにて列ベクトルｑｉを除算し、この除算結果を記憶部７の読み出した位置に書き込み、データの変更を行い、処理を処理（８）へ進める。
【００３１】
次に、処理（８）において、行列Ｑ演算部６は、数値ｊを「１」に初期化して、処理を処理（８）へ進める。
以下、行列Ｑ演算部６は、処理（８）〜処理（１０）までの演算ループを、数値ｊが１≦ｊ≦ｉ−１の間繰り返して行い、演算ループ毎に（３）式により、（２）式の最左辺の列ベクトルｑ１〜行ベクトルｑｉ−１の各列ベクトル（部分行列）を、行列の最右端の列ベクトルから最左端の列ベクトルの順に、すなわち列ベクトルｑｉ−１から列ベクトルｑ１に向かい、順に列ベクトルを演算する。ここで、列ベクトルｑjは、Ｑ（：,ｊ）と同様である。
【００３２】
次に、処理（９）において、行列Ｑ演算部６は、１≦ｊ≦ｉ−１の範囲から、Ｑ（：，ｉ）に対する（６）式の処理が実行されないため、演算ループにおいて、行列Ｑの第ｉ列目に対しては、（７）の処理のみが行われる。すなわち、ｉ列目の列ベクトルｑｉに対して、処理（７）の処理のみ行われ、処理（８）から処理（１０）までの処理は行われない。
そして、行列Ｑ演算部６は、数値ｊの示す列ベクトルｑｊ、すなわち部分行列Ｑ（,：ｉｊ）を、記憶部７に記憶されている行列Ｑから読み出す。
そして、行列Ｑ演算部６は、この部分行列Ｑ（,：ｉ）に対し、（６）式の演算を行い、記憶部７における読み出した位置に書き込み、処理を処理（１０）へ進める。
次に、処理（１０）において、行列Ｑ演算部６は、１回の演算ループの毎に数値ｊをインクリメントし、処理を処理（８）へ進める。
【００３３】
次に、行列Ｑ演算部６は、処理（８）にて数値ｊが１≦ｊ≦ｉ−１の範囲内であるか否かを検出し、範囲内であることを検出した場合、次の処理（９）へ処理を移し、一方、数値ｊが数値ｉ−１を超えたこと（範囲外であること）を検出すると、処理（８）〜処理（１０）の演算ループ（行列Ｑの生成の演算ループ）を終了させ、処理を処理（１１）へ移す。
【００３４】
＜第２の実施形態＞
第２の実施形態の数値分解システムは、第１の実施形態と同様の構成をしている。第２の実施形態と第１の実施形態との違いは、演算制御部８の行列Ｌ演算部５及び行列Ｑ演算部６の演算順序にある。すなわち、第１の実施形態においては、同一の演算ループ内にて、行列Ｌを生成する演算ループと行列Ｑを生成する演算ループとが実行されるアルゴリズムとなっている。
【００３５】
一方、第２の実施形態においては、演算制御部８が、行列Ｌを生成する演算ループと、行列Ｑを生成する演算ループとを、順番に、それぞれ独立に制御し、すなわち、行列Ｌの生成の演算ループが終了し、分割後の行列Ｌが求められた後、行列Ｑの生成の演算ループを開始して行列Ｑの生成を行い、行列Ｈが分解された行列Ｌ及び行列Ｑ各々の生成を別々に行うアルゴリズムとなっている。
したがって、演算制御部８及び初期化部４以外の他の構成要素（入力部１，行列Ｌ演算部５，行列Ｑ演算部６及び記憶部７）の動作は、第２の実施形態においても、第１の実施形態の構成と同様である。
【００３６】
以下、図２及び図４を参照して、第２の実施形態による数値分解システムの動作を説明する。図４は、第２の実施形態の数値分解システムのアルゴリズムにおける各部の処理を示したテーブルであり、（１）〜（１３）の処理が順次行われる。ここで、入力部１，複素共役転置行列生成部２及び正方行列生成部３の動作は省略され、行列Ｈ及び正方行列Ｇが各々求められ、すでに記憶部７に記憶されているとする。
処理（１）において、初期化部４は、記憶部７から分割対象の行列Ｈを読み出し、空行列Ｑに対し、この行列Ｈの各要素を、対応する行番号及び列番号で指定される位置に書き込み、すなわち空行列Ｑに対して行列Ｈの値を付与し、空行列ＱをＲ行，Ｔ列の行列とする。
また、初期化部４は、記憶部７から行列Ｇを読み出し、空行列Ｌに対し、この行列Ｇの各要素を、対応する行番号及び列番号で指定される位置に書き込み、すなわち空行列Ｌに対して行列Ｇの値を付与し、空行列ＬをＴ行，Ｔ列の正方行列とする。
【００３７】
次に、処理（２）において、演算制御部８は、正方行列である行列Ｌの列数及び行数の数値Ｔを抽出し、行列Ｌ演算回路５と行列Ｑ演算回路６とにおける繰り返し演算回数をＴとし、数値ｉを「Ｔ」に初期化して、処理（２）〜処理（７）までの、行列Ｌ演算回路５における演算処理を、数値ｉがＴから１の間、すなわち１≦ｉ≦Ｔの間繰り返して行う。ここで、例えば、１回の処理が終了した後、処理（７）にて数値ｉをデクリメント（１を減算）し、処理（２）にて数値ｉが１≦ｉ≦Ｔの範囲内であるか否か、すなわち数値ｉが０となったか否かを検出し、範囲内であることを検出した場合、次の処理（３）へ処理を移し、一方、数値ｉが１を下回ったこと（範囲外であること）を検出すると、処理（２）〜処理（７）の演算ループ（行列Ｌ生成の演算ループ）を終了し、その時点で記憶部７に記憶されている行列Ｌを、行列Ｈを分解した行列Ｑとして出力し、処理を処理（８）へ進める。
【００３８】
次に、処理（３）〜処理（６）までの処理は、第１の実施形態における処理（３）〜処理（６）それぞれと同様のため、処理の説明を省略する。
そして、処理（７）において、演算制御部８は、数値ｉをデクリメント（１を減算）し、処理を処理（２）ヘ進める。
次に、処理（２）において、演算制御部８は、数値ｉが１≦ｉ≦Ｔの範囲内であるか否かを検出し、範囲内であることを検出した場合、次の処理（３）へ処理を移し、一方、数値ｉが数値１を下回ったこと（範囲外であること）を検出すると、この時点における行列Ｌとして記憶部７へ記憶するとともに、処理を処理（８）へ進める。
【００３９】
次に、処理（８）において、演算制御部８は、Ｒ行，Ｔ列の行列である行列Ｑの列数及の数値Ｔを抽出し、行列Ｑ演算回路６における繰り返し演算回数をＴとし、数値ｉを「Ｔ」に初期化して、処理（８）〜処理（１３）までの、行列Ｌ演算部５における演算処理を、数値ｉがＴから１の範囲、すなわち１≦ｉ≦Ｔの間繰り返して行う。ここで、例えば、１回の演算ループの処理が終了した後、処理（１３）にて数値ｉをデクリメント（１を減算）し、処理（８）にて数値ｉが１≦ｉ≦Ｔの範囲内であるか否か、すなわちｉがおとなったか否かを検出し、範囲内であることを検出した場合、次の処理（９）へ処理を移し、一方、数値ｉが数値Ｔを下回ったこと（範囲外であること）を検出すると、処理（９）〜処理（１２）の演算ループ（行列Ｑ生成の演算ループ）を終了し、その時点で記憶部７に記憶されている行列Ｑを、行列Ｈを分解した行列Ｑとして出力し、行列Ｈの分解処理を終了する。上記、処理（９），（１０），（１１），（１２）各々は、それぞれ第１の実施形態における処理（７），（８），（９），（１０）と同様のため、説明を省略する。
【００４０】
すなわち、処理（２）〜処理（７）においては、Ｔ回（正方行列Ｇの行及び列の数に対応した回数）の演算ループにて、行列Ｌを（２）式の最下行の行ベクトルｌＴから、最上行の行ベクトルｌ１まで、順番に演算する。
また、処理（８）〜処理（１３）においては、Ｔ回（正方行列Ｇの行及び列の数に対応した回数）の演算ループにて、行列Ｑを（２）式の最右列の列ベクトルｑＴから、最左列の列ベクトルｑ１まで、順番に演算する。
【００４１】
＜第３の実施形態＞
以下、本発明の第３の実施形態による数値分解システムを図面を参照して説明する。図５は同実施形態による数値分解システムの構成例を示すブロック図である。構成は第１の実施形態と同様であるが各構成の機能が異なっている。
したがって、第３の実施形態による数値分解システムは、第１の実施形態と同様に、入力部１，初期化部４，行列Ｌ演算部５，行列Ｑ演算部６，記憶部７及び演算制御部８を有している。
【００４２】
入力部１は、分解対象のＲ行，Ｔ列の行列Ｈ及びＴ行，Ｔ列の正方行列Ｇが既知の値を、記憶部７に記憶する。すなわち、行列Ｈ及び行列Ｇ（＝ＨＨＨ）が既知であるとし、これらの行列が外部機器から入力されるとして、以下の説明を行う。また、入力部１が入力される行列Ｈ及び行列Ｇを、直接に初期下部４へ出力するようにしてもよい。
初期化部４は、行列Ｌ演算部５及び行列Ｑ演算部６にて用いる仮の行列を設定する。すなわち、初期化部４は、空行列Ｑに対して、分解対象の行列Ｈを付与して（対応する位置に要素のデータを上書きして）、行列Ｑとし、空行列Ｕに対して正方行列の上三角行列を付与して（対応する位置に要素のデータを上書きして）、行列Ｕとして初期化を行う。
【００４３】
行列Ｌ演算部５は、設定された数値ｉにより、記憶部７に記憶されている対応するｉ列目の列ベクトルＵ(1;i,i)のデータを読み出すとともに、スカラーｕｉ、ｋ＊を算出し、以下の（７）式により、新たな列ベクトルを算出して、記憶部７の読み出した位置に上書きを行い、列ベクトルのデータの変更を行う。
ここで、列ベクトルＵ(1;i,i)は、ｉ列目の列ベクトルにおける１番目の行成分からｉ番目までの行成分までの部分行列を示し、スカラーｕｉ、ｋ＊は行列Ｕのｉ行，ｋ列目の要素の複素共役を示している。ここで、Ｌ＝ＵＨであるため、行列Ｌの行ベクトルを最下部から順に最上部の行を順次計算することに相当する。
Ｕ（1:ｉ,i）：＝Ｕ（1:ｉ,i）−ｕｉ、ｋ＊・Ｕ（1:ｉ,ｋ）…（７）
【００４４】
すなわち、行列Ｌ演算部５は、行ベクトルＵ（1:ｉ,ｋ）に対して、スカラーｕｉ、ｋ＊を乗算し、乗算結果をこの行ベクトルＵ（1:ｉ,i）から減算して、この減算結果を新たな列ベクトルＵ（1:ｉ,i）として、記憶部７に対して、読み出した位置に上書きする。
このとき、行列Ｌ演算部４は、ｋをデクリメントして、上記（７）式を、Ｔからｉ＋１の範囲内、すなわちｉ＋１≦ｋ≦Ｔの間で繰り返して行う。
【００４５】
また、行列Ｌ演算部５は、以下の（８）式に示すように、最終的に得られた列ベクトルＵ（1:ｉ,i）を記憶部７から読み出し、スカラーｕｉ、ｉの平方根である（ｕｉ，ｉ）１／２により除算し、この得られた除算結果を最終的な列ベクトルＵ（1:ｉ,i）として、記憶部７に記憶する。このスカラーｕｉ、ｉは、行列Ｕのｉ行番目，ｉ列番目の要素を示している。
Ｕ（1:ｉ,i）：＝Ｕ（1:ｉ,i）／（ｕｉ，ｉ）１／２      …（８）
【００４６】
行列Ｑ演算部６は、設定された数値ｉにより、記憶部７から行列Ｑのｉ番目の列ベクトルＱ（：,ｉ）を読み出し、以下の（９）式に示すように、スカラーｕｉ、ｉにより除算し、除算結果を新たな列ベクトルＱ（：,ｉ）として、記憶部７において読み出した位置に書き込む。このスカラーｕｉ、ｉは、行列Ｕにおけるｉ行，ｉ列目の要素である。
Ｑ（：,ｉ）：＝Ｑ（：,ｉ）／ｕｉ、ｉ                …（９）
また、行列Ｑ演算部６は、記憶部７から列ベクトルＱ（：,ｊ）を読み出し、以下の（１０）式により、新たな列ベクトルＱ（：，ｊ）を算出し、記憶部７の読み出した位置に記憶する。ここで、スカラーｕｉ、ｊ＊は、行列Ｕにおけるｉ行目，ｊ列目の要素の複素共役である。
Ｑ（：,ｊ）：＝Ｑ（：,ｊ）−ｕｉ、ｊ＊・Ｑ（：,ｉ） …（１０）
【００４７】
すなわち、行列Ｑ演算部６は、列ベクトルＱ（：,ｉ）の要素に対して、スカラーｕｉ、ｊ＊を乗算し、この乗算結果を列ベクトルＱ（：,ｊ）から減算し、この減算結果を新たな列ベクトルＱ（：,ｊ）として、記憶部７の読み出した位置に書き込み、データの更新を行う。
このとき、行列Ｑ演算部６は、ｊを初期値１とし、処理を１回行う毎にインクリメントしつつ、上記（６）式を、１≦ｊ≦ｉ−１の間で繰り返して行う。
演算制御部８は、行列Ｌ演算部５及び行列Ｑ演算部６における演算処理の順序制御と、各演算部における演算処理の回数の制御、すなわち演算ループの制御とを行っている。
【００４８】
次に、図２及び図５を参照して、第３の実施形態による数値分解システムの動作を説明する。図５は、第３の実施形態の数値分解システムのアルゴリズムにおける各部の処理を示したテーブルであり、（１）〜（１３）の処理が順次行われる。ここで、入力部１，複素共役転置行列生成部２及び正方行列生成部３の動作は省略され、行列Ｈ及び正方行列Ｇが各々求められ、すでに記憶部７に記憶されているとする。
処理（１）において、初期化部４は、記憶部７から分割対象の行列Ｈを読み出し、空行列Ｑに対し、この行列Ｈの各要素を、対応する行番号及び列番号で指定される位置に書き込み、すなわち空行列Ｑに対して行列Ｈの値を付与し、空行列ＱをＲ行，Ｔ列の行列とする。
また、初期化部４は、記憶部７から行列Ｇを読み出し、この行列Ｇから上三角部分を抽出し、空行列Ｕの対応する行番号及び列番号で指定される位置に書き込み、すなわち空行列Ｕに対して行列Ｇの上三角部分の要素を付与し、行列Ｕを上三角部分が非ゼロ要素である上三角行列である行列Ｕとする。
【００４９】
次に、処理（２）において、演算制御部８は、正方行列である行列Ｕの列数及び行数の数値Ｔを抽出し、行列Ｒ演算回路５と行列Ｑ演算回路６とにおける繰り返し演算回数をＴとし、数値ｉを「Ｔ」に初期化して、処理（２）〜処理（１１）までの、行列Ｌ演算回路５と行列Ｑ演算回路６とにおける演算処理を、数値ｉがＴから１までの範囲、すなわち１≦ｉ≦Ｔの間繰り返して行う。ここで、例えば、１回の演算ループの処理が終了した後、処理（１１）にて数値ｉをデクリメント（１を減算）し、処理（２）にて数値ｉが１≦ｉ≦Ｔの範囲内であるか否か、すなわちｉが０となったか否かを検出し、範囲内であることを検出した場合、次の処理（３）へ処理を移し、一方、数値ｉが数値１を下回ったこと（範囲外であること）を検出すると、処理（２）〜処理（１１）の演算ループ（行列分割の演算ループ）を終了し、処理を処理（１２）へ進める。
また、行列Ｌ演算部５は、処理（１２）において、Ｌ＝ＵＨの演算を行い、すなわち上述した求めた上三角行列Ｕに対して複素共役転置の処理を行い、下三角行列の行列Ｌを算出して、記憶部７に記憶する。
次に、演算制御部８は、その時点で記憶部７に記憶されている行列Ｌ及び行列Ｑを、それぞれ行列Ｈを分解した上三角行列Ｌと行列Ｑとして出力する。
【００５０】
次に、処理（３）において、行列Ｒ演算部５は、演算制御部８から数値ｉを入力し、数値ｋを「１」に初期化して、処理（３）〜処理（５）までの演算ループを、数値ｋがＴからｉ＋１の範囲、すなわちｉ＋１≦ｋ≦Ｔの間繰り返して行い、演算ループ毎に（７）式により、行列Ｕの列ベクトルｕ１〜列ベクトルｕＴの各列ベクトル（部分行列）を求めるため、行列の最右部の列ベクトルから最左部の列ベクトルの順に、列ベクトルｕＴから列ベクトルｕ１に向かい、順に列ベクトルを演算する。ここで、列ベクトルｕTの全ての行成分から成る部分行列は、Ｕ（１:T,T）と同様である。
【００５１】
ここで、ｉ＋１≦ｋ≦Ｔの範囲内においてｋ＝ｉの場合が成り立たないため、ｉ＝１の際にもｋ＝１とはならず、１列目の列ベクトルｕ１は行列Ｇの１列目の行ベクトルのままとする。
そして、行列Ｌ演算部５は、数値ｋがｉ＋１≦ｋ≦Ｔの範囲内にあることを検出すると、処理（４）へ処理を進める。
【００５２】
次に、処理（４）において、行列Ｌ演算部５は、数値ｉの示す列ベクトルｕｉにおける部分行列Ｕ（１:ｉ,ｉ）を、記憶部７に記憶されている行列Ｕから読み出す。
そして、行列Ｌ演算部５は、この部分行列Ｕ（１:ｉ,ｉ）に対し、（７）式の演算を行い、記憶部７における読み出した位置に書き込み、処理を処理（５）へ進める。
次に、処理（５）において、行列Ｒ演算部５は、１回の演算ループの毎に数値ｋをデクリメントし、処理を処理（３）へ進める。
【００５３】
次に、行列Ｌ演算部５は、処理（３）にて数値ｋがｉ＋１≦ｋ≦Ｔの範囲内であるか否かを検出し、範囲内であることを検出した場合、次の処理（４）へ処理を移し、一方、数値ｋが０を下回ったこと（範囲外であること）を検出すると、処理（３）〜処理（５）の演算ループ（行列Ｕ生成の演算ループ）を終了させ、処理を処理（６）へ移す。
【００５４】
次に、処理（６）において、行列Ｒ演算部５は、この時点の数値ｉに対応した行ベクトルにおける部分行列Ｕ（１:ｉ,ｉ）を、記憶部７に記憶された行列Ｕから読み出し、（８）式の演算処理を行い、演算結果を記憶部７の読み出した位置に上書きし、データの変更を行い、処理を処理（７）へ移す。
【００５５】
次に、処理（７）において、行列Ｑ演算部６は、演算制御部８から数値ｉを入力し、記憶部７に記憶された行列Ｑから、数値ｉに対応した列ベクトルｑｉを読み出し、（９）式に示す処理を行い、すなわちスカラーｕｉ，ｉにて列ベクトルｑｉを除算し、この除算結果を記憶部７の読み出した位置に書き込み、データの変更を行い、処理を処理（８）へ進める。ここで、列ベクトルｑｉは、部分行列Ｑ（：,ｉ）に等しい。
【００５６】
次に、処理（８）において、行列Ｑ演算部６は、数値ｊを「１」に初期化して、処理を処理（８）へ進める。
以下、行列Ｑ演算部６は、処理（８）〜処理（１０）までの演算ループを、数値ｊが１≦ｊ≦ｉ−１の間繰り返して行い、演算ループ毎に（３）式により、（２）式の最右辺の列ベクトルｑＴから最左辺の列ベクトルｑ１の各列ベクトル（部分行列）を、行列の最右端の列ベクトルから最左端の列ベクトルの順に、すなわち列ベクトルｑＴから列ベクトルｑ１に向かい、順に列ベクトルを演算する。上述したように、列ベクトルｑjは、Ｑ（：,ｊ）と同様である。
【００５７】
次に、処理（９）において、行列Ｑ演算部６は、１≦ｊ≦ｉ−１の範囲にて（１０）式の処理が行われるため、ｉ＝１の場合の処理は行われず、演算ループにおいて、行列Ｑの第１列目に対して、（７）の処理のみが行われる。すなわち、１列目の列ベクトルｑ１に対して、処理（８）から処理（１０）までの処理は行われない。
そして、行列Ｑ演算部６は、数値ｊの示す列ベクトルｕｊ、すなわち部分行列Ｑ（,：ｊ）を、記憶部７に記憶されている行列Ｑから読み出す。
そして、行列Ｑ演算部６は、この部分行列Ｑ（,：ｊ）に対し、（１０）式の演算を行い、記憶部７における読み出した位置に書き込み、処理を処理（１０）へ進める。
次に、処理（１０）において、行列Ｑ演算部６は、１回の演算ループの毎に数値ｊをインクリメントし、処理を処理（８）へ進める。
【００５８】
次に、行列Ｑ演算部６は、処理（８）にて数値ｊが１≦ｊ≦ｉ−１の範囲内であるか否かを検出し、範囲内であることを検出した場合、次の処理（８）へ処理を移し、一方、数値ｊが数値ｉ−１を超えたこと（範囲外であること）を検出すると、処理（８）〜処理（１０）の演算ループ（行列Ｑの生成の演算ループ）を終了させ、処理を処理（１１）へ移す。
次に、処理（１１）において、演算制御部８は、数値ｉをデクリメント（１を減算）し、処理を処理（２）へ進める。
そして、処理（２）において、演算制御部８は、数値ｉが１≦ｉ≦Ｔの範囲内であるか否かを検出し、範囲内であることを検出した場合、次の処理（３）へ処理を移し、一方、数値ｉが１を下回った（０となった）こと（範囲外であること）を検出すると、処理（２）〜処理（１１）の演算ループ（行列分割の演算ループ）を終了し、処理を処理（１２）へ進める。
【００５９】
次に、行列Ｒ演算部５は、処理（１２）において、Ｌ＝ＵＨの演算を行い、すなわち上述した求めた上三角行列Ｕに対して複素共役転置の処理を行い、下三角行列の行列Ｌを算出して、記憶部７に記憶する。
上述した複素共役転置の処理後、演算制御部８は、記憶部７から行列Ｑ及び行列Ｌを読み出し、行列Ｈの分解結果として出力する。
【００６０】
＜第４の実施形態＞
第４の実施形態の数値分解システムは、第３の実施形態と同様の構成をしている。第４の実施形態と第３の実施形態との違いは、演算制御部８の行列Ｌ演算部５及び行列Ｑ演算部６の演算順序にある。すなわち、第３の実施形態においては、同一の演算ループ内にて、行列Ｌを生成する演算ループと行列Ｑを生成する演算ループとが実行されるアルゴリズムとなっている。
【００６１】
一方、第４の実施形態においては、演算制御部８が、行列Ｌを生成する演算ループと、行列Ｑを生成する演算ループとを、順番に、それぞれ独立に制御し、すなわち、行列Ｌの生成の演算ループが終了し、分割後の行列Ｌが求められた後、行列Ｑの生成の演算ループを開始して行列Ｑの生成を行い、行列Ｈが分解された行列Ｌ及び行列Ｑ各々の生成を別々に行うアルゴリズムとなっている。
したがって、行列Ｌ演算部５，行列Ｑ演算部６及び演算制御部８以外の他の構成要素（入力部１，初期化部４及び記憶部７）の動作は、第４の実施形態においても、第３の実施形態の構成と同様である。
【００６２】
以下、本発明の第４の実施形態において、第３の実施形態と異なる機能の構成のみの説明を行う。第４の実施形態の構成自体は、第３の実施形態と同様であるが各構成の機能が異なっている。
行列Ｌ演算部５は、設定された数値ｉにより、記憶部７に記憶されている対応するｉ列目の列ベクトルＵ（1:i,i）のデータを読み出すとともに、スカラーｕｉ、ｋ＊を算出し、以下の（７）式により、新たな列ベクトルを算出して、記憶部７の読み出した位置に上書きを行い、列ベクトルのデータの変更を行う。
ここで、列ベクトルＵ（1:i,i）は、ｉ列目の列ベクトルにおける１番目の行成分からｉ番目までの行成分までの部分行列を示し、スカラーｕｉ、ｋ＊は行列Ｕのｉ行，ｋ列目の要素の複素共役を示している。ここで、Ｌ＝ＵＨであるため、行列Ｕの行ベクトルを最下部から順に最上部の行を順次計算することに相当する。
【００６３】
すなわち、行列Ｒ演算部５は、列ベクトルＵ（1:i,i）に対して、スカラーｕｉ、ｋ＊を乗算し、乗算結果をこの列ベクトルから減算して、この減算結果を新たな列ベクトルＬＵ（1:i,i）として、記憶部７に対して、読み出した位置に上書きする。
このとき、行列Ｒ演算部４は、ｋをデクリメントして、上記（７）式を、ｋがＴからｉ＋１の範囲内、すなわちｉ＋１≦ｋ≦Ｔの間で繰り返して行う。
【００６４】
また、行列Ｌ演算部５は、上記（８）式に示すように、最終的に得られた列ベクトルＵ（1:i,i）を記憶部７から読み出し、スカラーｕｉ、ｉの平方根である（ｕｉ、ｉ）１／２により除算し、この得られた除算結果を最終的な列ベクトルＵ（1:i,i）として、記憶部７に記憶する。このスカラーｕｉ、ｉは、行列Ｌのｉ行番目，ｉ列番目の要素を示している。
【００６５】
行列Ｑ演算部６は、設定された数値ｉにより、記憶部７から行列Ｑのｉ番目の列ベクトルＱ（：,ｉ）を読み出し、上記（５）式に示すように、スカラーｌｉ，ｉにより除算し、除算結果を新たな列ベクトルＱ（：,ｉ）として、記憶部７において読み出した位置に書き込む。このスカラーｌｉ，ｉは、行列Ｌにおけるｉ行，ｉ列目の要素である。
また、行列Ｑ演算部６は、記憶部７から列ベクトルＱ（：,ｊ）を読み出し、上記（６）式により、新たな列ベクトルＱ（：，ｊ）を算出し、記憶部７の読み出した位置に記憶する。ここで、スカラーｌｉ，ｊは、行列Ｌにおけるｉ行目，ｊ列目の要素の複素共役である。
すなわち、行列Ｑ演算部６は、列ベクトルＱ（：,ｉ）の要素に対して、スカラーｌｉ，ｊを乗算し、この乗算結果を列ベクトルＱ（：,ｊ）から減算し、この減算結果を新たな列ベクトルＱ（：,ｊ）として、記憶部７の読み出した位置に書き込み、データの更新を行う。
このとき、行列Ｑ演算部６は、ｊを初期値１とし、処理を１回行う毎にインクリメントしつつ、上記（１２）式を、１≦ｊ≦ｉ−１の間で繰り返して行う。
演算制御部８は、行列Ｌ演算部５及び行列Ｑ演算部６における演算処理の順序制御と、各演算部における演算処理の回数の制御、すなわち演算ループの制御とを行っている。
【００６６】
次に、図２及び図６参照して、第４の実施形態による数値分解システムの動作を説明する。図６は、第４の実施形態の数値分解システムのアルゴリズムにおける各部の処理を示したテーブルであり、（１）〜（１４）の処理が順次行われる。ここで、入力部１，複素共役転置行列生成部２及び正方行列生成部３の動作は省略され、行列Ｈ及び正方行列Ｇが各々求められ、すでに記憶部７に記憶されているとする。
処理（１）における、初期化部４が行う処理（１）は、第３の実施形態と同様のため、説明を省略する。
【００６７】
次に、処理（２）において、演算制御部８は、正方行列である行列Ｕの列数及び行数の数値Ｔを抽出し、行列Ｌ演算回路５と行列Ｑ演算回路６とにおける繰り返し演算回数をＴとし、数値ｉを「Ｔ」に初期化して、処理（２）〜処理（７）までの、行列Ｌ演算回路５と行列Ｑ演算回路６とにおける演算処理を、数値ｉがＴから１までの範囲、すなわち１≦ｉ≦Ｔの間繰り返して行う。
ここで、例えば、１回の演算ループの処理が終了した後、処理（７）にて数値ｉをディクリメント（１を減算）し、処理（２）にて数値ｉが１≦ｉ≦Ｔの範囲内であるか否か、０となったか否かを検出し、範囲内であることを検出した場合、次の処理（３）へ処理を移し、一方、数値ｉが１を下回ったこと（範囲外であること）を検出すると、処理（２）〜処理（７）の演算ループ（行列分割の演算ループ）を終了し、処理を処理（８）へ進める。
また、行列Ｌ演算部５は、処理（８）において、Ｌ＝ＵＨの演算を行い、すなわち上述した求めた上三角行列Ｕに対して複素共役転置の処理を行い、下三角行列の行列Ｌを算出して、記憶部７に記憶する。
【００６８】
次の処理（３）〜処理（５）までは、第３の実施形態における処理（３）〜処理（５）各々と同様のため、説明を省略する。
次に、処理（７）において、演算制御部８は、数値ｉをディクリメント（１を減算）し、処理を処理（２）ヘ進める。
次に、処理（２）において、演算制御部８は、数値ｉが１≦ｉ≦Ｔの範囲内であるか否かを検出し、範囲内であることを検出した場合、次の処理（３）へ処理を移し、一方、数値ｉが０となったこと（範囲外であること）を検出すると、行列Ｕを上三角行列として記憶部７へ記憶するとともに、処理を処理（８）へ進める。
【００６９】
次に、処理（８）において、行列Ｒ演算部５は、Ｌ＝ＵＨの演算を行い、すなわち上述した求めた上三角行列Ｕに対して複素共役転置の処理を行い、下三角行列の行列Ｌを算出して、記憶部７に記憶するとともに、処理を処理（９）へ進める。
【００７０】
次に、処理（９）において、演算制御部８は、Ｒ行，Ｔ列の行列である行列Ｑの列数及の数値Ｔを抽出し、行列Ｑ演算回路６における繰り返し演算回数をＴとし、数値ｉを「Ｔ」に初期化して、処理（９）〜処理（１４）までの、行列Ｑ演算回路６における演算処理を、数値ｉがＴから１までの範囲、すなわち１≦ｉ≦Ｔの間繰り返して行う。ここで、例えば、１回の演算ループの処理が終了した後、処理（１４）にて数値ｉをデクリメント（１を減算）し、処理（９）にて数値ｉが１≦ｉ≦Ｔの範囲内であるか否か、すなわち
となったか否かを検出し、範囲内であることを検出した場合、次の処理（１０）へ処理を移し、一方、数値ｉが１を下回ったこと（範囲外であること）を検出すると、処理（９）〜処理（１４）の演算ループ（行列Ｑ生成の演算ループ）を終了し、その時点で記憶部７に記憶されている行列Ｑを、行列Ｈを分解した行列Ｑとして出力し、行列Ｈの分解処理を終了する。上記、処理（１０），（１１），（１２），（１３）各々は、それぞれ第３の実施形態における処理（７），（８），（９），（１０）と同様のため、説明を省略する。しかしながら、処理（１０）で用いる式は（５）式であり、処理（１２）で用いる式は（６）式である。
【００７１】
上述した第１から第４の実施形態によれば、以下に示す効果がある。
・本発明の各実施形態におけるアルゴリズムは、所要処理演算量が従来アルゴリズム（Classical Gram-Schmidt QR分解法，Modified Gram-Schmidt QR分解法，Householder QR分解法，Given QR分解法など）に比較して少なくなる。
・本発明の各実施形態におけるアルゴリズムは、ＱＬ分解法のための回路を小さい規模で実現できる。すなわち、回路規模は所要演算量に比例するため、従来例に比較して演算量が少なくなるため、行列のＱＬ分解の所要回路規模も従来に比較して小さくなり、従来装置に比較して小型化を実現できる。
【００７２】
・本発明の各実施形態におけるアルゴリズムは、上述したように回路規模を小さくすることが可能のため、従来に比較して消費電力を少なくすることができる。また、演算量が少なくなることにより、回路動作時間も減少させることができ、消費電力を従来に比較して減少することができ、バッテリ等で動作するＱＬ分解演算機能を有する携帯型の装置の使用時間を延ばすことができる。
・上述した各効果により、従来例に比較して、ＱＬ分解演算機能の装置への実装が簡易に行える。
・上述した各効果により、小型化、低消費電力化、低製造コスト化等が、従来例に比して向上しているため、経済的な大量生産を行うことができる。
【００７３】
次に、上述した各実施形態のアルゴリズムにおける式及び行列において用いた用語の定義を以下に示す。
行列及びスカラーは、その度毎に定義しているため省略し、以下、行列Ａ、この行列Ａの要素（スカラー）をａとして説明する。
ａｉまたはＡ（ｉ,：）…行列Ａのｉ番目の行ベクトル
ａｊまたはＡ（：,ｊ）…行列Ａのｊ番目の列ベクトル
ａｉｊ…行列Ａのｉ番目行，ｊ番目列の要素
Ａ（n：m,i：j）…行列Ａのｎ番目行〜ｍ番目行、ｉ番目列〜ｊ番目列の範囲の部分行列
ＡＨ…行列Ａの複素共役転置行列
ＡＴ…行列Ａの転置行列
‖ｂ‖…ベクトルｂの２次ノルム
ａ＊…スカラーａの複素共役
｜ａ｜…スカラーａの絶対値
ａ：＝ａ…ａの値の更新処理を示す
【００７４】
なお、図１における数値分解システムの機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより行列のＱＬ分解の処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータシステム」は、ホームページ提供環境（あるいは表示環境）を備えたＷＷＷシステムも含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【００７５】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【図面の簡単な説明】
【００７６】
【図１】本発明の第１〜第４の実施形態において用いられるＱＬ分解のアルゴリズムを説明する概念図である。
【図２】本発明の第１〜第４の実施形態による数値分解システムの構成例を示すブロック図である。
【図３】本発明の第１の実施形態におけるＱＬ分解のアルゴリズムを説明する、処理の順番を示すテーブルである。
【図４】本発明の第２の実施形態におけるＱＬ分解のアルゴリズムを説明する、処理の順番を示すテーブルである。
【図５】本発明の第３の実施形態におけるＱＬ分解のアルゴリズムを説明する、処理の順番を示すテーブルである。
【図６】本発明の第４の実施形態におけるＱＬ分解のアルゴリズムを説明する、処理の順番を示すテーブルである。
【図７】従来例において用いられるＱＬ分解のアルゴリズムを説明する概念図である。
【符号の説明】
【００７７】
１…入力部  ２…複素共役転置行列生成部  ３…正方行列生成部  ４…初期化部  ５…行列Ｌ生成部  ６…行列Ｑ生成部  ７…記憶部  ８…演算制御部
【図１】
2008129861.tif 000005
【図２】
2008129861.tif 000006
【図３】
2008129861.tif 000007
【図４】
2008129861.tif 000008
【図５】
2008129861.tif 000009
【図６】
2008129861.tif 000010
【図７】
2008129861.tif 000011