(57)【特許請求の範囲】
【請求項１】
ＣＰＵとメモリとを有するコンピュータを用いて、ｍ行ｎ列の行列Ａ＝（ａｉｊ）（ｉ＝１，２，・・・，ｍ；ｊ＝１，２，・・・，ｎ）とｎ行１列の行列ｘ＝（ｘｋ）（ｋ＝１，２，・・・，ｎ）との積Ａ×ｘを自動的に計算する自動計算方法であって、前記メモリには、階層型ツリーが格納されており、
該自動計算方法は、
（ａ）ｊ＝１，２，・・・，ｎの各ｊおよびｉ＝１，２，・・・，ｍの各ｉについて、ステップ（ａ１）およびステップ（ａ２）を繰り返すステップであって、
ステップ（ａ１）は、前記ＣＰＵが、ａｉｊ≠０であるか否かを判定するステップであり、
ステップ（ａ２）は、ステップ（ａ１）においてａｉｊ≠０であると判定された場合にのみ、前記ＣＰＵが、ａｉｊに対応するレコード（ｊ，ｉ，ａｉｊ）を生成することと、前記生成されたレコード（ｊ，ｉ，ａｉｊ）に対応する少なくとも１つのノードであって、ノードＮｊの下位ノードであるノードＮｊ，ｉを含む少なくとも１つのノードを前記メモリに格納されている前記階層型ツリーに追加することと、前記メモリに格納されている前記階層型ツリーに追加されたノードＮｊ，ｉの値としてａｉｊを設定することとを実行するステップであり、前記階層型ツリーのデータ構造は、バイナリ・ツリー・インデックス・テーブルによって表され、前記バイナリ・ツリー・インデックス・テーブルのデータは、前記メモリに格納されており、前記バイナリー・ツリー・インデックス・テーブルは、各ノードに割り当てられた情報を含み、各ノードに割り当てられた情報は、当該ノードのインデックス番号と、当該ノードの名称と、当該ノードの下位ノードのうち先頭にあるノードのインデックス番号と、当該ノードと同じレベルのノードのうち当該ノードの次の位置に位置するノードのインデックス番号とを含み、ステップ（ａ２）において少なくとも１つのノードを階層型ツリーに追加することは、前記少なくとも１つのノードのそれぞれに割り当てられた情報を生成し、生成された情報を前記バイナリ・ツリー・インデックス・テーブルに追加することによって行われる、ステップと、
（ｂ）ｊ＝１，２，・・・，ｎの各ｊについて、前記ＣＰＵが、前記メモリに格納されている前記階層型ツリーのノードＮｊの値としてｘｊを設定するステップと、
（ｃ）ｊ＝１，２，・・・，ｎの各ｊおよびｉ＝１，２，・・・，ｍの各ｉについて、前記ＣＰＵが、前記メモリに格納されている前記階層型ツリーのノードＮｊの値としてステップ（ｂ）において設定されたｘｊを前記メモリに格納されている前記階層型ツリーのノードＮｊの下位ノードであるノードＮｊ，ｉの値としてステップ（ａ２）において設定されたａｉｊに乗算することにより、重みづけられた値（ｘｊ・ａｉｊ）を計算するステップと、
（ｄ）ｉ＝１，２，・・・，ｍの各ｉについて、前記ＣＰＵが、前記重み付けれた値（ｘｊ・ａｉｊ）を加算することにより、ｂｉ＝Σｊ（ｘｊ・ａｉｊ）を計算するステップと
を包含し、
ここで、ｂｉは、積Ａ×ｘに等しいｍ行１列の行列Ｂのｉ行１列の成分の値を示す、自動計算方法。
【請求項２】
行列Ａは、製品の個数と前記製品を製造するために必要な部品の個数との関係を示す、請求項１に記載の自動計算方法。
【請求項３】
行列Ａは、制御対象である系の状態遷移行列を示し、行列ｘは、前記制御対象である系の状態ベクトルを示す、請求項１に記載の自動計算方法。
【請求項４】
行列Ａは、カルマンゲインを示す、請求項１に記載の自動計算方法。
【請求項５】
行列Ａは、フィードバックゲインを示す、請求項１に記載の自動計算方法。
【請求項６】
ｍ行ｎ列の行列Ａ＝（ａｉｊ）（ｉ＝１，２，・・・，ｍ；ｊ＝１，２，・・・，ｎ）とｎ行１列の行列ｘ＝（ｘｋ）（ｋ＝１，２，・・・，ｎ）との積Ａ×ｘを自動的に計算する自動計算装置であって、前記自動計算装置は、自動計算処理を実行する制御部を含み、前記制御部は、ＣＰＵと、階層型ツリーが格納されているメモリとを含み、
前記自動計算処理は、
（ａ）ｊ＝１，２，・・・，ｎの各ｊおよびｉ＝１，２，・・・，ｍの各ｉについて、ステップ（ａ１）およびステップ（ａ２）を繰り返すステップであって、
ステップ（ａ１）は、前記ＣＰＵが、ａｉｊ≠０であるか否かを判定するステップであり、
ステップ（ａ２）は、ステップ（ａ１）においてａｉｊ≠０であると判定された場合にのみ、前記ＣＰＵが、ａｉｊに対応するレコード（ｊ，ｉ，ａｉｊ）を生成することと、前記生成されたレコード（ｊ，ｉ，ａｉｊ）に対応する少なくとも１つのノードであって、ノードＮｊの下位ノードであるノードＮｊ，ｉを含む少なくとも１つのノードを前記メモリに格納されている階層型ツリーに追加することと、前記メモリに格納されている前記階層型ツリーに追加されたノードＮｊ，ｉの値としてａｉｊを設定することとを実行するステップであり、前記階層型ツリーのデータ構造は、バイナリ・ツリー・インデックス・テーブルによって表され、前記バイナリ・ツリー・インデックス・テーブルのデータは、前記メモリに格納されており、前記バイナリー・ツリー・インデックス・テーブルは、各ノードに割り当てられた情報を含み、各ノードに割り当てられた情報は、当該ノードのインデックス番号と、当該ノードの名称と、当該ノードの下位ノードのうち先頭にあるノードのインデックス番号と、当該ノードと同じレベルのノードのうち当該ノードの次の位置に位置するノードのインデックス番号とを含み、ステップ（ａ２）において少なくとも１つのノードを階層型ツリーに追加することは、前記少なくとも１つのノードのそれぞれに割り当てられた情報を生成し、生成された情報を前記バイナリ・ツリー・インデックス・テーブルに追加することによって行われる、ステップと、
（ｂ）ｊ＝１，２，・・・，ｎの各ｊについて、前記ＣＰＵが、前記メモリに格納されている前記階層型ツリーのノードＮｊの値としてｘｊを設定するステップと、
（ｃ）ｊ＝１，２，・・・，ｎの各ｊおよびｉ＝１，２，・・・，ｍの各ｉについて、前記ＣＰＵが、前記メモリに格納されている前記階層型ツリーのノードＮｊの値としてステップ（ｂ）において設定されたｘｊを前記メモリに格納されている前記階層型ツリーのノードＮｊの下位ノードであるノードＮｊ，ｉの値としてステップ（ａ２）において設定されたａｉｊに乗算することにより、重みづけられた値（ｘｊ・ａｉｊ）を計算するステップと、
（ｄ）ｉ＝１，２，・・・，ｍの各ｉについて、前記ＣＰＵが、前記重み付けれた値（ｘｊ・ａｉｊ）を加算することにより、ｂｉ＝Σｊ（ｘｊ・ａｉｊ）を計算するステップと
を包含し、
ここで、ｂｉは、積Ａ×ｘに等しいｍ行１列の行列Ｂのｉ行１列の成分の値を示す、自動計算装置。
【請求項７】
ｍ行ｎ列の行列Ａ＝（ａｉｊ）（ｉ＝１，２，・・・，ｍ；ｊ＝１，２，・・・，ｎ）とｎ行１列の行列ｘ＝（ｘｋ）（ｋ＝１，２，・・・，ｎ）との積Ａ×ｘを自動的に計算する自動計算処理をコンピュータに実行させるプログラムを記録した記録媒体であって、前記コンピュータは、ＣＰＵと、階層型ツリーが格納されているメモリとを含み、
前記自動計算処理は、
（ａ）ｊ＝１，２，・・・，ｎの各ｊおよびｉ＝１，２，・・・，ｍの各ｉについて、ステップ（ａ１）およびステップ（ａ２）を繰り返すステップであって、
ステップ（ａ１）は、前記ＣＰＵが、ａｉｊ≠０であるか否かを判定するステップであり、
ステップ（ａ２）は、ステップ（ａ１）においてａｉｊ≠０であると判定された場合にのみ、前記ＣＰＵが、ａｉｊに対応するレコード（ｊ，ｉ，ａｉｊ）を生成することと、前記生成されたレコード（ｊ，ｉ，ａｉｊ）に対応する少なくとも１つのノードであって、ノードＮｊの下位ノードであるノードＮｊ，ｉを含む少なくとも１つのノードを前記メモリに格納されている階層型ツリーに追加することと、前記メモリに格納されている前記階層型ツリーに追加されたノードＮｊ，ｉの値としてａｉｊを設定することとを実行するステップであり、前記階層型ツリーのデータ構造は、バイナリ・ツリー・インデックス・テーブルによって表され、前記バイナリ・ツリー・インデックス・テーブルのデータは、前記メモリに格納されており、前記バイナリー・ツリー・インデックス・テーブルは、各ノードに割り当てられた情報を含み、各ノードに割り当てられた情報は、当該ノードのインデックス番号と、当該ノードの名称と、当該ノードの下位ノードのうち先頭にあるノードのインデックス番号と、当該ノードと同じレベルのノードのうち当該ノードの次の位置に位置するノードのインデックス番号とを含み、ステップ（ａ２）において少なくとも１つのノードを階層型ツリーに追加することは、前記少なくとも１つのノードのそれぞれに割り当てられた情報を生成し、生成された情報を前記バイナリ・ツリー・インデックス・テーブルに追加することによって行われる、ステップと、
（ｂ）ｊ＝１，２，・・・，ｎの各ｊについて、前記ＣＰＵが、前記メモリに格納されている前記階層型ツリーのノードＮｊの値としてｘｊを設定するステップと、
（ｃ）ｊ＝１，２，・・・，ｎの各ｊおよびｉ＝１，２，・・・，ｍの各ｉについて、前記ＣＰＵが、前記メモリに格納されている前記階層型ツリーのノードＮｊの値としてステップ（ｂ）において設定されたｘｊを前記メモリに格納されている前記階層型ツリーのノードＮｊの下位ノードであるノードＮｊ，ｉの値としてステップ（ａ２）において設定されたａｉｊに乗算することにより、重みづけられた値（ｘｊ・ａｉｊ）を計算するステップと、
（ｄ）ｉ＝１，２，・・・，ｍの各ｉについて、前記ＣＰＵが、前記重み付けれた値（ｘｊ・ａｉｊ）を加算することにより、ｂｉ＝Σｊ（ｘｊ・ａｉｊ）を計算するステップと
を包含し、
ここで、ｂｉは、積Ａ×ｘに等しいｍ行１列の行列Ｂのｉ行１列の成分の値を示す、記録媒体。
【請求項８】
ｍ行ｎ列の行列Ａ＝（ａｉｊ）（ｉ＝１，２，・・・，ｍ；ｊ＝１，２，・・・，ｎ）とｎ行１列の行列ｘ＝（ｘｋ）（ｋ＝１，２，・・・，ｎ）との積Ａ×ｘを自動的に計算する自動計算処理をコンピュータに実行させるプログラムであって、前記コンピュータは、ＣＰＵと、階層型ツリーが格納されているメモリとを含み、
前記自動計算処理は、
（ａ）ｊ＝１，２，・・・，ｎの各ｊおよびｉ＝１，２，・・・，ｍの各ｉについて、ステップ（ａ１）およびステップ（ａ２）を繰り返すステップであって、
ステップ（ａ１）は、前記ＣＰＵが、ａｉｊ≠０であるか否かを判定するステップであり、
ステップ（ａ２）は、ステップ（ａ１）においてａｉｊ≠０であると判定された場合にのみ、前記ＣＰＵが、ａｉｊに対応するレコード（ｊ，ｉ，ａｉｊ）を生成することと、前記生成されたレコード（ｊ，ｉ，ａｉｊ）に対応する少なくとも１つのノードであって、ノードＮｊの下位ノードであるノードＮｊ，ｉを含む少なくとも１つのノードを前記メモリに格納されている階層型ツリーに追加することと、前記メモリに格納されている前記階層型ツリーに追加されたノードＮｊ，ｉの値としてａｉｊを設定することとを実行するステップであり、前記階層型ツリーのデータ構造は、バイナリ・ツリー・インデックス・テーブルによって表され、前記バイナリ・ツリー・インデックス・テーブルのデータは、前記メモリに格納されており、前記バイナリー・ツリー・インデックス・テーブルは、各ノードに割り当てられた情報を含み、各ノードに割り当てられた情報は、当該ノードのインデックス番号と、当該ノードの名称と、当該ノードの下位ノードのうち先頭にあるノードのインデックス番号と、当該ノードと同じレベルのノードのうち当該ノードの次の位置に位置するノードのインデックス番号とを含み、ステップ（ａ２）において少なくとも１つのノードを階層型ツリーに追加することは、前記少なくとも１つのノードのそれぞれに割り当てられた情報を生成し、生成された情報を前記バイナリ・ツリー・インデックス・テーブルに追加することによって行われる、ステップと、
（ｂ）ｊ＝１，２，・・・，ｎの各ｊについて、前記ＣＰＵが、前記メモリに格納されている前記階層型ツリーのノードＮｊの値としてｘｊを設定するステップと、
（ｃ）ｊ＝１，２，・・・，ｎの各ｊおよびｉ＝１，２，・・・，ｍの各ｉについて、前記ＣＰＵが、前記メモリに格納されている前記階層型ツリーのノードＮｊの値としてステップ（ｂ）において設定されたｘｊを前記メモリに格納されている前記階層型ツリーのノードＮｊの下位ノードであるノードＮｊ，ｉの値としてステップ（ａ２）において設定されたａｉｊに乗算することにより、重みづけられた値（ｘｊ・ａｉｊ）を計算するステップと、
（ｄ）ｉ＝１，２，・・・，ｍの各ｉについて、前記ＣＰＵが、前記重み付けれた値（ｘｊ・ａｉｊ）を加算することにより、ｂｉ＝Σｊ（ｘｊ・ａｉｊ）を計算するステップと
を包含し、
ここで、ｂｉは、積Ａ×ｘに等しいｍ行１列の行列Ｂのｉ行１列の成分の値を示す、プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ｍ行ｎ列の行列Ａとｎ行１列の行列ｘとの積Ａ×ｘを自動的に計算する自動計算方法、自動計算装置、記録媒体およびプログラムに関する。
【０００２】
【従来の技術】
２つの行列の乗算には、積和演算が必要である。例えば、行列Ａと行列Ｂとを
【０００３】
【数１】
0004243440.tif 000002
と定義すると、行列Ｃ＝Ａ×Ｂは、（数２）で表される。
【０００４】
【数２】
0004243440.tif 000003
従来、行列の成分ａij（ｉ，ｊは１または２）またはｂk（ｋは１または２）のいずれかが「０」に等しい場合であっても、（数２）に示されるようにして、行列Ｃの各成分が計算されていた。例えば、ａ11とａ22がともに０である場合、積和演算０・ｂ1＋ａ12・ｂ2と、積和演算ａ21・ｂ1＋０・ｂ2とを実行することによって、行列Ｃの各成分が計算されていた。
【０００５】
【発明が解決しようとする課題】
０・ｂ1の計算結果は０であるので、積和演算０・ｂ1＋ａ12・ｂ2の計算結果はａ12・ｂ2に等しい。しかし、コンピュータによって、積和演算０・ｂ1＋ａ12・ｂ2を実行するには、０・ｂ1とａ12・ｂ2との２回の乗算を行い、一方は０である２つの積を加算する必要がある。このように、コンピュータによってこのような０を含む積和演算を行う場合には、その結果が自明であるにもかかわらず、０を含む乗算と０を含む加算とを行う必要がある。０を含む乗算や０を含む加算を実行するためにある程度の時間が必要であるために、従来技術によれば行列の乗算を効率的に行うことができなかった。
【０００６】
上述した例では、行列Ａは２行２列、行列Ｂは２行１列の大きさであったが、行列Ａおよび行列Ｂの大きさが大きくなるに従い、行列の乗算が効率的ではなくなる。
【０００７】
本発明は、上記課題に鑑みてなされたものであって、行列の乗算を効率的に行うことが可能な自動計算方法、自動計算装置、記録媒体およびプログラムを提供することを目的とする。
【０００８】
【課題を解決するための手段】
本発明の自動計算方法は、コンピュータを用いて、ｍ行ｎ列の行列Ａ＝（ａij）（ｉ＝１，２，・・・，ｍ；ｊ＝１，２，・・・，ｎ）とｎ行１列の行列ｘ＝（ｘk）（ｋ＝１，２，・・・，ｎ）との積Ａ×ｘを自動的に計算する自動計算方法であって、（ａ）ａij≠０という条件を満たす行列Ａの各成分について、列番号ｊに対応するノードＮjとノードＮjの下位ノードとして行番号ｉに対応するノードＮj,iとを生成し、列番号ｊをキー項目としてノードＮjとノードＮj,iとを階層型ツリーに追加するステップと、（ｂ）行列Ａの成分の値ａijをノードＮj,iの値に設定するステップと、（ｃ）行列ｘの成分の値ｘjをノードＮjの値に設定するステップと、（ｄ）ノードＮjの下位ノードである各ノードＮj,iについて、ノードＮjの値によって重みづけられた値（ｘj・ａij）を求めるステップと、（ｅ）ｂi＝Σj（ｘj・ａij）を計算するステップとを包含し、ここで、ｂiは、積Ａ×ｘに等しいｍ行１列の行列Ｂのｉ行１列の成分の値を示し、これにより、上記目的が達成される。
【０００９】
前記ステップ（ａ）は、（ａ−１）ａij≠０という条件を満たす行列Ａの各成分について、列番号ｊと行番号ｉと行列Ａの成分の値ａijとを含むレコード（ｊ，ｉ，ａij）を生成するステップと、（ａ−２）前記レコードに含まれる列番号ｊをキー項目として、前記キー項目に対応する位置において、列番号ｊに対応するノードＮjとノードＮjの下位ノードとして行番号ｉに対応するノードＮj,iとを階層型ツリーに追加するステップとを包含してもよい。
【００１０】
行列Ａは、製品の個数と前記製品を製造するために必要な部品の個数との関係を示してもよい。
【００１１】
行列Ａは、制御対象である系の状態遷移行列を示し、行列ｘは、前記制御対象である系の状態ベクトルを示してもよい。
【００１２】
行列Ａは、カルマンゲインを示してもよい。
【００１３】
行列Ａは、フィードバックゲインを示してもよい。
【００１４】
本発明の自動計算装置は、ｍ行ｎ列の行列Ａ＝（ａij）（ｉ＝１，２，・・・，ｍ；ｊ＝１，２，・・・，ｎ）とｎ行１列の行列ｘ＝（ｘk）（ｋ＝１，２，・・・，ｎ）との積Ａ×ｘを自動的に計算する自動計算装置であって、前記自動計算装置は、自動計算処理を実行する制御部を含み、前記自動計算処理は、（ａ）ａij≠０という条件を満たす行列Ａの各成分について、列番号ｊに対応するノードＮjとノードＮjの下位ノードとして行番号ｉに対応するノードＮj,iとを生成し、列番号ｊをキー項目としてノードＮjとノードＮj,iとを階層型ツリーに追加するステップと、（ｂ）行列Ａの成分の値ａijをノードＮj,iの値に設定するステップと、（ｃ）行列ｘの成分の値ｘjをノードＮjの値に設定するステップと、（ｄ）ノードＮjの下位ノードである各ノードＮj,iについて、ノードＮjの値によって重みづけられた値（ｘj・ａij）を求めるステップと、（ｅ）ｂi＝Σj（ｘj・ａij）を計算するステップとを包含し、ここで、ｂiは、積Ａ×ｘに等しいｍ行１列の行列Ｂのｉ行１列の成分の値を示し、これにより、上記目的が達成される。
【００１５】
本発明の記録媒体は、ｍ行ｎ列の行列Ａ＝（ａij）（ｉ＝１，２，・・・，ｍ；ｊ＝１，２，・・・，ｎ）とｎ行１列の行列ｘ＝（ｘk）（ｋ＝１，２，・・・，ｎ）との積Ａ×ｘを自動的に計算する自動計算処理をコンピュータに実行させるプログラムを記録した記録媒体であって、前記自動計算処理は、（ａ）ａij≠０という条件を満たす行列Ａの各成分について、列番号ｊに対応するノードＮjとノードＮjの下位ノードとして行番号ｉに対応するノードＮj,iとを生成し、列番号ｊをキー項目としてノードＮjとノードＮj,iとを階層型ツリーに追加するステップと、（ｂ）行列Ａの成分の値ａijをノードＮj,iの値に設定するステップと、（ｃ）行列ｘの成分の値ｘjをノードＮjの値に設定するステップと、（ｄ）ノードＮjの下位ノードである各ノードＮj,iについて、ノードＮjの値によって重みづけられた値（ｘj・ａij）を求めるステップと、（ｅ）ｂi＝Σj（ｘj・ａij）を計算するステップとを包含し、ここで、ｂiは、積Ａ×ｘに等しいｍ行１列の行列Ｂのｉ行１列の成分の値を示し、これにより、上記目的が達成される。
【００１６】
本発明のプログラムは、ｍ行ｎ列の行列Ａ＝（ａij）（ｉ＝１，２，・・・，ｍ；ｊ＝１，２，・・・，ｎ）とｎ行１列の行列ｘ＝（ｘk）（ｋ＝１，２，・・・，ｎ）との積Ａ×ｘを自動的に計算する自動計算処理をコンピュータに実行させるプログラムであって、前記自動計算処理は、（ａ）ａij≠０という条件を満たす行列Ａの各成分について、列番号ｊに対応するノードＮjとノードＮjの下位ノードとして行番号ｉに対応するノードＮj,iとを生成し、列番号ｊをキー項目としてノードＮjとノードＮj,iとを階層型ツリーに追加するステップと、（ｂ）行列Ａの成分の値ａijをノードＮj,iの値に設定するステップと、（ｃ）行列ｘの成分の値ｘjをノードＮjの値に設定するステップと、（ｄ）ノードＮjの下位ノードである各ノードＮj,iについて、ノードＮjの値によって重みづけられた値（ｘj・ａij）を求めるステップと、（ｅ）ｂi＝Σj（ｘj・ａij）を計算するステップとを包含し、ここで、ｂiは、積Ａ×ｘに等しいｍ行１列の行列Ｂのｉ行１列の成分の値を示し、これにより、上記目的が達成される。
【００１７】
【発明の実施の形態】
行列演算が必要な問題の例として、部品展開問題を説明する。部品展開問題は、ある製品１つを製造するために必要な部品の個数が予め定義されている場合に、製品の個数から、その製品を製造するために必要な部品の個数を求める問題である。
【００１８】
図１は、製品Ａ１および製品Ａ２を製造するために必要な部品の種類とその個数を定義する構成品テーブル１００の一例を示す。行１０１および行１０２は、製品Ａ１を製造するのに部品Ｂ１が３個と部品Ｂ２が４個必要であることを示している。行１０３および行１０４は、製品Ａ２を製造するために部品Ｂ１が３個と部品Ｂ３が６個必要であることを示している。
【００１９】
図２は、部品展開問題を取り扱う本発明のコンピュータ３の構成の一例を示す。コンピュータ３は、ＣＰＵ３１と、主記憶３２と、ハードディスク装置（ＨＤＤ）３３と、入力デバイス３４とを含む。これらの構成要素３１〜３４は、例えば、バス３５を介して互いに接続されている。ＨＤＤ３３として、任意のタイプのメモリを使用してもよい。
【００２０】
ＨＤＤ３３には、自動計算処理を表現するプログラム（以下、自動計算プログラムという）が予め格納されている。あるいは、自動計算処理プログラムは、フレキシブルディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭなどの任意のタイプのコンピュータ読み取り可能な記録媒体に記録され得る。そのような記録媒体に記録された自動計算処理プログラムは、入力装置（例えば、ディスクドライブ）を介してＨＤＤ３３にロードされ得る。
【００２１】
ＣＰＵ３１は、ＨＤＤ３３に格納されている自動計算処理プログラムを実行する。ＣＰＵ３１が自動計算処理プログラムを実行することによって、コンピュータ３は、行列の乗算を行う自動計算装置として機能する。
【００２２】
入力デバイス３４は、例えば、キーボードである。入力デバイス３４は、コンピュータ３に必要なデータを入力するために用いられ得る。
【００２３】
自動計算処理プログラムの一部またはデータの一部は、必要に応じて主記憶３２に移される。ＣＰＵ３１は、主記憶３２に高速にアクセスすることが可能である。
【００２４】
図１に示される構成品テーブル１００は、例えば、入力デバイス３４を用いてコンピュータ３に入力され、マスターファイルとしてＨＤＤ３３に格納される。
【００２５】
図１に示される例において、製品Ａ１の製造個数をａ1とし、製品Ａ２の製造個数をａ2とする。また、部品Ｂ１の必要個数をｂ1とし、部品Ｂ２の必要個数をｂ2とし、部品Ｂ３の必要個数をｂ3とする。この場合、部品展開問題は、ａ1とａ2とが指定された場合に、ｂ1とｂ2とｂ3とを計算するという問題である。
【００２６】
構成品テーブル１００より、（数３）が成立する。
【００２７】
【数３】
0004243440.tif 000004
コンピュータ３は、後述する自動計算処理を実行することにより、部品展開問題を解く。自動計算処理においては、階層型ツリーが生成され、この階層型ツリーを用いて、行列の乗算が実行される。
【００２８】
自動計算処理では、構成品テーブル１００の各行から、レコードが生成される。例えば、行１０１〜１０４から、以下のレコード＃１〜＃４が生成される。
【００２９】
レコード＃１：（Ａ１，Ｂ１，３）
レコード＃２：（Ａ１，Ｂ２，４）
レコード＃３：（Ａ２，Ｂ１，３）
レコード＃４：（Ａ２，Ｂ３，６）
レコード＃１〜レコード＃４は、階層型ツリーを生成するために用いられる。
【００３０】
図３は、各レコードに対応するノードが階層型ツリーに追加されていく様子を示す。このように、各レコードに対応するノードを階層型ツリーに追加する処理は、ＣＰＵ３１（図２）が自動計算処理プログラムを実行することによって達成される。階層型ツリーとしては、複数の階層を有する任意のタイプのツリーを使用することができる。階層型ツリーは、例えば、バイナリ―・サーチ・ツリーであり得る。なお、階層型ツリーは、ＨＤＤ３３（図２）に格納されている。
【００３１】
図３（ａ）は、階層型ツリーの初期状態（ＲＯＯＴノードのみ）を示す。
【００３２】
図３（ｂ）は、レコード＃１の内容を示すノードＡ１と、ノードＡ１の下位ノードとしてノードＢ１とが階層型ツリーに追加された状態を示す。下位ノードであるノードＢ１の値が、レコード＃１における値「３」に設定される。
【００３３】
なお、図３において、ノードに付随するカッコ内の数字は、そのノードの値を示す。また、ノードに付随する数字なしのカッコは、そのノードの値が未設定であることを示す。
【００３４】
図３（ｃ）は、レコード＃２の内容を示すノードＡ１とノードＢ２とが階層型ツリーに追加された状態を示す。但し、ノードＡ１は、既に階層型ツリーに存在する（図３（ｂ））ので、ノードＡ１を新たに生成することはない。下位ノードであるノードＢ２の値が、レコード＃２における値「４」に設定される。
【００３５】
図３（ｄ）は、レコード＃３の内容を示すノードＡ２とノードＢ１とが階層型ツリーに追加された状態を示す。下位ノードであるノードＢ１の値が、レコード＃１における値「３」に設定される。
【００３６】
図３（ｅ）は、レコード＃４の内容を示すノードＡ２とノードＢ３とが階層型ツリーに追加された状態を示す。但し、ノードＡ２は、既に階層型ツリー（図３（ｄ））に存在するので、ノードＡ２を新たに生成することはない。下位ノードであるノードＢ３の値が、レコード＃４における値「６」に設定される。
【００３７】
図４は、図３（ｅ）に示される階層型ツリーのデータ構造を表すバイナリ・ツリー・インデックス・テーブル１４０の一例を示す。
【００３８】
図４において、欄１４１は、図３（ｅ）に示される階層型ツリーの各ノードに割り当てられたインデックス番号を示す。欄１４２は、階層型ツリーの各ノードの名称を示す。欄１４３は、そのノードの下位ノードのうち、先頭にあるノードのインデックス番号を示す。そのノードに下位ノードがない場合、欄１４３は、値「−１」に設定される。欄１４４は、そのノードと同じレベルのノードのうち、そのノードの次の位置に位置するノードのインデックス番号を示す。そのようなノードがない場合には、欄１４４は、値「−１」に設定される。欄１４５は、そのノードの値を示す。
【００３９】
図５は、図３（ｅ）に示される階層型ツリーを用いて、部品Ｂ１〜Ｂ３の必要個数が求められる様子を示す。
【００４０】
製品Ａ１の製造個数ａ1を５０個とし、製品Ａ２の製造個数ａ2を３０個とする。以下、階層型ツリーを用いて、部品Ｂ１〜Ｂ３の必要個数を求める手順を説明する。
【００４１】
まず、ａ1（＝５０）が、ノードＡ１の値に設定され、ａ2（＝３０）が、ノードＡ２の値に設定される。
【００４２】
次に、ノードＡ１の下位ノードである各ノードＢ１、Ｂ２について、各ノードの値がノードＡ１の値（＝５０）で乗算される。その積が、各ノードの値として新たに設定される。すなわち、ノードＢ１、Ｂ２の値は、それぞれ、３・５０（＝１５０）および４・５０（＝２００）となる。このような処理は、テーブル１４０を参照して行われる。
【００４３】
同様に、ノードＡ２の下位ノードである各ノードＢ１、Ｂ３について、各ノードの値がノードＡ２の値（＝３０）で乗算される。その積が、各ノードの値として新たに設定される。すなわち、ノードＢ１、Ｂ３の値は、それぞれ、３・３０（＝９０）および６・３０（＝１８０）となる。
【００４４】
部品Ｂ１の必要個数は、２つのノードＢ１（参照番号１３１および１３３）の値の和として求められる。部品Ｂ２の必要個数は、ノードＢ２（参照番号１３２）の値として求められる。部品Ｂ３の必要個数は、ノードＢ３（参照番号１３４）の値として求められる。すなわち、部品Ｂ１の必要個数は、３・５０＋３・３０＝２４０個であり、部品Ｂ２の必要個数は、４・５０＝２００個であり、部品Ｂ３の必要個数は、６・３０＝１８０個である。
【００４５】
このようにして、コンピュータ３は、階層型ツリーを用いた自動計算処理を実行することにより、部品展開問題を解く。部品展開問題を解くことは、（数３）に示される行列演算を行うことと等価である。従って、コンピュータ３は、階層型ツリーを用いた自動計算処理を実行することにより、（数３）に示される行列演算を行う。
【００４６】
上述した自動計算処理では、図１に示される構成品テーブル１００からレコード＃１〜＃４が生成された。しかし、（数３）に示される式からレコードを生成してもよい。その手順を以下に説明する。
【００４７】
ここで、
【００４８】
【数４】
0004243440.tif 000005
とおく。行列Ａは、製品の個数とその製品を製造するために必要な部品の個数との関係を示す。
【００４９】
レコードは、ａij≠０という条件を満たす行列Ａの各成分について、列番号ｊと行番号ｉと行列Ａの成分の値ａijとを含むように生成される。そのレコードは、例えば、（ｊ，ｉ，ａij）と略記される。例えば、（数４）に示される行列Ａから、以下のレコード＃１’〜＃４’が生成される。
【００５０】
レコード＃１’：（１，１，３）
レコード＃２’：（１，２，４）
レコード＃３’：（２，１，３）
レコード＃４’：（２，３，６）
レコード＃１’〜＃４’は、上述したレコード＃１〜＃４と等価である。
【００５１】
上述した例では、２行２列の行列と２行１列の行列との乗算を例にとって自動計算処理を説明した。しかし、自動計算処理の適用はこれに限定されない。自動計算処理によって、ｍ行ｎ列の行列Ａ＝（ａij）（ｉ＝１，２，・・・，ｍ；ｊ＝１，２，・・・，ｎ）とｎ行１列の行列ｘ＝（ｘk）（ｋ＝１，２，・・・，ｎ）との積Ａ×ｘを自動的に計算することが可能である。
【００５２】
図６は、階層型ツリーを用いて、ｍ行ｎ列の行列Ａ＝（ａij）とｎ行１列の行列ｘ＝（ｘk）との積Ａ×ｘを自動的に計算する自動計算処理の手順を示す。以下、自動計算処理の手順を各ステップごとに詳細に説明する。
【００５３】
ステップＳ６０１：変数ｊが１に初期化される。
【００５４】
ステップＳ６０２：変数ｉが１に初期化される。
【００５５】
ステップＳ６０３：ａij≠０という条件が満たされるか否かが判定される。ステップＳ６０３における判定が「Ｙｅｓ」である場合、処理はステップＳ６０４に進む。ステップＳ６０３における判定が「Ｎｏ」である場合、処理はステップＳ６０７に進む。
【００５６】
ステップＳ６０４：レコード（ｊ，ｉ，ａij）が生成される。
【００５７】
ステップＳ６０５：ステップＳ６０４で生成されたレコードに含まれる列番号ｊをキー項目として、そのキー項目に対応する位置において、列番号ｊに対応するノードＮjとノードＮjの下位ノードとして行番号ｉに対応するノードＮj,iとが階層型ツリーに追加される。この処理は、図３（ａ）〜（ｅ）を参照して上述したノードの追加処理と同様に行なわれる。図３（ａ）〜（ｅ）におけるノードＡ１またはＡ２がノードＮjに対応し、ノードＡ１の下位ノードであるノードＢ１またはＢ２、ノードＡ２の下位ノードであるノードＢ１またはＢ３がノードＮj,iに対応する。
【００５８】
ステップＳ６０６：レコードに含まれる行列Ａの成分の値ａijがノードＮj,iの値に設定される。
【００５９】
ステップＳ６０７：変数ｉの値が１増加される。
【００６０】
ステップＳ６０８：条件ｉ＞ｍが満たされるか否かが判定される。ステップＳ６０８における判定が「Ｙｅｓ」である場合、処理はステップＳ６０９に進む。ステップＳ６０８における判定が「Ｎｏ」である場合、処理はステップＳ６０３に戻る。
【００６１】
ステップＳ６０９：変数ｊの値が１増加される。
【００６２】
ステップＳ６１０：条件ｊ＞ｎが満たされるか否かが判定される。ステップＳ６１０における判定が「Ｙｅｓ」である場合、処理はステップＳ６１１に進む。ステップＳ６１０における判定が「Ｎｏ」である場合、処理はステップＳ６０２に戻る。
【００６３】
ステップＳ６１１：行列ｘの成分の値ｘjがノードＮjの値に設定される。この処理は、ｊ＝１，２，・・・，ｎの各ｊについて行なわれる。
【００６４】
ステップＳ６１２：ノードＮjの下位ノードである各ノードＮj,iについて、ノードＮjの値によって重みづけられた値（ｘj・ａij）が求められる。この処理は、ｉ＝１，２，・・・，ｍの各ｉおよびｊ＝１，２，・・・，ｎの各ｊについて行なわれる。
【００６５】
なお、重みづけられた値（ｘj・ａij）をノードＮj,iの値に新たに設定してもよいし、ノードＮj,iの値とは別の格納位置に格納してもよい。行列Ａは固定のまま、行列ｘを変化させて積Ａ×ｘを求める場合、ノードＮj,iの値とは別の格納位置に重みづけられた値（ｘj・ａij）を格納することが好ましい。ノードＮj,iの値が更新されないので、行列Ａが固定である限りステップＳ６０１〜Ｓ６１０を繰り返して行う必要がないからである。
【００６６】
ステップＳ６１３：ｉ＝１，２，・・・，ｍの各ｉについて、ｂi＝Σj（ｘj・ａij）が計算される。ここで、Σjは、ｊ＝１，２，・・・，ｎのすべてのｊについての和を意味する。
【００６７】
図６に示される各ステップにおいて、コンピュータ３のＣＰＵ３１（図２）は、各ステップにおける処理を実行するための手段として機能する。
【００６８】
図７は、図１を参照して説明した部品展開問題において、部品Ｂ１〜Ｂ３を製造するために必要な部品の種類とその個数を定義する構成品テーブル７００の一例を示す。
【００６９】
行７０１および行７０２は、部品Ｂ１を製造するために部品Ｃ１が２個と部品Ｃ２が４個必要であることを示している。行７０３および行７０４は、部品Ｂ２を製造するために部品Ｃ３が２個と部品Ｃ４が１個必要であることを示している。行７０５〜行７０７は、部品Ｂ３を製造するために部品Ｃ１が５個と部品Ｃ３が３個と部品Ｃ５が２個必要であることを示している。
【００７０】
図８は、図７に示される構成品テーブル７００から、図３を参照して説明した手順と同様にして生成される階層型ツリー８００を示す。階層型ツリー８００は、部分ツリー８０１〜８０３を含む。
【００７１】
部品Ｂ１〜Ｂ３をそれぞれｂ1〜ｂ3個製造するのに必要な部品Ｃ１〜Ｃ５の数をそれぞれｃ1〜ｃ5個であるとすると、構成品テーブル７００から（数５）が成立する。
【００７２】
【数５】
0004243440.tif 000006
ここで
【００７３】
【数６】
0004243440.tif 000007
とおくと、（数３）〜（数６）より、
【００７４】
【数７】
0004243440.tif 000008
が成立する。
【００７５】
図９は、（数７）に示される式を計算するための階層型ツリー９００を示す。階層型ツリー９００は、図３（ｅ）に示される階層型ツリーのノード１３１およびノード１３３に図８に示される部分ツリー８０１を結合し、図３（ｅ）に示される階層型ツリーのノード１３２およびノード１３４に図８に示される部分ツリー８０２およぴ８０３をそれぞれ結合することによって得られる。このような結合により、階層型ツリー９００の階層は、図３（ｅ）に示される階層型ツリーの階層よりも深くなっている。
【００７６】
図１０は、階層型ツリー９００を用いて、部品Ａ１およびＡ２をそれぞれ５０個および３０個製造するのに必要な部品Ｃ１〜Ｃ５の個数が求められる様子を示す。以下、図１０を参照しながら部品Ｃ１〜Ｃ５の個数を求める手順を説明する。
【００７７】
ノード９０１（Ａ１）とノード９０２（Ａ２）との値がそれぞれ５０と３０とに設定される。
【００７８】
次に、ノード９０３の値が、ノード９０１の値で乗算される。その積が、ノード９０３の値として新たに設定される。ノード９０４〜ノード９０６についても、ノード９０３と同様にノードの値が新たに設定される。
【００７９】
次に、ノード９０７の値が、ノード９０３の新たに設定された値で乗算される。その積が、ノード９０７の値として新たに設定される。ノード９０８〜ノード９１５についても、ノード９０８と同様にノードの値が新たに設定される。
【００８０】
部品Ｃ１の必要個数ｃ1は、ノード９０７、９１１および９１３の値の和として求められる。すなわち、ｃ1＝２・３・５０＋２・３・３０＋５・６・３０＝１３８０である。部品Ｃ２〜Ｃ５の必要個数も同様にして求められる。
【００８１】
図１０を参照して説明した手順により、（数７）に示される式の計算が行なわれる。このように、（数７）に示されるような３個以上の行列の積も、階層型ツリーの階層を深くすることによって、階層型ツリーを用いて計算され得る。
【００８２】
図１１は、さらに深い階層を有する階層型ツリー１１００の例を示す。階層型ツリー１１００において、製品Ａ１および製品Ａ２の製造個数をそれぞれノードＡ１およびノードＡ２の値に設定することにより、必要な各部品の個数を計算することができる。
【００８３】
行列の乗算を図６に示される自動計算処理によって行うことにより、下記（１）の利点が得られる。
【００８４】
（１）図６に示される処理手順のうち、ステップＳ６０４〜ステップＳ６０６は、ａij≠０という条件を満たす行列Ａの各成分についてのみ行なわれる。これにより、ａij＝０という条件を満たす行列Ａの各成分については、階層型ツリーにノードが追加されない。その結果、０を含む積和演算が行なわれない。このため、行列の乗算を効率的に、従って、高速に、行うことができる。
【００８５】
さらに、部品展開問題を上述したように階層型ツリーを用いた自動計算処理によって解くことにより、（１）の利点に加えて、下記（２）の利点が得られる。
【００８６】
（２）構成品テーブル（例えば、図１に示される構成品テーブル１００）から、階層型ツリーが自動的に生成される。このため、構成品テーブルに変更が生じた場合に、階層型ツリーを更新することが容易である。
【００８７】
なお、図６に示される自動計算処理の手順において、ステップＳ６０４を省略することも可能である。この場合には、ステップＳ６０５におけるノードの追加は、列番号ｊに対応するノードＮjとノードＮjの下位ノードとして行番号ｉに対応するノードＮj,iとを生成し、列番号ｊをキー項目としてノードＮjとノードＮj,iとを階層型ツリーに追加することにより行なわれる。
【００８８】
本発明の自動計算処理は、部品展開問題に限らず、ｍ行ｎ列の行列Ａ＝（ａij）（ｉ＝１，２，・・・，ｍ；ｊ＝１，２，・・・，ｎ）とｎ行１列の行列ｘ＝（ｘk）（ｋ＝１，２，・・・，ｎ）との積Ａ×ｘを計算することが必要な任意の用途に適用することができる。
【００８９】
図１２は、行列演算が必要な問題の他の例として、騒音キャンセル装置に本発明の自動計算処理を適用した例を示す。図１２に示される例では、騒音キャンセル装置１２０６は、騒音源１２０１から発生する騒音が観察者１２０７に聞こえないように（または、聞こえにくく）する機能を実現する。以下、騒音キャンセル装置１２０６が、騒音源１２０１から発生する騒音が観察者１２０７に聞こえないように（または、聞こえにくく）する原理を説明する。
【００９０】
騒音キャンセル装置１２０６は、センサ１２０２と、コントローラ１２０４と、スピーカ１２０３とを備える。センサ１２０２は、例えば、マイクロホンであり得る。センサ１２０２からは、コントローラ１２０４に時刻ｔにおける状態ベクトルｗtが入力される。騒音は、空気中を空気圧力の変動として伝播する。状態ベクトルｗtは
【００９１】
【数８】
0004243440.tif 000009
と表され、ここで、ｐtは、時刻ｔおよびセンサ１２０２の位置における空気圧力、ｐ’tはその時刻および位置における空気圧力の時間変化量である。
【００９２】
状態ベクトルｗtから、時刻ｔ＋１における状態ベクトルｗt+1を（数９）に示されるように予測することができる。
【００９３】
【数９】
ｗｅt+1＝Ａ×ｗt
ここで、ｗｅt+1は、時刻ｔにおいて時刻ｔ＋１における状態ベクトルｗt+1を予測したベクトルを示す。ベクトルは、ｎ行１列の行列として表され得る（ｎは２以上の自然数）。
【００９４】
ここで、Ａは所定の２行２列の行列であり、制御対象となる系（圧力変動を伴う空気）の状態遷移行列を示す。
【００９５】
コントローラ１２０４は、（数１０）に示されるように、制御電圧ｕt+1を計算する。
【００９６】
【数１０】
ｕt+1＝Ｂ×ｗｅt+1
ここで、Ｂは所定の１行２列の行列である。
【００９７】
コントローラ１２０４は、（数９）および（数１０）に示される行列演算を図６を参照して説明した自動計算処理によって行う。
【００９８】
制御電圧ｕt+1は、時刻ｔ＋１において、スピーカ１２０３に入力される。
【００９９】
このように、スピーカ１２０３は、状態ベクトルの予測値ｗｅt+1に基づいて制御される。行列Ｂは、制御電圧ｕt+1をスピーカ１２０３に入力することによって、状態ベクトルの予測値ｗｅt+1に示される空気圧力の変動を打ち消すように決定されている。これにより、騒音発生源１２０１により発生した騒音がキャンセルされ、観察者１２０７に聞こえなくなる（または、聞こえにくくなる）。
【０１００】
騒音がキャンセルされる効果は、状態ベクトルの予測値ｗｅt+1と、実際の時刻ｔ＋１における状態ベクトルｗt+1との差がいかに小さいかに依存する。この差は、時刻ｔ＋１と時刻ｔとの差（刻み時間）が小さいほど小さくなるので、騒音がキャンセルされる効果を高めるためには、刻み時間を小さくすればよい。
【０１０１】
上述したように、コントローラ１２０４は、その刻み時間の間に（数９）および（数１０）に示される行列演算を実行する必要がある。本発明の自動計算処理によれば、行列の乗算が高速に行なわれるので、刻み時間を小さくすることができ、これにより、騒音がキャンセルされる効果を高くすることが可能になる。
【０１０２】
（数９）に示される行列Ａは、時間に応じて変化してもよい。行列Ａが時間に応じて変化する場合には、図６に示されるステップＳ６０１〜ステップＳ６１３の処理は、各刻み時間において実行される。行列Ａが時間に応じて変化しない場合には、図６に示されるステップＳ６０１〜ステップＳ６１０の処理は、各刻み時間において実行される必要はない。
【０１０３】
行列演算が必要な問題のさらに他の例として、カルマンフィルタを用いた最適制御問題を説明する。
【０１０４】
図１３は、カルマンフィルタを用いた最適制御システムのブロック図を示す。
【０１０５】
制御対象となる系は、状態方程式に従って状態遷移する。状態方程式は、（数１１）によって表される。
【０１０６】
【数１１】
Ｘt+1＝Ａ×Ｘt＋Ｃ×ｕt＋ｗt
ここで、Ｘtは制御対象となる系の時刻ｔにおける状態ベクトル、ｕtは時刻ｔにおいて制御対象となる系に加えられる制御ベクトル、ｗtは、時刻ｔにおいて制御対象となる系に加えられるノイズである。ＡおよびＣは、所定の行列である。制御対象となる系は、例えば、自動車、宇宙船、鉄道車両等の任意の系であり得る。
【０１０７】
コントローラ１３０１は、状態ベクトルＸtを直接観測することはできない。コントローラ１３０１には、観測モデル１３０２によってフィルタリングされた、時刻ｔにおける観測ベクトルＹtが入力される。ここで、Ｂを所定の行列として、
【０１０８】
【数１２】
Ｙt＝ＢＸt＋ｖt
である。
【０１０９】
コントローラ１３０１に組み込まれたカルマンフィルタ１３０３は、時刻ｔにおける観測ベクトルＹtと、時刻ｔにおける状態ベクトルの推定値Ｘｅtとに基づいて、時刻ｔ＋１における状態ベクトルの推定値Ｘｅt+1を計算する。ここで、Ｋをカルマンゲインを示す行列として、
【０１１０】
【数１３】
Ｘｅt+1＝Ａ×Ｘｅt＋Ｋ×（Ｙt−Ｂ×Ｘｅt）＋Ｃ×ｕt
である。
【０１１１】
コントローラ１３０１は、（数１３）に従って求められた推定値Ｘｅt+1に基づいて、時刻ｔ＋１における制御ベクトルｕt+1を計算する。ここで、Ｆt+1をフィードバックゲインを示す行列として、
【０１１２】
【数１４】
ｕt+1＝−Ｆt+1×Ｘｅt+1
である。
【０１１３】
このように、コントローラ１３０１は、時刻ｔから時刻ｔ＋１の間に（すなわち、刻み時間の間に）、（数１３）および（数１４）に示される式を計算する。系を安定に制御するためには、刻み時間をできるだけ短くする必要がある。（数１３）および（数１４）に示される式には、ｍ行ｎ列の行列（ｉ＝１，２，・・・，ｍ；ｊ＝１，２，・・・，ｎ）とｎ行１列の行列（すなわち、ベクトル）との積を求める計算が含まれる。このような計算には、図６を参照して上述した自動計算処理を適用することができる。これは、例えば、（数１３）において、行列の積Ｋ×（Ｙt−Ｂ×Ｘｅt）は、カルマンゲインＫおよびベクトル（Ｙt−Ｂ×Ｘｅt）をそれぞれ図６に示される処理手順中の行列Ａおよびｘとおくことにより実現される。また、（数１４）において、行列の積Ｆt+1×Ｘｅt+1は、フィードバックゲインＦt+1およびベクトルＸｅt+1をそれぞれ図６に示される処理手順中の行列Ａおよびｘとおくことができる。
【０１１４】
コントローラ１３０１が、図６を参照して上述した自動計算処理を行うことにより、（数１３）および（数１３）に示される式を高速に計算することが可能になる。従って、刻み時間をできるだけ短くすることが可能になり、系を安定に制御することが可能になる。
【０１１５】
【発明の効果】
本発明によれば、ｍ行ｎ列の行列Ａ＝（ａij）（ｉ＝１，２，・・・，ｍ；ｊ＝１，２，・・・，ｎ）とｎ行１列の行列ｘ＝（ｘk）（ｋ＝１，２，・・・，ｎ）との積Ａ×ｘを自動的に計算する自動計算方法が提供される。この自動計算方法は、ａij≠０という条件を満たす行列Ａの各成分について、列番号ｊに対応するノードＮjとノードＮjの下位ノードとして行番号ｉに対応するノードＮj,iとを生成し、列番号ｊをキー項目としてノードＮjとノードＮj,iとを階層型ツリーに追加するステップを含む。階層型ツリーのノードの生成は、ａij≠０という条件を満たす行列Ａの各成分についてのみ行なわれる。従って、行列の乗算が効率的に、高速に行なわれる。通常、さまざまなアプリケーションにおいて、ｍ、ｎが大きくなった場合に、行列Ａの成分ａijには、ａij＝０という条件を満たす成分が含まれることが多い。従って、本発明によれば、ｍ、ｎが大きくなった場合に計算量が爆発的に増える（状態空間が発散する）ことを効率的に防止することができる。
【図面の簡単な説明】
【図１】製品Ａ１および製品Ａ２を製造するために必要な部品の種類とその個数を定義する構成品テーブル１００の一例を示す図である。
【図２】部品展開問題を取り扱う本発明のコンピュータ３の構成の一例を示す図である。
【図３】各レコードに対応するノードが階層型ツリーに追加されていく様子を示す図である。
【図４】階層型ツリーのデータ構造を表すバイナリ・ツリー・インデックス・テーブル１４０の一例を示す
【図５】階層型ツリーを用いて、部品Ｂ１〜Ｂ３の必要個数が求められる様子を示す図である。
【図６】階層型ツリーを用いて、ｍ行ｎ列の行列Ａ＝（ａij）とｎ行１列の行列ｘ＝（ｘk）との積Ａ×ｘを自動的に計算する自動計算処理の手順を示す図である。
【図７】図１を参照して説明した部品展開問題において、部品Ｂ１〜Ｂ３を製造するために必要な部品の種類とその個数を定義する構成品テーブル７００の一例を示す図である。
【図８】図７に示される構成品テーブル７００から、図３を参照して説明した手順と同様にして生成される階層型ツリー８００を示す図である。
【図９】（数７）に示される式を計算するための階層型ツリー９００を示す図である。
【図１０】階層型ツリー９００を用いて、部品Ａ１およびＡ２をそれぞれ５０個および３０個製造するのに必要な部品Ｃ１〜Ｃ５の個数が求められる様子を示す図である。
【図１１】さらに深い階層を有する階層型ツリー１１００の例を示す図である。
【図１２】行列演算が必要な問題の他の例として、騒音キャンセル装置に本発明の自動計算処理を適用した例を示す図である。
【図１３】カルマンフィルタを用いた最適制御システムのブロック図を示す図である。
【符号の説明】
３  コンピュータ
３１  ＣＰＵ
３２  主記憶
３３  ＨＤＤ
３４  入力デバイス
【図１】
0004243440.tif 000010
【図２】
0004243440.tif 000011
【図３】
0004243440.tif 000012
【図４】
0004243440.tif 000013
【図５】
0004243440.tif 000014
【図６】
0004243440.tif 000015
【図７】
0004243440.tif 000016
【図８】
0004243440.tif 000017
【図９】
0004243440.tif 000018
【図１０】
0004243440.tif 000019
【図１１】
0004243440.tif 000020
【図１２】
0004243440.tif 000021
【図１３】
0004243440.tif 000022