有向マトロイドの 実現不可能性を判定する手法

Presentation on theme: "有向マトロイドの 実現不可能性を判定する手法"— Presentation transcript:

1 有向マトロイドの 実現不可能性を判定する手法
超ロバスト計算原理プロジェクトRA 中山 裕貴 2005/10/19

2 今回の発表の流れ 背景 有向マトロイドとは 有向マトロイドの 実現不可能性判定問題 実現不可能性の十分条件 計算機実験による結果
代数的な立場より： 双二次最終多項式 幾何的な立場より： 非ユークリッド性 計算機実験による結果 幾何的構造の組合せ的抽象化 幾何的モデル 組合せ的モデル 計算は困難 ギャップ Grassmann-Plückerの多項式 イントロの部分：　究極目標は、代数的問題・幾何的問題の双方に有効なロバストなアルゴリズムの提案 代数的な実現例としてはasirなど、幾何的な例としては杉原先生の提案にあるように…両者を統合してロバストなアルゴリズムが 提案できるようなフレームワークの提案 そのために、有効的ロイドの実現性判定問題がよい例となっている： 擬長平面配置と超平面配置、少しずれただけで組み合わせ的（有効的ロイドとしては）には異なるものとなる。 片方は超平面にはできない。その違いを代数や幾何的な世界のアルゴリズムでも峻別できるようにはどうするか？→今回の提案 あと参考文献をきっちりと。 サーキットの小売は別に要らない、回路とーぷの小売の前にグラス万の式を説明する。 あとは森山さんのアドバイスより 線形計画問題

3 問題の背景 計算代数、計算幾何 それぞれの分野について、ロバスト性を持つプログラムの実装がされている 計算代数 計算幾何 目標：
（例：計算代数ソフトAsir [高山、野呂ら]） ・ 有理数の多倍長表現 ・ 多変数多項式の表現の工夫（再帰表現・分散表現） ・ 無理数（　 など）について、浮動小数を用いず 　「　　　　　　の正の解」という情報で保持する etc… アイデアとしては共通点も 多いが、双方はまだ独立して 考えられている 計算幾何 （例： 幾何計算ソフトウェア [杉原]） ・ 座標の有理数表現（多倍長表現で正確性を保持） ・ 計算中、対象の位相的関係を正しく保存 etc… 目標： 両者を統合して扱う フレームワークの提案

4 組合せ構造とは 両者を統合する足がかりとして、有向マトロイドによる組合せ構造に着目 組合せ構造
幾何的対象（ここでは曲線とする）の集合があるとする。 各曲線間の位置関係が保たれるならば、曲線を変形したものも 相互に同じとみなす ex. と は同じ組合せ構造を持つ わずかな変形でも、それによって各曲線間の位置関係が崩れる場合、 異なる組合せ構造を持つ ex. と は異なる組合せ構造を持つ

5 今回扱う問題： 有向マトロイドの実現可能性判定問題
問題（幾何的解釈）： ある組合せ構造が（有向マトロイドとして）与えられたとき、組合せ構造を保存したまま、すべての曲線（擬超平面）をstretchして直線（超平面）に変形できるか？ 問題（代数的解釈） 組合せ構造を連立代数不等式として表したとき、その 不等式系が実行可能解を持つか？ 　 有向マトロイドの実現可能性判定問題を考えることにより、計算幾何・計算代数の双方に有効な超ロバスト アルゴリズムの実現が期待される

6 今回の発表の流れ 背景 有向マトロイドとは 有向マトロイドの 実現不可能性判定問題 実現不可能性の十分条件 計算機実験による結果
代数的な立場より： 双二次最終多項式 幾何的な立場より： 非ユークリッド性 計算機実験による結果 幾何的構造の組合せ的抽象化 幾何的モデル 組合せ的モデル 計算は困難 ギャップ Grassmann-Plückerの多項式 イントロの部分：　究極目標は、代数的問題・幾何的問題の双方に有効なロバストなアルゴリズムの提案 代数的な実現例としてはasirなど、幾何的な例としては杉原先生の提案にあるように…両者を統合してロバストなアルゴリズムが 提案できるようなフレームワークの提案 そのために、有効的ロイドの実現性判定問題がよい例となっている： 擬長平面配置と超平面配置、少しずれただけで組み合わせ的（有効的ロイドとしては）には異なるものとなる。 片方は超平面にはできない。その違いを代数や幾何的な世界のアルゴリズムでも峻別できるようにはどうするか？→今回の提案 あと参考文献をきっちりと。 サーキットの小売は別に要らない、回路とーぷの小売の前にグラス万の式を説明する。 あとは森山さんのアドバイスより 線形計画問題

