2020-02-18

パラパラめくる『Polyhedral and Algebraic Methods in Computational Geometry』

ぱらぱらめくるシリーズ多面体代数多様体幾何計算幾何射影幾何ボロノイ図ドロネー三角化グレブナー基底プリュッカー座標

Polyhedral and Algebraic Methods in Computational Geometry【電子書籍】[ Michael Joswig ]

価格: 6767 円
楽天で詳細を見る

目次
- １イントロと概観
- Part I Linear Computational Geometry
  - 2 Geometric Fundamentals; 射影空間、射影幾何
  - 3 Polytopes and Polyhedra; (超)多面体
  - 4 Linear Programming
  - 5 Computation of Convex Hull
  - 6 Voronoi Diagrams
  - 7 Delone Triangulations
- Part II Non-linear Computational Geometry
  - 8 Algebraic and Geometric Foundations
  - 9 Grobner Bases and Buchberger's Algorithm
  - 10 Solving Systems of Polynomial Equations Using Grobner Bases
- Part III Applications
  - 11 Reconstruction of Curves
  - 12 Plucker Coordinates and Lines in Space
  - 13 Applications of Non-linear Computational Geometry
2 Geometric Fundamentals
- 射影幾何を使うのは、平行線ペアにも交点を持たせる枠組みを導入し、平行かそうでないかというような例外扱いを省略できるという利点があるようだ
- さらに、線形計算ですべて片が付くというのも魅力
- 射影空間の「点」は原点を通る直線 $(x_0:x_1:...:x_n)^T$ に相当するが、射影空間での超平面は、複数の係数の同次座標的表現 $u_0:u_1:...:u_n$ になるが、射影空間の「点」は、この超平面上では、[tex:=0]を満足するような $x$ に「ある」とみなせる
- 直線・平面・超平面は線形等式、向きを考えると線形不等式、内部・外部の区別も不等式
3 Polytopes and Polyhedra
- 凸多面体を扱うことにするらしい
- モーメントカーブというものが、大事な代数幾何的要素らしい
- モーメントカーブというのは、 $(t,t^2,t^3,...)$ という点を結んでできた曲線で、この曲線上の点を頂点とする凸多面体が（必ず？）作れるという意味で、凸多面体を扱うときに出てくるらしい
- 3次元空間にそのようなモーメントカーブを描きつつ、その曲線上に $m > 3$ 個の点を取って、凸包を作らせて図示してみよう

f:id:ryamada:20200218181838p:plain
f:id:ryamada:20200218181848p:plain

