Fast Rational Univariate Representation via Gaussian Elimination

Alexander Demin; Fabrice Rouillier

arxiv: 2607.06397 · v1 · pith:QK4UQSEI · submitted 2026-07-07 · cs.SC · cs.DS· math.AC

Fast Rational Univariate Representation via Gaussian Elimination

Alexander Demin , Fabrice Rouillier This is my paper

Reviewed by Pith2026-07-08 06:58 UTCglm-5.2pith:QK4UQSEI open to challenge →

classification cs.SC cs.DSmath.AC

keywords rational univariate representationFGLM algorithmGaussian eliminationzero-dimensional idealsGröbner basespolynomial systemssparse linear algebraJulia

0 comments

The pith

Dense Gaussian elimination beats sparse methods for polynomial root parametrization

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

This paper argues that classical dense Gaussian elimination is a better practical choice than sparse linear algebra (such as the Wiedemann algorithm) for computing rational univariate representations of zero-dimensional polynomial systems. A rational univariate representation encodes all roots of a polynomial system using one univariate polynomial and rational parametrizations of each coordinate. The standard FGLM approach to computing these representations relies on multiplication matrices, and recent solvers have favored sparse methods to exploit matrix sparsity. The authors present three observations that overturn this preference: first, multiplication matrices are often only moderately sparse in practice (median density around 19.5% across 45 benchmarks), which blunts the advantage of sparse methods; second, the cost of matrix-vector products is comparable to the cost of Gaussian elimination itself, so replacing Gaussian elimination with a faster sparse relation-finder (like Berlekamp-Massey) saves little because it requires roughly twice as many matrix-vector products; third, the row echelon form computed during the minimal polynomial stage can be reused directly in the subsequent bivariate elimination stage, amortizing the cost of dense elimination across the entire algorithm. The authors implement this approach in a Julia package and demonstrate that it computes certified parametrizations for systems with thousands of roots in seconds, competitively with or faster than state-of-the-art solvers.

Core claim

The central discovery is an engineering argument, not a new theorem: that the standard justification for sparse linear algebra in the FGLM stage does not hold in practice because the multiplication matrices are too dense, the matrix-vector products are too expensive, and the row echelon form from Gaussian elimination can be reused downstream. The reuse mechanism is the key structural insight — the incremental Gaussian elimination produces a row echelon basis of the vectors v(1), v(T), ..., v(T^{d-1}), and this same basis serves as the starting point for computing the bivariate elimination ideals needed to recover coordinate parametrizations. This means the cost of dense elimination is paid一次

What carries the argument

Incremental Gaussian elimination maintaining a packed lower-triangular times row-echelon decomposition, with delayed modular reduction enabling SIMD vectorization; reuse of the row echelon form across the minimal polynomial and bivariate elimination stages

If this is right

Systems with multiplication matrix density above ~10% will likely favor dense Gaussian elimination over Wiedemann-type sparse methods, giving a practical threshold for choosing between the two approaches.
The reuse of row echelon forms across algorithmic stages suggests that other parts of the FGLM pipeline might benefit from similar amortization strategies, potentially reducing the appeal of stage-by-stage optimization.
The deterministic certification provided by Gaussian elimination eliminates the need for probabilistic verification, which could simplify multi-modular computations for systems with rational coefficients.
If the benchmark suite's density distribution generalizes, sparse-FGLM methods may be relegated to a narrow class of problems with genuinely sparse multiplication matrices.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The 19.5% median density threshold suggests a natural problem partition: problems below this density favor sparse methods, above it favor dense methods. A hybrid solver that estimates matrix density before choosing a strategy could dominate both approaches.
The argument that matrix-vector products are non-negligible even for moderately sparse matrices implies that the crossover point where sparse methods win depends on both density and matrix size, not density alone — a two-dimensional decision boundary that the paper does not fully characterize.
The reuse of the row echelon form is structurally analogous to caching a partial LU decomposition; similar reuse strategies might apply to other algebraic algorithms that share intermediate linear algebra across stages.

Load-bearing premise

The claim that multiplication matrices are 'often only moderately sparse' rests on 45 benchmark examples whose selection is not justified against any sampling frame; if other problem classes produce sparser matrices, the dense linear algebra advantage diminishes.

What would settle it

A benchmark suite of zero-dimensional ideals whose multiplication matrices have density consistently below 5%, on which the Wiedemann approach would outperform this implementation — if such problems are common in practice, the dense approach loses its practical advantage.

