Gröbnerin perusteella

Gröbner -kanta on joukko , joka generoi tietyn polynomirenkaan ideaalin , jolla on erityisiä ominaisuuksia.

Määritelmä

Olkoon kenttä - ja työskentelymuuttujille annettu seuraava : jonkinlainen työskentelymuuttujien polynomirenkaan ideaali ja jokin täydellinen järjestys " " monomeilla , missä ts. varten . Tässä tapauksessa tilauksen on lisäksi täytettävä kaksi ehtoa: $F$ $(x_{1},\ldots ,x_{n})$ $minä$ $F[x_{1},\ldots ,x_{n}]$ $(x_{1},\ldots ,x_{n})$ $\prec$ $x^{a}=x_{1}^{a_{1}}\cdot \ldots \cdot x_{n}^{a_{n}}$ $a=(a_{1},\ldots ,a_{n})\geq 0$ $a_{j}\geq 0$ $j=1,\ldots ,n$ $\prec$

moninkertaisuus :tarkoittaa; _ $x^{a}\prec x^{b}$ $x^{{a+c}}\prec x^{{b+c}}$ $c\geq 0$
yksikön minimaalisuus : for, ts. . $1\prec x^{a}$ $a>0$ $\exists j:a_{j}>0$

Jäsentä kutsutaan polynomin johtavaksi (" johtavaksi ") jäseneksi (järjestyksen suhteen ), jos kaikille . ${\displaystyle l_{\prec }(p)=\varphi _{l}\cdot x^{l))$ $\prec$ $p=\sum _{a\in A(p)}\varphi _{a}\cdot x^{a}\in F[x_{1},\ldots ,x_{n}]$ ${\displaystyle x^{a}\prec x^{l))$ $a\in A(p)\setminus \{l\}$

Renkaan ideaalin Gröbner -kanta on äärellinen joukko polynomeja kohteesta , joka generoi ihanteen ja jolla on seuraava ominaisuus: mille tahansa polynomille on olemassa polynomi , joka on jaollinen . $minä$ $F[x_{1},\ldots ,x_{n}]$ $G=\{g_{1},\ldots ,g_{m}\}$ $F[x_{1},\ldots ,x_{n}]$ $minä$ $p\in I$ $g\in G$ $l_{\prec }(p)$ $l_{\prec }(g)$

Gröbner-pohjatyypit

Gröbnerin vähimmäisperusta

Polynomiideaalin I minimaalinen Gröbner -kanta on sen Gröbner -kanta G siten, että:

Jokaisen suurimman monomin kerroin on yhtä suuri kuin yksi. $p\in G$
Kummankaan korkein monomi ei ole jaollinen millään kantan muiden elementtien korkeimmalla monomialilla. $p\in G$

Alennettu Gröbner-peruste

Polynomiideaalin I pelkistetty Gröbner -kanta on sen Gröbner -kanta G , jolloin:

Jokaisen suurimman monomin kerroin on yhtä suuri kuin yksi. $p\in G$
Mikään monomeista ei ole jaollinen millään kannan muiden elementtien korkeimmalla monomillalla. $p\in G$

Supistetun Gröbner-ihanteen perusteella seuraava väite pitää paikkansa:

Olkoon I polynomiideaali ja jokin monomijärjestys on annettu. Sitten on olemassa ainutlaatuinen pelkistetty Gröbner-perusta ihanteelle I .

Rakennusalgoritmit

Ensimmäistä algoritmia ideaalin pelkistetyn Gröbner-pohjan muodostamiseksi pidetään Buchbergerin algoritmina . Mielenkiintoista on, että tunnettu Gaussin menetelmä lineaaristen yhtälöjärjestelmien ratkaisemiseksi on Buchberger-algoritmin erikoistapaus.

Lisäksi ranskalainen matemaatikko Jean-Charles Foger ehdotti F4- ja F5 -algoritmeja Gröbner-kannan löytämiseksi.

Sovellukset

Gröbnerin kanta on olennainen käsite tietokonealgebrassa , algebrallisessa geometriassa ja laskennallisessa kommutatiivisessa algebrassa .

Historia

