(17) 階層連立1次方程式のための効率的解消系の開発

研究テーマ、研究代表者：

（１）研究テーマ

階層連立1次方程式のための効率的解消系の開発

（２）研究代表者（氏名、所属、役職）

松岡　聡

東京工業大学大学院 情報理工学研究科 数理・計算科学専攻 助教授

記述項目：

（１）研究進捗状況

階層連立1次方程式(hierarchical linear system, HLS)を 解く制約解消系を研究・開発している．HLSとは1次方程式から なる制約階層に関する，我々が提案した新しい定式化である． HLSの理論および解消アルゴリズムは，線形代数と線形計算を 基礎とし，従来のグラフ理論を基礎とする局所伝播法と異なり， 1次方程式を適切に扱うことができるという特徴を持つ．
我々はこれまでに，この特徴を活かして，信頼性が高く効率的 な制約解消系HiRiseを設計し，その基礎部分を実装した．
また，HiRise解消系を利用して，GUIを備えたサンプルアプリ ケーションを作成した．

（２）現在までの主な成果

HiRise解消系の設計において，外部的には制約階層を扱う解消 系として利用できるように，レベルによる制約のグループ分け， stay制約およびedit制約の提供，プランニングと実行の2段階 解消などを行った．HiRise解消系の実装では，LU分解による アルゴリズムを採用することにより，制約解消の実行段階の効 率化を図った．さらにWindows 95/NT上で動作する，GUIを備 えた簡単なサンプルアプリケーションを作成し，現在のHiRise 解消系が一定の性能を実現していることを確認した．

（３）今後の研究概要

まず，HiRise解消系本体のさらなる性能向上を試みる．現在 採用しているLU分解アルゴリズムは，Crout法を応用したもの である．しかし，他のアルゴリズムの方が，GUIなどへの応用 で見られる制約系の疎性に有効である可能性があり，性能向上 の余地があると考えている．また，HiRise解消系のアプリケー ションプログラミングインターフェース(API)提供部の充実を 図る．現在，提供しているのは必要最小限のプリミティブのみ である．今後，1次方程式制約の記述を容易にするパーザーの 作成や，C++のコンストラクター/デストラクターなどの言語機 能を活用したAPIの設計および実装を予定している．

（４）今年度目標成果ソフトウェアイメージ

成果ソフトウェアは，HiRise制約解消系と，そのサンプルアプ リケーションから構成される．HiRiseは1次方程式からなる制約 階層の解消系であり，stay/edit制約の提供や，プランニング/ 実行の2段階解消などの実現により，GUIの開発に適している． 既存の制約階層解消系と異なり，HiRiseは内部で健全かつ完全 な数値的アルゴリズムを実行しているという点で特徴的である． このため，HiRiseを利用することにより，プログラマーはより 信頼性の高いシステムやアプリケーションを開発できる．また HiRiseは，既存の制約階層解消系に比べて充実したAPIを提供 するため，アプリケーションのプログラミングがより容易になる．