7 有向マトロイドの カイロトープ による表現 幾何的構造の符号への抽象化
有向マトロイドの カイロトープ　による表現 幾何的構造の符号への抽象化 　　中にn本のベクトルを配置し、その中の任意の r本のベクトルについて、符号を以下で定める r: ランク x y z v1 v2 v3 v4 v5 v6 ex. では すべてのχの値の集合により 有向マトロイドは定義される

8 ３項Grassmann-Plücker多項式
任意の　　　　　　　　　　　　　　　　　　　　について、

9 有向マトロイドの公理 （カイロトープの公理）
有向マトロイドが定義する組合せモデルは、 幾何的な配置よりも集合として広い カイロトープの公理： (B0) (B1) は交代性をみたす、つまり (B2) ３項Grassmann-Plücker多項式の符号への抽象化： 以上を満たすχの集合すべてが有向マトロイドをなす

10 擬超平面配置と超平面配置 擬超平面： 超平面を曲げたもの（homeomorphicな変形） 擬超平面配置 超平面配置 有向マトロイド全体
擬超平面を伸ばして 超平面にする 擬超平面配置 （図：　　中の擬超平面と球面　　の交差） 超平面配置 （図：　　中の超平面と球面　　の交差） equiv equiv 有向マトロイド全体 幾何的表現全体 ２つの集合には差があるか？

11 今回の発表の流れ 背景 有向マトロイドとは 有向マトロイドの 実現不可能性判定問題 実現不可能性の十分条件 計算機実験による結果
代数的な立場より： 双二次最終多項式 幾何的な立場より： 非ユークリッド性 計算機実験による結果 幾何的構造の組合せ的抽象化 幾何的モデル 組合せ的モデル 計算は困難 ギャップ Grassmann-Plückerの多項式 イントロの部分：　究極目標は、代数的問題・幾何的問題の双方に有効なロバストなアルゴリズムの提案 代数的な実現例としてはasirなど、幾何的な例としては杉原先生の提案にあるように…両者を統合してロバストなアルゴリズムが 提案できるようなフレームワークの提案 そのために、有効的ロイドの実現性判定問題がよい例となっている： 擬長平面配置と超平面配置、少しずれただけで組み合わせ的（有効的ロイドとしては）には異なるものとなる。 片方は超平面にはできない。その違いを代数や幾何的な世界のアルゴリズムでも峻別できるようにはどうするか？→今回の提案 あと参考文献をきっちりと。 サーキットの小売は別に要らない、回路とーぷの小売の前にグラス万の式を説明する。 あとは森山さんのアドバイスより 線形計画問題

12 有向マトロイドの 実現可能性判定問題 ある有向マトロイドには、幾何的配置が 存在しない場合もある（逆は必ず存在）
与えられた有向マトロイドに対し、それが幾何的な配置（ベクトル、超平面etc…)として与えられるか判定する問題 ＝実現可能性判定問題 （有向マトロイドによる）組合せ的モデル （行列などによる）幾何的モデル

13 実現不可能な有向マトロイドの例 Pappusの配置 (r = 3, n = 9) （超平面配置を上から見た図、円は三次元球の表面）
擬超平面を超平面に（中央の線を直線に）しようとすると、必ず中央の点を通らなければならない （左図の一部） ＝ 実現不可能

