2.9. Thuật toán Buchberger

Thuật toán Buchberger xây dựng cơ sở Gröbner bằng cách liên tục sửa những cặp đa thức chưa thỏa tiêu chuẩn Buchberger. Đây là thuật toán nền tảng để hiểu các phương pháp hiện đại như F4 và F5.

2.9.1. Thuật toán

Đầu vào là \(F=\{f_1,\ldots,f_s\}\). Đặt \(G\leftarrow F\) và tạo tập \(P\) chứa mọi cặp chỉ số của \(G\).

Khi \(P\) chưa rỗng:

  1. lấy một cặp \((i,j)\) khỏi \(P\);

  2. tính \(r=\operatorname{NF}_G(S(g_i,g_j))\);

  3. nếu \(r\ne0\), thêm \(r\) vào \(G\) và thêm vào \(P\) mọi cặp giữa \(r\) với các phần tử cũ.

Khi không còn cặp nào, mọi đa thức S đều rút gọn về không, nên theo tiêu chuẩn Buchberger, \(G\) là một cơ sở Gröbner.

G := F
P := {(i, j) | 0 <= i < j < |G|}
while P is not empty:
    (i, j) := select(P)
    r := normal_form(S(G[i], G[j]), G)
    if r != 0:
        append r to G
        add all pairs (old polynomial, r) to P
return G

2.9.2. Ví dụ

Xét \(F=\{f_1,f_2\}\subset\QQ[x,y]\) theo thứ tự lex \(x>y\), với

\[f_1=x^2-y,\qquad f_2=xy-1.\]

BCNN của \(\LM(f_1)=x^2\) và \(\LM(f_2)=xy\) là \(x^2y\). Do đó

\[S(f_1,f_2)=y f_1-x f_2=x-y^2.\]

Phần dư khác không nên ta thêm \(f_3=x-y^2\). Cặp mới lại sinh ra quan hệ \(y^3-1\). Sau khi xử lý hết các cặp và rút gọn, ta nhận được một hệ dạng tam giác; có thể giải \(y\) trước rồi suy ra \(x=y^2\).

2.9.3. Liên hệ với mã nguồn CudaPolynomial

Hiện thực trong src/BuchbergerAlgorithm.cpp bám sát giả mã:

  • pairs lưu các cặp tới hạn và chọn phần tử cuối, tức chiến lược ngăn xếp;

  • SPoly lấy BCNN hai đơn thức dẫn đầu;

  • PolynomialDivision trả phần dư ở phần tử đầu của vector kết quả;

  • mỗi phần dư khác không được thêm vào G và ghép cặp với toàn bộ phần tử cũ.

Các đa thức của dự án nằm trên \(\FF_2\), vì vậy SPoly dùng phép cộng: \(a-b=a+b\) trong trường đặc số hai. Đơn thức được biểu diễn bằng vector số mũ và được sắp theo graded lexicographic trong DeglexOrdering.

2.9.4. Chi phí và điểm nghẽn

Hai nguồn tăng chi phí là số cặp tới hạn và phép chia đa thức. Mỗi phần dư mới làm cơ sở lớn hơn, đồng thời sinh thêm nhiều cặp. Hơn nữa, kết quả xử lý một cặp có thể thay đổi cơ sở dùng để rút gọn cặp tiếp theo. Sự phụ thuộc này khiến vòng lặp chính của Buchberger khó song song hóa trực tiếp.

Các hiện thực thực tế thường cải thiện bằng cách:

  • dùng tiêu chuẩn để loại cặp chắc chắn cho phần dư bằng không;

  • chọn cặp theo bậc BCNN thay vì thứ tự thêm vào;

  • interreduce cơ sở trong quá trình tính;

  • gom nhiều cặp và thay các phép chia riêng lẻ bằng đại số tuyến tính, chính là ý tưởng của F4.