pith. sign in

arxiv: 2605.20884 · v1 · pith:FVVSFD5Onew · submitted 2026-05-20 · 💻 cs.MS · cs.NA· math.NA

Solving Multivariate Polynomial Systems and Rectangular Multiparameter Eigenvalue Problems with MacaulayLab

Pith reviewed 2026-05-21 02:13 UTC · model grok-4.3

classification 💻 cs.MS cs.NAmath.NA
keywords multivariate polynomial systemsmultiparameter eigenvalue problemsnumerical linear algebraMacaulayLabMatlab toolboxpositive-dimensional solutionsMacaulay matrixrectangular eigenvalue problems
0
0 comments X

The pith

MacaulayLab solves multivariate polynomial systems and rectangular multiparameter eigenvalue problems through one shared numerical linear algebra approach.

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

The paper introduces MacaulayLab, a Matlab toolbox that applies numerical linear algebra algorithms to two distinct problem classes. It demonstrates that the same underlying method can handle both multivariate polynomial systems and rectangular multiparameter eigenvalue problems. The approach operates without dependence on any particular polynomial basis or monomial ordering. It also accommodates positive-dimensional solution sets that extend to infinity. A sympathetic reader would care because these problems appear across control theory, optimization, and engineering design, and a unified, basis-independent solver could reduce the need for specialized code or manual reformulation.

Core claim

The toolbox implements numerical linear algebra algorithms that solve both multivariate polynomial systems and rectangular multiparameter eigenvalue problems via one common approach. This implementation works independently of the chosen polynomial basis and monomial order. It is also capable of dealing with positive-dimensional solution sets at infinity. The toolbox and a collection of test problems are made freely available.

What carries the argument

The MacaulayLab toolbox, which encodes both problem types into a common numerical linear algebra framework based on Macaulay-type constructions.

If this is right

  • A single code base can be used for both polynomial root-finding and multiparameter eigenvalue calculations without reformulation.
  • Users need not adjust their choice of basis functions or variable ordering to obtain reliable results.
  • Problems whose solutions form curves or surfaces at infinity become tractable within the same framework.
  • Test suites supplied with the toolbox allow direct verification of accuracy on standard and user-supplied instances.

Where Pith is reading between the lines

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

  • The unified treatment could simplify pipelines that alternate between polynomial system solving and eigenvalue analysis, such as in robust control or algebraic statistics.
  • Extending the same linear-algebra core to overdetermined or underdetermined rectangular cases might naturally follow from the current rectangular multiparameter support.
  • Because the method avoids explicit Gröbner basis computation, it may scale more gracefully to systems where symbolic methods become prohibitive.

Load-bearing premise

The numerical linear algebra algorithms correctly recover solutions on the tested problems and the performance comparisons with PNLA, PHCpack, and MultiParEig reflect typical rather than selected cases.

What would settle it

A benchmark instance with a positive-dimensional solution set at infinity on which MacaulayLab returns incorrect multiplicity or misses solutions, or on which results change when the monomial order is altered.

Figures

Figures reproduced from arXiv: 2605.20884 by Bart De Moor, Christof Vermeersch.

