groebner

Groebner bases over F_p on the GPU, loadable through kernels. Degree-reverse-lexicographic order. Reference baselines: a classical single-pair Buchberger implementation compared element for element, with msolve and Singular std as the standard CPU systems.

A Groebner basis turns questions about polynomial systems, whether equations are solvable, whether a polynomial is a combination of others, what the solution set looks like, into mechanical division. Computing one is the bottleneck of computer algebra, and it has lived on the CPU. This kernel runs the linear-algebra core of the F4 algorithm, reduction of Macaulay matrices, as a GPU kernel, so basis computations over finite fields run on the same device as the rest of a modern pipeline.

Reduction modulo a computed basis: a degree-12 polynomial's monomials (cyan) cascade below the staircase carved by the basis leading terms (orange) in 66 division steps, landing exactly on the kernel's normal_form, coefficient for coefficient. The cyclic-5 system's 20-element reduced basis computes in 919 ms with every S-polynomial verified to reduce to zero.

Usage

import torch
from kernels import get_kernel

gb = get_kernel("phanerozoic/groebner", version=1, trust_remote_code=True)

P = 32003
# cyclic-3: x+y+z, xy+yz+xz, xyz-1
system = [
    {(1, 0, 0): 1, (0, 1, 0): 1, (0, 0, 1): 1},
    {(1, 1, 0): 1, (0, 1, 1): 1, (1, 0, 1): 1},
    {(1, 1, 1): 1, (0, 0, 0): P - 1},
]

basis = gb.groebner_basis(system, nvars=3, prime=P)
assert gb.is_groebner_basis(basis, P)

version selects the release branch; trust_remote_code is required by kernels for publishers without the trusted-publisher mark.

Representation

A polynomial is a dict mapping exponent tuples to coefficients in F_p. The tuple (2, 0, 1) is x^2 z in three variables. Coefficients are reduced modulo the prime on entry. The returned basis is monic, fully interreduced, and sorted by descending leading monomial.

API

The prime must be odd and below 2^31.

Method

The algorithm is F4. Critical pairs whose lcm has minimal degree are processed as one batch. For each pair the two S-polynomial rows are formed, then symbolic preprocessing closes the row set: every monomial appearing in a row that is divisible by some leading monomial of the current basis contributes the corresponding reductor as a further row, repeated until no new monomials appear.

Those rows form a Macaulay matrix whose columns are the monomials in descending order. Reducing that matrix to reduced row echelon form performs every reduction in the batch simultaneously, and that reduction is the GPU kernel: Gauss-Jordan elimination over F_p with the pivot column of each step reported back. The prime stays below 2^31 so a product of residues fits in 62 bits and Barrett reduction needs one 64-bit high-multiply.

A reduced row becomes a new basis element when its leading monomial is not already divisible by a leading monomial of the basis. Pairs with coprime leading monomials are discarded by Buchberger's first criterion. The loop ends when no pairs remain, and the result is interreduced.

Measured

Verification

The reduced Groebner basis in a fixed monomial order is unique, so the suite compares element for element against a classical single-pair Buchberger run computed independently in Python with no GPU involvement, on cyclic-3, katsura-2, and smaller systems. Buchberger's criterion is checked directly on the returned basis, every input generator is confirmed to reduce to zero modulo it, and the unit ideal, the empty ideal, and already-reduced input are covered.

Requirements and limits

• NVIDIA GPU with compute capability 8.0+.
• Coefficients in F_p, prime odd and below 2^31; drevlex order only.
• The Macaulay matrices of large systems grow quickly; cyclic-class systems beyond moderate size are research problems for every implementation.

References

Faugere, "A new efficient algorithm for computing Groebner bases (F4)" (1999); Buchberger's criterion; msolve and Singular as CPU references.

License

Apache-2.0.