(57)【要約】【課題】平方根計算をなくし、除算を低減させることができ、この場合にも適切な解を求める。【解決手段】３行３列の行列式による３次固有値方程式を２回微分した方程式の解について、当該解の分母を構成する「３」により前記３次方程式の２次項の係数を割り算する割算器４５を有する初期値生成回路４２と、二つの初期値に基づき二分法を用いて一つの解を求める二分法回路を二回路（５０１、５０２）有し、前記初期値生成回路４２の出力、ゼロ及び前記３行３列の行列式における対角要素の最大値の和であるＭＡＸ値を前記二分法回路の入力とする第一群ブロック４３と、前記二分法回路を３回路（５０３、５０４、５０５）有する第二群ブロック４４であって、ゼロ及びＭＡＸ値と前群ブロックである第一群ブロック４３の出力を入力とするブロックとを具備する。【選択図】  図７
2008282365.tif 000002
【特許請求の範囲】
【請求項１】
Ｎ行Ｎ列の行列式によるＮ次固有値方程式を（Ｎ−１）回微分した方程式の解について、当該解の分母を構成する数により前記Ｎ次方程式の（Ｎ−１）次項の係数を割り算する割算手段及び／または前記解の分母を素因数分解して得られる２の羃乗に対応して前記係数を右シフトするシフト手段とを有する初期値生成回路と、
二つの初期値に基づき二分法を用いて一つの解を求める二分法回路を二回路有し、前記初期値生成回路の出力、ゼロ及び前記Ｎ行Ｎ列の行列式における対角要素の最大値の和であるＭＡＸ値を前記二分法回路の入力とする第一群ブロックと、
前記二分法回路を３、４、・・・、（Ｎ−１）回路有する第（Ｎ−１）群までのブロックであって、それぞれが前記ＭＡＸ値、ゼロ及び前群ブロックの出力を入力とするブロックと
を具備することを特徴とする固有値方程式の求解装置。
【請求項２】
二分法回路は、
二入力値について中間値を求める中間値算出手段と、
前記中間値を、該当次数方程式の関数における変数として関数値を求める第１の関数値算出手段と、
前記二入力値の一方の値または前回の中間値を、該当次数方程式の関数における変数として関数値を求める第２の関数値算出手段と、
これら第１、第２の関数値算出手段により求められた関数値の符号に基づき、前回の中間値演算に用いた値の一方を選択して、前記中間値算出手段により算出された中間値と共に前記中間値算出手段へ供給する数値供給制御手段と
を具備することを特徴とする請求項１に記載の固有値方程式の求解装置。
【請求項３】
Ｎ行Ｎ列の行列式によるＮ次固有値方程式のＮ個の解をそれぞれ二分法を用いて求めるＮ次用二分法手段、前記Ｎ次方程式の極小値と極大値を前記Ｎ次方程式の微分である（Ｎ−１）次方程式により求める（Ｎ−１）次用二分法手段、前記（Ｎ−１）次方程式の極小値と極大値を前記（Ｎ−１）次方程式の微分である（Ｎ−２）次方程式により求める（Ｎ−２）次用二分法手段、・・・、前記３次方程式の極小値と極大値を３次方程式の微分である２次方程式により求める２次用二分法手段と、
前記２次方程式の微分である１次方程式の解を作成し、この解とゼロ及び前記Ｎ行Ｎ列の行列式における対角要素の最大値の和であるＭＡＸ値を前記２次用二分法手段へ与える初期値付与手段とを具備し、
前記Ｎ次用二分法手段、（Ｎ−１）次用二分法手段、・・・が前段の手段による出力とゼロ及び前記Ｎ行Ｎ列の行列式における対角要素の最大値の和であるＭＡＸ値を入力として処理を実行することを特徴とする固有値方程式の求解装置。
【請求項４】
Ｎ次用二分法手段、（Ｎ−１）次用二分法手段、・・・がそれぞれ、Ｎ個、（Ｎ−１）個、・・・の二分法演算手段を備え、
各二分法演算手段が、二つの初期値に基づき二分法を用いて一つの解を求めることを特徴とする請求項３に記載の固有値方程式の求解装置。
【請求項５】
二分法演算手段は、
二入力値について中間値を求める中間値算出手段と、
前記中間値を、該当次数方程式の関数における変数として関数値を求める第１の関数値算出手段と、
前記二入力値の一方の値または前回の中間値を、該当次数方程式の関数における変数として関数値を求める第２の関数値算出手段と、
これら第１、第２の関数値算出手段により求められた関数値の符号に基づき、前回の中間値演算に用いた値の一方を選択して、前記中間値算出手段により算出された中間値と共に前記中間値算出手段へ供給する数値供給制御手段と
を具備することを特徴とする請求項４に記載の固有値方程式の求解装置。
【請求項６】
Ｎ行Ｎ列の行列式によるＮ次固有値方程式のＮ個の解をそれぞれ二分法を用いて求めるＮ次用二分法ステップ、前記Ｎ次方程式の極小値と極大値を前記Ｎ次方程式の微分である（Ｎ−１）次方程式により求める（Ｎ−１）次用二分法ステップ、前記（Ｎ−１）次方程式の極小値と極大値を前記（Ｎ−１）次方程式の微分である（Ｎ−２）次方程式により求める（Ｎ−２）次用二分法ステップ、・・・、前記３次方程式の極小値と極大値を３次方程式の微分である２次方程式により求める２次用二分法ステップとを有しており、
前記２次方程式の微分である１次方程式の解を作成し、この解とゼロ及び前記Ｎ行Ｎ列の行列式における対角要素の最大値の和であるＭＡＸ値を前記２次用二分法ステップへ与える初期値付与ステップと、
この初期値付与ステップにより与えられた値とゼロ及び前記Ｎ行Ｎ列の行列式における対角要素の最大値の和であるＭＡＸ値に基づき前記２次用二分法ステップを実行し、
この前記２次用二分法ステップにより求められた値とゼロ及び前記Ｎ行Ｎ列の行列式における対角要素の最大値の和であるＭＡＸ値を次の３次用二分法ステップの入力として、３次用二分法ステップを実行し、
以下同様に、前記Ｎ次用二分法ステップ、（Ｎ−１）次用二分法ステップ、・・・が前段のステップによる出力とゼロ及び前記Ｎ行Ｎ列の行列式における対角要素の最大値の和であるＭＡＸ値を入力として処理を実行することを特徴とする固有値方程式の求解方法。
【請求項７】
Ｎ次用二分法ステップ、（Ｎ−１）次用二分法ステップ、・・・がそれぞれ、Ｎ個、（Ｎ−１）個、・・・の二分法演算ステップを備え、
各二分法演算ステップが、二つの初期値に基づき二分法を用いて一つの解を求めることを特徴とする請求項６に記載の固有値方程式の求解方法。
【請求項８】
二分法演算ステップは、
二入力値について中間値を求める中間値算出ステップと、
前記中間値を、該当次数方程式の関数における変数として関数値を求める第１の関数値算出ステップと、
前記二入力値の一方の値または前回の中間値を、該当次数方程式の関数における変数として関数値を求める第２の関数値算出ステップと、
これら第１、第２の関数値算出ステップにより求められた関数値の符号に基づき、前回の中間値演算に用いた値の一方を選択して、前記中間値算出ステップにより算出された中間値と共に前記中間値算出ステップへ供給する数値供給制御ステップと
を具備することを特徴とする請求項７に記載の固有値方程式の求解方法。
【請求項９】
コンピュータを、
Ｎ行Ｎ列の行列式によるＮ次固有値方程式のＮ個の解をそれぞれ二分法を用いて求めるＮ次用二分法手段、前記Ｎ次方程式の極小値と極大値を前記Ｎ次方程式の微分である（Ｎ−１）次方程式により求める（Ｎ−１）次用二分法手段、前記（Ｎ−１）次方程式の極小値と極大値を前記（Ｎ−１）次方程式の微分である（Ｎ−２）次方程式により求める（Ｎ−２）次用二分法手段、・・・、前記３次方程式の極小値と極大値を３次方程式の微分である２次方程式により求める２次用二分法手段と、
前記２次方程式の微分である１次方程式の解を作成し、この解とゼロ及び前記Ｎ行Ｎ列の行列式における対角要素の最大値の和であるＭＡＸ値を前記２次用二分法手段へ与える初期値付与手段、
として機能させ、
前記Ｎ次用二分法手段、（Ｎ−１）次用二分法手段、・・・が前段の手段による出力とゼロ及び前記Ｎ行Ｎ列の行列式における対角要素の最大値の和であるＭＡＸ値を入力として処理を実行するように制御することを特徴とする固有値方程式の求解プログラム。
【請求項１０】
Ｎ次用二分法手段、（Ｎ−１）次用二分法手段、・・・がそれぞれ、Ｎ個、（Ｎ−１）個、・・・の二分法演算手段を備え、
各二分法演算手段が、二つの初期値に基づき二分法を用いて一つの解を求めることを特徴とする請求項９に記載の固有値方程式の求解プログラム。
【請求項１１】
二分法演算手段は、
二入力値について中間値を求める中間値算出手段と、
前記中間値を、該当次数方程式の関数における変数として関数値を求める第１の関数値算出手段と、
前記二入力値の一方の値または前回の中間値を、該当次数方程式の関数における変数として関数値を求める第２の関数値算出手段と、
これら第１、第２の関数値算出手段により求められた関数値の符号に基づき、前回の中間値演算に用いた値の一方を選択して、前記中間値算出手段により算出された中間値と共に前記中間値算出手段へ供給する数値供給制御手段と
を具備することを特徴とする請求項１０に記載の固有値方程式の求解プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、固有値演算を用いた処理を行う各種分野に適用可能な固有値方程式の求解装置、求解方法及び求解プログラムに関するものである。
【背景技術】
【０００２】
従来、固有値を演算する際に用いられるＮ次の固有値方程式を解く場合には、数多くの除算や平方根計算を行っており、サイクル数の増加により誤差が伝搬して精度の悪い固有値が出力される問題点があった。また、除算や平方根計算を行う素子のエリア数が多くなり、半導体設計を行う場合に開発期間が長くなるなどの問題があった。
【０００３】
繰返し演算を行うことにより非線形方程式の解析を行う装置としては、特許文献１に記載のものがあり、収束判定条件を設定して、解析の高速化を図っているものの、平方根計算をなくし、除算を低減させる観点からの発明ではない。
【特許文献１】特開２００３−１６２５１７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明は上記のような従来の固有値方程式の求解を行う装置における現状に鑑みてなされたもので、その目的は、平方根計算をなくし、除算を低減させることができ、この場合にも適切な解を求めることができ、素子数の低減と誤差伝搬の低減を図ることができ、ＬＳＩ化する場合には、開発期間の短縮化を図ることが可能な固有値方程式の求解装置、求解方法及び求解プログラムを提供することである。
【課題を解決するための手段】
【０００５】
本発明に係る固有値方程式の求解装置は、Ｎ行Ｎ列の行列式によるＮ次固有値方程式を（Ｎ−１）回微分した方程式の解について、当該解の分母を構成する数により前記Ｎ次方程式の（Ｎ−１）次項の係数を割り算する割算手段及び／または前記解の分母を素因数分解して得られる２の羃乗に対応して前記係数を右シフトするシフト手段とを有する初期値生成回路と、二つの初期値に基づき二分法を用いて一つの解を求める二分法回路を二回路有し、前記初期値生成回路の出力、ゼロ及び前記Ｎ行Ｎ列の行列式における対角要素の最大値の和であるＭＡＸ値を前記二分法回路の入力とする第一群ブロックと、前記二分法回路を３、４、・・・、（Ｎ−１）回路有する第（Ｎ−１）群までのブロックであって、それぞれが前記ＭＡＸ値、、ゼロ及び前群ブロックの出力を入力とするブロックとを具備することを特徴とする。
【０００６】
本発明に係る固有値方程式の求解装置では、二分法回路が、二入力値について中間値を求める中間値算出手段と、前記中間値を、該当次数方程式の関数における変数として関数値を求める第１の関数値算出手段と、前記二入力値の一方の値または前回の中間値を、該当次数方程式の関数における変数として関数値を求める第２の関数値算出手段と、これら第１、第２の関数値算出手段により求められた関数値の符号に基づき、前回の中間値演算に用いた値の一方を選択して、前記中間値算出手段により算出された中間値と共に前記中間値算出手段へ供給する数値供給制御手段とを具備することを特徴とする。
【０００７】
本発明に係る固有値方程式の求解装置は、Ｎ行Ｎ列の行列式によるＮ次固有値方程式のＮ個の解をそれぞれ二分法を用いて求めるＮ次用二分法手段、前記Ｎ次方程式の極小値と極大値を前記Ｎ次方程式の微分である（Ｎ−１）次方程式により求める（Ｎ−１）次用二分法手段、前記（Ｎ−１）次方程式の極小値と極大値を前記（Ｎ−１）次方程式の微分である（Ｎ−２）次方程式により求める（Ｎ−２）次用二分法手段、・・・、前記３次方程式の極小値と極大値を３次方程式の微分である２次方程式により求める２次用二分法手段と、前記２次方程式の微分である１次方程式の解を作成し、この解とゼロ及び前記Ｎ行Ｎ列の行列式における対角要素の最大値の和であるＭＡＸ値を前記２次用二分法手段へ与える初期値付与手段とを具備し、前記Ｎ次用二分法手段、（Ｎ−１）次用二分法手段、・・・が前段の手段による出力とゼロ及び前記Ｎ行Ｎ列の行列式における対角要素の最大値の和であるＭＡＸ値を入力として処理を実行することを特徴とする。
【０００８】
本発明に係る固有値方程式の求解装置は、Ｎ次用二分法手段、（Ｎ−１）次用二分法手段、・・・がそれぞれ、Ｎ個、（Ｎ−１）個、・・・の二分法演算手段を備え、各二分法演算手段が、二つの初期値に基づき二分法を用いて一つの解を求めることを特徴とする。
【０００９】
本発明に係る固有値方程式の求解装置では、二分法演算手段が、二入力値について中間値を求める中間値算出手段と、前記中間値を、該当次数方程式の関数における変数として関数値を求める第１の関数値算出手段と、前記二入力値の一方の値または前回の中間値を、該当次数方程式の関数における変数として関数値を求める第２の関数値算出手段と、これら第１、第２の関数値算出手段により求められた関数値の符号に基づき、前回の中間値演算に用いた値の一方を選択して、前記中間値算出手段により算出された中間値と共に前記中間値算出手段へ供給する数値供給制御手段とを具備することを特徴とする。
【００１０】
本発明に係る固有値方程式の求解方法は、Ｎ行Ｎ列の行列式によるＮ次固有値方程式のＮ個の解をそれぞれ二分法を用いて求めるＮ次用二分法ステップ、前記Ｎ次方程式の極小値と極大値を前記Ｎ次方程式の微分である（Ｎ−１）次方程式により求める（Ｎ−１）次用二分法ステップ、前記（Ｎ−１）次方程式の極小値と極大値を前記（Ｎ−１）次方程式の微分である（Ｎ−２）次方程式により求める（Ｎ−２）次用二分法ステップ、・・・、前記３次方程式の極小値と極大値を３次方程式の微分である２次方程式により求める２次用二分法ステップとを有しており、前記２次方程式の微分である１次方程式の解を作成し、この解とゼロ及び前記Ｎ行Ｎ列の行列式における対角要素の最大値の和であるＭＡＸ値を前記２次用二分法ステップへ与える初期値付与ステップと、この初期値付与ステップにより与えられた値とゼロ及び前記Ｎ行Ｎ列の行列式における対角要素の最大値の和であるＭＡＸ値に基づき前記２次用二分法ステップを実行し、この前記２次用二分法ステップにより求められた値とゼロ及び前記Ｎ行Ｎ列の行列式における対角要素の最大値の和であるＭＡＸ値を次の３次用二分法ステップの入力として、３次用二分法ステップを実行し、以下同様に、前記Ｎ次用二分法ステップ、（Ｎ−１）次用二分法ステップ、・・・が前段のステップによる出力とゼロ及び前記Ｎ行Ｎ列の行列式における対角要素の最大値の和であるＭＡＸ値を入力として処理を実行することを特徴とする。
【００１１】
本発明に係る固有値方程式の求解方法は、Ｎ次用二分法ステップ、（Ｎ−１）次用二分法ステップ、・・・がそれぞれ、Ｎ個、（Ｎ−１）個、・・・の二分法演算ステップを備え、各二分法演算ステップが、二つの初期値に基づき二分法を用いて一つの解を求めることを特徴とする。
【００１２】
本発明に係る固有値方程式の求解方法では、二分法演算ステップが、二入力値について中間値を求める中間値算出ステップと、前記中間値を、該当次数方程式の関数における変数として関数値を求める第１の関数値算出ステップと、前記二入力値の一方の値または前回の中間値を、該当次数方程式の関数における変数として関数値を求める第２の関数値算出ステップと、これら第１、第２の関数値算出ステップにより求められた関数値の符号に基づき、前回の中間値演算に用いた値の一方を選択して、前記中間値算出ステップにより算出された中間値と共に前記中間値算出ステップへ供給する数値供給制御ステップとを具備することを特徴とする。
【００１３】
本発明に係る固有値方程式の求解プログラムは、コンピュータを、Ｎ行Ｎ列の行列式によるＮ次固有値方程式のＮ個の解をそれぞれ二分法を用いて求めるＮ次用二分法手段、前記Ｎ次方程式の極小値と極大値を前記Ｎ次方程式の微分である（Ｎ−１）次方程式により求める（Ｎ−１）次用二分法手段、前記（Ｎ−１）次方程式の極小値と極大値を前記（Ｎ−１）次方程式の微分である（Ｎ−２）次方程式により求める（Ｎ−２）次用二分法手段、・・・、前記３次方程式の極小値と極大値を３次方程式の微分である２次方程式により求める２次用二分法手段と、前記２次方程式の微分である１次方程式の解を作成し、この解とゼロ及び前記Ｎ行Ｎ列の行列式における対角要素の最大値の和であるＭＡＸ値を前記２次用二分法手段へ与える初期値付与手段、として機能させ、前記Ｎ次用二分法手段、（Ｎ−１）次用二分法手段、・・・が前段の手段による出力とゼロ及び前記Ｎ行Ｎ列の行列式における対角要素の最大値の和であるＭＡＸ値を入力として処理を実行するように制御することを特徴とする。
【００１４】
本発明に係る固有値方程式の求解プログラムは、Ｎ次用二分法手段、（Ｎ−１）次用二分法手段、・・・がそれぞれ、Ｎ個、（Ｎ−１）個、・・・の二分法演算手段を備え、各二分法演算手段が、二つの初期値に基づき二分法を用いて一つの解を求めることを特徴とする。
【００１５】
本発明に係る固有値方程式の求解プログラムでは、二分法演算手段が、二入力値について中間値を求める中間値算出手段と、前記中間値を、該当次数方程式の関数における変数として関数値を求める第１の関数値算出手段と、前記二入力値の一方の値または前回の中間値を、該当次数方程式の関数における変数として関数値を求める第２の関数値算出手段と、これら第１、第２の関数値算出手段により求められた関数値の符号に基づき、前回の中間値演算に用いた値の一方を選択して、前記中間値算出手段により算出された中間値と共に前記中間値算出手段へ供給する数値供給制御手段とを具備することを特徴とする。
【発明の効果】
【００１６】
本発明によれば、二分法回路に初期値を与える初期値生成回路が、方程式の解の分母を構成する数により割算手段及び／またはシフト手段により構成されるので、平方根演算がなくなり、割算が低減し、素子数の低減を図ることができ、各段において前段で得られた解を用いて二分法演算を行うので、誤差の伝搬は各段で遮断されることになり、平方根演算や除算などを繰り返して誤差伝搬を遮断することのなく最終的な解を求める従来手法に比べて誤差伝搬の低減を図ることができ、ＬＳＩ化する場合には、開発期間の短縮化を図ることが可能となる。
【００１７】
また、本発明によれば、同じ構成の二分法回路を複数用いた構造であるため、回路の共通化を図り開発期間の短縮を実現できる。
【００１８】
更に、本発明では、極小値と極大値を求めて次段の二分法手段へ送る構成を採用し、この極小値と極大値に加えてゼロ及びＮ行Ｎ列の行列式における対角要素の最大値の和であるＭＡＸ値を初期値として二分法により解を求めるので、解を挟んだ二つの値に基づき二分法による処理がなされ、適切に解を求めることが可能となる。
【発明を実施するための最良の形態】
【００１９】
以下、添付図面を参照して本発明に係る固有値方程式の求解装置、求解方法及び求解プログラムの実施例を説明する。各図において、同一の構成要素には、同一の符号を付して重複する説明を省略する。図１に示すように、本実施例に係る固有値方程式の求解装置は、一般的にＮ行Ｎ列の行列式によるＮ次固有値方程式のＮ個の解をそれぞれ二分法を用いて求めるＮ次用二分法手段１０Ｎを備える。
【００２０】
また、（Ｎ−１）次用二分法手段１０（Ｎ−１）、・・・、２次用二分法手段１０２を備える。（Ｎ−１）次用二分法手段１０（Ｎ−１）は、Ｎ次方程式の極小値と極大値を上記Ｎ次方程式の微分である（Ｎ−１）次方程式により求めるものである。（Ｎ−２）次用二分法手段１０（Ｎ−２）は、上記（Ｎ−１）次方程式の極小値と極大値を上記（Ｎ−１）次方程式の微分である（Ｎ−２）次方程式により求めるものである。以下、同様の手段がＮに応じて設けられており、最前段として、２次用二分法手段１０２が設けられ、この２次用二分法手段１０２は、後段となる二分法手段における処理対象に係る３次方程式の極小値と極大値を３次方程式の微分である２次方程式により求めるものである。
【００２１】
また、求解装置には、初期値付与手段１１が備えられている。初期値付与手段１１は、与えられたＮ行Ｎ列の行列式の各要素に基づき固有方程式を生成する方程式生成手段１３からＮ次方程式の係数値などを与えられ、２次用二分法手段１０２の処理対象に係る２次方程式の微分である１次方程式の解を作成し、この解とゼロ及び上記Ｎ行Ｎ列の行列式における対角要素の最大値の和であるＭＡＸ値を上記２次用二分法手段１０２へ与えるものである。この結果、２次用二分法手段１０２に対しては、上記２次方程式の関数における極小値である方程式の解が初期値として与えられると共にゼロ及びＭＡＸ値が与えられる。また、初期値付与手段１１は、当初のＮ次方程式の係数に含まれておらず、微分の結果係数となる数値を保持し、これをＮ次用二分法手段１０Ｎ、（Ｎ−１）次用二分法手段１０（Ｎ−１）、・・・、２次用二分法手段１０２中の必要な手段へ供給する。例えば、固有方程式がＸ3＋ＢＸ2＋ＣＸ＋Ｄ＝０であるときには、３乗の項を微分することにより、「３」が係数となるので、これを例えば検出保持し、２次用二分法手段１０２へ供給する。
【００２２】
上記のＭＡＸ値は、図２に示されるように、Ｎ行Ｎ列の行列式における対角要素であるａ１１、ａ２２、ａ３３、・・・、ａＮＮの各要素について最大値の和である。各要素についての最大値は、各要素のビット数により決定され、符号なしの３ビットであれば最大値は「８」であり、符号付きの６ビットであれば最大値は「３１」である。この和がＭＡＸ値であるから、３×３の行列式で符号なしの３ビットであれば、「８＋８＋８＝２４」となり、３×３の行列式で符号付きの６ビットであれば、「３１＋３１＋３１＝９３」となる。
【００２３】
Ｎ次用二分法手段１０Ｎ、（Ｎ−１）次用二分法手段１０（Ｎ−１）、・・・は、それぞれ、Ｎ個、（Ｎ−１）個、・・・の二分法演算手段１２を備える。
【００２４】
Ｎ次用二分法手段１０Ｎ、（Ｎ−１）次用二分法手段１０（Ｎ−１）、・・・が前段の手段による出力とゼロ及び上記Ｎ行Ｎ列の行列式における対角要素の最大値の和であるＭＡＸ値を入力として与えられている。そして、Ｎ次用二分法手段１０Ｎ、（Ｎ−１）次用二分法手段１０（Ｎ−１）、・・・、２次用二分法手段１０２において、各二分法演算手段１２へ上記の初期値の中から選択された２つの初期値が与えられており、各二分法演算手段１２へ与えられる２つの初期値は、それぞれ異なる解を挟むように該当の二分法演算手段１２へ設定される。
【００２５】
二分法演算手段１２は、図３に示されるように構成されている。二分法演算手段１２は、中間値算出手段２１、第１の関数値算出手段２２、第２の関数値算出手段２３、数値供給制御手段２４を備える。中間値算出手段２１は、二入力値について中間値を求めるものである。例えば、図４に示されている関数Ｆ（Ｘ）について、Ｆ（Ｘ）＝０の方程式の解を二分法により求めると、次の通りになる。当初において、初期値Ｘ０とＸ１が与えられると、中間値として（Ｘ０＋Ｘ１）／２を求め、出力ＯＵＴとする。次に、上記出力ＯＵＴをＸ２とし、Ｆ（Ｘ２）とＦ（Ｘ０）の符号が異なるのでＸ０を用いて、（Ｘ０＋Ｘ２）／２を求め、出力ＯＵＴとする。図４の例ではないが、Ｆ（Ｘ２）とＦ（Ｘ１）の符号が異なる場合にはＸ１を用いて、（Ｘ１＋Ｘ２）／２を求める。図４において、上記で求めた（Ｘ０＋Ｘ２）／２を出力ＯＵＴとする。次に、上記出力ＯＵＴをＸ３とし、Ｆ（Ｘ３）とＦ（Ｘ２）の符号が異なるのでＸ２を用いて、（Ｘ３＋Ｘ２）／２を求め、出力ＯＵＴとする。以下同様に、このような繰返し演算を行う。このようにして、解に近づいてゆくものである。
【００２６】
第１の関数値算出手段２２は、中間値算出手段２１により得られた中間値を、該当次数方程式の関数における変数として関数値を求めるものである。第１の関数値算出手段２２は、この二分法演算手段１２がＮ次用二分法手段に用いられている場合には、当該Ｎ次関数の変数に中間値算出手段２１の出力を代入して関数値を求める。また、この二分法演算手段１２が（Ｎ−１）次用二分法手段に用いられている場合には、上記Ｎ次関数を微分して得た（Ｎ−１）次関数の変数に中間値算出手段２１の出力を代入して関数値を求める。以下同様に、この二分法演算手段１２が２次用二分法手段に用いられている場合には、上記Ｎ次関数を何度か微分して得た２次関数の変数に中間値算出手段２１の出力を代入して関数値を求める。
【００２７】
第２の関数値算出手段２３は、二入力値Ｘ０、Ｘ１の一方の値（ここでは、Ｘ０）または中間値算出手段２１から出力された前回の中間値を、該当次数方程式の関数における変数として代入し関数値を求めるものである。第２の関数値算出手段２３は、この二分法演算手段１２がＮ次用二分法手段に用いられている場合には、当該Ｎ次関数の変数に上記いずれかの値を代入して関数値を求める。また、この二分法演算手段１２が（Ｎ−１）次用二分法手段に用いられている場合には、上記Ｎ次関数を微分して得た（Ｎ−１）次関数の変数に上記いずれかの値を代入して関数値を求める。以下同様に、この二分法演算手段１２が２次用二分法手段に用いられている場合には、上記Ｎ次関数を何度か微分して得た２次関数の変数に上記いずれかの値を代入して関数値を求める。
【００２８】
数値供給制御手段２４は、第１の関数値算出手段２２と第２の関数値算出手段２３により求められた関数値の符号に基づき、前回の中間値演算に用いた値の一方を選択し、上記中間値算出手段２１により算出された中間値と共に上記中間値算出手段２１へ供給するものである。この数値供給制御手段２４は、中間値算出手段２１に供給される２入力が、解を挟んだ二つの値となること、つまり、図４に示される例えばＸ１とＸ２の位置関係になることを確保するための回路である。
【００２９】
二分法演算手段１２における繰返し演算回数は、演算回数制御手段２０が演算回数をカウントして、或いは第１の関数値算出手段２２または第２の関数値算出手段２３の出力を参照して、当該出力とゼロとの差が所定以内となったことを検出して、制御する。
【００３０】
以上の構成に係る手段は、コンピュータが図５に示されるフローチャートに対応する固有値方程式の求解プログラムを実行することにより実現される。コンピュータは、与えられたＮ行Ｎ列の行列式の各要素に基づき固有方程式を生成する（Ｓ１１）。このステップＳ１１の次に、上記において生成した固有方程式の関数を微分して１次関数とした場合の解を求める（Ｓ１２）。
【００３１】
ステップＳ１２において求めた解と、０（ゼロ）と上記Ｎ行Ｎ列の行列式における対角要素の最大値の和であるＭＡＸ値を２次用二分法手段へ与えて、解を求め（Ｓ１３）、所定演算回数に達したか（或いは第１の関数値算出手段２２または第２の関数値算出手段２３の出力を参照して、当該出力とゼロとの差が所定以内となったか）を検出する（Ｓ１４）。
【００３２】
上記のステップＳ１３においては、二分法演算手段１２として図６に示されるフローチャートに対応する処理を行っている。即ち、与えられた２入力値を用いて中間値を求め（Ｓ２１）、既に説明した通りの次数（ここでは２）の関数の変数に、上記中間値を代入して第１の関数値を求める（Ｓ２２）。また、既に説明した通りの次数（ここでは２）の関数の変数に、二入力値の一方の値または前回の中間値を代入して第２の関数値を求める（Ｓ２３）。
【００３３】
ステップＳ２３に続いて第１の関数値の符号と第２の関数値の符号に基づき、前回の中間値演算に用いた２値の一方を選択して、上記算出された中間値と共に中間値算出手段へ供給する（Ｓ２４）。これを受けて、与えられた２入力値を用いて中間値を求め（Ｓ２５）、所定演算回数の演算が行われたかを検出し（Ｓ２６）、所定演算回数の演算が行われていなければ、ステップＳ２２へ戻って処理を続け、所定演算回数の演算が行われると処理を終了する。
【００３４】
図６のフローチャートに対応する処理の終了により、図５ではステップＳ１４からステップＳ１５へ進み、ステップＳ１３において求めた解と、０（ゼロ）と上記Ｎ行Ｎ列の行列式における対角要素の最大値の和であるＭＡＸ値を３次用二分法手段へ与えて、解を求めさせ（Ｓ１５）、所定演算回数に達したか（或いは第１の関数値算出手段２２または第２の関数値算出手段２３の出力を参照して、当該出力とゼロとの差が所定以内となったか）を検出する（Ｓ１６）。上記ステップＳ１５においても上記図６のフローチャートを用いて説明した処理が行われ、所定演算回数に達した場合には、次の次数である４次用二分法手段による求解処理へ進み、以下同様に次数を上げて前段の処理により得られた解と、０（ゼロ）と上記Ｎ行Ｎ列の行列式における対角要素の最大値の和であるＭＡＸ値を入力値として処理が行われる。
【００３５】
そして、最終的にＮ次用二分法手段による求解処理へ進み、前段のステップにおいて求めた解（（Ｎ−１）次方程式の解）と、０（ゼロ）と上記Ｎ行Ｎ列の行列式における対角要素の最大値の和であるＭＡＸ値をＮ次用二分法手段へ与えて、解を求めさせ（Ｓ１７）、所定演算回数に達したか（或いは第１の関数値算出手段２２または第２の関数値算出手段２３の出力を参照して、当該出力とゼロとの差が所定以内となったか）を検出する（Ｓ１８）。上記ステップＳ１７においても上記図６のフローチャートを用いて説明した処理が行われ、所定演算回数に達した場合には、固有方程式の解が求まったことになり、求解処理を終了する。
【００３６】
次に、ハードウエアにより構成した固有値方程式の求解装置の実施例を説明する。図７には、３行３列の行列式に対応する固有値方程式の求解装置の実施例に係る構成図が示されている。この固有値方程式の求解装置は、方程式生成手段４１、初期値付与手段である初期値生成回路４２、２次用二分法手段である第一群ブロック４３、３次用二分法手段である第二群ブロック４４、制御回路４９を主な構成要素として構成されている。
【００３７】
方程式生成手段４１は、３行３列の行列式の数値を入力され、これに対応する固有値方程式を生成するもので、実際には行列計算により３次方程式の係数を求める。Ｎ次の固有値方程式では、Ｎ次の項に係る係数は１であり、ここでは３次方程式の３次の項における係数が１である。また、２次の項における係数をＢ、１次の項における係数をＣ、定数項の値をＤとすると、方程式生成手段４１は、Ｂ、Ｃ、Ｄを求めて、これらを初期値生成回路４２へ送出する。
【００３８】
初期値生成回路４２には、３を分母とするように割算を行う割算器４５、１ビット分の左シフトを行うシフタ４６、３を出力するレジスタ４７が備えられている。初期値生成回路４２は、３次方程式を２度微分した１次方程式の解を作成するもので、方程式生成手段４１から出力された２次の項における係数Ｂを割算器４５によって「３」にて除算する。割算器４５により３次方程式（Ｘ3＋ＢＸ2＋ＣＸ＋Ｄ＝０）を２度微分した１次方程式（６Ｘ＋２Ｂ＝０）の解（Ｂ／−３）を求め、第一群ブロック４３へ入力する。上記において、割算器４５は、Ｎ行Ｎ列の行列式によるＮ次固有値方程式を（Ｎ−１）回微分した方程式の解について、当該解の分母を構成する数により上記Ｎ次方程式の（Ｎ−１）次項の係数を割り算する割算手段を構成する。ここに、分母を構成する数素は、因数分解して得られる素数を例として挙げることができるが、これら素数の乗算値なども含まれる。
【００３９】
一方、シフタ４６によりＢを１ビット左シフトする。シフタ４６による１ビット左シフトは、２を掛けることを意味し、２Ｂを得ている。また、レジスタ４７により３を出力している。第一群ブロック４３、第二群ブロック４４には、同一構成の二分法演算手段を構成する二分法回路５０1〜５０5が備えられている。
【００４０】
二分法回路５０1〜５０5は、図８に示すように構成されている。二分法回路５０1〜５０5は、加算器５１と１ビット右シフトを行うシフタ５２を備え、この加算器５１とシフタ５２により二入力値について中間値を求める中間値算出手段を構成する。
【００４１】
二分法回路５０1〜５０5は、関数値演算回路５３、５４を備える。関数値演算回路５３、５４は、図９に示されるように構成されている。関数値演算回路５３、５４は、乗算器６１〜６４と、加算器６５及びセレクタ６６とを備えている。乗算器６１は入力値Ｘを２入力とし、Ｘ2を出力する。乗算器６２は入力値Ｘと乗算器６１の出力であるＸ2を入力とし、Ｘ3を出力する。乗算器６３は入力値Ｘと初期値生成回路４２から送られるＢまたはレジスタ４７の出力である３を入力とし、ＢＸ2または３Ｘ2を出力する。乗算器６４は入力値Ｘと初期値生成回路４２から送られるＣまたは２Ｂを入力とし、ＣＸまたは２ＢＸを出力する。
【００４２】
セレクタ６６は、制御回路４９から出力されるイネーブル信号ＥＮに応じて、一方から入力されている「０」または乗算器６２の出力であるＸ3を選択的に出力する。加算器６５には上記セレクタ６６の出力、乗算器６３、６４の出力、及びＣまたはＤが入力され、加算器６５からはこれらの加算値が出力される。
【００４３】
二分法回路５０1、５０2の乗算器６３にはレジスタ４７から３が入力され、二分法回路５０3、５０4、５０5の乗算器６３にはＢが入力される。二分法回路５０1、５０2の乗算器６４には２Ｂが入力され、二分法回路５０3、５０4、５０5の乗算器６４にはＣが入力される。二分法回路５０1、５０2の加算器６５にはＣが入力され、二分法回路５０3、５０4、５０5の加算器６５にはＤが入力される。
【００４４】
関数値演算回路５３の出力はセレクタ５５の制御端子に与えられ、関数値演算回路５４の出力はセレクタ５６の制御端子に与えられる。セレクタ５５からは、制御端子の信号Ｓ２が０より大きければ「１」が出力され、制御端子の信号Ｓ２が０より小さければ「０」が出力される。セレクタ５６からは、制御端子の信号Ｓ１が０より大きければ「１」が出力され、制御端子の信号Ｓ１が０より小さければ「０」が出力される。
【００４５】
セレクタ５５、５６の出力は排他的論理和回路５７へ与えられ、排他的論理和回路５７の出力はセレクタ５８、５９の制御端子に与えられる。セレクタ５８からは、制御端子の信号Ｓ３が１であればシフタ５２の出力である中間値が選択出力され、制御端子の信号Ｓ３が０であれば入力値であるＸ０が選択出力される。セレクタ５９からは、制御端子の信号Ｓ３が０であればシフタ５２の出力である中間値が選択出力され、制御端子の信号Ｓ３が１であれば入力値であるＸ１が選択出力される。このように、セレクタ５５、５６、排他的論理和回路（ＥＸ−ＮＯＲ）５７、セレクタ５８、５９は、関数値演算回路５３、５４により求められた関数値の符号に基づき、前回の中間値演算に用いた値の一方を選択して、中間値算出手段により算出された中間値と共に中間値算出手段を構成する加算器５１へ供給する数値供給制御手段を構成する。
【００４６】
図７に示されるように、信号線４８Ａを介して「０」が二分法回路５０1、５０3の入力値Ｘ０として与えられ、信号線４８を介して先に説明したＭＡＸ値が二分法回路５０2、５０5の入力値Ｘ１として与えられる。二分法回路５０1〜５０5の入力値Ｘ０、Ｘ１をまとめると次の表１に示すように、それぞれが前群ブロックの出力を入力とする。
【００４７】
【表１】
2008282365.tif 000003
【００４８】
制御回路４９は、例えば、二分法回路５０1〜５０5の固有値出力の和と行列対角要素の和の差分がゼロに近いかどうかを監視して、所定演算回数に達したかを検出し、或いは、関数値演算回路５３、５４の出力を参照してゼロとの差が所定以内となったかを検出し、繰返し演算回数を制御する。または、二分法回路５０1〜５０5内にシフト演算実行回数をカウントするカウンタを実装し、このカウンタが指定演算回数（内部で固定もしくは外部入力による可変）となったときにシフト演算の結果を出力する構成を採用することもできる。
【００４９】
次に、ハードウエアにより４行４列の行列式に対応する固有値方程式の求解装置の実施例を構成した。この装置は、図１０に示されるように、方程式生成手段７１、初期値付与手段である初期値生成回路７２、２次用二分法手段である第一群ブロック７３、３次用二分法手段である第二群ブロック７４、４次用二分法手段である第三群ブロック７５、制御回路７９を主な構成要素として構成されている。
【００５０】
方程式生成手段７１は、４行４列の行列式の数値を入力され、これに対応する固有値方程式を生成するもので、実際には行列計算により４次方程式の係数を求める。Ｎ次の固有値方程式では、Ｎ次の項に係る係数は１であり、ここでは４次方程式の４次の項における係数が１である。また、３次の項における係数をＢ、３次の項における係数をＣ、２次の項における係数をＤ、定数項の値をＥとすると、方程式生成手段７１は、Ｂ、Ｃ、Ｄ、Ｅを求めて、これらを初期値付与手段である初期値生成回路７２へ送出する。
【００５１】
初期値生成回路７２には、Ｎ次方程式を（Ｎ−１）回微分した方程式の解について、当該解の分母を素因数分解して得られる２の羃乗に対応して上記Ｎ次方程式の（Ｎ−１）次項の係数を右シフトするシフト手段である２ビット右シフトを行うシフタ７６と、３を掛ける乗算器７７と、１ビット分の左シフトを行うシフタ４６と、３を出力するレジスタ４７、２を出力するレジスタ７８が備えられている。初期値生成回路７２は、４次方程式を３度微分した１次方程式の解を作成するもので、方程式生成手段７１から出力された３次の項における係数Ｂをシフタ７６により２ビット右シフトすることにより「４」にて除算する。シフタ７６により４次方程式（Ｘ4＋ＢＸ3＋ＣＸ2＋ＤＸ＋Ｅ＝０）を３度微分した１次方程式（２４Ｘ＋６Ｂ＝０）の解（Ｂ／−４）を求め、第一群ブロック７３へ入力する。
【００５２】
３を掛ける乗算器７７によりＢに３を掛けて３Ｂを得る。１ビット分の左シフトを行うシフタ４６に上記３Ｂ、またＣを適用して左シフトにより６Ｂ、２Ｃを得る。３を出力するレジスタ４７の出力３をシフタ４６に２度通して１２を得る。２を出力するレジスタ７８の出力２をシフタ４６に通して４を得る。これらは、４次方程式（Ｘ4＋ＢＸ3＋ＣＸ2＋ＤＸ＋Ｅ＝０）を１〜３回微分したときの方程式の係数として用いられる。
【００５３】
第一群ブロック７３、第二群ブロック７４、第三群ブロック７５には、同一構成の二分法演算手段を構成する図８に示した二分法回路８０1〜８０9が備えられている。二分法回路８０1〜８０9は、図８に示すブロック構成を有するが、関数値演算回路５３、５４の構成が異なっている。
【００５４】
関数値演算回路５３、５４は、図１１に示されるように構成されている。関数値演算回路５３、５４は、乗算器９１〜９６と、加算器９９及びセレクタ９７、９８とを備えている。乗算器９１は入力値Ｘを２入力とし、Ｘ2を出力する。乗算器９２は入力値Ｘと乗算器９１の出力であるＸ2を入力とし、Ｘ3を出力する。乗算器９３は入力値Ｘと乗算器９２の出力であるＸ3を入力とし、Ｘ4を出力する。乗算器９４は乗算器９２の出力であるＸ3と初期値生成回路７２から送られるＢまたは４を入力とし、ＢＸ3または４Ｘ3を出力する。乗算器９５は乗算器９１の出力であるＸ2と初期値生成回路４２から送られるＣ、３Ｂまたは１２を入力とし、ＣＸ2、３ＢＸ2または１２Ｘ2を出力する。乗算器９６は入力値Ｘと初期値生成回路７２から送られるＤ、２Ｃまたは６Ｂを入力とし、ＤＸ、２ＣＸまたは６ＢＸを出力する。
【００５５】
セレクタ９７は、制御回路４９から出力されるイネーブル信号ＥＮ１に応じて、一方から入力されている「０」または乗算器９３の出力であるＸ4を選択的に出力する。セレクタ９８は、制御回路４９から出力されるイネーブル信号ＥＮ２に応じて、一方から入力されている「０」または乗算器９４の出力であるＢＸ3（或いは４Ｘ3）を選択的に出力する。加算器９９には上記セレクタ９７、９８の出力、乗算器９５、９６の出力、及びＥ、Ｄ、２Ｃのいずれかが入力され、加算器９９からはこれらの加算値が出力される。
【００５６】
二分法回路８０3、８０4、８０5の乗算器９４には４が入力され、二分法回路８０6〜８０9の乗算器９４にはＢが入力される。二分法回路８０1、８０2の乗算器９５には１２が入力され、二分法回路８０3、８０4、８０5の乗算器９５には３Ｂが入力され、二分法回路８０6〜８０9の乗算器９５にはＣが入力される。二分法回路８０1、８０2の乗算器９６には６Ｂが入力され、二分法回路８０3、８０4、８０5の乗算器９６には２Ｃが入力され、二分法回路８０6〜８０9の乗算器９５にはＤが入力される。二分法回路８０1、８０2の加算器９９には２Ｃが入力され、二分法回路８０3、８０4、８０5の加算器９９にはＤが入力され、二分法回路８０6〜８０9の加算器９９にはＥが入力される。
【００５７】
図１０に示されるように、信号線４８Ａを介して「０」が二分法回路８０1、８０3、８０6の入力値Ｘ０として与えられ、信号線４８を介して先に説明したＭＡＸ値が二分法回路８０2、８０5、８０9の入力値Ｘ１として与えられる。二分法回路８０1〜８０9の入力値Ｘ０、Ｘ１をまとめると次の表２に示すように、それぞれが前群ブロックの出力を入力とする。
【００５８】
【表２】
2008282365.tif 000004
【００５９】
制御回路７９は、例えば、二分法回路８０1〜８０9の固有値出力の和と行列対角要素の和の差分がゼロに近いかどうかを監視して、所定演算回数に達したかを検出し、或いは、関数値演算回路５３、５４の出力を参照して、この出力とゼロとの差が所定以内となったかを検出し、繰返し演算回数を制御する。または、二分法回路８０1〜８０9内にシフト演算実行回数をカウントするカウンタを実装し、このカウンタが指定演算回数（内部で固定もしくは外部入力による可変）となったときにシフト演算の結果を出力する構成を採用することもできる。
【００６０】
以上のハードウエア構成の装置によれば、二分法に対する初期値を自動で演算することができ、平方根演算器を除去し、除算器を削減させることができる。また、２の羃乗サイズの行列の場合に、右シフトによる回路を用いて構成することができ、除算が不要となる。同一構成の二分法回路の使いまわしが可能な構成であるため、設計期間短縮可能なであると共に、並列演算処理、演算器の共有構成を採用しているので、よりバリエーションが増すことができ、拡張性にも富むものである。また、使用用途に応じた二分法演算終了条件を容易に付加できるばかりか、前段二分法回路で出力される値は後段二分法回路に対する初期値であり、ここで誤差が生じたとしても二分法の特徴として収束先は同じであるために前段演算の誤差による影響を受けない効果を有し、割算器の分母を固定値としているため発散対策の必要性がないものである。また、二分法回路を並列動作させる構成であり超高速出力が可能となり、1つの二分法回路を共有化することによるゲート規模削減を図ることができる利点がある。
【図面の簡単な説明】
【００６１】
【図１】本発明に係る固有値方程式の求解装置の第１の実施例を示す構成図。
【図２】本発明に係る固有値方程式の求解装置の実施例において処理対象となるＮ行Ｎ列の行列式を示す図。
【図３】本発明に係る固有値方程式の求解装置の第１の実施例の要部構成を示す構成図。
【図４】二分法による求解の手順を説明するための図。
【図５】本発明に係る固有値方程式の求解装置の第１の実施例の動作を説明するためのフローチャート。
【図６】本発明に係る固有値方程式の求解装置の第１の実施例の動作を説明するためのフローチャート。
【図７】本発明に係る３次固有値方程式の求解装置をハードウエアにより構成した実施例のブロック図。
【図８】本発明に係る３次固有値方程式の求解装置をハードウエアにより構成した実施例の要部ブロック図。
【図９】図８に示した実施例の要部構成を示すブロック図。
【図１０】本発明に係る４次固有値方程式の求解装置をハードウエアにより構成した実施例のブロック図。
【図１１】本発明に係る４次固有値方程式の求解装置をハードウエアにより構成した実施例の要部ブロック図。
【符号の説明】
【００６２】
１０Ｎ、１０（Ｎ−１）、・・・１０Ｎ  Ｎ、（Ｎー１）、２次用二分法手段
１１  初期値付与手段
１２  二分法演算手段
１３  方程式生成手段
２０  演算回数制御手段
２１  中間値算出手段
２２  関数値算出手段
２３  関数値算出手段
２４  数値供給制御手段
４１  方程式生成手段
４２  初期値生成回路
４３  第一群ブロック
４４  第二群ブロック
４９  制御回路
５１  加算器
５２、７６  シフタ
５３  関数値演算回路
５４  関数値演算回路
５５、５６、５８、５９、６６  セレクタ
５７  排他的論理和回路
６５、９９  加算器
７１  方程式生成手段
７２  初期値生成回路
７３  第一群ブロック
７４  第二群ブロック
７５  第三群ブロック
７９  制御回路
９７、９８  セレクタ
８０1-８０9  二分法回路
５０1-５０5  二分法回路
６１-６４、７７、９１-９６  乗算器
８０6-８０9  二分法回路
【図１】
2008282365.tif 000005
【図２】
2008282365.tif 000006
【図３】
2008282365.tif 000007
【図４】
2008282365.tif 000008
【図５】
2008282365.tif 000009
【図６】
2008282365.tif 000010
【図７】
2008282365.tif 000011
【図８】
2008282365.tif 000012
【図９】
2008282365.tif 000013
【図１０】
2008282365.tif 000014
【図１１】
2008282365.tif 000015