Pravidelný řetěz - Regular chain

v počítačová algebra, a běžný řetěz je zvláštní druh trojúhelníkové množiny ve vícerozměrné proměnné polynomiální kruh přes pole. Zvyšuje představu o charakteristická sada.

Úvod

Vzhledem k lineární systém, lze jej převést na a trojúhelníkový systém přes Gaussova eliminace. Pro nelineární případ, daný a polynomický systém F nad polem ho lze převést (rozložit nebo triangularizovat) na konečnou množinu trojúhelníkových množin v tom smyslu, že algebraická rozmanitost PROTI(F) je popsán těmito trojúhelníkovými množinami.

Trojúhelníková množina může pouze popsat prázdnou množinu. Abychom napravili tento zvrhlý případ, představili jsme pojem regulárního řetězce, nezávisle na tom Kalkbrenerem (1993), Yangem a Zhangem (1994). Pravidelné řetězce se objevují také v Chou a Gao (1992). Pravidelné řetězce jsou speciální trojúhelníkové množiny, které se používají v různých algoritmech pro výpočet nemixovaných dimenzionálních rozkladů algebraických variet. Bez použití faktorizace mají tyto rozklady lepší vlastnosti, než jaké produkuje Wuův algoritmus. Kalkbrenerova původní definice vycházela z následujícího pozorování: každá neredukovatelná odrůda je jednoznačně určena jedním z jejích obecné body a odrůdy mohou být reprezentovány popisem obecných bodů jejich neredukovatelných složek. Tyto obecné body jsou dány pravidelnými řetězci.

Příklady

Označit Q pole racionálního čísla. v Q[X₁, X₂, X₃] s variabilním uspořádáním x₁ 2 3,

{displaystyle T = {x_ {2} ^ {2} -x_ {1} ^ {2}, x_ {2} (x_ {3} -x_ {1})}}

je trojúhelníková sada a také běžný řetěz. Dva obecné body dané T jsou (a, a, a) a (a, -a, a) kde A je transcendentální QExistují tedy dvě neredukovatelné složky, dané {x₂ - X₁, X₃ - X₁ } a {x₂ + x₁, X₃ - X₁ } Upozorňujeme, že: (1) obsah druhého polynomu je x₂, který nepřispívá k reprezentovaným obecným bodům, a proto jej lze odstranit; (2) dimenze každé komponenty je 1, počet volných proměnných v regulárním řetězci.

Formální definice

Proměnné v polynomiálním kruhu

{displaystyle R = k [x_ {1}, ldots, x_ {n}]}

jsou vždy tříděny jako x₁ <... n. Nekonstantní polynom F v ${displaystyle R}$ lze považovat za jednorozměrný polynom v jeho největší proměnné F se nazývá jeho hlavní proměnná, označená mvar(F). Nechat u být hlavní proměnnou F a napište to jako

{displaystyle f = a_ {e} u ^ {e} + cdots + a_ {0}}

,

kde E je stupeň F w.r.t. u a ${displaystyle a_ {e}}$ je hlavní koeficient F w.r.t. u. Pak počáteční z Fje ${displaystyle a_ {e}}$ a E je jeho hlavní stupeň.

Trojúhelníková sada

Neprázdná podmnožina T z ${displaystyle R}$ je trojúhelníková množina, pokud jsou polynomy v T jsou nekonstantní a mají odlišné hlavní proměnné. Trojúhelníková množina je tedy konečná a nanejvýš má mohutnost n.

Pravidelný řetěz

Nechť T = {t₁, ..., t_s} být trojúhelníková množina taková, že mvar(t₁) < ... < mvar(t_s), ${displaystyle h_ {i}}$ být iniciálou t_i a h být produktem h_ije. Pak T je běžný řetěz -li

{displaystyle mathrm {resultant} (h, T) = mathrm {resultant} (cdots (mathrm {resultant} (h, t_ {s}), ldots, t_ {i}) cdots) eq 0}

,

kde každý výsledný je počítán s ohledem na hlavní proměnnou t_i, resp. Tato definice pochází z Yang a Zhang, která má hodně algoritmického vkusu.

Kvazikomponentní a nasycený ideál pravidelného řetězce

The kvazikomponenta Ž(T) popsané běžným řetězcem T je

{displaystyle W (T) = V (T) setminus V (h)}

