F4 (algoritme)

Algoritme F4 blev foreslået af Jean-Charles Faugeré i 1999 som en ny effektiv Gröbner -basisberegningsalgoritme [1] . Denne algoritme beregner Gröbner-grundlaget for et ideal i en polynomialring ved hjælp af en række standard lineære algebraprocedurer: matrixreduktioner. Det er en af de hurtigste til dato.

Algoritme

Definitioner

Det kritiske par er medlem $(f_{i},f_{j})$

$T\cdot T\cdot K[x_{1},...,x_{n}]\cdot T\cdot K[x_{1},...,x_{n}],Pair(f_ {i},f_{j}):=(HOK_{ij},t_{i},f_{i},t_{j},f_{j})$

sådan at

$HOK(Pair(f_{i},f_{j}))=HOK_{ij}=LT(t_{i}f_{i})=LT(t_{j}f_{j})=HOK( f_{i},f_{j})$

Vi definerer graden af et kritisk par som . $p_{i,j}=Par(f_{i},f_{j}),deg(p_{i,j})$ $deg(HOK_{i,j})$

Vi definerer følgende operatorer: og $Left(p_{i,j}):=t_{i}\cdot f_{i}$ $Right(p_{i,j}):=t_{j}\cdot f_{j}$

Pseudokode for F4-algoritmen (forenklet version)

Indgang: ${\begin{cases}F{\text{ finite subset }}K[X_{1},...,X_{n}]\\Sel{\text{ funktion }}Liste(par)\højrepil Liste(par)\\{\tekst{sådan }}Sel(I)\neq \varnothing {\text{ if }}I\neq \varnothing \end{cases}}$

Output: begrænset delmængde $K[X_{1},...,X_{n}]$

$G:=F,{\tilde {F}}_{0}+:=F:=0{\text{ og }}P:=\{Pair(f,g)|(f,g) \i G^{2}{\text{ c }}f\neq g\}$

mens gør $P\neq \varnothing$

$d:=d+1$

$P_{d}:=Sel(p)$

${\displaystyle P:=P\backslash P_{d))$

$L_{d}:=Venstre(P_{d})\kop Højre(P_{d})$

${\tilde {F}}_{d}^{+}:=Reduktion(L_{d},G)$

for gøre $h\in {\tilde {F}}_{d}^{+}$

${\displaystyle P:=P\kop \{Pair(h,g)|g\in G\}G:=G\cup \{h\))$

Vend tilbage $G$

Reduktionsalgoritme

Nu kan vi udvide definitionen af polynomiel reduktion modulo

delmængde , indtil reduktionen af delmængden med $K[X_{1},...,X_{n}]$ $K[X_{1},...,X_{n}]$

modulo en anden undergruppe : $K[X_{1},...,X_{n}]$

Input: L, G endelige delmængder $K[X_{1},...,X_{n}]$

Output: endelige delmængder (kan være tomme) $K[X_{1},...,X_{n}]$

$F:={\text{Symbolic Preprocessing}}(L,G)$

${\tilde {F}}:={\text{Gauss-reduktion }}F{\text{ relativ}}<$

${\tilde {F}}^{+}:=\{f\in {\tilde {F}}|LT(f)\ikke \i LT(F)\}$

Vend tilbage ${\displaystyle {\tilde {F^{+)))))$

Der bruges ingen aritmetisk operation: dette er symbolsk forbehandling.

Symbolsk forbehandlingsalgoritme

Input: L, G endelige delmængder $K[X_{1},...,X_{n}]$

Output: endelige delmængder $K[X_{1},...,X_{n}]$

$F:=L$

$Udført:=LT(F)$

mens gør $T(F)\neq Udført$

$m\in T(F)\backslash Udført$

$Done:=Done\kop \{m\}$

hvis støbt ovenfra modulo så $m$ $G$

eksisterer $g\in G{\text{ OG }}m^{'}\in T:m=m^{'}\cdot LT(g)$

