学術情報処理研究 No.1 1997 pp.3-15

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


和田 武 、 保田 貴史 *、 野田 松太郎 **


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

*富士通中国通信システム(株)
広島市中区東白島町14-15
TEL 082-228-3501, yasuda@hpc.cs.ehime-u.ac.jp

**愛媛大学工学部情報工学科
松山市文京町3
TEL 089-927-9954, noda@cs.ehime-u.ac.jp


概要

　総合情報処理センター等の大型計算機を核とする学内共同利用センターの役割 も情報時代の進展とともに変質しつつある。一部にはネットワークセンター化 を目指す方向もあるが、逆に利用者の拡大および数値計算ライブラリを含む大 量のソフトウェアの出現により、利用者に対して適切な計算技術の支援を行い 得るシステム開発の重要性がある。そこで、浮動小数計算による誤差や解法ア ルゴリズムの特性のため、場合によっては全く信頼できない結果を生じる可能 性がある数値計算ライブラリの使用時に、複数の使用可能アルゴリズム中から、 問題に適合し、安定した結果を生じるアルゴリズムを自動的に選択するしくみ が必要と考える。 本論では、与えた問題の性質を自動的に判定し、適 切なアルゴリズムを選択し、かつその計算実行までもを行い得るような利用者 支援システムの開発を行う。具体的には解きにくい問題の例として硬い常微分 方程式の数値解法を考え、硬さの度合い（スティッフ率）を数式処理システム を利用して計算し、データベースに格納されたアルゴリズム中から適切なもの を選択・実行するようにした。ユーザインターフェースを簡便にするため、 Netscape NavigatorなどのWebブラウザでのシステムの利用を可能とした。実際 のシステム動作を広く使用されている数値計算アルゴリズムSSL-IIを対象とし て示した。

キーワード

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


An automatic system for the selection of mathematical software

Takeshi Wada, Takashi Yasuda*, Matsu-taro Noda**


General Information Processing Center, Ehime University
3 Bunkyo,Matsuyama, Ehime 790, Japan
089-927-8801, wada@dpc.ehime-u.ac.jp
* FUJITSU Chugoku Communication Systems
14-15 Higashi hakushima,naka-ku,Hiroshima, Hiroshima 730, Japan
082-228-3501, yasuda@hpc.cs.ehime-u.ac.jp
** Department of Computer Science, Ehime University
3 Bunkyo,Matsuyama, Ehime 790, Japan
089-927-9954, noda@cs.ehime-u.ac.jp

Abstract

　A prototype of an automated system to aid users in selecting mathematical software is presented. Given an input problem, the system selects an appropriate algorithm in a library stored in a database and executes the problem and finally gives results. A computer algebra system, MAPLE, is used to extract specific features of the problem. Users use the system through web browsers such as the Netscape Navigator etc. As an mathematical software, the SSL-II, Fujitsu Co., is considered.

Keywords

User support system, Algorithm selection, Math. library

1. はじめに

