三角分解

コンピュータ代数では、多項式系Sの三角分解は、より単純な多項式系S ₁、...、S _eの集合であり、ある点がSの解であるためには、それが系S ₁、...、S _eのいずれかの解である必要があります。

Sの解集合をその係数体の代数閉包で記述することが目的である場合、それらのより単純なシステムは正則連鎖です。多項式システムS ₁、...、S _eの係数が実数である場合、 Sの実数解は、正則半代数システムへの三角分解によって取得できます。どちらの場合も、これらのより単純なシステムのそれぞれは三角形の形状と注目すべき特性を持ち、それが用語の正当性を証明しています。

特性集合法は、代数多様体を等次元成分に分解するために提案された、因数分解を必要としない最初のアルゴリズムです。さらに、著者のWen-Tsun Wu は、この方法の実装を実現し、1987 年の先駆的な論文「多項式方程式を解くためのゼロ構造定理」で実験データを報告しました。^[1]この研究を理解するために、この記事が書かれた当時の代数集合分解の一般的な考え方を思い出してみましょう。

K を代数的に閉体とし、k をKの部分体とする。部分集合V ⊂ K ⁿがk上の（アフィン）代数多様体であるとは、多項式集合F ⊂ k [ x ₁ , ..., x _n ]が存在して、Fの零点集合V ( F ) ⊂ K ^{n が}V に等しいことをいう。

すべての代数多様体V ₁ , V ₂ ⊂ K ⁿに対して、関係V = V ₁ ∪ V _2がV = V ₁またはV = V ₂を意味するとき、 Vは既約であると言われることを思い出してください。最初の代数多様体分解の結果は、有名なラスカー・ノイマン定理であり、これは次のことを意味します。

定理（ラスカー＝ノイマン）。各代数多様体V ⊂ K ⁿに対して、有限個の既約代数多様体V ₁ , ..., V _e ⊂ K ⁿが存在し、

${\displaystyle V=V_{1}\cup \cdots \cup V_{e}.}$

さらに、 1 ≤ i < j ≤ eに対してV _i ⊈ V _jが成り立つ場合、集合{ V ₁ , ..., V _e }は一意であり、Vの不可分分解を形成します。

上記の定理の多様体V ₁、...、V _{e は}Vの既約成分と呼ばれ、分解アルゴリズム、つまりk [ x ₁、...、x _n ]の連立方程式を解くアルゴリズムの自然な出力と見なすことができます。

コンピュータプログラムに導くためには、このアルゴリズム仕様は、既約成分がどのように表現されるかを規定する必要がある。このような符号化は、Joseph Ritt ^[2]によって 次の結果を通じて導入されている。

定理（Ritt）。V ⊂ K ⁿが空でない既約多様体である場合、 k [ x ₁ , ..., x _n ]におけるFによって生成されるイデアルに含まれ、 C に関する擬似除算によってにおけるすべての多項式g が0 に簡約されるような、簡約三角集合C を計算できます。${\displaystyle \langle F\rangle }$${\displaystyle \langle F\rangle }$

リットの定理における集合C をイデアルのリット特性集合と呼びます。三角集合の概念については、 正則連鎖を参照してください。${\displaystyle \langle F\rangle }$

ジョセフ・リットは、体拡大上の多項式因数分解と素イデアルの特性集合の計算に基づいて多項式系を解く方法を説明しました。

しかし、この方法の実用的な実装を導き出すことは、当時も今も難しい問題です。特性集合法が導入された1980年代には、多項式因数分解は活発な研究分野であり、この主題に関するいくつかの基本的な疑問は最近解決されました^[3]

現在では、計算コストの少ない、より弱い分解の概念で十分であるため、代数多様体を既約成分に分解することは、ほとんどの応用問題の処理に必須ではありません。

特性セット法は、 Ritt の定理の次の変形に依存します。

定理（Wen-Tsun Wu）。任意の有限多項式集合F ⊂ k [ x ₁ , ..., x _n ]に対して、 F内のすべての多項式g がCに関する擬似除算によってゼロになるような縮小三角集合を計算できます。${\displaystyle C\subset \langle F\rangle }$

さまざまな概念とアルゴリズムがWen-Tsun Wuの研究を拡張しました。1990年代初頭、Michael Kalkbrenerが1991年に博士論文で独立に導入し、Lu YangとJingzhong Zhang ^{[4]によって導入された}正規連鎖の概念は、重要なアルゴリズムの発見につながりました。