Figure 1
Figure 1. Figure 1: Visualization of the (block) Macaulay matrix for a multivariate polynomial system (Figure 1a) and a rectangular multiparameter eigenvalue problem (Figure 1b). The (block) Macaulay matrix is constructed from the coefficients of the polynomials or the coefficient matrices of the rectangular multiparameter eigenvalue problem. The original coefficients are indicated by solid red dots ( ), while the open blue d… view at source ↗
Figure 2
Figure 2. Figure 2: Visualization of the structure of a basis matrix Z of the null space of the (block) Macaulay matrix when increasing the degree d. More (block) rows are added in every degree, in accordance with the growing (block) Macaulay matrix. From a certain degree on, d ∗ in this example, the nullity n corresponds to the number of solutions. By checking the rank structure, it is possible to split the affine solutions … view at source ↗
Figure 3
Figure 3. Figure 3: Pseudocode for the (block) Macaulay matrix approach, as described in Section 3. Six coherent steps can be deduced from the pseudocode, which are explained and linked to the implementation of MacaulayLab in Section 4. 4 Structure of the software package The different steps of the (block) Macaulay matrix approach are outlined in the pseu￾docode shown in [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Diagram of the main functions (rectangles) implemented in MacaulayLab and their dependencies (arrows). The gray rectangles indicate local functions from macaulaylab and the dashed arrows denote dependencies that are only used in the null space based approach. Since the solution approach is similar for both problem types, the same six steps are used and most functions are capable of dealing directly with bo… view at source ↗
Figure 5
Figure 5. Figure 5: Construction of the data structure to represent a multivariate polynomial system or a rectangular multiparameter eigenvalue problem. Both problem types are internally represented by the same problemstruct: all necessary information is stored in the cells coef and supp. The sub-classes systemstruct and mepstruct provide constructors to set-up the problems more easily, but it is also possible to submit the p… view at source ↗
Figure 6
Figure 6. Figure 6: Different configurations for MacaulayLab are used to solve the noon4 multivariate polynomial system ( ) and cube rectangular multiparameter eigenvalue problem ( ). The options are mentioned below the computation times: the first option is the solution space, the second option is the decision of how the rank checks and shifts in the multiplication maps are performed, and the third option is the chosen enlar… view at source ↗
Figure 7
Figure 7. Figure 7: Performance profiles for a subset of 50 multivariate polynomial systems. We run MacaulayLab ( ), PNLA, using the singular value ( ) or QR decomposition ( ), and PHClab ( ) on this subset. In more than half of the problems, PHClab is the fastest solver, while MacaulayLab has a comparable performance on the test set when we increase the ratio τ . MacaulayLab even manages to solve a slightly larger subset of … view at source ↗
Figure 8
Figure 8. Figure 8: Performance profiles for 30 rectangular multiparameter eigenvalue problems. We compare MacaulayLab ( ) with the Kronecker matrix approach ( ) and randomized sketching approach ( ) of MultiParEig. The problem set contains a lot of polynomial problems, which explains the overall better preformance of MacaulayLab . of polynomial problems with modestly sized coefficient matrices, MacaulayLab has an overall bet… view at source ↗
read the original abstract

We present the Matlab toolbox MacaulayLab, which implements numerical linear algebra algorithms for solving multivariate polynomial systems and rectangular multiparameter eigenvalue problems. Its structure and functionality are the result of several years of research and algorithmic development. We demonstrate how the software works and compare its performance with other software packages, such as PNLA, PHCpack, and MultiParEig. Some core features of MacaulayLab are the fact that it solves two key problems via one common approach, works independently of the chosen polynomial basis and monomial order, and is capable of dealing with positive-dimensional solution sets at infinity. The toolbox (including its future updates) and a large collection of test problems are freely available online.

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

1 major / 3 minor

Summary. The manuscript presents MacaulayLab, a MATLAB toolbox implementing numerical linear algebra algorithms to solve multivariate polynomial systems and rectangular multiparameter eigenvalue problems via a single unified framework. Core claims include independence from the chosen polynomial basis and monomial order, plus the ability to handle positive-dimensional solution sets at infinity. The paper demonstrates the software, reports performance comparisons against PNLA, PHCpack, and MultiParEig, and makes the toolbox together with a large collection of test problems freely available online.

Significance. If the algorithmic claims hold, MacaulayLab supplies a practical, basis-independent tool that unifies two related problem classes, which could reduce the need for separate solvers in computational algebra and multiparameter eigenvalue applications. The open release of code and test problems supports reproducibility and further benchmarking.

major comments (1)
  1. §4 (algorithmic description): the claim that the common Macaulay-matrix construction works independently of monomial order is supported by the reported experiments, but a side-by-side numerical example on the same input system with two distinct orders would make the independence explicit rather than inferred from aggregate timings.
minor comments (3)
  1. Table 2 (timing results): hardware specifications, MATLAB version, and number of runs per instance are not stated; adding these details would allow readers to assess variability in the reported speed-ups.
  2. Figure 3 caption: the legend does not indicate which curves correspond to the positive-dimensional cases; clarifying this would improve readability of the infinity-handling experiments.
  3. Section 2.1: the reference list omits the original Macaulay-matrix papers that underpin the numerical linear algebra approach; including them would strengthen the background.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive evaluation of our manuscript and the recommendation for minor revision. We address the single major comment below.

read point-by-point responses
  1. Referee: §4 (algorithmic description): the claim that the common Macaulay-matrix construction works independently of monomial order is supported by the reported experiments, but a side-by-side numerical example on the same input system with two distinct orders would make the independence explicit rather than inferred from aggregate timings.

    Authors: We agree that an explicit side-by-side demonstration would strengthen the presentation of the monomial-order independence claim. In the revised version of the manuscript we will add a short numerical example in Section 4 that applies the Macaulay-matrix construction to the same input system under two different monomial orders and shows that the extracted solution sets coincide (up to numerical tolerance). revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper is a software presentation describing the MacaulayLab toolbox and its performance on test problems. Its central claims rest on explicit algorithmic descriptions, pseudocode, and direct comparisons against independent external packages (PNLA, PHCpack, MultiParEig). No derivation chain, fitted parameter renamed as prediction, or load-bearing self-citation reduces any result to its own inputs by construction. The reported independence from polynomial basis/monomial order and handling of positive-dimensional components at infinity are demonstrated on an openly available collection of test problems and are therefore externally falsifiable.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

This is a software implementation paper; no mathematical free parameters, axioms, or invented entities are introduced or required for the central claim.

pith-pipeline@v0.9.0 · 5653 in / 1154 out tokens · 41256 ms · 2026-05-21T02:13:40.358804+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

45 extracted references · 45 canonical work pages

  1. [1]

    Agudelo, Christof Vermeersch, and Bart De Moor

    Oscar M. Agudelo, Christof Vermeersch, and Bart De Moor. Globally optimalH 2- norm model reduction: A numerical linear algebra approach.IFAC-PapersOnLine, 54(9):564–571, 2021. Part of special issue: 24th International Symposium on Math- ematical Theory of Networks and Systems (MTNS)

  2. [2]

    Bates, Jonathan D

    Daniel J. Bates, Jonathan D. Hauenstein, Sommese Andrew J., and Charles W. Wampler, II. Bertini: Software for numerical algebraic geometry.https:// bertini.nd.edu, 2013

  3. [3]

    PhD thesis, KU Leuven, Leuven, Belgium, 2013

    Kim Batselier.A Numerical Linear Algebra Framework for Solving Problems with Multivariate Polynomials. PhD thesis, KU Leuven, Leuven, Belgium, 2013

  4. [4]

    On the null spaces of the Macaulay matrix.Linear Algebra and its Applications, 460:259–289, 2014

    Kim Batselier, Philippe Dreesen, and Bart De Moor. On the null spaces of the Macaulay matrix.Linear Algebra and its Applications, 460:259–289, 2014

  5. [5]

    Mat´ ıas R. Bender. Solving sparse polynomial systems using Gr¨ obner bases and resultants. InProc. of the 2022 International Symposium on Symbolic and Algebraic Computation (ISSAC), pages 21–30, Villeneuve-d’Ascq, France, 2022

  6. [6]

    Bender and Simon Telen

    Mat´ ıas R. Bender and Simon Telen. Yet another eigenvalue algorithm for solv- ing polynomial systems. Technical report, Technische Universit¨ at Berlin, Berlin, Germany, 2022

  7. [7]

    Homotopycontinuation.jl: A package for ho- motopy continuation in Julia

    Paul Breiding and Sascha Timme. Homotopycontinuation.jl: A package for ho- motopy continuation in Julia. In James H. Davenport, Manuel Kauers, George Labahn, and Josef Urban, editors,Proc. of the 6th International Conference on Mathematical Software, pages 458–465, South Bend, IN, USA, 2018. 21

  8. [8]

    Hom4PS-3: A parallel numerical solver for systems of polynomial equations based on polyhedral homotopy continua- tion methods

    Tian-ran Chen, Tsung-Lin Lee, and Tien-Yien Li. Hom4PS-3: A parallel numerical solver for systems of polynomial equations based on polyhedral homotopy continua- tion methods. InProc. of the 4th International Congress on Mathematical Software (ICMS), pages 183–190, Seoul, South Korea, 2014

  9. [9]

    Corless, Gianni M

    Robert M. Corless, Gianni M. Patrizia, and Barry M. Trager. A reordered Schur factorization method for zero-dimensional polynomial systems with multiple roots. InProc. of the 1997 International Symposium on Symbolic and Algebraic Compu- tation (ISSAC), pages 133–140, Maui, HI, USA, 1997

  10. [10]

    Cox.Applications of Polynomial Systems, volume 134 ofRegional Con- ference Series in Mathematics

    David A. Cox.Applications of Polynomial Systems, volume 134 ofRegional Con- ference Series in Mathematics. Conference Board of the Mathematical Sciences, Providence, RI, USA, 2020

  11. [11]

    Least squares realization of LTI models is an eigenvalue problem

    Bart De Moor. Least squares realization of LTI models is an eigenvalue problem. In Proc. of the 18th European Control Conference (ECC), pages 2270–2275, Naples, Italy, 2019

  12. [12]

    Least squares optimal realisation of autonomous LTI systems is an eigenvalue problem.Communications in Information and Systems, 20(2):163–207, 2020

    Bart De Moor. Least squares optimal realisation of autonomous LTI systems is an eigenvalue problem.Communications in Information and Systems, 20(2):163–207, 2020

  13. [13]

    Dolan and Jorge J

    Elizabeth D. Dolan and Jorge J. Mor´ e. Benchmarking optimization software with performance profiles.Mathematical Programming, 91:201–213, 2002

  14. [14]

    PhD thesis, KU Leuven, Leuven, Belgium, 2013

    Philippe Dreesen.Back to the Roots: Polynomial System Solving Using Linear Algebra. PhD thesis, KU Leuven, Leuven, Belgium, 2013

  15. [15]

    Efficient computation of zero-dimensional Gr¨ obner bases by change of ordering.Journal of Symbolic Computation, 16(4):329–344, 1993

    Jean-Charles Faug` ere, Patrizia Gianni, Daniel Lazard, and Teo Mora. Efficient computation of zero-dimensional Gr¨ obner bases by change of ordering.Journal of Symbolic Computation, 16(4):329–344, 1993

  16. [16]

    Cryptanalysis of MinRank

    Jean-Charles Faug` ere, Fran¸ coise Levy-dit Vehel, and Ludovic Perret. Cryptanalysis of MinRank. InProc. of the 28th Annual International Cryptology Conference, pages 280–296, Santa Barbara, CA, USA, 2008

  17. [17]

    PHoM- para – parallel implementation of the polyhedral homotopy continuation method for polynomials systems.Computing, 77:387–411, 2006

    Takayuki Gunji, Sunyoung Kim, Katsuki Fujisawa, and Masakuzu Kojima. PHoM- para – parallel implementation of the polyhedral homotopy continuation method for polynomials systems.Computing, 77:387–411, 2006

  18. [18]

    PHoM – a polyhedral homotopy continuation method for polynomial systems.Computing, 73:57–77, 2004

    Takayuki Gunji, Sunyoung Kim, Masakuzu Kojima, Akiko Takeda, Katsuki Fu- jisawa, and Tomohiko Mizutani. PHoM – a polyhedral homotopy continuation method for polynomial systems.Computing, 73:57–77, 2004

  19. [19]

    Randomized methods for comput- ing joint eigenvalues, with applications to multiparameter eigenvalue problems and root finding.Numerical Algorithms, pages 1–32, 2024

    Haoze He, Daniel Kressner, and Bor Plestenjak. Randomized methods for comput- ing joint eigenvalues, with applications to multiparameter eigenvalue problems and root finding.Numerical Algorithms, pages 1–32, 2024

  20. [20]

    Hochstenbach, Tomaˇ z Koˇ sir, and Bor Plestenjak

    Michiel E. Hochstenbach, Tomaˇ z Koˇ sir, and Bor Plestenjak. Numerical methods for rectangular multiparameter eigenvalue problems, with applications to finding optimal ARMA and LTI models.Numerical Linear Algebra with Applications, 31(2):e2540:1–23, 2024. 22

  21. [21]

    Agudelo, and Bart De Moor

    Sibren Lagauw, Oscar M. Agudelo, and Bart De Moor. Globally optimal SISO h2-norm model reduction using Walsh’s theorem.IEEE Control System Letters, 7:1670–1675, 2023

  22. [22]

    Numerical algebraic geometry.Journal of Software for Algebra and Geometry, 3:5–10, 2011

    Anton Leykin. Numerical algebraic geometry.Journal of Software for Algebra and Geometry, 3:5–10, 2011

  23. [23]

    Numerical solution of multivariate polynomial systems by homotopy continuation methods.Acta Numerica, 6:399–436, 1997

    Tien-Yien Li. Numerical solution of multivariate polynomial systems by homotopy continuation methods.Acta Numerica, 6:399–436, 1997

  24. [24]

    Morgan.Solving Polynomial Systems Using Continuation for Engi- neering and Scientific Problems

    Alexander P. Morgan.Solving Polynomial Systems Using Continuation for Engi- neering and Scientific Problems. Prentice-Hall, Englewood Cliffs, NJ, USA, 1987

  25. [25]

    MultiParEig: Toolbox for multiparameter eigenvalue problems

    Bor Plestenjak. MultiParEig: Toolbox for multiparameter eigenvalue problems. https://mathworks.com/matlabcentral/fileexchange/47844-multipareig,

  26. [26]

    (Visited on September 8, 2025)

  27. [27]

    Hochstenbach

    Bor Plestenjak and Michiel E. Hochstenbach. Roots of bivariate polynomial sys- tems via determinantal representations.SIAM Journal on Scientific Computing, 38(2):765–788, 2016

  28. [28]

    Algebro-geometric aspects of Heine–Stieltjes theory.Journal of the London Mathematical Society, 83(1):36–56, 2010

    Boris Shapiro. Algebro-geometric aspects of Heine–Stieltjes theory.Journal of the London Mathematical Society, 83(1):36–56, 2010

  29. [29]

    Sommese, Jan Verschelde, and Charles W

    Andrew J. Sommese, Jan Verschelde, and Charles W. Wampler, II. Numerical de- composition of the solution sets of polynomial systems into irreducible components. SIAM Journal on Numerical Analysis, 38(6):2022–2046, 2001

  30. [30]

    Sommese and Charles W

    Andrew J. Sommese and Charles W. Wampler, II.The Numerical Solution of Systems of Polynomials Arising in Engineering and Science. World Scientific Pub- lishing Company, Singapore, 2005

  31. [31]

    Stetter.Numerical Polynomial Algebra

    Hans J. Stetter.Numerical Polynomial Algebra. SIAM, Philadelphia, PA, USA, 2004

  32. [32]

    Solving polynomial systems via truncated normal forms.SIAM Journal on Matrix Analysis and Applications, 39(3):1421 –1447, 2018

    Simon Telen, Bernard Mourrain, and Marc Van Barel. Solving polynomial systems via truncated normal forms.SIAM Journal on Matrix Analysis and Applications, 39(3):1421 –1447, 2018

  33. [33]

    Trefethen.Approximation Theory and Approximation Practice

    Lloyd N. Trefethen.Approximation Theory and Approximation Practice. SIAM, Philadelphia, PA, USA, extended edition, 2019

  34. [34]

    Trefethen

    Llyod N. Trefethen. Six myths of polynomial interpolation and quadrature.Math- ematics Today, pages 184–188, 2011

  35. [35]

    Systems of polynomial equations, higher-order tensor decompositions and multidimensional harmonic retrieval: An unifying framework

    Jeroen Vanderstukken and Lieven De Lathauwer. Systems of polynomial equations, higher-order tensor decompositions and multidimensional harmonic retrieval: An unifying framework. part I: The canonical polyadic decomposition.SIAM Journal on Matrix Analysis and Applications, 42(2):883–912, 2021

  36. [36]

    PhD thesis, KU Leuven, Leuven, Belgium, 2023

    Christof Vermeersch.The (Block) Macaulay Matrix. PhD thesis, KU Leuven, Leuven, Belgium, 2023. 23

  37. [37]

    Solving multivariate polynomial systems and rectangular mul- tiparameter eigenvalue problems with macaulaylab.https://www.macaulaylab

    Christof Vermeersch. Solving multivariate polynomial systems and rectangular mul- tiparameter eigenvalue problems with macaulaylab.https://www.macaulaylab. net, 2025

  38. [38]

    Globally optimal least-squares ARMA model identification is an eigenvalue problem.IEEE Control Systems Letters, 3(4):1062–1067, 2019

    Christof Vermeersch and Bart De Moor. Globally optimal least-squares ARMA model identification is an eigenvalue problem.IEEE Control Systems Letters, 3(4):1062–1067, 2019

  39. [39]

    A column space based approach to solve systems of multivariate polynomial equations.IFAC-PapersOnLine, 54(9):137–144,

    Christof Vermeersch and Bart De Moor. A column space based approach to solve systems of multivariate polynomial equations.IFAC-PapersOnLine, 54(9):137–144,

  40. [40]

    Part of special issue: 24th International Symposium on Mathematical Theory of Networks and Systems (MTNS)

  41. [41]

    Two complementary block Macaulay ma- trix algorithms to solve multiparameter eigenvalue problems.Linear Algebra and its Applications, 654:177–209, 2022

    Christof Vermeersch and Bart De Moor. Two complementary block Macaulay ma- trix algorithms to solve multiparameter eigenvalue problems.Linear Algebra and its Applications, 654:177–209, 2022

  42. [42]

    Christof Vermeersch and Bart De Moor. Recursive algorithms to update a numerical basis matrix of the null space of the block row, (banded) block Toeplitz, and block Macaulay matrix.SIAM Journal on Scientific Computing (SISC), 45(2):A596– A620, 2023

  43. [43]

    PhD thesis, KU Leuven, Leuven, Belgium, 1996

    Jan Verschelde.Homotopy Continuation Methods for Solving Polynomial Systems. PhD thesis, KU Leuven, Leuven, Belgium, 1996

  44. [44]

    Algorithm 795: PHCpack: A general-purpose solver for polynomial systems by homotopy continuation.ACM Transactions on Mathematical Software, 25(2):251–276, 1999

    Jan Verschelde. Algorithm 795: PHCpack: A general-purpose solver for polynomial systems by homotopy continuation.ACM Transactions on Mathematical Software, 25(2):251–276, 1999

  45. [45]

    Watson, Stephen C

    Layne T. Watson, Stephen C. Billups, and Alexander P. Morgan. Algorithm 652: HOMPACK: A suite of codes for globally convergent homotopy algorithms.ACM Transactions on Mathematical Software, 13(3):281–310, 1987. 24