　わが国の大学での幅広いコンピュータ利用を促進し、現在の情報時代に対応し える学術・研究体制の基盤を築いて来たものとして、全国各大学の大型計算機 センター、情報処理センター、総合情報処理センター等の果して来た役割は大 きく評価することが出来る。本来、貧弱なコンピュータ利用を広めるための計 算サーバ的な意味を強く持っていた上記各種センターであるが、近年の急激な ハードウェアの進歩や多様なソフトウェアの出現にともない、これらセンター には、むしろ情報リテラシー教育への対応やネットワークサーバ的機能の充実 あるいは図書館との有機的連携による電子図書館の基幹としての役割が期待さ れる側面が多い。従来型のFORTRAN による高速計算の支援のみで十分であった センター業務が大きく変化していることは事実であるが、特に理工系学生を多 くかかえる大学においては、FORTRAN にこだわることはなくとも、基本的な数 値計算機能を提供し続けることも重要な業務であることに変わりはない。特に、 この様な基本的な計算に対するアドバイザ的役割は大きい。このような役割の 中核は伝統的な「プログラム相談」的業務である。それも、単に窓口を設けて プログラム相談員を配置するような手法ではなく、自動化とネットワーク化を 基本とした手法の確立である。
　このような方向の最初の試みは、国内でもいくつかの開発の動きはあったよう なプログラムの自動選択機能を有するシステムの開発と利用者への提供である。 学内センターでは利用者層の変質から、このようなシステムの開発の動きは最 近では盛んではない。また、外国で開発された数値計算パッケージには、アル ゴリズムの自動選択機能の一部を組み込んだものも出現し[4,6]、 それらが研究者の個人所有によるワークステーション等で稼働するため、学内 センターでの開発の動きは十分には進んでいない。しかし、非常に幅広い分野 に置ける計算の要求と問題の多様化が進む中で、 「問題の性質を把握しなければ安定した結果が得れない」 ような計算が出現している。その多くは数値計算に出現する。数値計算では常 にある種の近似解を求めるため、浮動小数計算による誤差が重要になったり、 計算精度との関連でおかしな結果を生んだりすることは一般に知られている。 これらは広く悪条件問題と呼ばれている。悪条件問題は大半の数値解析の教科 書で扱われているので(例えば [5])、その詳細を述べないが、本論で は「硬い」(スティッフ:stiff) 常微分方程式を例にとって、その振舞について 実験的に簡単に述べる。このような問題に対しても単に数値計算プログラムを 提示するのみでは問題が生じる。硬い常微分方程式の場合に一般的な数値解法 を用いると、与えられた方程式の性質によって、非常に小さな刻み幅で数値解 を求めない限り、正確な解の近似値を求められない場合がある。当然、大量の 計算時間を消費し、かつ計算回数の増大とともに結果に含まれる数値誤差も無 視できなくなる。しかし、この様な場合にも硬い微分方程式に適する数値解法 を用いると、上の困難を回避しつつ満足良く結果を得ることが出来る。このよ うに問題に適合した最適の解法(アルゴリズム)を自動的に選択するシステムを アルゴリズム選択システムという。計算センターにこの様な システムが構築され、学内外から自由にネットワークを通じて利用することが 可能になれば、多くの利用者の便をはかり、かつ新しい学内センターの方向を 示すことも出来よう。
　アルゴリズム選択システムを構築するための研究としては、上でも少し述べた が、数値計算アルゴリズムを木構造のデータベース化したGAMS[2]が 知られていた。しかし、近年、数値計算ライブラリ中の多数のアルゴリズムの 利用の便を図る目的で、特に数値計算アルゴリズムが持つ引数の数や型に注意 を払うことなく検索・実行するためにユーザインターフェースを改良する試み が提案されている。数値計算ライブラリとしてNAG を考え、引数に対する配慮 を数式処理システムAXIOM での入力のようにして利用の便の向上を図ったエキ スパートシステムANNAの提案[3]や、楕円型偏微分方程式に対しての 引数選択を容易にしたPYTHIA[8]が考えられたりしている。特徴とし て、旧来からのアルゴリズム選択システムと異なり、いずれもが知識ベースの 処理に何らかの意味で数式処理システムを使用している点がある。しかし、数 式処理システムの利用は単に数式の入出力部分にとどまっており、上で議論し た数式の特徴を抽出して最適のアルゴリズムを選択するような使用は行われて いない。後者は ELLPACK[7]の一つの発展的形態と見ることが出来る。 また、数値計算で解きにくい問題の代表例の一つである「硬い(stiff)」常微分 方程式に対してはパソコンで稼働するエキスパートシステムである PLOD [1]等 が開発されているが、ここではいくつかの数値アルゴリズムに 対して関数評価の回数を知らせる程度の働きしかしていない。
　そこで本論文では、数値計算ライブラリ中のアルゴリズムを用いて数値計算す る場合に、入力した数式の悪条件性の判定等に数式処理を利用することによっ て、複雑な問題にも安定な数値結果を得ることが可能なシステムの構築を考え る。ここでは、数値計算ライブラリとして富士通で開発され、大型計算機を中 心として広く利用されているSSL-II を、数式処理システムとして Maple を、またデータベースとしてオブジェクト・リレーショナル型の Illustra を 用いた。ユーザインターフェースの向上を図るため、上の諸システムをNetscape Navigator等のWebブラウザから自由に操作できるようにした。以下では、主に 硬い常微分方程式に関してシステムの構築の意味と結果について述べる。

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

