The reviewed record of science sign in
Pith

arxiv: 2607.06372 · v1 · pith:3RZDX5LQ · submitted 2026-07-07 · cs.SC · math.AC

Groebner.jl: Fast Gr\"obner Tracing in Julia

Alexander Demin This is my paper

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel 2026-07-08 07:56 UTCglm-5.2pith:3RZDX5LQrecord.jsonopen to challenge →

classification cs.SC math.AC
keywords Gröbner basisF4 algorithmTraverso's tracingJuliaSIMDproduct ring arithmeticstructural identifiabilityrational univariate representation
0
0 comments X

The pith

Reusable Gröbner tracing in Julia yields up to 6.6× speedups

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents Groebner.jl, a Julia implementation of the F4 Gröbner basis algorithm that exposes Traverso's tracing — a two-stage learn/apply technique for accelerating repeated Gröbner basis computations — through a reusable public interface. During the learn stage, a single Gröbner basis computation records which S-polynomials reduce to zero. During subsequent apply stages, that trace is reused to skip those reductions for specializations of the same ideal that differ only in coefficients. The implementation also supports SIMD-friendly product-ring coefficient arithmetic (tuples of machine integers), allowing multiple modular computations to share monomial operations and enabling automatic vectorization through Julia's LLVM compiler. The author demonstrates end-to-end speedups of 1.5–6.6× in two applications: structural identifiability of ODE models and polynomial system solving via rational univariate representations. The key design contribution is making tracing available as a reusable learn/apply API rather than an internal optimization hidden inside a Gröbner basis engine, so that downstream Julia packages can benefit without reimplementing tracing infrastructure.

Core claim

The central claim is that Traverso's tracing, when exposed through a reusable learn/apply interface and combined with SIMD-friendly product-ring coefficient arithmetic in Julia, achieves 1.5–6.6× end-to-end speedups in real applications that require many Gröbner basis computations of structurally identical ideals with varying coefficients. The paper identifies the break-even point (typically 4–19 computations) at which the overhead of learning a trace is amortized, and shows that batch sizes of 8–16 primes processed simultaneously in product-ring arithmetic provide near-optimal throughput. The generic coefficient design means that product-ring arithmetic — where each element is a tuple of N=

What carries the argument

Traverso's tracing (learn/apply), F4 algorithm, product-ring coefficient arithmetic, SIMD vectorization, rational function interpolation

If this is right

  • Any computer algebra workflow in Julia that repeatedly computes Gröbner bases of specializations of the same ideal — multi-modular computation over the rationals, evaluation-interpolation for parametric systems — can directly use the learn/apply interface for speedups without modifying the F4 algorithm itself.
  • The product-ring batch approach with automatic SIMD vectorization could be adopted by other Gröbner basis engines, particularly those in languages with LLVM-based JIT compilation, to parallelize modular computations at the coefficient level without restructuring the symbolic algorithm.
  • Structural identifiability analysis of ODE models, which often requires hundreds of Gröbner basis computations, becomes substantially cheaper, potentially enabling analysis of larger or more complex dynamical systems than previously feasible.
  • The break-even analysis (4–19 computations) provides a practical decision rule: tracing is worthwhile precisely when the number of required specializations exceeds this threshold, which is typical for interpolation-based methods but not for one-off computations.

Load-bearing premise

The apply stage's correctness check compares polynomial supports against the trace and can produce false negatives — no inconsistency is detected even when the result is not actually a Gröbner basis. The paper states this is a useful proxy in practice but provides no probability bound or experimental failure rate.

What would settle it

If the false-negative rate of the apply-stage correctness check is non-trivial for certain ideal structures, downstream applications could silently consume incorrect Gröbner bases, producing wrong identifiability results or invalid polynomial system solutions without any warning.

Figures

Figures reproduced from arXiv: 2607.06372 by Alexander Demin.

Figure 1
Figure 1. Figure 1: A single iteration of the F4 algorithm as a row-reduction of a Macaulay matrix. Learn stage (on the left) and apply stage (on the right). LM denotes the leading monomial without coefficient. Learn stage. Input: a system of polynomials F1. Output: a trace. The algorithm per￾forms a modified F4 computation on F1. At each iteration, it constructs and row-reduces a Macaulay matrix. In addition to the operation… view at source ↗
read the original abstract