${\displaystyle F:=F\cup \{m^{'}\cdot g\))$

Vend tilbage $F$

Lemma

For alle polynomier vi har ${\displaystyle p\in L_{d))$ $p{\xrightarrow[{}]{G\cup {\tilde {F}}+}}0$

Sætning (intet bevis)

Algoritmen beregner Gröbner-grundlaget G in $F_{4}$ $K[X_{1},...,X_{n}]$

sådan at $F\subseteq G{\text{ I }}Id(G)=Id(F).$

Kommentar

Hvis # er for alle , reduceres algoritmen til Buchbergers algoritme . I dette tilfælde er Sel-funktionen den tilsvarende udvælgelsesstrategi for Buchberger-algoritmen. $Sel(I)=1$ $I\neq \varnothing$ $F_{4}$

Valgfunktion

Input : liste over kritiske par $P$

Output : liste over kritiske par

$d:=min\{deg(lcm(p))\}$

$P_{d}:=\{p\in P|deg(lcm(p))=d\}$

Vend tilbage $P_d$

Vi kalder denne strategi for den normale strategi for . $F_{4}$

Derfor, hvis inputpolynomierne er ensartede, kommer vi til potensen, og d er Gröbner-grundlaget.

I det næste trin vælger vi alle de kritiske par , der er nødvendige for at beregne Gröbner-grundlaget til potensen d+1.

Optimering af F4-algoritmen

Der er flere måder at optimere algoritmen på:

medtagelse af Buchberger-testen (eller F5-testen);

genbrug af alle rækker i de givne matricer.

Buchberger kriterier Algoritme - implementering:

$(G_{ny},p_{ny}):=Opdater(G_{gammel},P_{gammel},h)$

Indgang: ${\begin{cases}{\text{slut delmængde af }}G_{old}{\text{ i }}K[X_{1},...,X_{n}]\\{\text { finite subset }}P_{gammel}{\tekst{ af kritiske par i }}K[X_{1},...,X_{n}]\\0\neq h\in K[x_{1}, .. .,X_{n}]\end{cases}}$

Output: endelig undersæt til opdateret liste over kritiske par $K[X_{1},...,X_{n}]$

Pseudokode for F4-algoritmen (med kriterium)

Indgang: ${\begin{cases}F\subset K[X_{1},...,X_{n}]\\Sel{\text{ function }}Liste(par)\højrepil Liste(par)\slut {cases}}$

Output: endelig delmængde af . $K[X_{1},...,X_{n}]$

$G:=\varnothing {\text{ OG }}P:=\varnothing {\text{ OG }}d:=0$

mens gør $F\neq \varnothing$

$f:=first(F);F:F\backslash \{f\}$

$(G,P):=Opdater(G,P,f)$

mens gør $P\neq \varnothing$

$d:=d+1$

${\displaystyle P_{d}:=Sel(P);P:=P\backslash P_{d))$

$L_{d}:=Venstre(P_{d})\kop Højre(P_{d})$

$({\tilde {F}}_{d}^{+},F_{d}):=Reduktion(L_{d},G,(F_{i})_{d=1,.. .,(d-1)})$

til $P\neq {\tilde {F}}_{d}^{+}$

${\displaystyle P:=P\cup \{Pair(h,g)|g\in G\))$

$(G,P):=Opdater(G,P,h)$

Vend tilbage $G$

F4 og dens forskelle fra Buchberger-algoritmen

Lad der være et begrænset sæt polynomier . Baseret på dette sæt konstrueres en stor sparsom matrix, hvis rækker svarer til polynomier fra , og kolonnerne svarer til monomer. Matrixen indeholder koefficienterne for polynomier ved de tilsvarende monomer. Matricens kolonner er sorteret i henhold til den valgte monomial rækkefølge (det højeste monomium svarer til den første kolonne). Reduktion af en sådan matrix til en trinvis form gør det muligt at finde ud af grundlaget for det lineære spænd af polynomier fra polynomiers rum. $F$ $F$ $F$

Antag, at i den klassiske Buchberger-algoritme er det nødvendigt at udføre et trin med at reducere polynomiet med hensyn til , og samtidig skal det multipliceres med et monomial . I F4-algoritmen, og vil være specielt placeret i matrixen . Det hævdes, at det er muligt på forhånd at forberede et sæt af alle potentielle multiplikationsreducere, der kan være nødvendige, og placere dem på forhånd i en matrix. [2] $f$ $g$ $g$ $M$ $f$ $M$ $g$

Vi generaliserer algoritmen F4 [3] :

lad os reducere polynomiet i forhold til mængden . Til dette vi $f$ $F$

(1) tilføje til matrixen; $f$

(2) vi konstruerer understøttelsen af polynomiet (sættet af monomialer); ${\mathcal {M}}$ $f$

(3) hvis tom, afslut derefter proceduren; ${\mathcal {M}}$

(4) vælg det maksimale monomial i (og kasser det fra ); $M$ ${\mathcal {M}}$ ${\mathcal {M}}$

(5) hvis det ikke er deleligt med nogen af de højeste monomer af elementer , så gå til trin (3); $M$ $F$

(6) ellers vælger vi reducereren ∈ (og den ekstra faktor ): derefter ; $r$ $F$ $t$ $M$ $=LM$ $tr$

(7) tilføje til matrixen; $tr$

(8) tilføje monomer af polynomiet (undtagen det højeste ) til mængden ; $tr$ $M$ ${\mathcal {M}}$

(9) gå til trin (3).

Denne procedure til at genopfylde en matrix med multiplicerede reduktionselementer kaldes symbolsk forbehandling . Derudover kan du i stedet for S-polynomier lægge deres venstre og højre del i matricen (når du reducerer en række med en anden, får du automatisk et S-polynomium).

Endelig er den tredje forskel fra Buchberger-algoritmen , at det i F4-algoritmen er tilladt at placere dele af flere S-polynomier valgt efter en eller anden strategi i én matrix. Så hvis et S-polynomium er valgt ved hvert trin, gentager det den klassiske Buchberger-algoritme .

Den anden yderlighed er, når mængden af alle tilgængelige S-polynomier reduceres ved næste trin. Dette er heller ikke særlig effektivt på grund af matricernes store størrelse. Forfatteren af algoritmen J.-Sh. Faugère foreslog en normal strategi for valg af S-polynomier til reduktion [4] , hvorefter S-polynomier med den mindste grad af venstre og højre side vælges. Det giver gode empiriske resultater for bestilling af DegRevLex, og dets valg er naturligt for homogene idealer.

Der kan laves flere naturlige forbedringer af algoritmen. Som i den klassiske algoritme til beregning af Gröbner -grundlaget, kan Buchbergers kriterier bruges til at bortfiltrere åbenlyst unødvendige S-polynomier.

Implementeringer

F4 algoritme implementeret

i FGb, Faugères [4] egen implementering , som inkluderer grænseflader til at bruge den fra C / C++ eller Maple ;
i Maple computeralgebrasystemet som en option metode = fgb af Groebner [gbasis] funktionen ;
i Magma computeralgebrasystemet , i SageMath computeralgebrasystemet.

Eksempel

Opgave: Beregn Gröbner-grundlaget for polynomier Først tildeler vi $\{f_{1}=abcd-1;f_{2}=abc+abd+acd+bcd;f_{3}=ab+bc+ad+cd;f_{4}=a+b+c +d\}$ $G={f_{4)),$ $P_{1}={Pair(f_{3},f_{4})},$ ${\displaystyle L_{1}=\{(1,f_{3}),(b,f_{4})\))$

1) Symbolforbehandling $(L_{1},G,\varnothing ):$

$F_{1}=\{{f_{3},bf_{4}}\},T(F_{1})=\{ab,ad,b^{2},bc,bd,cd\ }$

$ab$ Jeg er klar nu.

2) Symbolforbehandling $(L_{1},G,\varnothing ):$

$F_{1}=\{{f_{3},bf_{4}}\},T(F_{1})=\{ab,ad,b^{2},bc,bd,cd\ }$

$annonce$ fra oven reduceres til . $f_{4}\in G$

3) Symbolforbehandling $(L_{1},G,\varnothing ):$

