学術情報処理研究 No.1 1997 pp.39-43

数値計算ライブラリの自動選択システム


和田 武


愛媛大学総合情報処理センター
松山市文京町3
TEL 089-927-8801, wada@dpc.ehime-u.ac.jp


概要

  数値計算ライブラリを使用する際、浮動小数計算による誤差や解法アルゴリ ズムの特性のため、場合によっては全く信頼できない結果を生じる可能性が ある。そこで、複数の使用可能なアルゴリズムの中から、問題に適合し、安定 した結果を生じるアルゴリズムを自動的に選択するしくみが必要になる。本論 では、与えた問題の性質を自動的に判定し、適切なアルゴリズムを選択し、か つその計算実行までも行い得るような利用者支援システムの開発を行う。具体 的には解きにくい問題の例として硬い常微分方程式の数値解法を考え、硬さの 度合い(スティッフ率)を数式処理システムを利用して計算し、データベース に格納されたアルゴリズム中から適切なものを選択・実行するようにした。ユ ーザインターフェースを簡便にするため、Netscape NavigatorなどのWebブラ ウザの利用を可能とした。また、実際のシステム動作を広く使用されている数 値計算アルゴリズムSSL-IIを対象として示した。

キーワード

利用者支援、アルゴリズム選択、数値計算ライブラリ

1. はじめに

 幅広い分野における計算の要求と問題の多様化が進む中で、「問題の性質を把 握しなければ安定した結果が得れない」ような計算が出現している。その多く は数値計算に出現する。数値計算では常にある種の近似解を求めるため、浮動 小数計算による誤差が重要になったり、計算精度との関連で信じられないよう な結果を生んだりすることは一般に知られている。これらは広く悪条件問題と 呼ばれている。本論では「硬い」(スティッフ:stiff) 常微分方程式を例にとっ て、その振舞について実験的に述べる。硬い常微分方程式の場合、一般的な数 値解法を用いると、与えられた方程式の性質によって、非常に小さな刻み幅で 数値解を求めない限り、正確な解の近似値を求められない場合がある。当然、 大量の計算時間を消費し、かつ計算回数の増大とともに結果に含まれる数値誤 差も無視できなくなる。しかし、このような場合にも硬い微分方程式に適する 数値解法を用いると、上の困難を回避しつつ満足な結果を得ることができる。 このように問題に適合した最適の解法(アルゴリズム)を自動的に選択するシス テムをアルゴリズム選択システムという。計算機センターにこのようなシステ ムが構築され、学内外から自由にネットワークを通じて利用することが可能に なれば、多くの利用者の便をはかり、かつ新しい学内センターの方向を示すこ ともできると思われる。

2. アルゴリズム選択と硬い常微分方程式

 アルゴリズム選択の例として、次の一階連立常微分方程式の数値解を得る場合を考 える。



この式は近似的に



となる。また、(2)をオイラー法で解くと、刻み幅 h



という制約がつくことがわかる。t=1 までの数値解を得ようとすると、 106 ステップもの計算が必要になる。この状況はオイラー法より 少し複雑なルンゲ-クッタ法やアダムス法(Adams-Bashforth法など)を適用し ても同様である。これは、行列 A の固有値の 大きさが極端に異なることに起因している。このような微分方程式を硬い微分方程 式と呼び、電気回路網、化学反応、原子炉の問題、制御系、偏微分方程式に対する 「 線の方法」などによくあらわれる。
 (1)の連立常微分方程式を、適当な刻み幅$h$によって、ルンゲ--クッタ--ギル 法(RKG)で解いた場合と、硬い連立常微分方程式に適したギア法(ODGE)で解いた 場合の結果を Table1に示す。