Figures

Figures reproduced from arXiv: 2607.06397 by Alexander Demin, Fabrice Rouillier.

**Figure 1.** Figure 1: Density of the multiplication matrix MT , measured as the ratio of nonzero entries. In each example, the radical is put in shape position with respect to T [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗

read the original abstract

In this note, we present RationalUnivariateRepresentation.jl (https://newrur.gitlabpages.inria.fr/RationalUnivariateRepresentation.jl/), a Julia package for computing rational univariate representations of zero-dimensional polynomial systems. The package uses dense linear algebra and Gaussian elimination for the FGLM-like stage. The purpose of this contribution is to advocate for this choice and explain the implementation details that turn the algorithm into practical software. In particular, we show that our implementation can compute guaranteedly correct parametrizations of ideals with thousands of solutions within seconds.

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.

Desk Editor's Note private letter to a colleague

Implementation note with real engineering contributions and honest but limited experiments; deserves a serious referee.

read the letter

This is a solid implementation note. The main thing to know: the authors ship a working Julia package (RationalUnivariateRepresentation.jl) that computes certified RURs using dense Gaussian elimination, and they make a genuine practical observation that the row echelon form computed during minimal polynomial extraction can be reused for the bivariate elimination bases (Section 4.3). That reuse, plus the delayed modular reduction trick (28-bit primes, 64-bit accumulators, 27 AXPYs before reduction), is the real engineering contribution here. The code is public and the algorithmic description is clear enough to reproduce. Table 1, which shows that matrix-vector products and Gaussian elimination cost roughly the same order of magnitude, is a useful data point for anyone deciding between dense and sparse approaches. The density plot (Figure 1) is also informative, even if limited. Credit where it's due: the deterministic certification via the separation test from [2] and the echelon-form amortization are the two ideas that make this more than a naive reimplementation. The paper is honest about scope — it explicitly says multi-modular computation over rationals is out of scope and that comparisons with msolve and Giac are difficult. That honesty is refreshing. The soft spots are real but proportionate. The benchmark suite is small: 7 systems in Table 2, 45 in Figure 1, with no sampling frame. The density argument rests on those 45 examples, and the paper doesn't try to claim representativeness it can't justify. The msolve comparison is confounded — msolve fails on 2 of 7 benchmarks with 'not generic,' and the paper itself says direct comparison is hard. The abstract's 'competitive with state-of-the-art software' is stronger than what Table 2 actually supports, given that msolve's failures may reflect configuration issues rather than algorithmic disadvantage. But I don't think this is a load-bearing flaw. The paper is a short note advocating for a design choice, not a comprehensive benchmarking study. The engineering is real, the observations are useful, and the implementation is available for anyone to test. This is for computer algebra practitioners who need certified RURs and want to understand when dense linear algebra is the right call. It deserves a serious referee — the kind who can push back on the benchmark breadth and the competitiveness claim while recognizing the genuine contributions.

Referee Report

2 major / 7 minor

Summary. This paper presents RationalUnivariateRepresentation.jl, a Julia package for computing rational univariate representations (RUR) of zero-dimensional polynomial systems. The implementation uses dense linear algebra and incremental Gaussian elimination for the FGLM-like stage, following the algorithm of Demin, Rouillier, and Ruiz [2]. The authors argue that multiplication matrices encountered in practice are often only moderately sparse, making dense Gaussian elimination competitive with sparse methods (Wiedemann/Block Krylov). Experimental results on 7 benchmark systems compare the implementation against msolve 0.10.0, showing favorable timings on several examples. The paper is primarily an implementation report with motivating empirical observations.

Significance. The paper provides a well-specified, publicly available implementation (RationalUnivariateRepresentation.jl) with reproducible benchmark methodology (stated compiler flags, msolve version, hardware). The implementation produces certified parametrizations deterministically, which is a meaningful practical contribution. The observation about multiplication matrix density (Figure 1, 45 examples, median ~19.5%) and the cost comparison between matrix-vector products and Gaussian elimination (Table 1) provide useful empirical grounding for the dense-linear-algebra design choice. The reuse of the row echelon form across computation stages (Section 4.3) is a legitimate engineering insight that amortizes cost.

major comments (2)

Section 5.1, Figure 1: The claim that multiplication matrices are 'often only moderately sparse' is a load-bearing motivation for the dense-linear-algebra design, but the 45-example benchmark suite has no stated sampling frame. The authors do not explain how these examples were selected or why they are representative of zero-dimensional ideals encountered in practice. Without this justification, the generalizability of the density observation is unclear. The authors should either (a) describe the selection criteria for the 45 examples and argue for representativeness, or (b) temper the claim from 'in practice' to 'on the tested benchmark suite.'
Abstract and Section 6: The abstract claims the implementation is 'competitive with state-of-the-art software,' and Section 6 states 'It is difficult to compare our implementation with msolve or Giac.' Yet Table 2 shows msolve fails with 'not generic' on 2 of 7 benchmarks, and the paper itself attributes this to msolve's recomputation strategy rather than a controlled algorithmic comparison. The competitive claim in the abstract is stronger than what the evidence supports. The authors should either soften the abstract claim to match the caveats in Section 6, or provide additional benchmarks where both tools complete successfully on comparable configurations.

minor comments (7)

Section 4.2: The statement that 'we may accumulate 27 such row multiples in one buffer before modular reduction is required' with a 28-bit prime and 64-bit integers should be verified: 2^27 * (2^28 - 1) is close to 2^55, which fits in 64 bits, but the exact bound and overflow analysis should be stated explicitly.
Table 1: The system names (Chandra-13, Eco-14, etc.) differ from those in Table 2 (Katsura-13-EXT, Chandra-13-EXT, etc.). Clarify the relationship between the two tables and what the '-EXT' suffix denotes.
Section 5.1, Figure 1: The figure is difficult to read; the system labels are small and overlapping. A table with density values or a clearer bar chart would improve readability.
Section 6: The hardware description 'MacBook PRO MAX m2 running OSX 26.5' is informal. A more precise specification (CPU model, core count, memory bandwidth) would aid reproducibility.
Algorithm 1, step (4): The loop 'For i = 1, 2, ... do' has no explicit termination bound stated. While the text mentions termination occurs at i = d, adding an explicit bound (e.g., i <= D) in the algorithm pseudocode would improve clarity.
Reference [2] is cited as 'arXiv preprint arXiv:2402.07141 (2024).' If a published or refereed version exists, the updated citation should be provided.
Section 4.1, Case 3: The choice of variable x_k dividing w_j is described but no tie-breaking rule is specified. A brief note on the heuristic used (or a statement that any choice suffices) would be helpful.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and the constructive feedback. Both major comments are well-taken and will be addressed in the revised manuscript.

read point-by-point responses

Referee: Section 5.1, Figure 1: The claim that multiplication matrices are 'often only moderately sparse' is a load-bearing motivation for the dense-linear-algebra design, but the 45-example benchmark suite has no stated sampling frame. The authors do not explain how these examples were selected or why they are representative of zero-dimensional ideals encountered in practice. Without this justification, the generalizability of the density observation is unclear. The authors should either (a) describe the selection criteria for the 45 examples and argue for representativeness, or (b) temper the claim from 'in practice' to 'on the tested benchmark suite.'

Authors: The referee is correct that the 45-example suite lacks a stated sampling frame and that the generalizability claim is not fully justified as written. We will address this by taking approach (b): tempering the claim. Specifically, in the revision we will (1) add a brief description of the benchmark suite composition, noting that it consists of standard test systems from the symbolic computation literature (Katsura, Eco, Noon, Reimer, Henrion, Chandra families, and others commonly used in FGLM benchmarks), and (2) rephrase the claim from 'multiplication matrices encountered in practice' to 'multiplication matrices encountered on our benchmark suite' in both Section 5.1 and the Conclusion. We will retain the empirical observation itself, which is factual for the tested examples, but will not claim it generalizes beyond them without further evidence. revision: yes
Referee: Abstract and Section 6: The abstract claims the implementation is 'competitive with state-of-the-art software,' and Section 6 states 'It is difficult to compare our implementation with msolve or Giac.' Yet Table 2 shows msolve fails with 'not generic' on 2 of 7 benchmarks, and the paper itself attributes this to msolve's recomputation strategy rather than a controlled algorithmic comparison. The competitive claim in the abstract is stronger than what the evidence supports. The authors should either soften the abstract claim to match the caveats in Section 6, or provide additional benchmarks where both tools complete successfully on comparable configurations.

Authors: The referee is right that the abstract's claim of being 'competitive with state-of-the-art software' is stronger than what the evidence in Table 2 supports, given that msolve does not complete on 2 of 7 benchmarks and the comparison is not fully controlled. We will soften the abstract claim. In the revision, the abstract will say that the implementation achieves 'favorable performance compared to state-of-the-art software on several benchmark systems,' which accurately reflects Table 2. We will also add a sentence in Section 6 explicitly acknowledging that the comparison is not a controlled algorithmic benchmark, since msolve and our implementation differ in their handling of non-generic quotients and in their recomputation strategies. We considered adding further benchmarks where both tools complete, but the 5 systems where both tools finish already show a mixed picture (our implementation is faster on 4, slower on 1), so we believe the softened claim is the honest characterization. revision: yes

Circularity Check

0 steps flagged

No significant circularity: implementation report with self-cited algorithm, but performance claims tested against external benchmarks.

full rationale

This paper is an implementation report, not a derivation. The algorithm is explicitly attributed to Demin, Rouillier, and Ruiz [2], and the present paper does not re-derive that algorithm's correctness—it implements it. The self-citation to [2] is load-bearing for the algorithm's theoretical guarantees (shape position test, parametrization recovery formulas), but the paper's central claims are empirical: (1) multiplication matrices are often moderately sparse (Section 5.1, Figure 1), (2) dense Gaussian elimination is competitive (Table 2), and (3) the row echelon form can be reused (Section 4.3). These claims are tested against external benchmarks and an external competitor (msolve). The density observations are empirical measurements, not derived from the authors' own theory. The performance comparisons, while acknowledged as imperfect ('It is difficult to compare our implementation with msolve or Giac'), are run against independently developed software. No step in the paper reduces to its inputs by construction. The self-citation to [2] is standard practice for an implementation paper and does not create circularity because the present paper's claims (performance, density) are not theorems proved in [2].

Axiom & Free-Parameter Ledger

1 free parameters · 3 axioms · 0 invented entities

No new mathematical entities or physical objects are invented. The free parameter (linear form coefficients) is a standard algorithmic choice, not an ad hoc fitting parameter. The axioms are either standard results in algebraic geometry or reliance on the authors' prior algorithmic work [2].

free parameters (1)

Linear form coefficients a_1,...,a_n = random or sparse
Chosen in step (2) of Algorithm 1. The paper notes random choice is reliable, and sparse forms may be tried first. Not fitted to data but a design choice.

axioms (3)

domain assumption The algorithm of Demin, Rouillier, and Ruiz [2] correctly computes RUR and verifies shape position
The entire implementation is built on this algorithm (Section 3). The correctness of the parametrization and the injectivity test (Lemma 1) depend on results proven in [2].
standard math Over an infinite field k, there exists a linear form t such that sqrt(I_T) is in shape position
Stated in Section 2.2, citing Rouillier [8]. This is a standard result in computational algebraic geometry.
domain assumption The benchmark suite of 45 examples is representative of practical zero-dimensional ideals
The density argument in Section 5.1 and the performance comparisons in Table 2 depend on this representativeness, which is not justified against a sampling frame.

pith-pipeline@v1.1.0-glm · 11559 in / 1856 out tokens · 382340 ms · 2026-07-08T06:58:37.400421+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages · 3 internal anchors

[1]

Reading Rational Univariate Representations on lexicographic Groebner bases

Demin, Alexander and Rouillier, Fabrice and Ruiz, Joao , title =. arXiv preprint arXiv:2402.07141 , year =

work page internal anchor Pith review Pith/arXiv arXiv
[2]

, journal=

Wiedemann, D. , journal=. Solving sparse linear equations over finite fields , year=

work page
[3]

Applicable Algebra in Engineering, Communication and Computing , volume =

Rouillier, Fabrice , title =. Applicable Algebra in Engineering, Communication and Computing , volume =. 1999 , doi =

work page 1999
[4]

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

Gowda, Shashi and Demin, Alexander , title =. arXiv preprint arXiv:2304.06935 , year =

work page internal anchor Pith review Pith/arXiv arXiv
[5]

Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation , year =

Fieker, Claus and Hart, William and Hofmann, Tommy and Johansson, Fredrik , title =. Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation , year =

work page 2017
[6]

Journal of Symbolic Computation , volume =

Faug\`ere, Jean-Charles and Gianni, Patrizia and Lazard, Daniel and Mora, Teo , title =. Journal of Symbolic Computation , volume =

work page
[7]

Journal of Symbolic Computation , volume =

Faug\`ere, Jean-Charles and Mou, Chenqi , title =. Journal of Symbolic Computation , volume =. 2017 , doi =

work page 2017
[8]

Hyun, Seung Gyu and Neiger, Vincent and Rahkooy, Hamid and Schost,. Block-. Journal of Symbolic Computation , volume =. 2020 , note =. doi:10.1016/j.jsc.2019.07.010 , url =

work page doi:10.1016/j.jsc.2019.07.010 2020
[9]

Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation , year =

Berthomieu, J\'er\'emy and Eder, Christian and Safey El Din, Mohab , title =. Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation , year =

work page 2021
[10]

, title =

Bezanson, Jeff and Edelman, Alan and Karpinski, Stefan and Shah, Viral B. , title =. SIAM Review , volume =

work page
[11]

Traverso, Carlo , title =

work page
[12]

Demin, Alexander , title =

work page
[13]

Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation , year =

Kobel, Alexander and Rouillier, Fabrice and Sagraloff, Michael , title =. Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation , year =

work page 2016
[14]

2023 , doi =

Berthomieu, J\'er\'emy and Graillat, Stef and Lesnoff, Dimitri and Mary, Th\'eo , title =. 2023 , doi =

work page 2023
[15]

Certifying a probabilistic parallel modular algorithm for rational univariate representation

Parisse, Bernard , title =. arXiv preprint arXiv:2106.10912 , year =

work page internal anchor Pith review Pith/arXiv arXiv
[16]

Demin, Alexander and Rouillier, Fabrice , title =

work page

[1] [1]

Reading Rational Univariate Representations on lexicographic Groebner bases

Demin, Alexander and Rouillier, Fabrice and Ruiz, Joao , title =. arXiv preprint arXiv:2402.07141 , year =

work page internal anchor Pith review Pith/arXiv arXiv

[2] [2]

, journal=

Wiedemann, D. , journal=. Solving sparse linear equations over finite fields , year=

work page

[3] [3]

Applicable Algebra in Engineering, Communication and Computing , volume =

Rouillier, Fabrice , title =. Applicable Algebra in Engineering, Communication and Computing , volume =. 1999 , doi =

work page 1999

[4] [4]

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

Gowda, Shashi and Demin, Alexander , title =. arXiv preprint arXiv:2304.06935 , year =

work page internal anchor Pith review Pith/arXiv arXiv

[5] [5]

Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation , year =

Fieker, Claus and Hart, William and Hofmann, Tommy and Johansson, Fredrik , title =. Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation , year =

work page 2017

[6] [6]

Journal of Symbolic Computation , volume =

Faug\`ere, Jean-Charles and Gianni, Patrizia and Lazard, Daniel and Mora, Teo , title =. Journal of Symbolic Computation , volume =

work page

[7] [7]

Journal of Symbolic Computation , volume =

Faug\`ere, Jean-Charles and Mou, Chenqi , title =. Journal of Symbolic Computation , volume =. 2017 , doi =

work page 2017

[8] [8]

Hyun, Seung Gyu and Neiger, Vincent and Rahkooy, Hamid and Schost,. Block-. Journal of Symbolic Computation , volume =. 2020 , note =. doi:10.1016/j.jsc.2019.07.010 , url =

work page doi:10.1016/j.jsc.2019.07.010 2020

[9] [9]

Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation , year =

Berthomieu, J\'er\'emy and Eder, Christian and Safey El Din, Mohab , title =. Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation , year =

work page 2021

[10] [10]

, title =

Bezanson, Jeff and Edelman, Alan and Karpinski, Stefan and Shah, Viral B. , title =. SIAM Review , volume =

work page

[11] [11]

Traverso, Carlo , title =

work page

[12] [12]

Demin, Alexander , title =

work page

[13] [13]

Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation , year =

Kobel, Alexander and Rouillier, Fabrice and Sagraloff, Michael , title =. Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation , year =

work page 2016

[14] [14]

2023 , doi =

Berthomieu, J\'er\'emy and Graillat, Stef and Lesnoff, Dimitri and Mary, Th\'eo , title =. 2023 , doi =

work page 2023

[15] [15]

Certifying a probabilistic parallel modular algorithm for rational univariate representation

Parisse, Bernard , title =. arXiv preprint arXiv:2106.10912 , year =

work page internal anchor Pith review Pith/arXiv arXiv

[16] [16]

Demin, Alexander and Rouillier, Fabrice , title =

work page