$F_{1}=\{{f_{3},bf_{4},df_{4}}\},T(F_{1})=\{ab,ad,b^{2},bc ,bd,cd,d^{2}\}$

$b^{2}$ koger ikke ned til . $G$

fire) $F_{1}=\{{f_{3},bf_{4},df_{4}}\}.$

Matrixrepræsentation af det resulterende : $F_{1}$

$A_{1}=M(F_{1})={\begin{pmatrix}\{&ab&b^{2}&bc&ad&bd&cd&d^{2}\}\\(df_{4})&0&0&0&1&1&1&1\\(f_{ 3})&1&0&1&1&0&1&0\\(bf_{4})&1&1&1&0&1&0&0\end{pmatrix}}$

Gaussisk reduktion af den resulterende matrix : $A_{1}$

${\tilde {A_{1}}}={\begin{pmatrix}\{&ab&b^{2}&bc&ad&bd&cd&d^{2}\}\\(df_{4})&0&0&0&1&1&1&1\\(f_{3} )&1&0&1&0&-1&0&-1\\(bf_{4})&0&1&0&0&2&0&1\end{pmatrix}}$

Fra denne matrix får vi:

${\tilde {F_{1}}}=[f_{5}=ad+bd+cd+d^{2},f_{6}=ab+bc-bd-d^{2},f_ {7}=b^{2}+2bd+d^{2}]$

Og siden da $ab,ad\in LT(F_{1})$

${\tilde {F_{1+))}=[f_{7}]$ og så $G=\{f_{4},f_{7}\}.$