overflow は数値結果が浮動小数の表現範囲を越えたために演算が不可能 になったことを意味する。なお、計算には富士通が開発した 数値計算ライブラリ、SSL-IIに含まれるアルゴリズムを用いた。 このような刻み幅では通常用いるルンゲ-クッタ--ギル法(RKG)による結果は全 く信用をおくことができない。もちろん、刻み幅を上述のように極端に小さく すると、それなりの結果を得るが、計算回数が飛躍的に増大し、その間の誤差 の累積も増大するので、数値結果の安定性と正確性の両面から、この方法の 利用は不適切であることがわかる。もちろん、上のような悪条件性を持たない 方程式に対しては、敢えて計算量の増すギア法等を採用しなくとも信頼のおけ る結果を得ることが出来る。このように硬い常微分方程式を解く際にはアルゴ リズム選択が極めて重要になる。しかし、常微分方程式がスティッフであるか 否かは一般に計算前にはわからないので、誤って不安定な結果を生じるアルゴ リズムによる結果を盲信する危険がある。スティッフ率の大きさを事前に求め れれば、正しいアルゴリズムを選択できることは明らかである。

3. アルゴリズム選択システム

 図1 にアルゴリズム選択システムの構成を示す。点線の左側はユーザの マシン(クライアント)、右側はサーバマシン(ホスト)のシステムである。 ユーザはNetscape Navigator等のWebブラウザを起動しサーバマシン上の Illustraデータベースにアクセスしアルゴリズム検索を行う。システム の動作環境はWindows95 上の Webサーバ、WindowsNT4.0 上のデータベー スシステム Illustra を中核とし、UNIX環境下の数式処理システム Maple と結合する。


Fig.1 システム構成


 次に、アルゴリズム選択システムの動作例を示す。本システムを起動し、 パッケージ選択後、問題の種類を与え、目的とするアルゴリズムの種類ま で順次検索を行なっていく。 図2は、SSL-IIの常微分方程式入力画面である。システムは、入力された 問題に対するスティッフ率を計算し、スティッフな常微分方程式に適したアル ゴリズムを呼び出し、実行可能な Fortranプログラムを自動的に作成する。 図3がプログラムを実行した画面である。


Fig.2 常微分方程式の入力

Fig.3 SSL-IIの実行


4. むすび

 本論では、アルゴリズム選択システムの開発について述べた。 現在開発できている部分の概要は次のようにまとめることができる。
  1. 数式として入力された常微分方程式の特徴抽出に数式処理システム Maple を活用し、アルゴリズム選択を行う。
  2. ユーザインターフェースの向上を目指し、Netscape Navigatorなどの Webブラウザでのシステムの利用を可能とした。このことにより、ネッ トワークを通じて、ユーザの場所、計算機の種類にとらわれない利用が 可能となった。
  3. 膨大なアルゴリズムの情報や検索システムを格納するため、オブジェク トリレーショナルデータベースシステム Illustra を活用した。
  4. アルゴリズム名の選択のみでなく、実際の数値計算を行い結果を得るこ とを可能とした。
 今後は、このようなシステムの一層の充実を図るため、以下の事項を早急に 実現する必要がある。
  1. 最近の関連する論文[1,2] に見られるようなアルゴリズム 選択システムの知識ベース化により、引数の数や型を意識せずに数値計 算ライブラリを使用できるシステムの構成。
  2. 数値計算ライブラリだけでなく、同様のシステムを統計計算ライブラリ の使用に拡張し、多くのパッケージ間の引数や命令の差異を意識せずに 計算可能な知的システムの作成。

参考文献

[1]
B.J.Dupee and J.H.Davenport, An Intelligent Interface to Numerical Routines, In Design and Implementation of Symbolic Computation Systems Eds. J.Calmet and C.Limongelli, Lecture Notes in Computer Science 1128, pp.252-262, Springer, 1996.

[2]
S.Weerawarana, E.N.Houstis, J.H.Rice, A.Joshi and C.E.Houstis, PYTHIA : A Knowledge-Based System to Select Scientific Algorithms, ACM Tran. Math. Soft., Vol.22, pp.447-468, 1996.