JPH04111165A - 方程式解析装置 - Google Patents
方程式解析装置Info
- Publication number
- JPH04111165A JPH04111165A JP22825890A JP22825890A JPH04111165A JP H04111165 A JPH04111165 A JP H04111165A JP 22825890 A JP22825890 A JP 22825890A JP 22825890 A JP22825890 A JP 22825890A JP H04111165 A JPH04111165 A JP H04111165A
- Authority
- JP
- Japan
- Prior art keywords
- matrix
- circuit
- approximate
- backward substitution
- coefficient
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
- 239000011159 matrix material Substances 0.000 claims abstract description 68
- 238000004364 calculation method Methods 0.000 claims abstract description 51
- 238000006467 substitution reaction Methods 0.000 claims abstract description 27
- 238000000354 decomposition reaction Methods 0.000 claims description 16
- 238000004458 analytical method Methods 0.000 claims description 10
- 230000006866 deterioration Effects 0.000 abstract description 2
- 238000000034 method Methods 0.000 description 22
- 230000007423 decrease Effects 0.000 description 3
- 238000010586 diagram Methods 0.000 description 3
- 230000008901 benefit Effects 0.000 description 2
- 230000000694 effects Effects 0.000 description 2
- 238000002939 conjugate gradient method Methods 0.000 description 1
- 238000007796 conventional method Methods 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
Landscapes
- Complex Calculations (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔産業上の利用分野］
本発明は、方程式解析装置に関するものであり、例えば
差分法による偏微分方程式解析のための高速演算装置に
関するものである。
差分法による偏微分方程式解析のための高速演算装置に
関するものである。
〔従来の技術］
方程式の解を求める場合、従来の技術としてはｆ＝Ｌ＋
ｃｍによる再グループ化を行わずに上三角行列と上三角
行列への近似分解を行う方法（ハイパープレーン法）が
あった。
ｃｍによる再グループ化を行わずに上三角行列と上三角
行列への近似分解を行う方法（ハイパープレーン法）が
あった。
更に詳しく述べるに、解くべき連立一次方程式Ａｕ＝ｆ
と表すと、上三角行列りと上三角行列しによる計算は、
Ａの近似分解 Ｍ＝ＬＵ＝ＡｔＲ を用いて、ｋ （ｋ、＝ｏ、 １．、 ２． ・・
・）による繰り返し計算 Ｍ ｕ ｆｋ−１ｆ−Ｒｕ（ｋ＋ 士ｆにより近似解ｕ
０°１′ を求めることであり、ここで必要となるＬと
Ｕの逆行列計算が前進代入 後退代入と呼ばれるもので
ある。
Ａの近似分解 Ｍ＝ＬＵ＝ＡｔＲ を用いて、ｋ （ｋ、＝ｏ、 １．、 ２． ・・
・）による繰り返し計算 Ｍ ｕ ｆｋ−１ｆ−Ｒｕ（ｋ＋ 士ｆにより近似解ｕ
０°１′ を求めることであり、ここで必要となるＬと
Ｕの逆行列計算が前進代入 後退代入と呼ばれるもので
ある。
ハイパープレーン法による前進代入Ｌ−’の計算は１−
ｉ ＋ ｊ ＋にの格子点について同時並列に行うこと
ができ、複数の演算回路を持つ装置を有効に活用できる
。この方法は例えば「スーパーコンピューター科学技術
計算への応用−」村田健部他（丸善）に更に詳しく述べ
られている。
ｉ ＋ ｊ ＋にの格子点について同時並列に行うこと
ができ、複数の演算回路を持つ装置を有効に活用できる
。この方法は例えば「スーパーコンピューター科学技術
計算への応用−」村田健部他（丸善）に更に詳しく述べ
られている。
もう一つの従来法としては、直方体格子上の格子点を、
格子座標（ｉ、ｊ、ｋ）の和が奇数の点と偶数の点に分
け、各グループに対して上三角行列と上三角行列への近
似分解を行う方法（Ｏｄｄ−Ｅｖｅｎ法）があった。０
ｄｄ−Ｅｖｅｎ法における計算順序を第３図に示す。
格子座標（ｉ、ｊ、ｋ）の和が奇数の点と偶数の点に分
け、各グループに対して上三角行列と上三角行列への近
似分解を行う方法（Ｏｄｄ−Ｅｖｅｎ法）があった。０
ｄｄ−Ｅｖｅｎ法における計算順序を第３図に示す。
なお、反復計算回路においては共役勾配法などのよく知
られた方法を用いて、複数の演算回路を生かした計算が
容易に実現できる。これＳ：ついては例えば、前記「ス
ーパーコンピューター科学技術計算への応用−Ｊに詳し
く述べられている。
られた方法を用いて、複数の演算回路を生かした計算が
容易に実現できる。これＳ：ついては例えば、前記「ス
ーパーコンピューター科学技術計算への応用−Ｊに詳し
く述べられている。
〔発明が解決しようとする課題］
一般に前記構成からなる方程式解析装置では近似行列前
進後退代入回路が演算時間の大部分を費やし、その高速
化が重要であると同時に、近似の精度、即ち誤差行列Ｒ
の要素値が小さいことが重要である。上述したハイパー
プレーン法にあっては、ｆ＝ｉ＋ｊ＋にの格子点につい
て同時計算できるが、その数は平均するとＮ ２／ ３
（Ｎ ＝ ｎ ｘ＝ｌ’ｌ、 ＝ｎ２のとき）であり
、さらに多数の独立な演算回路を持つ前進後退代入回路
を利用することができない。
進後退代入回路が演算時間の大部分を費やし、その高速
化が重要であると同時に、近似の精度、即ち誤差行列Ｒ
の要素値が小さいことが重要である。上述したハイパー
プレーン法にあっては、ｆ＝ｉ＋ｊ＋にの格子点につい
て同時計算できるが、その数は平均するとＮ ２／ ３
（Ｎ ＝ ｎ ｘ＝ｌ’ｌ、 ＝ｎ２のとき）であり
、さらに多数の独立な演算回路を持つ前進後退代入回路
を利用することができない。
また０ｄｄ−Ｅｖｅｎ法は半数、即ちＮ：ｌ／２の格子
点に関する計算が同時に行えるため、複数の演算回路を
持つ前進後退代入回路を利用できる反面、近似行列Ｍの
近似精度か高（ないことが知られており、ハイパープレ
ーン法と同じ精度の近似解を得るのに数倍の計算を必要
とするため、複数回路を用いることにより高速化のノリ
ノドか打ち消されてしまう。
点に関する計算が同時に行えるため、複数の演算回路を
持つ前進後退代入回路を利用できる反面、近似行列Ｍの
近似精度か高（ないことが知られており、ハイパープレ
ーン法と同じ精度の近似解を得るのに数倍の計算を必要
とするため、複数回路を用いることにより高速化のノリ
ノドか打ち消されてしまう。
本発明の目的は、複数の演算回路を用いた高速並列計算
が可能な方程式解析装置を提供することにある。
が可能な方程式解析装置を提供することにある。
〔課題を解決するための手段］
本発明は、直方体領域で定義された偏微分方程式を直交
格子点（ｉ、ｊ、ｋ）（１≦ｊ≦ｎｘ、１≦Ｊ≦ｎｙ、
ｌ≦ｋ≦ｎｚ）上で離散近似して得られる連立一次方程
弐の係数行列と係数へ、クトルを入力データとし、 係数行列を近似行列に分解する係数行列分解回路と、反
復計算回路と、係数行列分解回路で生成された近似行列
の逆行列を反復計算回路から入力したベクトルデータに
掛け反復計算回路に出力する前進後退代入回路とを備え
、 前記連立一次方程弐の近似解を出力とする方程式解析装
置において、 係数行列分解回路は、前記直交格子点をｆｆ−１＋ｊ−
１−にの値によってグループ分けし、与えられたｍに対
して、ｆｆ−Ｌ＋−ｃｍ （ｃは任意の整数）となるＬ
によってさらにこれらをグループ分けして得られるｍ個
のグループについて、Ｌの若い順に各直交格子点に関す
る係数行列を上三角行列と上三角行列に分割し、それら
の積の形で近似し、前進後退代入回路は、反復計算回路
から入力したベクトルデータに各々のグループについて
前記上三角行列と上三角行列による前進後退代入を行う
ことによって近似行列の逆行列計算を行うことを特徴と
している。
格子点（ｉ、ｊ、ｋ）（１≦ｊ≦ｎｘ、１≦Ｊ≦ｎｙ、
ｌ≦ｋ≦ｎｚ）上で離散近似して得られる連立一次方程
弐の係数行列と係数へ、クトルを入力データとし、 係数行列を近似行列に分解する係数行列分解回路と、反
復計算回路と、係数行列分解回路で生成された近似行列
の逆行列を反復計算回路から入力したベクトルデータに
掛け反復計算回路に出力する前進後退代入回路とを備え
、 前記連立一次方程弐の近似解を出力とする方程式解析装
置において、 係数行列分解回路は、前記直交格子点をｆｆ−１＋ｊ−
１−にの値によってグループ分けし、与えられたｍに対
して、ｆｆ−Ｌ＋−ｃｍ （ｃは任意の整数）となるＬ
によってさらにこれらをグループ分けして得られるｍ個
のグループについて、Ｌの若い順に各直交格子点に関す
る係数行列を上三角行列と上三角行列に分割し、それら
の積の形で近似し、前進後退代入回路は、反復計算回路
から入力したベクトルデータに各々のグループについて
前記上三角行列と上三角行列による前進後退代入を行う
ことによって近似行列の逆行列計算を行うことを特徴と
している。
簡単のため、２次元長方形格子を例に説明する。
第２図は２次元の長方形格子である。前進後退代入計算
は格子によって直接つながっている隣接格子点において
同時に行うことはできないという制約がある。ハイパー
プレーン法は格子の端点より斜めの線上の格子点につい
て並列に計算する方法であり、この方法では最大ｍ Ｉ
ｎ （ｎＸｎｙ、ｎ、ｎ。
は格子によって直接つながっている隣接格子点において
同時に行うことはできないという制約がある。ハイパー
プレーン法は格子の端点より斜めの線上の格子点につい
て並列に計算する方法であり、この方法では最大ｍ Ｉ
ｎ （ｎＸｎｙ、ｎ、ｎ。
ｎｚｎｘ）格子点についてしか並列例算できない。
０ｄｄ−ＥＶｅｎ法は、第３回で示される○の点につい
で計算したあと、・の点について計算を行う。○同士（
・同士）は互いにつながっていないので同時計算が可能
である。しかしながら、前記のように近似精度が低いた
め、ハイパープレーン法と同し精度の解を得るために非
常に多くの反復計算を要し、並列化のメリットが生かせ
ない。
で計算したあと、・の点について計算を行う。○同士（
・同士）は互いにつながっていないので同時計算が可能
である。しかしながら、前記のように近似精度が低いた
め、ハイパープレーン法と同し精度の解を得るために非
常に多くの反復計算を要し、並列化のメリットが生かせ
ない。
第４図は本発明による計算の順序（ｍ−３の場合）を表
している。ｍおきの複数のハイパープレーン内に含まれ
る格子点の計算が同時に行われる。
している。ｍおきの複数のハイパープレーン内に含まれ
る格子点の計算が同時に行われる。
すなわち、同じ番号のハイパープレーンが同時処理され
る。ここでｍを領域の２辺の長さの和とすると、この手
法は従来のハイパープレーン法となる。また０ｄｄ−Ｅ
ｖｅｎ法は、ｍが２の場合に相当する。
る。ここでｍを領域の２辺の長さの和とすると、この手
法は従来のハイパープレーン法となる。また０ｄｄ−Ｅ
ｖｅｎ法は、ｍが２の場合に相当する。
格子のサイズをｎＸｎ、同一グループに含まれるハイパ
ープレーン間隔をｍとすると、ｎ ２７ ｍの独立な計
算となり、それに相当する独立な演算器による計算が可
能となる。例えばｎを１２８ 、ｍを１６とすると１２
８Ｘ （１２８／１６） −１０２４個の演算器による
並列計算が可能となる。
ープレーン間隔をｍとすると、ｎ ２７ ｍの独立な計
算となり、それに相当する独立な演算器による計算が可
能となる。例えばｎを１２８ 、ｍを１６とすると１２
８Ｘ （１２８／１６） −１０２４個の演算器による
並列計算が可能となる。
一方、Ｍの近似精度について、ｍを小さくすると精度が
低下することが確かめられる。例えばｍ＝２とすると独
立な演算数は増えるが、近似精度の点で問題が生しる。
低下することが確かめられる。例えばｍ＝２とすると独
立な演算数は増えるが、近似精度の点で問題が生しる。
ｍ＝２ｎ−川とすると前記ハイパープレーン法となり、
収束精度は良好であるが、複数の演算器を有効利用でき
ない。
収束精度は良好であるが、複数の演算器を有効利用でき
ない。
即ち、本発明は与えられた個数の演算器をフルに生かし
ながら、最小限の近イ以精度の低下で計算を行うことを
可能とするものである。さらに、ｍが適当に大きい場合
、近似精度の低下は極めて僅かであることが確かめられ
ている。従って、実際にはほとんど近似精度の低下を起
こさずに複数の演算器により並列計算ができ、高速化が
達成できる。
ながら、最小限の近イ以精度の低下で計算を行うことを
可能とするものである。さらに、ｍが適当に大きい場合
、近似精度の低下は極めて僅かであることが確かめられ
ている。従って、実際にはほとんど近似精度の低下を起
こさずに複数の演算器により並列計算ができ、高速化が
達成できる。
次に、本発明の実施例について図面を参照して説明する
。
。
第１図は本発明の一実施例である方程式解析装置の構成
を示す。この方程式解析装置は、プロセッサから構成さ
れ、入力データ（行列Ａ、ヘクトルｆ）１１が供給され
る係数行列分解回路１と、係数行列分解回路１からＡの
近似行列Ｍの分解された行列１２が与えられる前進後退
代入回路２と、前進後退代入回路２に接続された反復計
算回路３から成っている。
を示す。この方程式解析装置は、プロセッサから構成さ
れ、入力データ（行列Ａ、ヘクトルｆ）１１が供給され
る係数行列分解回路１と、係数行列分解回路１からＡの
近似行列Ｍの分解された行列１２が与えられる前進後退
代入回路２と、前進後退代入回路２に接続された反復計
算回路３から成っている。
反復計算回路３には、入力データ１１が供給される。ま
た、反復計算回路３は、前進後退代入回路２に対し、ベ
クトル１３（ベクトルｇ）を与えるようになっていると
共に、前進後退代入回路２からベクトル１４（ベクトル
ｖ＝Ｍ−’ｇ）が与えられるようになっている。
た、反復計算回路３は、前進後退代入回路２に対し、ベ
クトル１３（ベクトルｇ）を与えるようになっていると
共に、前進後退代入回路２からベクトル１４（ベクトル
ｖ＝Ｍ−’ｇ）が与えられるようになっている。
係数行列分解回路１は、偏微分方程式の離散近似により
得られる連立一次方程式の係数行列と係数ベクトルを入
力データとし、係数行列を反転が容易な近似行列に分解
する回路であって、更に、係数行列を小直方体に対応す
る複数の下三角行列と上三角行列に分解し、それらの積
で近似する処理を行う。
得られる連立一次方程式の係数行列と係数ベクトルを入
力データとし、係数行列を反転が容易な近似行列に分解
する回路であって、更に、係数行列を小直方体に対応す
る複数の下三角行列と上三角行列に分解し、それらの積
で近似する処理を行う。
前進後退代入回路２は、係数行列分解回路１で生成され
る近似行列の反転行列を反復計算回路３から入力したベ
クトルデータに掛け反復計算回路３へ出力し、反復計算
回路３から入力したへクトルデータに前記上三角行列と
下三角行列による前進後退代入計算を行うことによって
近似行列の反転を行う。
る近似行列の反転行列を反復計算回路３から入力したベ
クトルデータに掛け反復計算回路３へ出力し、反復計算
回路３から入力したへクトルデータに前記上三角行列と
下三角行列による前進後退代入計算を行うことによって
近似行列の反転を行う。
方程式Ａｕ＝ｆの近憤解ｕ１５は、反復計算回路３から
取り出される。
取り出される。
このように、連立一次方程式の係数行列と係数ベクトル
を入力データとし、係数行列を近似行列に分解する係数
行列分解回路１と、係数行列分解回路１で生成された近
イ以行列の反転行列を反復計算回路３から入力したベク
トルデータに掛け反復計算回路３に出力する前進後退代
入回路２と、これに接続される反復計算回路から成り、
前記連立一次方程式の近似解を出力とする連立一次方程
式解析装置であって、係数行列分解回路１は前記係数行
列を複数のハイパープレーンに対応する複数の下三角行
列と上三角行列とＳこ分解し、それるの積で近似し、前
進後退代入回路２は反復計算回路３かる入力しター・ク
トルデータに前記下三角行列上上三角行列二二よる前進
後退代入を行うこと二こよって近似行列の反転を行うよ
うにする。このようにすると各ハイパープレーン及びハ
イパーブレーン内の格子点５＋対応する前進後退代入計
算が複数の演算回路で互いに独立乙こ実行でき、高速化
が達成できる。
を入力データとし、係数行列を近似行列に分解する係数
行列分解回路１と、係数行列分解回路１で生成された近
イ以行列の反転行列を反復計算回路３から入力したベク
トルデータに掛け反復計算回路３に出力する前進後退代
入回路２と、これに接続される反復計算回路から成り、
前記連立一次方程式の近似解を出力とする連立一次方程
式解析装置であって、係数行列分解回路１は前記係数行
列を複数のハイパープレーンに対応する複数の下三角行
列と上三角行列とＳこ分解し、それるの積で近似し、前
進後退代入回路２は反復計算回路３かる入力しター・ク
トルデータに前記下三角行列上上三角行列二二よる前進
後退代入を行うこと二こよって近似行列の反転を行うよ
うにする。このようにすると各ハイパープレーン及びハ
イパーブレーン内の格子点５＋対応する前進後退代入計
算が複数の演算回路で互いに独立乙こ実行でき、高速化
が達成できる。
以上説明したように、本発明によれば複数の演算回路を
用いた高速並列演算が可能となる。
用いた高速並列演算が可能となる。
第１図は本発明の一実施例の構成を示す図、第２図、第
３回は従来技術における計算格子の例を示す図、 第４図は本発明における計算格子の例を示す図である。 １・・・・・係数行列分解回路 ２・・・・・前進後退代入回路 ■ ；入力データ（行列Ａ、’＜’クトルｆ）Ａの近イ以イ
１列ＭのＬＵつ１Ｒさｔ″Ｕだ行列１３、へ゛クトル９ ４、穴′クトルｖ （：Ｍ−’ｇ ） １５、方！：Ｘ、Ａｕ ：ｆ（Ｄ近イ以角ｅＡＸ゛クト
ルＵ第 図 ・反復計算回路
３回は従来技術における計算格子の例を示す図、 第４図は本発明における計算格子の例を示す図である。 １・・・・・係数行列分解回路 ２・・・・・前進後退代入回路 ■ ；入力データ（行列Ａ、’＜’クトルｆ）Ａの近イ以イ
１列ＭのＬＵつ１Ｒさｔ″Ｕだ行列１３、へ゛クトル９ ４、穴′クトルｖ （：Ｍ−’ｇ ） １５、方！：Ｘ、Ａｕ ：ｆ（Ｄ近イ以角ｅＡＸ゛クト
ルＵ第 図 ・反復計算回路
Claims (1)
- （１）直方体領域で定義された偏微分方程式を直交格子
点（ｉ、ｊ、ｋ）（１≦ｉ≦ｎ＿ｘ、１≦ｊ≦ｎ＿ｙ、
１≦ｋ≦ｎ＿ｚ）上で離散近似して得られる連立一次方
程式の係数行列と係数ベクトルを入力データとし、 係数行列を近似行列に分解する係数行列分解回路と、反
復計算回路と、係数行列分解回路で生成された近似行列
の逆行列を反復計算回路から入力したベクトルデータに
掛け反復計算回路に出力する前進後退代入回路とを備え
、 前記連立一次方程式の近似解を出力とする方程式解析装
置において、 係数行列分解回路は、前記直交格子点をｌ＝ｉ＋ｊ＋ｋ
の値によってグループ分けし、与えられたｍに対して、
ｌ＝Ｌ＋ｃｍ（ｃは任意の整数）となるＬによってさら
にこれらをグループ分けして得られるｍ個のグループに
ついて、Ｌの若い順に各直交格子点に関する係数行列を
下三角行列と上三角行列に分割し、それらの積の形で近
似し、前進後退代入回路は、反復計算回路から入力した
ベクトルデータに各々のグループについて前記下三角行
列と上三角行列による前進後退代入を行うことによって
近似行列の逆行列計算を行うことを特徴とする方程式解
析装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP22825890A JP2870161B2 (ja) | 1990-08-31 | 1990-08-31 | 方程式解析装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP22825890A JP2870161B2 (ja) | 1990-08-31 | 1990-08-31 | 方程式解析装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH04111165A true JPH04111165A (ja) | 1992-04-13 |
| JP2870161B2 JP2870161B2 (ja) | 1999-03-10 |
Family
ID=16873652
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP22825890A Expired - Fee Related JP2870161B2 (ja) | 1990-08-31 | 1990-08-31 | 方程式解析装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP2870161B2 (ja) |
-
1990
- 1990-08-31 JP JP22825890A patent/JP2870161B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JP2870161B2 (ja) | 1999-03-10 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Wu et al. | Parallel solution of large sparse matrix equations and parallel power flow | |
| EP4095719A1 (en) | Sparse matrix multiplication in hardware | |
| EP0523544A2 (en) | Calculating equipment for solving systems of linear equation | |
| Cheng et al. | Hardware efficient fast DCT based on novel cyclic convolution structures | |
| Lin et al. | Parallel solution of sparse algebraic equations | |
| Chionh et al. | Fast computation of the Bezout and Dixon resultant matrices | |
| KR20220158768A (ko) | 기계 학습 가속을 위한 전력 감소 | |
| Grinberg et al. | The n body matrix and its determinant | |
| JPH04111165A (ja) | 方程式解析装置 | |
| Göttfert | An acceleration of the Niederreiter factorization algorithm in characteristic 2 | |
| Ohno et al. | A quadrature-based eigensolver with a Krylov subspace method for shifted linear systems for Hermitian eigenproblems in lattice QCD | |
| Omar et al. | Parallel two-point explicit block method for solving high-order ordinary differential equations | |
| Annaratone et al. | Using Warp as a supercomputer in signal processing | |
| Yamazaki et al. | Analyzing performance of bicgstab with hierarchical matrix on gpu clusters | |
| JPH03266173A (ja) | 方程式解析装置 | |
| EP0438119A2 (en) | Numerical processing of optical wavefront data | |
| Huang et al. | A parallel FFT algorithm for transputer networks | |
| Yamazaki et al. | Performance of hierarchical-matrix BiCGStab solver on GPU clusters | |
| JPH0477961A (ja) | 方程式解析装置 | |
| Taniguchi et al. | Enumeration algorithm for genus-4 superspecial hyperelliptic curves with automorphism group Q8 | |
| Wyrzykowski | Processor arrays for matrix triangularisation with partial pivoting | |
| JPH0328961A (ja) | 高速演算装置 | |
| Ghouse | 2D grid architectures for the DFT and the 2D DFT | |
| JP3648286B2 (ja) | 並列機向け固有ベクトル求解方法及びこれを用いた構造解析シミュレーション方法 | |
| Stetsyura | Combining computation and data transmission in the systems with switches |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |