Triangulär sönderdelning

I datoralgebra är en triangulär nedbrytning av ett polynomsystem $S$ en uppsättning enklare polynomsystem $S 1, ..., S e$ så att en punkt är en lösning av $S$ om och bara om den är en lösning av ett av systemen $S1, ..., S e$ .

När syftet är att beskriva lösningsuppsättningen av $S$ i den algebraiska stängningen av dess koefficientfält , är dessa enklare system vanliga kedjor . Om koefficienterna för polynomsystemen $S 1, ..., S e$ är reella tal, så kan de reella lösningarna av $S$ erhållas genom en triangulär nedbrytning till reguljära semi-algebraiska system . I båda fallen har vart och ett av dessa enklare system en triangulär form och anmärkningsvärda egenskaper, vilket motiverar terminologin.

Historia

Den karakteristiska uppsättningsmetoden är den första faktoriseringsfria algoritmen, som föreslogs för att sönderdela en algebraisk variation i ekvidimensionella komponenter. Dessutom insåg författaren, Wen-Tsun Wu , en implementering av denna metod och rapporterade experimentella data i sin pionjärartikel från 1987 med titeln "A zero structure theorem for polynomial equations solving". För att sätta detta arbete i ett sammanhang, låt oss komma ihåg vad som var den vanliga idén om en algebraisk uppsättningsupplösning vid den tidpunkt då denna artikel skrevs.

Låt $K$ vara ett algebraiskt slutet fält och $k$ vara ett underfält till $K$ . En delmängd $V \subset K n$ är en (affin) algebraisk variation över $k$ om det finns en polynommängd $F \subset k [x 1, ..., x n]$ så att nollmängden $V (F) \subset K n$ av $F$ är lika med $V$ .

Kom ihåg att $V$ sägs vara irreducerbar om för alla algebraiska varianter $V 1, V 2 \subset K n innebär$ relationen $V = V 1 \cup V 2$ antingen $V = V 1$ eller $V = V 2$ . Ett första resultat av algebraisk sortnedbrytning är den berömda Lasker-Noether-satsen som antyder följande.

Sats (Lasker - Noether). För varje algebraisk variant

V \subset K n

finns det ändligt många irreducerbara algebraiska varianter

V 1, ..., V e \subset K n

så att vi har

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

Dessutom, om

V i ⊈ V j

gäller för

1 \leq i < j \leq e

så är mängden

{V 1, ..., V e}

är unik och bildar den irreducerbara nedbrytningen av

V

.

Varieteterna $V 1, ..., V e$ i ovanstående sats kallas de irreducerbara komponenterna i $V$ och kan betraktas som en naturlig utdata för en nedbrytningsalgoritm, eller, med andra ord, för en algoritm som löser ett ekvationssystem i $k [x 1, ..., x n]$ .

För att leda till ett datorprogram bör denna algoritmspecifikation föreskriva hur irreducerbara komponenter representeras. En sådan kodning introduceras av Joseph Ritt genom följande resultat.

Sats (Ritt). Om

V \subset K n

är en icke-tom och irreducerbar varietet så kan man beräkna en reducerad triangulär mängd

C

som ingår i den ideala

\langle F\rangle

genererad av

F

in

k [x 1, ... , x n]

och så att alla polynom

g

i

\langle F\rangle

reduceras till noll med pseudo-division wrt

C

.

Vi kallar mängden $C$ i Ritts sats en Ritt karakteristisk mängd av idealet $\langle F\rangle$ . Se vanlig kedja för begreppet en triangulär uppsättning.

Joseph Ritt beskrev en metod för att lösa polynomsystem baserat på polynomfaktorisering över fältförlängningar och beräkning av karakteristiska uppsättningar av primideal.

Att härleda en praktisk implementering av denna metod var och förblir dock ett svårt problem. På 1980-talet, när den karaktäristiska mängdmetoden introducerades, var polynomfaktorisering ett aktivt forskningsområde och vissa grundläggande frågor om detta ämne löstes nyligen

Nuförtiden är det inte nödvändigt att sönderdela en algebraisk variant till irreducerbara komponenter för att bearbeta de flesta applikationsproblem, eftersom svagare uppfattningar om nedbrytningar, mindre kostsamma att beräkna, räcker.

The Characteristic Set Method bygger på följande variant av Ritts sats.