　アルゴリズム選択の例として、一階連立常微分方程式の数値解を得る場合を考 える。このための、アルゴリズムは多様だが、解に対する要求精度や常微分方程式が 「 硬い」か否かで、対応するアルゴリズムを慎重に選択する必要がある。硬い 連立常微分方程式については数値解析の教科書等で詳し く述べられているが、以下本論の一貫性のために、簡単に例を挙げながらその 性質をみる。次の連立常微分方程式を考える。


ベクトル記法を用いれば



となり、行列 A の固有値は、



となる。よって、(1)の解はとすると



となる。ここでとすると、上述の式は近似的に



と表される。μの値が 106と極端に大きいため、x(t) の第2項は、t=0のごく近傍でのみ意味を持つにすぎず、 tの値が0から少しでも離れれば 次のようにみなし得る。



この方程式を良く知られたオイラー法によって数値的に解く。数値解は



を満たす。もとの微分方程式の真の解は、t → ∞ で x(t) → 0,y(t) →0 となるから、数値解も当然、 n → ∞ で 0に収束する。 そのためには(3)の右辺の行列



の固有値の絶対値がいずれも 1 以下でなければならない。この条件から 刻み幅 hに関し



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



の右辺のヤコビ行列



の固有値を とすると



を満たせばその方程式はスティッフであるといい、 (4)の左辺をスティッフ率(stiff ratio)という。 (1)の連立常微分方程式を、スティッフであるか否かを知らずに、 適当な刻み幅 h によって、ルンゲ-クッタ-ギル法(RKG) で解いた場合と、硬い 連立常微分方程式に適したギア法(ODGE)で解いた場合の結果を Table１に示す。

Table 1: 硬い常微分方程式の数値解と真の解の比較


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

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

3.1 アルゴリズム選択システムの形態

　すでに上でも述べたが、アルゴリズム選択システムには基本的に次の方法がある。
  1. ユーザ支援システムとして、アルゴリズム名を出力し、利用はユーザの 知識に委ねる。場合によってはアルゴリズムの引数や性質等の解説を付ける。
  2. 数値計算中のアルゴリズムの引数の数や型等をユーザが意識しなくても 良いようにする。アルゴリズム名だけでなく、引数情報などをデータベースに 格納し、これを知識ベース的に活用するある種のエキスパートシステム。
  3. エキスパートシステムをさらに進め、アルゴリズムの特性を知り、入力 した問題に最適なアルゴリズムを自動的に選択する。
第１のものは各種の大規模な数値計算ライブラリをユーザに開放している計算セ ンターで開発されていたが、一般にはシステム依存性が強かった。汎用化を目 指しネットワークを経由して利用可能にしたこの種のシステムとしては GAMS [2]が著名である。また、第２のものとしては楕円型偏微分方程 式の数値解法に対して開発されたELLPACK[7]や、その発展形である PYTHIA[8]や、NAG ライブラリ[6] との結合をはかった ANNA[3]等がある。本研究での意図は、後者をさらに発展させ悪条 件問題等の数値的に 解きにくい問題に対して、単にアルゴリズム名を羅列するのみでなく、最適な 数値解法を自動的に選択し、その実行までもを行うシステムの開発にある。さ らに、初心者でも利用可能なように簡単な入力でアルゴリズム選択が可能なよ うに心がけた。このためユーザーインターフェースの向上を目指してNetscape NavigatorなどのWebブラウザを用いてのシステムの利用を可能とした。これを 前節の硬い常微分方程式に関して述べる。硬い微分方程式を安定に解くために は、以下の手続きが必要になる。
  1. 微分方程式の入力（Webブラウザを用いる）
  2. スティッフ率の計算（ヤコビ行列の計算等を記号的に計算する）
  3. スティッフ率がある値より大なら、硬い常微分方程式に適するギア法を選択
  4. スティッフ率が大きくない場合は係数行列の形状が特殊な場合は対応する解法を選択
  5. 上記以外の場合は要求精度によって、ルンゲクッタ法その他を選択
  6. 初期値等のパラメータをメニュー的に入力し計算実行
  7. 結果の出力