- Polytopeを頂点集合とそれが張る凸包と見ることもできるが、(超)平面によって囲まれたものと見ることもできる(V-表現とH-表現と呼び分ける)
- ポセット構造も持つ
- 内部に原点を持っていると(そのような場合をpolarityありと言うそうだ)、双対が取れて、n次元面には、k-n次元面が対応するというような対応構造が取れる
- 組み合わせ幾何的に考えていくと、オイラーの式が $(-1)^k$ を係数として一般型として表れる
- 球面上の乱点からランダム多面体が作れる
- Minkowski sum of a polytopeと言うのがある…要、確認
- SAGEにも入れられる polynajeなるアプリを使うと、いろいろ試せるらしい(モーメントカーブ上に点を持つ、cyclic多面体を作って、その点、線分、面、…の数を出したり、超面と頂点との関係行列を出したりできる(こちら)
4 Linear Programming
- 連立線形不等式が多面体を定めるので、それに基づくアルゴリズムが提唱されている
5 Computation of Convex Hull
- 具体的なアルゴリズム
6 Voronoi Diagrams
- 空間に点集合があれば、空間の任意の点を、最近点にて分割することができて、それがボロノイ分割
- n+1次元空間の開放多面体を射影するとn次元空間のボロノイ分割に対応することが、多面体におけるボロノイ分割の役割らしい
7 Delone Triangulations
- ドロネー三角化はボロノイ図の双対
- したがって、ボロノイ分割を多面体の写像と見たのをドロネー分割にも適用することができる
8 Algebraic and Geometric Foundations
- Non-linear にする
- 多面体を1次線形代数でやっていたのを、高次式にして、代数多様体で考えることでNon-linearにする
9 Grobner Bases and Buchberger's Algorithm
- 高次代数多様体になったので、探解が難しくなるらしく、そこにグレブナー基底の活躍場所が登場するらしい

2013-04-05

ぱらぱらめくる『グレブナー基底とその応用』

ぱらぱらめくるシリーズグレブナー基底代数多項式環

グレブナー基底とその応用 (共立叢書・現代数学の潮流)

作者: 丸山正樹
出版社/メーカー: 共立出版
発売日: 2002/10
メディア: 単行本
クリック: 4回
この商品を含むブログを見る

はしがき
- グレブナー基底は多項式環とそのイデアルについての多くの問題において、具体的に計算することを可能とする、そんな手続き(アルゴリズム)を用意するのに使える
  - このようなグレブナー基底の役割は、「素数を見つけるためにエラトステネスの篩」が役に立つことになぞらえてもよい
  - 素数にとってエラトステネスの篩の対極(？）にあるのは、「素数は無限にあるよ、だって、素数の積に１を足したものは、その計算に使った素数では割り切れないことから、いくらでも素数が作れることを証明しているから」という証明だ、という。この証明は、素数が無限にあることは教えてくれても、素数を用いた現実的な問題(たとえば素数のリストを作るとか)には役に立たないから、というのがその理由だという
第１章　可換環
- 可換環、イデアル、可換環上の加群を経て
- 多項式環へ話を進める
- 多項式環にまつわる(連立多項式にもまつわる)諸問題は、多項式環のイデアルについての問題に置き換えて考えることが有効であることにつなげる
第２章　グレブナー基底
- イデアルが大事なことはすでに示してある
- イデアルの生成元としてのグレブナー基底へ話を進める
- グレブナー基底が有用なものであることを示すと同時に、それが有限回の手続きで得られることも示し、有用なものが、高嶺の花ではなく、確かに「使えるやつ」であることも示す
第３章　消去法とグレブナー基底
- グレブナー基底を比較的なじみのある事項との関係からとっつきやすくする
第４章　代数幾何学の基本概念
- 代数幾何学は多項式の共通零点(代数多様体)を対象とするので、代数幾何学を多項式環で捉えるとグレブナー基底が役に立つ
- 後続の章では代数幾何におけるグレブナー基底の活用の話になるのだが、それを理解するための代数幾何の基礎を扱う
第５章　次元と根基(radical)
- 多項式環のイデアルの次元(イデアルが定義するアフィン空間の閉部分スキームの次元)の意味を扱い、グレブナー基底を使ってその次元の計算をする
- 多項式がイデアルの根基かどうかの判定にもグレブナー基底が役に立つ
第６章　自由加群の部分加群のグレブナー基底
- また、グレブナー基底を多項式環上の加群に一般化する話を導入する
- その延長線上で、代数幾何学で用いられる射影(的)多様体とその上での不変量の計算にとってのグレブナー基底の役割に話が展開する
- それを理解するにあたって、「層」「コホモロジーの次元」「組合せ」による代数幾何学の理解へとつながる
- 種とか次元とか次数と言った幾何・位相的な世界と話がつながっていく
付録A　層(Sheaf)の概説
- 幾何学的対象を記述する基本的な言葉としての層。代数的多様体、スキームの定義に必要な層

2013-02-10

グレブナー基底の有用性と使い方駆け足で読む『What is ... a Grobner Basis?』

グレブナー基底駆け足で読むシリーズ

連立多項方程式を解くのに便利
- 解は「多項式集合が定める多様体」
- 多項式集合Fが定める多様体は、多項式集合のイデアルが定める多様体と同じ。また、イデアルに対するreduced グレブナー基底Gの作るイデアルが定める多様体とも同じで、さらに、Gの定める多様体とも同じ、という関係がある
- Fが定める多様体がemptyである(連立多項方程式の解が無い)とは、Gが{1}であること(Hilbertの零点定理)
- あるイデアルが定める多様体が有限かどうか。initial idealに含まれない単項式をstandardと呼ぶことにすると、このstandardな要素がイデアルに含まれる数が有限か否かの判定ができる。そしてこのstandardな要素が有限であることは「イデアルの多様体が有限である」ことのif and only if な条件
多様体のCardinality(CartinalityのWikiへと話がつながり、それは多様体の次元へとつながる(ようだ)
グレブナー基底(らしきものがとれたとして)がグレブナー基底であるかの確認方法もある

2013-02-10

グレブナー基底の定義と性質駆け足で読む『What is ... a Grobner Basis?』

グレブナー基底駆け足で読むシリーズ

グレブナー基底は「多変数の多項式の集合」
グレブナー基底はアルゴリズム的取り扱いをしやすい性質を持つ
任意の多項式集合はグレブナー基底に変換できる
グレブナー基底への変換は３つの方法で行う(グレブナー基底は多項式集合に変換ルールを適用した写像のこと？)。その変換方法は:
イデアル
- 多項式集合と多項式環があると、イデアルができる。イデアルは、多項式環の要素を係数とした多項式集合の(１次)線形結合で表される多項式の集合
- イデアルに対応する要素数有限の多項式集合が必ずある(Hilbert's basis theorem)
項の順序ルール
- 多項式環のすべての項に全順序を定めることとする
- 多項式を構成する項で順位が1位の項を"initial term"と呼ぶ
Initial ideal
- あるイデアル(多項式の集合)のすべての多項式について、その個々の多項式のinitial termが生成するイデアルを"initial ideal"と呼ぶ
グレブナー基底と項の順序ルールとのつながり
- あるイデアルの部分集合Gがグレブナー基底である、とは、次のことを意味する
  - そのイデアルの部分集合である
  - Gのinitial termsがそのイデアルを生成する(多項式環の要素を係数とした多項式集合の(１次)線形結合で表される多項式の集合が、そのイデアルとなる)
  - この条件を満たせば、グレブナー基底(多項式の集合)の要素数に縛りはない
    - したがって、あるグレブナー基底を含む多項式集合もグレブナー基底になる
- とはいえ、「最も小さくしたグレブナー基底」はほしい(呼び名がもほしい)。それを"reduced グレブナー基底"と呼ぶ
- "reduced グレブナー基底"とは
  - グレブナー基底である
  - initial termの係数が1である
  - グレブナー基底のinitial termsはイデアルのinitial termsをminimally 生成する
  - グレブナー基底の要素の"trailing terms (initial term以外のtermsのこと?)"はイデアルのinitial termに含まれない
これらをまとめて：『多項式環と項の順序ルールが決まると、ある多項式集合のreduced グレブナー基底は一意に決まる』
- アルゴリズム的で一意に決まる→計算機が出してくれる→例えばSingular(ソフトウェア)

2013-02-10

駆け足で読む『What is ... a Grobner Basis?』

グレブナー基底駆け足で読むシリーズ

『What is ... a Grobner Basis?』を読む
大きく分けて
- 1. グレブナー基底の定義と性質(１ページ目)
- 2. グレブナー基底の有用性と使い方(２ページ目)

2013-02-01

2.グレブナーの扇ぱらぱらめくる『Comutational Algebra and Combinatorics of Toric Ideals』

ぱらぱらめくるシリーズ環多項式環分割表トーリック・イデアルイデアルグレブナー基底扇グレブナーの扇錐

多項式環のイデアルのグレブナーの扇って何？、というのをわかるのがこの章の目的
グレブナー基底についての付言
- グレブナー基底は項の順序ルールで変わることからもわかるように、色々にとれる
- 色々な取り方は、重みづけベクトルに対応付けることができる
- 色々な取り方に対応する重みづけベクトルはたくさんあるけれど、それが決めるのは項の順序だけで、順序の種類数は重みづけベクトルの数に比べて圧倒的に少ない
- それはBuchberger's algorithmが順序ルールが産む違いをぱっぱと捨ててしまえるような、そんな背景があるかららしい
- これは、ひとまず置いて置いて
ポリトープについて
- 凸多面体
- Polyhedral cone(錐)というものがある
- Polyhedral fan(扇)はPolyhedral conesの集まりであって、cone同士が面を共有するように接しているようなもの
グレブナーの扇
- イデアルの構成要素に順序があって、最初に来るのが、グレブナーの扇の最初のつかまえ方(最高次元)を決める
- 「多項式」の多項表現には複数の表記ができる
- それは「構成の素」とする多項式を変えれば、そうなるのは容易に想像できる
- 同じ「構成も素」を使っても、それぞれにどういう割り付けをしていくかの順序が変われば出来上がった表記も変わるだろう
- グレブナーの扇も、そういう「貼り合わせ」が「素のセット」とその「順序」に依存して決まってくるよ、という話のようだ

2013-02-01

1.グレブナー基底ぱらぱらめくる『Comutational Algebra and Combinatorics of Toric Ideals』

ぱらぱらめくるシリーズ環多項式環分割表トーリック・イデアルイデアルグレブナー基底

イントロダクション
- 体 $k$ 上の多項式環 $S:=k[x_1,...,x_n]=:k[x]$ を考える
- $k$ を複素数体とすることを通常とする
- の部分集合をイデアルとする
  - $\forall f,g \in I, f+g \in I$
  - $\forall h \in S, f \in I \Rightarrow hf \in I$
  - イデアル $I$ が $I=\{\sum_{i=1}^t h_i f_i: h_i \in S$ と書けるとき、 $\{f_1,...,f_t\}$ を基底と言う
- 多項式の中で最も単純なのは、単項式ただしは非負整数。これをと書けば、すべての多項式は単項式の線形和で表せて
  - このとき $\{\mathbf{a_j}\}$ を多項式環 $f$ のサポートと呼ぶ
- 多項式の集合に、多様体が対応付けられて、それは
  - $V(f_i,...,f_t)=\{\mathbf{p} \in k^n: f_1(\mathbf{p}) = f_2(\mathbf{p}) = ... = f_t(\mathbf{p}) =0\}$
動機・目的
- Ideal membership problem
  - ある多項式がイデアルに含まれるかどうかを知りたいとする
  - それを解くのにグレブナー基底を使うとよい
  - それがグレブナー基底を用いる理由
いくつかの例
- 単変量イデアル
- 線形イデアル
  - 行列計算 $A p = 0$ の例
  - サーキットというものもあるらしく、それを求めるアルゴリズムもあるらしい(何のため?)
- 単純な例(単変量イデアル、多変量線形イデアル)で、何かしら便利なアルゴリズムがあることの確認がとれたので、多項式イデアル一般に話を広げよう、そこでグレブナー基底がどういう位置づけかを見てみよう
グレブナー基底
- 単純な例でガウスジョルダンの消去法を使った
- 一般化した多項式イデアルに用いるには、これを適用するのを許すような「ルール」が必要らしい
  - それが、式の多項の扱い順序とか多項式の各単項の記述ルールとからしい("term order")
    - 群論アプリでそれを指定しないと、計算してくれなかったこと(こちら)を思い出そう
- 計算できるアルゴリズムがあることがわかれば、とりあえず、その中味について今は、興味がない→Buchberger's algorithmはイデアルのreduced グレブナー基底を導き出してくれるアルゴリズムである、ということがわかればよしとする
そしてMacaulay2を用いた演習がついているので、(やりたくなったら)やろう