Itävaltalainen matemaatikko Wolfgang Gröbner kommutatiivisen tapauksen standardikantoista 1930-luvun alussa ja julkaisi sen 1950 - julkaisussa [1] , jossa hän kirjoitti:

Aloin käyttää tätä menetelmää 17 vuotta sitten erilaisiin esimerkkeihin, joistakin erittäin monimutkaisiin.

Alkuperäinen teksti (saksa)[ näytäpiilottaa] Ich habe diese Methode seit etwa 17 Jahren in den verschiedensten, auch kompliziersten Fällen verwendet.

Vuonna 1964 samanlaisen konseptin paikallisille renkaille kehitti Heisuke Hironaka , joka voitti vuoden 1970 Fields Prize -palkinnon . Hän kutsui käyttöön otettuja polynomijärjestelmiä standardipohjaksi .

Gröbner-pohjan käsitteen esitteli vuonna 1965 itävaltalainen matemaatikko Bruno Buchberger , Gröbnerin entinen oppilas. Buchberger ehdotti rakentavaa menettelyä Gröbner-kannan rakentamiseksi tehokkaan tietokonealgoritmin muodossa, josta myöhemmin tuli tunnetuksi -

Ihanteen standardiperustan olemassaolo perustuu "kokoonpanolemmaan", jonka AI Shirshov osoitti ensin monimutkaisimman tunnetuista tapauksista (vapaat Lie-algebrat ) [2] . Lisäksi samanlaisen väitteen oikeellisuutta vapaille assosiatiivisille ja kommutatiivisille tapauksille pidettiin ilmeisenä, ja se herätti paljon huomiota vasta myöhemmin L. A. Bokutin teoksissa assosiatiivisten renkaiden upottamisesta renkaisiin ja renkaisiin, joilla on tietyt ominaisuudet. Vuonna 1972 L. A. Bokut julkaisi Novosibirskin yliopiston assosiatiivisten algebroiden kurssin muistiinpanoissa "Shirshovin sävellyslemman" vapaalle assosiatiiviselle tapaukselle . Sieltä ja suullisesta viestinnästä se tuli tunnetuksi amerikkalaisen algebratikon J. Bergmanille, joka julkaisi sen vuonna 1979 otsikolla "Diamond Lemma" ("Timanttilemma"). Teoksessa ei ollut tiukkaa näyttöä, ja vain "fuusion" muistokaavio ilmoitettiin, mikä on välttämätöntä Shirshovin kokoonpanoidean ymmärtämiseksi. Bergmanin julkaisun jälkeen "timanttilemmasta" tuli suosittu algebraistien ja geometrien keskuudessa, ja se kiinnitti huomion myös Buchbergerin "Gröbner-pohjaan". 1980-luvun puolivälissä Moskovan algebrasti A. A. Mikhalev rakensi standardin perustan superalgebroille ja värillisille Lie-algebroille.

Muistiinpanot

↑ W. Gröbner. Über die Eliminationstheorie // Monatshefte für Mathematik : päiväkirja. - 1950. - Voi. 54 . - s. 71-78 .
↑ SMJ, 1962, osa 3, nro 2, s. 292-296.

Kirjallisuus

Arzhantsev IV Gröbnerin algebrallisten yhtälöiden perusteet ja järjestelmät . - M .: MTSNMO , 2003. - 68 s. — ISBN 5-94057-095-X .
Buchberger B. ja muut. Tietokonealgebra: Symboliset ja algebralliset laskelmat. - M .: Mir, 1986. - 392 s.
Cox D., Little J., O'Shea D. Ihanteet, lajikkeet ja algoritmit. Johdatus algebrallisen geometrian ja kommutatiivisen algebran laskennallisiin näkökohtiin. - M .: Mir, 2000. - 687 s. - ISBN 5-03-003320-3 .
Pankratiev EV Johdatus tietokonealgebraan . – Intuitio. — ISBN 978-5-9556-0099-4 .

Linkit

Churkin V. A. Polynomiyhtälöjärjestelmät, ihanteet ja niiden jakajakannat .
Bernd Sturmfels . Mikä on Gröbner-perusta?