ここで、数値計算ライブラリの情報はオブジェクトリレーショナル型データベ ース Illustra に格納され、記号的にスティッフ率を求める部分は数式処理シ ステム Maple によっている。

3.2 数式処理システムの利用

　記号的にスティッフ率を求める必要性は、今取り扱っている問題では にある。係数部分の取り出しやヤコビ行列の計算を行う場合は、各々の操作を 数式処理システム Mapleで行うため、Maple で読み込み可能な形式のファイル を作成したり、Maple からの出力を数値計算に引き渡すためのファイルを用い る必要がある。特に、アルゴリズム選択後に入力常微分方程式の実行を行うた めには、入力数式や初期値その他の情報を持つファイルを作成保持する必要が ある。SSL-II はFORTRAN プログラムの集合であるので、このファイルはFORTRAN 形式で書かれていて、選択した最適アルゴリズムの正しい位置に組み込まれな ければならない。したがって、実行ファイルには、アルゴリズム選択システム で選択した最適アルゴリズムと入力数式及び初期値等の関連するデータが含ま れることになる。


Fig.1 システム構成


4. システムの構成

　Fig.1 に作成したシステムの構成を簡単に示した。点線の左側はユーザの マシン（クライアント）、右側はサーバマシン（ホスト） のシステムである。ユーザは Netscape Navigator等のWebブラウザを起動しサーバマシン上のIllustra データベースにアクセスしアルゴリズム検索を行う。 データベースには、入力用の メニュー作成を行うHTML形式の言語とTable ２の形のアルゴリズム データ(分類、名称、特徴他)が格納されている。

Table 2: SSL-IIのアルゴリズムデータ(線形計算と微分方程式の一部)


5. システムの動作

　アルゴリズム選択システムの具体的な動作例を示す。システムの動作環境は Windows95 上の Webサーバ、WindowsNT4.0 上のデータベースシステム Illustra を中核とし、UNIX環境下の数式処理システム Maple と結合する。 これらの環境や各種システムを変化させても、本論で構築しているアルゴリ ズム選択システムは大きな変更なく動作可能である。

5.1 木構造を用いたパッケージ別、計算分野別の検索

　パッケージ別に数学の問題に対して木構造化された分類を定義しデータベース に格納する。検索可能なパッケージとしてここではSSL-IIを考え、 これをFig.2に示す。次に、パッケージ選択後、 Fig.3のように、最も広い問題の種類（大分類）を与える。このようにして、 目的とするアルゴリズムの種類に至るまで順次検索を行っていく。


Fig.2　第１メニュー　

Fig.3　第２メニュー


5.2 連立一階常微分方程式のスティッフ率の演算

　常微分方程式の数値解を安定に求めるための最適アルゴリズムの選択 に重要なスティッフ率の演算を行う。 2章で述べた硬い常微分方程式の場合を例として システムの動作を示す。

連立一階常微分方程式の入力

　木構造的な検索によりSSL-IIの常微分方程式の入力画面を呼 び入力を行う(Fig.4)。

スティッフ率を求める


　入力された問題をMapleで使える形に変換し、その ヤコビ行列を求め、スティッフ率を求める。例として入力した常 微分方程式のスティッフ率は 4000002 と非常に大きいため、スティッ フな常微分方程式に適したアルゴリズムODGEを選択する(Fig.5)。


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

Fig.5　アルゴリズム表示


5.3 連立一階常微分方程式の数値解の計算

　実際にSSL-IIを用いて以下の順に一階連立常微分方程式を数値的に計算する。


Fig.7　SSL-IIの実行


6. 結論

