HiRise アルゴリズム

本節では，HiRise 制約解消系のために設計した制約解消アルゴリズムについ て述べる．

GUI のための制約階層解消系を作成するには、既存の解消系との互換性のために、 以下のような点を考慮する必要がある。

• 制約階層は複数個の レベルと呼ばれる集合からなる。同一レベル に存在する制約は同じ 強さという優先度を持っている。例えば、常に満 たすべき制約のレベル required を最上位とし、その下に strong， medium， weakのような段階的なレベルが存在する。
• 制約には1次方程式以外に stay と edit がある。stay とは変 数の値を一定にする制約で、GUI では、あるオブジェクトの位置を固定しておく場合 などに用いられる。一方、edit とは変数の値を繰り返し更新するための制約で、 あるオブジェクトをマウスでドラッグする場合などに用いられる 。
• 制約解消を プランニングと 実行の2段階に分割する。edit 制約を用いることにより、制約の集合自体を変化することなく、特定の変数の 値を更新することが可能である。上で述べたように edit による変数の更新は繰 り返されるため、必要な部分だけ再計算を行うことが高速化のために不可欠で ある。このために、制約解消を2段階に分け、プランニング段階で制約階層の 「解き方」を求め、実行段階でその解き方に基づいて実際に変数の値を計算する。

前節で述べたように、制約階層を HLS に変換して、元の制約階層の locally-error-better 解を求めることが可能である。また、stay 制約と edit 制約は 1 次方程式として表現できる。従って、HLS を用いることにより、 最初の 2 点は対処できる。

プランニング段階と実行段階の分割は、係数行列を LU 分解することにより実現 している。edit 制約による変数の値の更新は、拡大係数行列 ( A c ) の定数項部分 c のみに現れるため、変数の値を更新しても係数行列 A の LU 分解をし直す必要がないためである。従って、HiRise では、プランニング段階 で拡大係数行列の作成とLU分解を行い、実行段階で変数の値の計算を行う。

さらに、プランニング段階の効率化のため、制約の追加・削除の際に インクリメンタルな制約解消を行う。 このためには、以下の2点を考慮する必要がある。

• 実際に解くべき制約を効率的に決定する。制約の追加・削除により、 解くべき制約の集合が変化する。これを効率的に管理することが、プランニング の高速化に不可欠である。
• LU 分解の修正を高速に行う。解くべき制約の集合の変化に応じて、LU 分解を更新する必要が生じる。この際、LU 分解の部分的な修正を実現することが 効率化に重要である。

解くべき制約の管理には、 DeltaBlue [4]で提案された walkabout strength を応用した。これは、多くの局所伝播法アルゴリズムで 効率化の核となっていた技術である。HiRise は walkabout strength を 採用した最初の数値的アルゴリズムであり、これは局所伝播法のアイデアが数 値的アルゴリズムでも有効であることを示したものといえる。

一方、LU 分解の修正には，線形計画法のために考案された Forrest と Tomlin の 方法[3]を応用した。