A standard way to control expression swell in computer algebra is to use multi-modular or evaluation-interpolation methods. In computations involving Gr\"obner bases, these techniques typically require repeatedly computing Gr\"obner bases of specializations of the same ideal. These repeated computations can be accelerated through precomputation, notably using Traverso's tracing. We present Groebner.jl (https://github.com/sumiya11/Groebner.jl), a Julia implementation of the F4 algorithm that exposes Traverso's tracing through a reusable public interface. The implementation supports SIMD-friendly coefficient types, such as tuples of machine integers, which Julia compiles to efficient code with little manual intervention. This lets other Julia software leverage tracing to obtain speedups in applications such as structural identifiability of ordinary differential equation models and polynomial system solving.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 6 minor

Summary. This paper presents Groebner.jl, a Julia implementation of the F4 algorithm that exposes Traverso's Gröbner basis tracing through a public learn/apply interface. The learn stage records which S-polynomials reduce to zero during a Gröbner basis computation; the apply stage uses this trace to skip those reductions for subsequent computations on specializations of the same ideal. The implementation supports SIMD-friendly product-ring coefficient arithmetic (tuples of machine integers), enabling batched multi-modular computation. The paper evaluates the approach on standard benchmark systems (Katsura, Cyclic, Chandra) and two real applications: polynomial system solving via rational univariate representations (Table 3) and structural identifiability of ODE models (Table 4), reporting 1.5–6.6x end-to-end speedups.

Significance. The paper makes a useful systems contribution: it exposes Traverso's tracing through a reusable public API, whereas prior high-performance implementations (msolve, Giac/Xcas) use tracing only internally. The product-ring arithmetic design leveraging Julia's LLVM-based SIMD vectorization is a practical engineering contribution, and the break-even analysis (Table 1) provides actionable guidance for practitioners. The application benchmarks on real identifiability and polynomial solving workflows demonstrate concrete end-to-end speedups. The open-source implementation and reproducible benchmarks are strengths. The paper is appropriate in scope for a software/systems contribution in symbolic computation.

major comments (2)
  1. Section 3.2: The apply stage's correctness check—comparing polynomial supports against the trace—can produce false positives (success reported when the output is not a Gröbner basis). The paper acknowledges this but does not discuss what happens downstream when a false positive occurs in the multi-modular pipelines of Tables 3–4. In multi-modular computation, a wrong Gröbner basis for one prime typically causes rational reconstruction to fail, which is then handled by retrying with additional primes. The end-to-end timings in Tables 3–4 would absorb any such retries. However, the paper does not state this mitigation explicitly, nor does it report how many primes failed reconstruction during the experiments. A reader cannot assess whether the reported speedups are 'clean' (zero false positives) or 'dirty' (some primes failed and were retried). Adding a brief discussion of this mitigation,
  2. Section 3.2: The apply stage's correctness check—comparing polynomial supports against the trace—can produce false positives (success reported when the output is not a Gröbner basis). The paper acknowledges this but does not discuss what happens downstream when a false positive occurs in the multi-modular pipelines of Tables 3–4. In multi-modular computation, a wrong Gröbner basis for one prime typically causes rational reconstruction to fail, which is then handled by retrying with additional primes. The end-to-end timings in Tables 3–4 would absorb any such retries. However, the paper does not state this mitigation explicitly, nor does it report how many primes failed reconstruction during the experiments. A reader cannot assess whether the reported speedups are 'clean' (zero false positives) or 'dirty' (some primes failed and were retried). Adding a brief discussion of this mitigation,