　本論では、情報時代における学内(総合)情報処理センターの新しい方向性として、 アルゴリズム選択システムの開発について言及し、数式処理の機能を利用した 数値計算ライブラリ中のアルゴリズム選択を行い、かつその実行までもを行う システムを作成した。現在開発できている部分の概要は次のようにまとめるこ とが出来る。
  1. 数式として入力された常微分方程式の特徴抽出に数式処理システム Maple を活用し、アルゴリズム選択を行う。
  2. ユーザインターフェースの向上を目指し、Netscape Navigatorなどの Webブラウザでのシステムの利用を可能とした。このことにより、ネットワー クを通じて、ユーザの場所、計算機の種類にとらわれない利用を可能となった。
  3. 膨大なアルゴリズムの情報や検索システムを格納するため、オブジェク トリレーショナルデータベースシステム Illustra を活用した。
  4. アルゴリズム名の選択のみでなく、実際の数値計算を行い結果を得るこ とを可能とした。
　本論では主に硬い常微分方程式のアルゴリズム選択を述べ、スティッフ率を数 式処理で求めることによる入力数式の特徴抽出を考えた。同様のことは定積分 において関数の振る舞いの激しさを抽出して利用する積分公式を選択する等の 問題への拡張が容易である。また、本論では数式処理システムとして既存の商 用システムである Maple を、数値計算ライブラリとして SSL-II を、データ ベースシステムとして Illustra を用いたが、これらを他のシステムに置き換 えることは困難ではない。 なお、このようにして科学計算ライブラリから問題に適合したアルゴリズムを 選択する方法を実際に活用する場合には、いくつかの注意が必要である。例え ば、微分方程式を解く場合に、その係数を変化させ一連の計算を必要とする場 合がある。この様な場合には、個別にユーザインターフェースを通じて問題の 入力を繰り返すのは手間の増大を招くのみである。このような連続計算に対し てシステムを拡充することは必要である。このような方向は査読者の示唆によ る。この点を感謝する。
　この様なシステムの一層の充実を図るためには、以下の事項を早急に実現する 必要がある。
  1. 最近の関連する論文[3,8] に見られるようなアルゴリズム 選択システムの知識ベース化により、引数の数や型を意識せずに数値計算ライ ブラリを使用できるシステムの構成。
  2. 数値計算ライブラリだけでなく、同様のシステムを統計計算ライブラリ の使用に拡張し、多くのパッケージ間の引数や命令の差異を意識せずに 計算可能な知的システムの作成。
　今後、ネットワーク時代が進展することは明らかだが、今日までの文明社会を 構築して来た伝統的な工学分野や人類の英知を探るための理学分野の研究開発 の重要性が低くなることはないであろう。その場合の基本技術としての「計算」 を支える支援システムの開発も現在より一層重要になろう。特に、取り扱う問 題が巨大化、複雑化するとともに、本論で触れたような悪条件問題も多く含ま れることになるであろう。問題の中にはその意味で本論に述べたような利用者 支援のアルゴリズム選択システムを充実させ、大規模問題にも適合できるよう なシステム開発を行うことは、情報工学の研究促進の面と、学内センターの新 しい方向性の指針の一つとしても極めて重要であろうと思われる。

　なお、本論の一部は平成9年3月数式処理研究集会(開催地：愛媛大学)で発表 され、同研究集会の会議報告として本年10月城西大学から出版予定であるこ とを付記する。

参考文献

[1]
D.Barnett and D.Kahaner,Experience with an Expert System for ODE, in Intelligent Mathematical Software System Eds. E.N.Houstis et al., Elsevier Science Pub., pp.5-13, 1990.

[2]
R.F.Boisvert and J.L.Springman,Internal Structure of the Guide to Available Mathematical Software,NISTIR 89-4042, Gaitersburg, MD 20899, 1993.

[3]
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.

[4]
IMSL, Math/Library, STAT/Library, SFUN/Library User's Manual, IMSL, Houston, 1987.

[5]
三井 斌友、微分方程式の数値解法 I、岩波書店、1993.

[6]
Numerical Algorithm Group, The NAG Fortran Library Manual -Mark 12, NAG Ltd., Oxford, 1987.

[7]
J.R.Rice and R.F.Boisvert,Solving Elliptic Problems Using ELLPACK, Sprinber-Verlag, 1985.

[8]
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.



（1997年8月4日受付；1997年8月15日採録）
(Received 4 August 1997 ; accepted 15 August 1997)


Contents Back Next