| --- |
| library_name: kernels |
| license: apache-2.0 |
| --- |
| |
| # 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 |
|
|
| ```python |
| 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 |
| |
| | Symbol | Purpose | |
| |---|---| |
| | `groebner_basis(polys, nvars, prime)` | reduced Groebner basis of the ideal generated by `polys` | |
| | `normal_form(f, basis, prime)` | full reduction of `f` modulo `basis` | |
| | `spoly(f, g, prime)` | S-polynomial of two polynomials | |
| | `is_groebner_basis(basis, prime)` | whether every S-polynomial reduces to zero | |
| | `monomial_key(exps)` | ascending sort key for degree-reverse-lexicographic order | |
|
|
| 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 |
| |
| | system | vars | basis size | time | |
| |---|---|---|---| |
| | cyclic-5 | 5 | 20 | 919 ms | |
| | random dense (deg 4, 5) | 2 | 5 | under 100 ms | |
| |
| ## 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. |
|
|