minor comments (6)
  1. Section 4.2: The claim that Julia 'often automatically generates SIMD-optimized assembly' for product-ring tuple operations is supported only by a footnote pointing to code_native. A brief quantitative comparison (e.g., instruction counts or throughput) between the generated SIMD code and the scalar case would strengthen the architecture claims.
  2. Table 2, Yang1 row: The speedup for Yang1 is notably lower than other systems (1.24 at N=8, declining to 0.95 at N=32). The paper attributes this to tracing already eliminating most monomial operations, but the decline below 1.0 at N=32 is not discussed. A brief note on why throughput degrades below the scalar baseline for large N would help.
  3. Table 1: The break-even column reports the number of computations needed to amortize the learn cost, but the formula used to compute this is not stated. Adding the formula (e.g., ceil(Learn / (Classic - Apply)) or similar) would make the table self-contained.
  4. Section 5: The paper does not report the number of primes used in the multi-modular computations for Tables 3–4. This information would help readers assess the amortization of the learn cost and is a common reader question.
  5. Section 3.2: The code examples use Groebner.Examples.katsuran(10) and change_base_ring without import context. A brief note on which package provides change_base_ring (presumably Nemo.jl) would improve readability.
  6. The GitHub URL in the abstract (https://github.com/sumiya11/Groebner.jl) and the version number (0.10.3, Section 5) are noted, but no commit hash or DOI for the exact version used in experiments is provided. Including this would strengthen reproducibility.

Simulated Author's Rebuttal

1 responses · 0 unresolved

The referee raises a single substantive point (duplicated in the report): the paper does not discuss how false positives from the apply stage's correctness check are handled in multi-modular pipelines, nor does it report whether any primes failed reconstruction during the experiments. We agree this should be addressed and will add the relevant discussion and data.

read point-by-point responses

  1. Referee: Section 3.2: The apply stage's correctness check can produce false positives, and the paper does not discuss downstream mitigation in multi-modular pipelines (Tables 3-4), nor report how many primes failed reconstruction during experiments.

    Authors: The referee is correct that the paper does not currently explain the mitigation mechanism or report false-positive rates. We will address this in the revision. To clarify the situation: in both application pipelines (rational univariate representation and structural identifiability), the downstream rational reconstruction step serves as an independent correctness check. If a false positive from groebner_apply! produces an incorrect Gröbner basis for one prime, rational reconstruction for that prime fails, and the pipeline automatically retries with an additional prime. The end-to-end timings in Tables 3-4 absorb any such retries. We will add a brief paragraph in Section 3.2 explaining this mitigation explicitly. We will also report the number of failed reconstructions observed during the experiments. In our experiments, zero false positives occurred across all benchmark systems in Tables 3-4, so the reported timings are 'clean' in the referee's terminology. We will state this explicitly in the revised text. revision: yes

Circularity Check

0 steps flagged

No circularity found: systems paper with self-contained benchmarks and independent external comparisons

full rationale

This is a systems paper presenting an implementation (Groebner.jl) and its performance benchmarks. The central claims—1.5–6.6x speedups from tracing and batched product-ring arithmetic—are measured against an independent baseline (the same system's non-tracing F4 implementation, justified in Remark 1 as state-of-the-art randomized linear algebra). The speedup numbers in Tables 1–4 are empirical measurements, not derivations that could be circular. Self-citations to [5], [6], and [10] reference prior algorithmic work (rational univariate representations, identifiable function generators, and the Groebner.jl package itself), but these are used to define the application context, not to prove the performance claims. The tracing technique itself (Traverso's tracing [19]) is attributed to external work. The apply-stage correctness check (Section 3.2) is a heuristic with acknowledged false positives, but this is a correctness concern, not circularity—the paper does not claim the check proves correctness, only that it is 'a useful proxy.' No step in the paper's argument reduces to its inputs by construction.

Axiom & Free-Parameter Ledger

2 free parameters · 4 axioms · 0 invented entities

No new mathematical entities, particles, forces, or dimensions are introduced. The paper is a software systems contribution. The free parameters (batch size N, prime choices) are engineering heuristics, not theoretical constructs. The axioms are domain assumptions about the correctness and practicality of established algorithms (Traverso tracing, F4, SIMD auto-vectorization), all traceable to prior literature or empirical observation.

free parameters (2)
  • Batch size N (internal default) = 4
    Section 4.3 and Remark 3: Groebner.jl internally uses N=4 for multi-modular computation. Table 2 shows this is a heuristic choice based on the throughput saturation observed at N=8–16, balanced against memory growth (2.7GB to 29.3GB for Katsura-13).
  • Prime selection (2^30+3, 2^30+7, 2^30+9, 2^30+15) = Specific 31-bit primes
    Section 4.2 code listing: these are chosen as 31-bit primes fitting in Int64 for the product-ring SIMD example. The choice is conventional for modular Gröbner basis computation.
axioms (4)
  • domain assumption Traverso's tracing is correct: the trace recorded during learn captures coefficient-independent structural information that remains valid for specializations of the same ideal.
    Section 2: the paper describes tracing but defers to [19] (Traverso 1989) for correctness. The entire learn/apply framework depends on this.
  • domain assumption The support-comparison check in apply is a sufficient correctness proxy in practice.
    Section 3.2: 'This test may produce false positives... In practice, however, it can still serve as a useful proxy.' No probability bound or empirical failure rate is given.
  • domain assumption Julia's LLVM compiler generates efficient SIMD code for tuple-of-Int64 product-ring arithmetic across architectures.
    Section 4.2: 'Julia, via LLVM, often automatically generates SIMD-optimized assembly.' This is observed empirically on Intel; ARM (Apple M2 Max) is noted as less effective.
  • standard math The F4 algorithm with randomized linear algebra (following Magma/Monagan-Pearce) is the appropriate state-of-the-art baseline.
    Remark 1: the baseline is Groebner.jl's own implementation using techniques from [3, 16]. This is a reasonable baseline choice.

pith-pipeline@v1.1.0-glm · 11343 in / 2905 out tokens · 287989 ms · 2026-07-08T07:56:54.650300+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages · 2 internal anchors

  1. [1]

    Ahmed, S., Crepeau, N., Dessauer, P.R., Edozie, A., Garcia-Lopez, O., Grimsley, T., Garcia, J.L., Neri, V., Shiu, A.: Identifiability of directed-cycle and catenary linearcompartmentalmodels.SIAMJournalonAppliedDynamicalSystems25(1), 304–350 (2026).https://doi.org/10.1137/25M1728636

    work page doi:10.1137/25m1728636 2026

  2. [2]

    In: Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation

    Berthomieu,J.,Eder,C.,SafeyElDin,M.:msolve:Alibraryforsolvingpolynomial systems. In: Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation. pp. 51–58 (2021).https://doi.org/10.1145/3452143. 3465545

    work page doi:10.1145/3452143 2021

  3. [3]

    Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system. I. The user language. J. Symbolic Comput.24(3-4), 235–265 (1997).https://doi.org/10. 1006/jsco.1996.0125,http://dx.doi.org/10.1006/jsco.1996.0125, Computa- tional algebra and number theory (London, 1993)

    work page doi:10.1006/jsco.1996.0125 1997

  4. [4]

    Drug Design and Delivery1(4), 333–348 (May 1987), https://pubmed.ncbi.nlm.nih.gov/2855567/

    Demignot, S., Domurado, D.: Effect of prosthetic sugar groups on the pharmacoki- netics of glucose-oxidase. Drug Design and Delivery1(4), 333–348 (May 1987), https://pubmed.ncbi.nlm.nih.gov/2855567/

    work page arXiv 1987

  5. [5]

    arXiv preprint arXiv:2602.10878 (2026),https://arxiv.org/abs/2602.10878 10 Demin

    Demin, A., Pogudin, G.: Simple generators of rational function fields. arXiv preprint arXiv:2602.10878 (2026),https://arxiv.org/abs/2602.10878 10 Demin

    work page arXiv 2026

  6. [6]

    Reading Rational Univariate Representations on lexicographic Groebner bases

    Demin, A., Rouillier, F., Ruiz, J.: Reading rational univariate representations on lexicographic Gröbner bases. arXiv preprint arXiv:2402.07141 (2024),https:// arxiv.org/abs/2402.07141

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  7. [7]

    SIAM Journal on Applied Algebra and Geometry7(1), 194–235 (2023).https: //doi.org/10.1137/22M1469067,https://doi.org/10.1137/22M1469067

    Dong, R., Goodbrake, C., Harrington, H.A., Pogudin, G.: Differential elimination for dynamical models via projections with applications to structural identifiability. SIAM Journal on Applied Algebra and Geometry7(1), 194–235 (2023).https: //doi.org/10.1137/22M1469067,https://doi.org/10.1137/22M1469067

    work page doi:10.1137/22m1469067 2023

  8. [8]

    Journal of Pure and Applied Algebra139(1–3), 61–88 (1999).https://doi.org/10.1016/S0022-4049(99)00005-5

    Faugère, J.C.: A new efficient algorithm for computing Gröbner bases without reduction to zero (F4). Journal of Pure and Applied Algebra139(1–3), 61–88 (1999).https://doi.org/10.1016/S0022-4049(99)00005-5

    work page doi:10.1016/s0022-4049(99)00005-5 1999

  9. [9]

    Chaos, Solitons & Fractals 140, 110244 (2020),http://dx.doi.org/10.1016/j.chaos.2020.110244

    Fokas, A., Cuevas-Maraver, J., Kevrekidis, P.: A quantitative framework for ex- ploring exit strategies from the COVID-19 lockdown. Chaos, Solitons & Fractals 140, 110244 (2020),http://dx.doi.org/10.1016/j.chaos.2020.110244

    work page doi:10.1016/j.chaos.2020.110244 2020

  10. [10]

    Groebner.jl: A package for Gr\"obner bases computations in Julia

    Gowda, S., Demin, A.: Groebner.jl: A package for Gröbner bases computations in Julia. arXiv preprint arXiv:2304.06935 (2023),https://arxiv.org/abs/2304. 06935

    work page internal anchor Pith review Pith/arXiv arXiv 2023

  11. [11]

    Journal of Symbolic Computation15(2), 199–209 (1993),https://www.informatik.uni-leipzig.de/~graebe/ComputerAlgebra/ Publications/olp.pdf

    Gräbe, H.G.: On lucky primes. Journal of Symbolic Computation15(2), 199–209 (1993),https://www.informatik.uni-leipzig.de/~graebe/ComputerAlgebra/ Publications/olp.pdf

    work page 1993

  12. [12]

    ACM Trans

    van der Hoeven, J., Lecerf, G., Quintin, G.: Modular simd arithmetic in math- emagix. ACM Trans. Math. Softw.43(1) (Aug 2016).https://doi.org/10.1145/ 2876503,https://doi.org/10.1145/2876503

    work page doi:10.1145/2876503 2016

  13. [13]

    Cryptology ePrint Archive, Paper 2010/158 (2010),https://eprint.iacr.org/2010/158

    Joux, A., Vitse, V.: A variant of the F4 algorithm. Cryptology ePrint Archive, Paper 2010/158 (2010),https://eprint.iacr.org/2010/158

    work page 2010

  14. [14]

    MS project report, Simon Fraser Univ

    de Kleine, J., Monagan, M.: A modular design and implementation of Buchberger’s algorithm. MS project report, Simon Fraser Univ. (2001)

    work page 2001

  15. [15]

    Kouba, R., Neiger, V., Din, M.S.E.: A complexity analysis of the f4 gröbner basis algorithm with tracer data (2026),https://arxiv.org/abs/2603.16378

    work page arXiv 2026

  16. [16]

    In: Pro- ceedings of the 2015 International Workshop on Parallel Symbolic Computation

    Monagan, M., Pearce, R.: A compact parallel implementation of F4. In: Pro- ceedings of the 2015 International Workshop on Parallel Symbolic Computation. pp. 95–100. PASCO ’15, Association for Computing Machinery, New York, NY, USA(2015).https://doi.org/10.1145/2790282.2790293,https://doi.org/10. 1145/2790282.2790293

    work page doi:10.1145/2790282.2790293 2015

  17. [17]

    univ-grenoble-alpes.fr/~parisse/giac.html(2026), version 2.0.0

    Parisse, B., De Graeve, R.: Giac/xcas.http://www-fourier. univ-grenoble-alpes.fr/~parisse/giac.html(2026), version 2.0.0

    work page 2026

  18. [18]

    Applicable Algebra in Engineering, Communication and Computing 9(5), 433–461 (1999).https://doi.org/10.1007/s002000050114

    Rouillier, F.: Solving zero-dimensional systems through the rational univariate rep- resentation. Applicable Algebra in Engineering, Communication and Computing 9(5), 433–461 (1999).https://doi.org/10.1007/s002000050114

    work page doi:10.1007/s002000050114 1999

  19. [19]

    In: Gianni, P

    Traverso, C.: Gröbner trace algorithms. In: Gianni, P. (ed.) Symbolic and Algebraic Computation. pp. 125–138. Springer, Berlin, Heidelberg (1989).https://doi.org/ 10.1007/3-540-51084-2_12

    work page doi:10.1007/3-540-51084-2_12 1989