Dekompozycja trójkątna

W algebrze komputerowej trójkątny rozkład systemu wielomianowego S jest zbiorem prostszych układów wielomianowych S ₁ , ..., S _e takich, że punkt jest rozwiązaniem S wtedy i tylko wtedy, gdy jest rozwiązaniem jednego z układów S ₁ , ..., S _mi .

Kiedy celem jest opisanie zbioru rozwiązań S w algebraicznym domknięciu jego pola współczynników , te prostsze układy są regularnymi łańcuchami . Jeżeli współczynniki systemów wielomianowych S ₁ , ..., S _e są liczbami rzeczywistymi, to rzeczywiste rozwiązania S można otrzymać przez trójkątny rozkład na regularne układy półalgebraiczne . W obu przypadkach każdy z tych prostszych układów ma trójkątny kształt i niezwykłe właściwości, co uzasadnia terminologię.

Historia

Metoda zbiorów charakterystycznych jest pierwszym algorytmem bez faktoryzacji, który został zaproponowany do dekompozycji rozmaitości algebraicznej na składowe równowymiarowe. Co więcej, autor, Wen-Tsun Wu , zrealizował implementację tej metody i przedstawił dane eksperymentalne w swoim pionierskim artykule z 1987 roku zatytułowanym "Twierdzenie o strukturze zerowej do rozwiązywania równań wielomianowych". Aby umieścić tę pracę w kontekście, przypomnijmy sobie, jaka była powszechna koncepcja dekompozycji zbioru algebraicznego w czasie pisania tego artykułu.

Niech K będzie algebraicznie domkniętym ciałem i k będzie podciałem K . Podzbiór V ⊂ K ⁿ jest (afiniczną) rozmaitością algebraiczną nad k , jeśli istnieje zbiór wielomianowy F ⊂ k [ x ₁ , ..., x _n ] taki, że zbiór zerowy V ( F ) ⊂ K ⁿ z F jest równy V .

Przypomnijmy, że mówi się , że V jest nieredukowalne , jeśli dla wszystkich rozmaitości algebraicznych V ₁ , V ₂ ⊂ K ⁿ relacja V = V ₁ ∪ V ₂ implikuje albo V = V ₁ , albo V = V ₂ . Pierwszym wynikiem rozkładu rozmaitości algebraicznej jest słynne twierdzenie Laskera-Noethera , z którego wynika, co następuje.

Twierdzenie (Laskera - Noether). Dla każdej rozmaitości algebraicznej V ⊂ K ⁿ istnieje skończenie wiele nieredukowalnych rozmaitości algebraicznych V ₁ , ..., V _e ⊂ K ⁿ takich, że mamy

${\ Displaystyle V = V_ {1} \ puchar \ cdots \ puchar V_ {e}.}$

Ponadto, jeśli V _ja ⊈ V _j zachodzi dla 1 ≤ ja < j ≤ e wtedy zbiór { V ₁ , ..., V _e } jest unikalny i tworzy nieredukowalną dekompozycję V .

Rozmaitości V ₁ , ..., V _e w powyższym Twierdzeniu nazywane są składowymi nieredukowalnymi V i mogą być traktowane jako naturalne wyjście dla algorytmu dekompozycji, czyli innymi słowy dla algorytmu rozwiązującego układ równań w k [ x ₁ , ..., x _n ] .

Aby doprowadzić do programu komputerowego, ta specyfikacja algorytmu powinna określać, w jaki sposób reprezentowane są komponenty nieredukowalne. Takie kodowanie wprowadza Joseph Ritt poprzez następujący wynik.

Twierdzenie (Ritt). Jeśli V ⊂ K ⁿ jest niepustą i nieredukowalną rozmaitością, to można obliczyć zredukowany trójkątny zbiór $wygenerowanym$ w ideale F w k [ x ₁ , ... , x _n ] i takie, że wszystkie wielomiany g in ${\ Displaystyle \ langle F \ rangle}$ redukuje się do zera przez pseudopodział wrt C .

C w twierdzeniu Ritta nazywamy charakterystycznym zbiorem ideału Ritta ${\ displaystyle \ langle F \ rangle}$ . Proszę odnieść się do zwykłego łańcucha , aby zapoznać się z pojęciem zestawu trójkątnego.

Joseph Ritt opisał metodę rozwiązywania układów wielomianowych opartą na faktoryzacji wielomianów po rozszerzeniach pól i obliczaniu charakterystycznych zbiorów ideałów pierwszych.

Wyprowadzenie praktycznej implementacji tej metody było jednak i pozostaje trudnym problemem. W latach 80., kiedy wprowadzono metodę zbiorów charakterystycznych , faktoryzacja wielomianów była aktywnym obszarem badawczym, a niektóre fundamentalne pytania na ten temat zostały niedawno rozwiązane

Obecnie rozkład rozmaitości algebraicznej na składowe nieredukowalne nie jest niezbędny do rozwiązania większości problemów aplikacyjnych, ponieważ wystarczą słabsze pojęcia dekompozycji, mniej kosztowne w obliczeniach.

Metoda zestawów charakterystycznych opiera się na następującym wariancie twierdzenia Ritta.

Twierdzenie (Wen-Tsun Wu). Dla dowolnego skończonego zbioru wielomianów fa ⊂ k [ x ₁ , ..., n _] , x można obliczyć zredukowany zbiór $g$ że wielomiany F redukuje się do zera przez pseudopodział wrt C .