, to znamená,

nastavený rozdíl odrůd PROTI(T) a PROTI(h). Připojený algebraický objekt pravidelného řetězce je jeho nasycený ideál

{displaystyle mathrm {sat} (T) = (T): h ^ {infty}}

.

Klasickým výsledkem je, že Zariski uzavření z Ž(T) se rovná odrůdě definované sat (T), to znamená,

{displaystyle {overline {W (T)}} = V (mathrm {sat} (T))}

,

a jeho rozměr je n - | T |, rozdíl počtu proměnných a počtu polynomů v T.

Trojúhelníkové rozklady

Obecně existují dva způsoby, jak rozložit polynomiální systém F. Prvním z nich je líně se rozložit, to znamená pouze představovat jeho obecné body ve smyslu (Kalkbrener),

{displaystyle {sqrt {(F)}} = čepice _ {i = 1} ^ {e} {sqrt {mathrm {sat} (T_ {i})}}}

.

Druhým je popsat všechny nuly v Lazard smysl,

{displaystyle V (F) = pohár _ {i = 1} ^ {e} W (T_ {i})}

.

Pro trojúhelníkové rozklady jsou v každém smyslu k dispozici různé algoritmy.

Vlastnosti

Nechat T být pravidelným řetězcem v polynomiálním kruhu R.

Nasycený ideální sat (T) je nesmíchaný ideál s rozměrem n - |T|.
Pravidelný řetězec má silnou eliminační vlastnost v tom smyslu, že:

{displaystyle mathrm {sat} (Tcap k [x_ {1}, ldots, x_ {i}]) = mathrm {sat} (T) cap k [x_ {1}, ldots, x_ {i}]}

.

Polynom p je v sat (T) právě tehdy, když p je pseudo-redukováno na nulu o T, to znamená,

{displaystyle pin mathrm {sat} (T) iff mathrm {prem} (p, T) = 0}

.

Z tohoto důvodu test členství pro sat (T) je algoritmický.

Polynomial p je a nulový dělitel modulo sat (T) právě tehdy ${displaystyle mathrm {prem} (p, T) eq 0}$ a ${displaystyle mathrm {resultant} (p, T) = 0}$ .

Proto je test pravidelnosti pro sat (T) je algoritmický.

Vzhledem k prvotřídnímu ideálu P, existuje pravidelný řetězec C takhle P = sat (C).
Pokud je prvním prvkem pravidelného řetězce C je neredukovatelný polynom a ostatní jsou ve své hlavní proměnné lineární, pak sat (C) je prvotřídním ideálem.
Naopak, pokud P je prvotřídním ideálem, pak po téměř všech lineárních změnách proměnných existuje regulární řetězec C předchozího tvaru tak, že P = sat (C).
Trojúhelníková sada je pravidelný řetěz právě tehdy, pokud jde o a Sada charakteristik Ritt jeho nasyceného ideálu.

Viz také

Další reference

P. Aubry, D. Lazard, M. Moreno Maza. Na teoriích trojúhelníkových množin. Journal of Symbolic Computation, 28 (1–2): 105–124, 1999.
F. Boulier a F. Lemaire a M. Moreno Maza. Známé věty o trojúhelníkových systémech a princip D5. Transgressive Computing 2006, Granada, Španělsko.
E. Hubert. Poznámky k trojúhelníkovým množinám a algoritmům triangulace a rozkladu I: Polynomiální systémy. LNCS, svazek 2630, Springer-Verlag Heidelberg.
F. Lemaire a M. Moreno Maza a Y. Xie. Knihovna RegularChains. Konference Maple 2005.
M. Kalkbrener: Algoritmické vlastnosti polynomiálních kroužků. J. Symb. Comput. 26 (5): 525–581 (1998).
M. Kalkbrener: Zobecněný euklidovský algoritmus pro výpočet trojúhelníkových reprezentací algebraických odrůd. J. Symb. Comput. 15 (2): 143–167 (1993).
D. Wang. Výpočet trojúhelníkových systémů a běžných systémů. Journal of Symbolic Computation 30 (2) (2000) 221–236.
Yang, L., Zhang, J. (1994). Hledání závislosti mezi algebraickými rovnicemi: algoritmus aplikovaný na automatické uvažování. Artificial Intelligence in Mathematics, str. 14715, Oxford University Press.