14 実現可能性の判定法： 単純な方法 有向マトロイドはカイロトープの形で与えられているとする 行列を と置き、連立方程式
が解を持つとき、またそのときに限り実現可能 計算が複雑（実はNP-hard [Mnev 1988] 誤差を含みうる(Robustでない）

15 実現可能性判定問題の代数的解釈 以下の２つは同値[Sturmfels 1987]
与えられた有向マトロイドが、　　上のベクトルの集合として表せる 同値 多変数関数　　　　　　　　　　　　　　　がある有理数に対して零点を持つ 実現可能性判定の良いアルゴリズムが見つかれば、 様々な代数的問題についても応用ができそう（だが、難しそう） 実現不可能なものの一部しか見つけられない代わりに、 誤差を含まずに計算できるアルゴリズムの提案

16 今回の発表の流れ 背景 有向マトロイドとは 有向マトロイドの 実現不可能性判定問題 実現不可能性の十分条件 計算機実験による結果
代数的な立場より： 双二次最終多項式 幾何的な立場より： 非ユークリッド性 計算機実験による結果 幾何的構造の組合せ的抽象化 幾何的モデル 組合せ的モデル 計算は困難 ギャップ Grassmann-Plückerの多項式 イントロの部分：　究極目標は、代数的問題・幾何的問題の双方に有効なロバストなアルゴリズムの提案 代数的な実現例としてはasirなど、幾何的な例としては杉原先生の提案にあるように…両者を統合してロバストなアルゴリズムが 提案できるようなフレームワークの提案 そのために、有効的ロイドの実現性判定問題がよい例となっている： 擬長平面配置と超平面配置、少しずれただけで組み合わせ的（有効的ロイドとしては）には異なるものとなる。 片方は超平面にはできない。その違いを代数や幾何的な世界のアルゴリズムでも峻別できるようにはどうするか？→今回の提案 あと参考文献をきっちりと。 サーキットの小売は別に要らない、回路とーぷの小売の前にグラス万の式を説明する。 あとは森山さんのアドバイスより 線形計画問題 幾何的な立場からの十分条件として 非HK*性もあるが、今回は説明しない

17 どのようにして有向マトロイドの 実現可能性を効率よく判定するか
実現不可能性の十分条件となる性質を用いる （実現不可能なものの一部でもいいので、 ある条件を満たすものを正確に判定したい） 代数的性質： 双二次最終多項式 ３項Grassmann-Plückerの多項式を利用 線形方程式の求解に帰着 幾何的性質： 非ユークリッド性 通常の線形計画問題では決して起こらない、 非退化なサイクルを見つける

18 実現不可能性の十分条件： 双二次最終多項式
用いるアイデア：３項Grassmann-Plücker多項式 任意のベクトル　　　　　　　　　　　　　　　　　　　　について、 が成立 ブラケット項　　　　　　で表す、また 有向マトロイドが実現可能ならば、ベクトル配置が存在するはず 対偶 ベクトル配置が無いことが示せれば、有向マトロイドは実現不可能

19 ３項Grassmann-Plücker多項式の抽象化
行列式を符号へ抽象化 任意のインデックス　　　　　　　　　　　　　　　　　について、 が成立 さらに、　　　　　　　　　を適切にpermutationすることによって ３つ全てが同時に0 or 1 が成立 以後、λは適切にpermutationされているものとする （normalizedという）

20 有向マトロイドを入力とした 連立不等式の生成
得られている情報：各カイロトープの符号のみ normalizedな3項Grassmann-Plücker多項式 について (1) ３つの項の符号がすべて+1のとき ２つの不等式 が成立 (2) 左辺の２項のどちらかの符号が0のとき 等式 が成立 全てのインデックスの組合せについて、(1)(2)どちらかにより 等式、不等式を生成する ⇒ 連立不等式

21 有向マトロイドを入力とした 連立線形不等式の生成
生成された連立不等式 → 連立線形不等式へ 得られた連立線形不等式を、LP-solverを用いて 実行可能であるか判定し、解が無ければ その有向マトロイドは実現不可能 LP-solver: cdd+[Fukuda], lrs[Avis]など。有理数演算を利用して誤差を排除する（Robustなプログラム） 対数をとる 変数とみる

22 実現不可能な有向マトロイドの例： (r = 4, n = 8) 上のχより導ける3項Grassmann-Plücker多項式の集合
上４行がカイロトープの引数、下１行がカイロトープの値 上のχより導ける3項Grassmann-Plücker多項式の集合 各ブラケット　　　　　　　について 　　　　　　　　　　　　とソート済み 各ブラケットの値は 正 or ０ ([1234]のみ) + + + + +

23 実現不可能な 有向マトロイドの例（続き） このような場合、双二次最終多項式が存在し、 有向マトロイドは実現不可能
[1234] = 0, それ以外のブラケットは＋ 不等式を生成し、対数をとって線形化 上の線形不等式系の項は全て打ち消しあう ⇒ “0 < 0”、つまり解なし このような場合、双二次最終多項式が存在し、 有向マトロイドは実現不可能

24 どのようにして有向マトロイドの 実現可能性を効率よく判定するか
実現不可能性の十分条件となる性質を用いる 代数的性質： 双二次最終多項式 ３項Grassmann-Plückerの多項式を利用 線形方程式の求解に帰着 幾何的性質： 非ユークリッド性 通常の線形計画問題では決して起こらない、 非退化なサイクルを見つける

25 問題の背景：線形計画問題 ex. 球面が、中心を通る超平面により領域に分割される y x 斉次化 （球面 の上部から見た図） ( f )
(1) (2) (3) ( f ) (4) (5) ( f ) (1) (2) (3) (4,5) 斉次化 (1) (2) (3) (4) (5) (g) ( f ) ( f ) (1) (2) (3) (4,5,g) （球面　　の上部から見た図） 球面が、中心を通る超平面により領域に分割される

26 有向マトロイドの コサーキットC*による表現
x y z v1 v2 v3 v4 v5 v6 ex. 各ベクトルが法線ベクトルとなる超平面で、　　空間を分割 ⇒ 領域が平面に対しどちら側にあるかを符号で表す＝コベクトル コサーキット（極小なコベクトル）の集合　　による有向マトロイドの表現： 上の例では この符号の集合は有向マトロイドを定義する、またχによる定義と同値

27 有向マトロイドの公理 （サーキットの公理）
以下の公理を全て満たす符号の集合のみが有向マトロイドをなす (C0) Y の非零indexの集合 (C1) (C2) Y の負indexの集合 (C3) コサーキットの集合C*もサーキットの公理を満たす

28 有向マトロイド計画問題： 線形計画問題の抽象化
( ) (4) (1) ( f g) ( ) 球面上の領域 ＝ コベクトル 球面上の点 ＝ コサーキット (5) (2) ( f ) (3) 球面の上半分（超平面gに対して正 or ０） にあるコサーキットのみ考える (g) (+++00 ‐+) 有向マトロイド計画問題： ある実行可能なコサーキットC0*を初期解として、 目的関数 f に対して値を改善していき、最適なコサーキットを得る

29 有向マトロイド計画問題 をコベクトルの集合とする アフィン空間： 無限遠点： 実行可能領域： 目的関数が増加する方向：
(‐+‐0+ +0) 無限遠点： (4) (1) ( f g) ( ) 実行可能領域： (5) (2) 左の例では、12345全てが非負 ( f ) (3) 目的関数が増加する方向： (g) ( ) (+++00 ‐+) 有向マトロイド計画問題は　　　　　　　の三つ組みの形で与えられる コベクトルの集合

30 有向マトロイド計画問題における 単体法アルゴリズム
入力： 有向マトロイド計画問題 出力： 目的関数 f に対して最適なコサーキット Phase I: 実行可能なコサーキット　　　　　　　を一つ見つける、 存在しなければ実行可能解なし→アルゴリズム終了 Phase II: (i) 現在のコサーキットと辺を共有し、かつ増加する方向を見つける (ii) (i)の方向に対して非有界であれば最適解なし→アルゴリズム終了 (iii) 解を改善する方向に向かい、新たなコサーキットを得る (iv) これ以上増加する方向がなければ、最適解を出力してアルゴリズム終了、 　　 そうでなければ(i) に戻る

31 非退化なサイクル 単体法におけるステップ(Cold→Cnew)の分類： degenerate horizontal
{Cold,Cnew に共通する非零要素} Ｕ {f, g}が従属 strictly increasing 有向辺Cold→Cnew は目的関数が増加する方向、かつ degenerateではない 非退化なサイクル： ステップの列　　　　　　　　　　　　　　　　　について、　　　　　　　かつ 各ステップは{degenerate, horizontal, strictly increasing}のどれか、 さらに少なくとも１つのステップはstrictly increasing C0 C3 C1 =C2

32 非ユークリッド性を用いた 有向マトロイドの実現不可能性の判定
通常の線形計画問題は、決して非退化な サイクルをもたない 有向マトロイドが非退化なサイクルを持つならば、その有向マトロイドは実現不可能 このような有向マトロイドを 非ユークリッドな有向マトロイドとよぶ

33 今回の発表の流れ 背景 有向マトロイドとは 有向マトロイドの 実現不可能性判定問題 実現不可能性の十分条件 計算機実験による結果
代数的な立場より： 双二次最終多項式 幾何的な立場より： 非ユークリッド性 計算機実験による結果 幾何的構造の組合せ的抽象化 幾何的モデル 組合せ的モデル 計算は困難 ギャップ Grassmann-Plückerの多項式 イントロの部分：　究極目標は、代数的問題・幾何的問題の双方に有効なロバストなアルゴリズムの提案 代数的な実現例としてはasirなど、幾何的な例としては杉原先生の提案にあるように…両者を統合してロバストなアルゴリズムが 提案できるようなフレームワークの提案 そのために、有効的ロイドの実現性判定問題がよい例となっている： 擬長平面配置と超平面配置、少しずれただけで組み合わせ的（有効的ロイドとしては）には異なるものとなる。 片方は超平面にはできない。その違いを代数や幾何的な世界のアルゴリズムでも峻別できるようにはどうするか？→今回の提案 あと参考文献をきっちりと。 サーキットの小売は別に要らない、回路とーぷの小売の前にグラス万の式を説明する。 あとは森山さんのアドバイスより 線形計画問題

34 各ランク、要素数(r, n)における 有向マトロイドの個数
2 3 4 5 6 7 8 9 10 r=2 1 r=3 17 143 4890 461053 r=4 12 206 181472 … r=5 25 6029 r=6 50 508321 ... 　　　　ならばすべて ユークリッド性をみたす すべて実現可能 実現不可能な有向マトロイドを含み、かつユークリッド性を 満たさないものが存在する(r, n) = (4, 8)のケースについて、 計算機実験により実現不可能な有向マトロイドを列挙する

35 (r, n) = (4, 8)における「実現不可能な」 有向マトロイドの個数
uniform: χの値が常に 1or -1 #OM(4,8) = Uniform OMs 2628 Non-uniform OMs non-realizable 24 (non-realizable ??) 双二次最終多項式 24 双二次最終多項式 3944 非ユークリッド性 18 非ユークリッド性 3444 非HK*性 18 非HK*性 1364 非シャノン性 1 (非HK性 0) (非HK性 0) non-Euclidean, non-HK(*), non-Shannon: [Fukuda, Moriyama, Okamoto 2004] BFP: [Nakayama, Moriyama, Fukuda, Okamoto 2005]

36 (r, n) = (4, 8)における「実現不可能な」 有向マトロイドの個数
計算機実験の結果より、 有向マトロイドがuniformである場合： 双二次最終多項式で全ての実現不可能なものを列挙 非ユークリッド性によっては列挙できないものもあり uniform, non-uniform両方の場合について 非HK*性を満たす ⇒ 非ユークリッド性を満たす 非ユークリッド性を満たす ⇒ 双二次最終多項式が存在 実現不可能性を示す性質の有用さとして、 双二次最終多項式 ＞ 非ユークリッド性 ＞ 非HK*性 が成り立つことを示唆している 双二次最終多項式 ＞ 非ユークリッド性については、理論的証明が完了 [Richter-Gebert 1993] [Nakayama, Moriyama and Fukuda, in preparation] 証明の方針は定まっておらず、rが大きくなると成り立たないかもしれない

37 まとめ 実現不可能な有向マトロイドを列挙するための性質 性質の間に真の強弱関係が存在することが 計算機実験により示唆された
代数的手法： 双二次最終多項式 幾何的手法： 非ユークリッド性 の紹介 性質の間に真の強弱関係が存在することが 計算機実験により示唆された

38 参考文献 A.Bjorner, M.Las Vergnas, B.Sturmfels, N.White and G.Ziegler: Oriented Matroids, Encyclopedia of Mathematics (1993) K.Fukuda: Oriented Matroid Programming, Ph.D. Thesis (1982) K.Fukuda, S.Moriyama and Y.Okamoto: Non-LP orientations, nonlinear shellings and non-representable oriented matroids, Technical Group of Computation (2004) K.Fukuda, H.Nakayama and S.Moriyama: Every non-Euclidean oriented matroid admits a biquadratic final polynomial, in preparation H.Nakayama, S.Moriyama, K.Fukuda and Y.Okamoto: Comparing the strength of the non-realizability certificates for oriented matroids, in proc. of 4th Japanese-Hungarian Symposium (2005) J.Richter-Gebert: Euclideanness and final polynomials in oriented matroid theory, Combinatorica (1993)