For det næste skridt skal vi overveje $P_{2}=\{Pair(f_{2},f_{4})\}$

Herfra $L_{2}=\{(1,f_{2}),(bc,f_{4})\}{\text{u}}{\mathcal {F}}=\{F_{1} \}.$

I symbolsk forbehandling kan du prøve at forenkle ved hjælp af de tidligere beregninger: $1\cdot f_{2}{\text{and}}bc\cdot f_{4}$

For eksempel 1) Symbolforbehandling $LT(bcf_{4})=abc=LT(cf_{6}){\text{ og så i stedet for }}bc\cdot f_{4}{\text{ kan du bruge }}c\cdot f_ {6}$

$F_{2}=\{{f_{2},cf_{6}}\},T(F_{2})=\{abc,bc^{2},abd,acd,bcd,cd^ {2}\}$

2) Symbolforbehandling

$F_{2}=\{{f_{2},cf_{6}}\},T(F_{2})=\{abc,bc^{2},abd,acd,bcd,cd^ {2}\}$

3) Symbolforbehandling

$F_{2}=\{{f_{2},cf_{6}}\},T(F_{2})=\{abc,bc^{2},abd,acd,bcd,cd^ {2}\}$ $abd{\text{ reducerer til }}bcf_{4}{\text{ og også til }}bf_{5}$

Lad os beskrive forenklingen

Formål: at erstatte ethvert produkt med produktet , hvor er den tidligere beregnede streng, og dividerer monomiet $m\cdot f$ $(uf)\cdot f'$ $(t,f')$ $uf$ $m$

I den første version af algoritmen: nogle rækker i matrixen bruges aldrig (rækker i matrixen ). ${\tilde {F}}_{d}\backslash {\tilde {F}}_{d}^{+}$

Ny version af algoritmen: vi gemmer disse strenge