カルクブレンナーの構想では、^[5]正則連鎖は代数多様体の既約成分のジェネリック零点を表現するために使われます。ヤンとチャンのオリジナルの研究では、正則連鎖は超曲面が準多様体（正則連鎖によって与えられる）と交差するかどうかを決定するために使われます。 正則連鎖は実際、いくつかの興味深い特性を持ち、代数方程式や微分方程式のシステムを分解する多くのアルゴリズムの重要な概念となっています。

正規鎖は多くの論文で研究されてきた。^{[6] [7] [8]}

このテーマに関する豊富な文献は、正則鎖の多くの同等の定義によって説明できます。実際、カルクブレンナーの元の定式化は、ヤンとチャンのものとはかなり異なります。カルクブレンナーの観点とヤンとチャンの観点という2つの概念の橋渡しは、ドンミン・ワンの論文に示されています。^[9]

V ( F )の三角分解を得るためのアルゴリズムは、Kalkbrenerの意味でも、LazardとWen-Tsun Wuの意味でも、様々なものがあります。Daniel Lazard ^[10]によるLextriangularアルゴリズムとMarc Moreno Maza ^[11]によるTriadeアルゴリズムは、特性集合法とともに、 AxiomやMapleを含む様々なコンピュータ代数システムで利用できます。

k を体とし、x ₁ < ... < x _nを順序付き変数とする。対応する多項式環をR = k [ x ₁ , ..., x _n ]で表す。多項式方程式のシステムとみなされるF ⊂ Rに対して、 kの代数閉包上の三角分解の2つの概念がある。1つ目は、いわゆるカルクブレンナーの意味で 代数集合V ( F )の一般点のみを表すことによって、遅延分解する方法である。

${\displaystyle {\sqrt {(F)}}=\bigcap _{i=1}^{e}{\sqrt {\mathrm {sat} (T_{i})}}.}$

2つ目は、 LazardとWen-Tsun Wuのいわゆる意味でV ( F )のすべての点を明示的に記述することです。

${\displaystyle V(F)=\bigcup _{i=1}^{e}W(T_{i}).}$

どちらの場合も、T ₁、...、T _{e は}Rの有限個の正規鎖であり、T _iの飽和イデアルの根基を表します。一方、W ( T _i ) はT _iの準成分を表します。これらの概念の定義については、 正規鎖を参照してください。${\displaystyle {\sqrt {\mathrm {sat} (T_{i})}}}$

これからk は実閉体であると仮定する。 Rの多項式を含む半代数系S を考える。 ^[12]有限個の正則半代数系S ₁ , ..., S _eが存在し、

${\displaystyle Z_{\mathbf {k} }(S)=Z_{\mathbf {k} }(S_{1})\cup \cdots \cup Z_{\mathbf {k} }(S_{e})}$

ここで、Z _k ( S ) はSを解くk ⁿの点を表します。正規半代数系S ₁、...、S _{e は}半代数系Sの三角分解を形成します。

Q を有理数体と表記します。変数順序 で、次の多項式系を考えます。 ${\displaystyle Q[x,y,z]}$${\displaystyle x>y>z}$

${\displaystyle S={\begin{cases}x^{2}+y+z=1\\x+y^{2}+z=1\\x+y+z^{2}=1\end{cases}}}$

Mapleコード によると:

( RegularChains )の場合: 
R := PolynomialRing ([ x , y , z ]) : sys := { x ^ 2 + y + z - 1 , x + y ^ 2 + z - 1 , x + y + z ^ 2 - 1 } : l := Triangularize ( sys , R ) : map ( Equations , l , R ) ;    
    
   
  

RegularChains ライブラリを使用した Sのソリューション セットの 1 つの可能な三角分解は次のとおりです。

${\displaystyle {\begin{cases}z=0\\y=1\\x=0\end{cases}}\cup {\begin{cases}z=0\\y=0\\x=1\end{cases}}\cup {\begin{cases}z=1\\y=0\\x=0\end{cases}}\cup {\begin{cases}z^{2}+2z-1=0\\y=z\\x=z\end{cases}}}$

• ウーの特性集合法
• レギュラーチェーン
• 正規半代数システム