Teorem (Wen-Tsun Wu). För vilken finit polynommängd som helst

F \subset k [x 1, ..., x n]

, kan man beräkna en reducerad triangulär mängd

C\subset \langle F\rangle

så att alla polynom

g

in

F

reducerar till noll med pseudo-division wrt

C

.

Wen-Tsun Wus arbete . I början av 1990-talet ledde begreppet en vanlig kedja , som introducerades oberoende av Michael Kalkbrener 1991 i sin doktorsavhandling och av Lu Yang och Jingzhong Zhang till viktiga algoritmiska upptäckter.

I Kalkbreners vision används regelbundna kedjor för att representera de generiska nollorna för de irreducerbara komponenterna i en algebraisk sort. I Yangs och Zhangs originalverk används de för att avgöra om en hyperyta skär en kvasivarietet (given av en vanlig kedja). Reguljära kedjor har faktiskt flera intressanta egenskaper och är nyckelbegreppet i många algoritmer för att sönderdela system av algebraiska eller differentialekvationer.

Regelbundna kedjor har undersökts i många tidningar.

Den rikliga litteraturen om ämnet kan förklaras av de många motsvarande definitionerna av en vanlig kedja. Egentligen är den ursprungliga formuleringen av Kalkbrener helt annorlunda än den för Yang och Zhang. En bro mellan dessa två föreställningar, Kalkbreners synvinkel och Yangs och Zhangs synvinkel, dyker upp i Dongming Wangs tidning.

Det finns olika algoritmer tillgängliga för att erhålla triangulär sönderdelning av $V (F)$ både i betydelsen Kalkbrener och i betydelsen Lazard och Wen-Tsun Wu . Lextriangular Algorithm av Daniel Lazard och Triade Algorithm av Marc Moreno Maza tillsammans med Characteristic Set Method finns tillgängliga i olika datoralgebrasystem, inklusive Axiom och Maple .

Formella definitioner

Låt $k$ vara ett fält och $x 1 < ... < x n$ vara ordnade variabler. Vi betecknar med $R = k [x 1, ..., x n]$ motsvarande polynomring . För $F \subset R$ , betraktat som ett system av polynomekvationer, finns det två föreställningar om en triangulär nedbrytning över den algebraiska stängningen av $k$ . Den första är att sönderdelas lätt, genom att endast representera de generiska punkterna i den algebraiska mängden $V (F)$ i den så kallade betydelsen av Kalkbrener.

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

Den andra är att explicit beskriva alla punkter i $V (F)$ i den så kallade betydelsen av i Lazard och Wen-Tsun Wu .

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

I båda fallen är $T 1, ..., T e$ ändligt många regelbundna kedjor av $R$ och ${\sqrt {\mathrm {sat} (T_{i})}}$ betecknar radikal av $Ti det$ mättade idealet av medan $W (T i)$ betecknar kvasikomponenten av $Ti .$ Se den vanliga kedjan för definitioner av dessa begrepp.

Antag från och med nu att $k$ är ett riktigt slutet fält . Betrakta $S$ som ett semi-algebraiskt system med polynom i $R$ . Det finns ändligt många reguljära semi-algebraiska system $S 1, ..., S e$ sådana att vi har

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

där $Z k (S)$ betecknar punkterna i $k n$ som löser $S$ . De reguljära semi-algebraiska systemen $S 1, ..., S e$ bildar en triangulär nedbrytning av det semi-algebraiska systemet $S$ .

Exempel

Beteckna $Q$ det rationella talfältet. I $Q[x,y,z]$ med variabelordning $x>y>z$ , överväg följande polynomsystem:

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

Enligt Maple -koden:


    
    
   
   med  (  RegularChains  )  :  R  :=  PolynomialRing  ([  x  ,  y  ,  z  ] )  :  sys  :=  {  x  ^  2  +  y  +  z  -  1  ,  x  +  y  ^  2  +  z  -  1  ,  x  +  y  +  z  ^  2  -  1  }  :  l  :=  Triangularisera  (  sys  ,  R  )  :  karta  (  Ekvationer  ,  l  ,  R  )  ;

En möjlig triangulär nedbrytning av lösningsuppsättningen av $S$ med hjälp av RegularChains -biblioteket är:

{\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}}

Se även