Różne koncepcje i algorytmy rozszerzyły pracę Wen-Tsun Wu . Na początku lat 90. pojęcie regularnego łańcucha , wprowadzone niezależnie przez Michaela Kalkbrenera w 1991 roku w jego rozprawie doktorskiej oraz przez Lu Yang i Jingzhong Zhanga, doprowadziło do ważnych odkryć algorytmicznych.

W wizji Kalkbrenera regularne łańcuchy są używane do reprezentowania ogólnych zer nieredukowalnych składników rozmaitości algebraicznej. W oryginalnej pracy Yanga i Zhanga są one używane do decydowania, czy hiperpowierzchnia przecina quasi-rozmaitość (daną przez regularny łańcuch). Łańcuchy regularne mają w rzeczywistości kilka interesujących właściwości i są kluczowym pojęciem w wielu algorytmach rozkładających układy równań algebraicznych lub różniczkowych.

Regularne łańcuchy były badane w wielu artykułach.

Obfitą literaturę na ten temat można wytłumaczyć wieloma równoważnymi definicjami regularnego łańcucha. W rzeczywistości oryginalne sformułowanie Kalkbrenera różni się od sformułowania Yang i Zhanga. W artykule Dongminga Wanga pojawia się pomost między tymi dwoma pojęciami, punkt widzenia Kalkbrenera oraz Yang i Zhang.

Dostępne są różne algorytmy uzyskiwania trójkątnej dekompozycji V ( F ) zarówno w sensie Kalkbrenera, jak iw sensie Lazarda i Wen-Tsun Wu . Algorytm Lextriangular Daniela Lazarda i Triade Algorithm Marca Moreno Mazy wraz z metodą zestawu charakterystycznego są dostępne w różnych systemach algebry komputerowej, w tym w Axiom i Maple .

Definicje formalne

Niech k będzie polem, a x ₁ < ... < x _n będzie zmiennymi uporządkowanymi. Oznaczamy przez R = k [ x ₁ , ..., x _n ] odpowiedni pierścień wielomianowy . Dla F ⊂ R , traktowanego jako układ równań wielomianowych, istnieją dwa pojęcia rozkładu trójkątnego na algebraicznym domknięciu k . Pierwszym z nich jest leniwa dekompozycja, przedstawiająca tylko punkty rodzajowe zbioru algebraicznego V ( F ) w tzw. sensie Kalkbrenera.

${\ Displaystyle {\ sqrt {(F)}} = \ bigcap _ {i = 1} ^ {e} {\ sqrt {\ operatorname {s} (T_ {i})}}.}$

Drugim jest jawne opisanie wszystkich punktów V ( F ) w tak zwanym znaczeniu u Lazarda i Wen-Tsun Wu .

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

W obu przypadkach T ₁ , ..., T _mi to skończenie wiele regularnych łańcuchów R i oznacza ${\ Displaystyle {\ sqrt {\ operatorname {sat} (T_ {i})}}$ } pierwiastek nasyconego T i ) _oznacza ideału T i ( _natomiast W quasi - składową T _i . Proszę odnieść się do zwykłego łańcucha o definicje tych pojęć.

Załóżmy od teraz, że k jest ciałem rzeczywistym zamkniętym . Rozważmy S jako system półalgebraiczny z wielomianami w R . Istnieje skończenie wiele regularnych układów półalgebraicznych S ₁ , ..., S _e takich, że mamy

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

gdzie Z _k ( S ) oznacza punkty k ⁿ , które rozwiązują S . Regularne układy półalgebraiczne S ₁ , ..., S _e tworzą trójkątną dekompozycję układu półalgebraicznego S .

Przykłady

Oznaczmy Q polem liczb wymiernych. Q ${\ Displaystyle Q [x, y, z]}$ z uporządkowaniem zmiennych ${\ Displaystyle x> y> z}$ rozważ następujący system wielomianów: Q [ x ,

${\ Displaystyle S = {\ rozpocząć {przypadki} x ^ {2} + y + z = 1 \ \x+y^{2}+z=1\\x+y+z^{2}=1\end{przypadki}}}$

Zgodnie z kodem Maple :

    
    
 gdzie  (  Łańcuchy Regularne  )  :  R  :=  Pierścień Wielomianowy  ([  x  ,  y  ,  z  ])  :  sys  :=  {  x  ^  2  +  y  +  z  -  1  ,  x  +  y  ^  2  +  z  -  1  ,  x  +  y  +  z  ^  2  -  1  }  :  l    
   :=  Triangularyzacja  (  sys  ,  R  )  :  map  (  Równania  ,  l  ,  R  )  ; 

Jedną z możliwych trójkątnych dekompozycji zbioru rozwiązań S przy użyciu biblioteki RegularChains jest:

${\ Displaystyle {\ rozpocząć {przypadki} z = 0 \\ y = 1 \\ x = 0 \ koniec {przypadków}} \ kubek {\ rozpocząć {przypadków} z = 0 \\ y = 0 \\ x = 1 \ koniec {przypadków}}\cup {\begin{przypadków}z=1\\y=0\\x=0\end{przypadków}}\cup {\początek{przypadków}z^{2}+2z-1= 0\\y=z\\x=z\end{przypadki}}}$

Zobacz też

• Metoda zbioru charakterystycznego Wu
• Zwykły łańcuch
• Regularny system półalgebraiczny