Bazy Grobnera, algorytm L4 oraz współczynniki rzeczywiste

Grupy, pierścienie, ciała, rozkładalność, klasyczne struktury algebraiczne...
Awatar użytkownika
Borneq
Użytkownik
Użytkownik
Posty: 247
Rejestracja: 23 lip 2010, o 07:50
Płeć: Mężczyzna
Lokalizacja: geo:lat=0 geo:lon=0
Podziękował: 13 razy

Bazy Grobnera, algorytm L4 oraz współczynniki rzeczywiste

Post autor: Borneq »

Patrzę na algorytm L4 z (github)JohnS0819/Faugere-s-F4-algorithm-over-finite-fields-with-multithreaded-matrix-reduction
Mam zapytania:
konwertowałem układ

Kod: Zaznacz cały

x + y + z + s + w + l
x*y*z*s*w*l - 1
x*y + y*z + z*s + s*w + w*l + l*x
x*y*z + y*z*s + z*s*w + s*w*l + w*l*x + l*x*y
x*y*z*s + y*z*s*w + z*s*w*l + s*w*l*x + w*l*x*y + l*x*y*z
x*y*z*s*w + y*z*s*w*l + z*s*w*l*x + s*w*l*x*y + w*l*x*y*z + l*x*y*z*s
otrzymując

Kod: Zaznacz cały

(1)*x + (1)*y + (1)*z + (1)*s + (1)*w + (1)*l
(1)*x*y + (1)*y*z + (1)*z*s + (1)*s*w + (1)*x*l + (1)*w*l
(1)*x*y*z + (1)*y*z*s + (1)*z*s*w + (1)*x*y*l + (1)*x*w*l + (1)*s*w*l
(1)*x*y*z*s + (1)*y*z*s*w + (1)*x*y*z*l + (1)*x*y*w*l + (1)*x*s*w*l + (1)*z*s*w*l
(1)*x*y*z*s*w + (1)*x*y*z*s*l + (1)*x*y*z*w*l + (1)*x*y*s*w*l + (1)*x*z*s*w*l + (1)*y*z*s*w*l
(1)*x*y*z*s*w*l + (-1)
(natomiast rowechelonv3 zwraca pusty wektor)
Oczekiwałem , że pierwszy wektor wyniku będzie miał tylko jedną zmienną, aby można go było rozwiązać, drugi dwie, w tym tę poprzednią itd.
Dla znacznie prostszego układu

Kod: Zaznacz cały

x+xy+y^2
x+y-xy        
funkcja F4_2 się zawiesza.
Poza tym , biblioteka wymaga całkowitoliczbowych współczynników, czy to ograniczenie tylko tej biblioteki czy algorytmu L4?
Można by współczynniki pomnożyć przez 1e8, i zaokrąglając otrzymać całkowitoliczbowe, jednak co z pośrednimi obliczeniami? czy nie przekroczy któreś zakresu int czy nawet int64?
Awatar użytkownika
Borneq
Użytkownik
Użytkownik
Posty: 247
Rejestracja: 23 lip 2010, o 07:50
Płeć: Mężczyzna
Lokalizacja: geo:lat=0 geo:lon=0
Podziękował: 13 razy

Re: Bazy Grobnera, algorytm L4 oraz współczynniki rzeczywiste

Post autor: Borneq »

To znaczy F4, nie L4
bough
Użytkownik
Użytkownik
Posty: 19
Rejestracja: 23 kwie 2012, o 22:15
Płeć: Mężczyzna
Lokalizacja: Stalowa Wola
Pomógł: 9 razy

Re: Bazy Grobnera, algorytm L4 oraz współczynniki rzeczywiste

Post autor: bough »

Cześć, nie znam tego algorytmu, ale na twoim miejscu zastosowałbym jeden ze znanych "Computer algebra systems". Macaulay2 obsługuje bazy Gröbnera nad \(\displaystyle{ \mathbb{Q}}\) i nad ciałami skończonymi. Działa w szczególności na ubuntu i debianopodobnych.

Za pomocą funkcji eliminate można sobie wyeliminować z układu zmienne (jeśli się da). Ona sama dba o to, by porządek na jednomianach był odpowiedni.

Kod: Zaznacz cały


S = ZZ/11587[x,y,z,s,w,l]

I = ideal{x + y + z + s + w + l,
          x*y*z*s*w*l - 1,
          x*y + y*z + z*s + s*w + w*l + l*x,
          x*y*z + y*z*s + z*s*w + s*w*l + w*l*x + l*x*y,
          x*y*z*s + y*z*s*w + z*s*w*l + s*w*l*x + w*l*x*y + l*x*y*z,
          x*y*z*s*w + y*z*s*w*l + z*s*w*l*x + s*w*l*x*y + w*l*x*y*z + l*x*y*z*s}

eliminate({x,y,z,s,w}, I)
eliminate({x,y,z,s}, I)
eliminate({x,y,z}, I)
eliminate({x,y}, I)
eliminate({x}, I)

ODPOWIEDZ