$m\cdot f\in Rows(F)\rightarrow m^{'}\cdot f^{'}{\text{ c }}m\geq m^{'}$

$m\cdot f\in Rows(F)\rightarrow X_{k}\cdot f^{'}$

SIMPLIFY forsøger at erstatte produktet med produktet , hvor $m\cdot f$ ${\displaystyle (ut)\cdot f^{'))$

$(t,f^{'})$ allerede beregnet streng i Gaussisk reduktion, og ut deler det monomiale m; Hvis vi har fundet sådan et bedste produkt, så kalder vi rekursivt SIMPLIFY-funktionen:

Indgang: ${\begin{cases}t\in T{\text{ monomial))\\t\i K[X_{1},...,X_{n}]{\text{ polynomial))\\ F=(F_{i})_{d=1,...,(d-1)},{\text{ Hvor }}F_{k}\i K[X_{1},...,X_ {n}]\end{cases}}$

Output: Resultat svarer til $m^{'}*f^{'}$ $t*f$

for gøre $u\in {\text{ liste over divisorer }}t$

hvis $\exists j(1\leq j<d):(u\cdot f)\in F_{j}{\text{ then))$

${\tilde {F}}_{j}{\text{Gaussisk reduktion}}F_{j}{\text{ Relativ}}<$

$\exists !p\in {\tilde {F}}_{j}:LT(p)=LT(u*f)$

hvis $u\neq t{\text{ derefter}}$

Vend tilbage $Simplify({\frac {t}{u}},p,F)$

ellers vende tilbage $1*p$

Vend tilbage $t*f$

Algoritme SYMBOLIK FORBEHANDLING

Indgang: ${\begin{cases}L,G{\text{ endelige delmængder }}K[X_{1},...,X_{n}]\\F=(F_{i})_{d= 1,...,(d-1)},{\text{ Hvor }}F_{k}\\{\text{endelig delmængde}}K[X_{1},...,X_{n}] \end{sager}}$

Output: endelig delmængde af . $K[X_{1},...,X_{n}]$

$F:=L$

$Udført:=LT(F)$

mens gør $T(F)\neq Udført$

$m\in T(F)\backslash Udført$

hvis støbt ovenfra modulo så $m$ $G$

eksisterer $g\in G{\text{ OG }}m^{'}\in T:m=m^{'}\cdot LT(g)$

$F:=F\kop \{Simplify(m^{'},g,F)\}$

Vend tilbage $F$

Nu tilbage til eksemplet.

4) Symbolforbehandling

$F_{2}=\{{f_{2},cf_{6},bf_{5}}\},T(F_{2})=\{abc,bc^{2},abd,acd ,bcd,cd^{2},b^{2}d,bd^{2}\}$

Og så videre....

5) Symbolforbehandling

$F_{2}=[cf_{5},df_{7},bf_{5},f_{2},cf_{6}]$

$A_{2}=M(F_{2})={\begin{bmatrix}0&0&0&0&1&1&1&0&1&0&0\\0&0&0&1&0&0&0&2&0&1&0\\0&0&1&1&0&1&0&1&0&0&0\\1&0&1&0&1&1&0&0&0&0&0\\1&1&0&0&0&-1&0&0&-1&0&0\end{bmatrix}}$

Efter Gauss-reduktion:

${\tilde {A_{2))}={\tilde {M(F_{2))}={\begin{bmatrix}0&0&0&0&1&1&1&0&1&0\\0&0&0&1&0&0&0&2&0&1\\0&0&1&0-1&1&0 -&0&0&0-1&1&0 -&0 1&1&-1&1\\0&1&0&0&0&0&1&-1&0&-1\end{bmatrix}}$

${\tilde {F_{2}}}={\begin{bmatrix}f_{9}=acd+bcd+c^{2}d+cd^{2},\\f_{10}=b ^{2}d+2bd^{2}+d^{3},\\f_{11}=abd+bcd-bd^{2}-d^{3},\\f_{12}=abc- bcd-c^{2}d+bd^{2}-cd^{2}+d^{3},\\f_{13}=bc^{2}+c^{2}d-bd^{ 2}-d^{3}\end{bmatrix}}$

og ${\displaystyle G=\{f_{4},f_{7},f_{13}\))$

På næste trin har vi:

$L_{3}=\{(1,f_{1}),(bcd,f_{4}),(c^{2},f_{7}),(b,f_{13})\ }$

og rekursivt kalder forenklingen:

$Simplify(bcd,f_{4})=Simplify(cd,f_{6})=Simplify(d,f_{12})=(d,f_{12})$

På næste trin har vi:

$L_{3}=\{(1,f_{1}),(bcd,f_{4}),(c^{2},f_{7}),(b,f_{13})\ }$ og $F_{3}=[f_{1},df_{12},c^{2}f_{7},bf_{13},df_{13},df_{10}]$

Efter nogle beregninger viser det sig, at rangen er 5. $M(F_{3})$

Det betyder, at der er en ubrugelig ophævelse.

På næste trin har vi:

$L_{3}=\{(1,f_{1}),(bcd,f_{4}),(c^{2},f_{7}),(b,f_{13})\ }$ og $F_{3}=[f_{1},df_{12},c^{2}f_{7},bf_{13}]$

Symbolforbehandling

$F_{3}=[f_{1},df_{12},c^{2}f_{5},bf_{13},df_{13},df_{10}]$

${\tilde {F_{3}}}={\begin{bmatrix}f_{15}=c^{2}b^{2}-c^{2}d^{2}+2bd^{ 3}+2d^{4},\\f_{16}=abcd-1,\\f_{17}=-bcd^{2}-c^{2}d^{2}-bd^{3} -d^{4}+1,\\f_{18}=c^{2}bd+c^{2}d^{2}-bd^{3}-d^{4},\\f_{ 19}=b^{2}d^{2}+2bd^{3}+d^{4}\end{bmatrix}}$

Noter

↑ Jean-Charles Faugère. En ny effektiv algoritme til beregning af gr¨obner-baser (f4). Journal of Pure and Applied Algebra. – 1999.
↑ Studie af Gröbner-baser // msu. Arkiveret fra originalen den 11. juli 2019.
↑ [ http://www.broune.com/papers/f4.pdf F4-ALGORITHMEN FREMSTILLER GROBNER-BASIS-BEHANDLINGER MED LINEÆR ALGEBRA] // BJARKE HAMMERSHOLT ROUNE. Arkiveret fra originalen den 30. december 2019.
↑ 1 2 Faugères egen implementering ? . Hentet 1. december 2020. Arkiveret fra originalen 15. juni 2021. (ubestemt)

Litteratur

J.-C. Faug'ere. En ny effektiv algoritme til beregning af Gr¨obner-baser uden reduktion til nul (F5).
J.-C. Faug'ere En ny effektiv algoritme til beregning af gr¨obner-baser (F4). Journal of Pure and Applied Algebra, 139 (1999), 61–88.
Cox D., Little J., O'Shea D., idealer, varianter og algoritmer. An Introduction to Computational Algebraic Geometry and Commutative Algebra, New York, NY: Springer, 1998]

F4 (algoritme)

Algoritme

Optimering af F4-algoritmen

F4 og dens forskelle fra Buchberger-algoritmen

Implementeringer

Eksempel

Links

Noter

Litteratur