Solving Multivariate Polynomial Systems and Rectangular Multiparameter Eigenvalue Problems with MacaulayLab
Pith reviewed 2026-05-21 02:13 UTC · model grok-4.3
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.
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
- 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
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.
Referee Report
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)
- §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)
- 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.
- 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.
- 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
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
-
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
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
Lean theorems connected to this paper
-
IndisputableMonolith/Foundation/AbsoluteFloorClosure.leanreality_from_one_distinction unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
transforms both key problems into a multidimensional realization problem by using the column space or (right) null space of the (block) Macaulay matrix ... resulting in one or multiple generalized eigenvalue problems
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
works independently of the chosen polynomial basis and monomial order
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
-
[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)
work page 2021
-
[2]
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
work page 2013
-
[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
work page 2013
-
[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
work page 2014
-
[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
work page 2022
-
[6]
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
work page 2022
-
[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
work page 2018
-
[8]
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
work page 2014
-
[9]
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
work page 1997
-
[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
work page 2020
-
[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
work page 2019
-
[12]
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
work page 2020
-
[13]
Elizabeth D. Dolan and Jorge J. Mor´ e. Benchmarking optimization software with performance profiles.Mathematical Programming, 91:201–213, 2002
work page 2002
-
[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
work page 2013
-
[15]
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
work page 1993
-
[16]
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
work page 2008
-
[17]
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
work page 2006
-
[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
work page 2004
-
[19]
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
work page 2024
-
[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
work page 2024
-
[21]
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
work page 2023
-
[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
work page 2011
-
[23]
Tien-Yien Li. Numerical solution of multivariate polynomial systems by homotopy continuation methods.Acta Numerica, 6:399–436, 1997
work page 1997
-
[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
work page 1987
-
[25]
MultiParEig: Toolbox for multiparameter eigenvalue problems
Bor Plestenjak. MultiParEig: Toolbox for multiparameter eigenvalue problems. https://mathworks.com/matlabcentral/fileexchange/47844-multipareig,
-
[26]
(Visited on September 8, 2025)
work page 2025
-
[27]
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
work page 2016
-
[28]
Boris Shapiro. Algebro-geometric aspects of Heine–Stieltjes theory.Journal of the London Mathematical Society, 83(1):36–56, 2010
work page 2010
-
[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
work page 2022
-
[30]
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
work page 2005
-
[31]
Stetter.Numerical Polynomial Algebra
Hans J. Stetter.Numerical Polynomial Algebra. SIAM, Philadelphia, PA, USA, 2004
work page 2004
-
[32]
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
work page 2018
-
[33]
Trefethen.Approximation Theory and Approximation Practice
Lloyd N. Trefethen.Approximation Theory and Approximation Practice. SIAM, Philadelphia, PA, USA, extended edition, 2019
work page 2019
- [34]
-
[35]
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
work page 2021
-
[36]
PhD thesis, KU Leuven, Leuven, Belgium, 2023
Christof Vermeersch.The (Block) Macaulay Matrix. PhD thesis, KU Leuven, Leuven, Belgium, 2023. 23
work page 2023
-
[37]
Christof Vermeersch. Solving multivariate polynomial systems and rectangular mul- tiparameter eigenvalue problems with macaulaylab.https://www.macaulaylab. net, 2025
work page 2025
-
[38]
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
work page 2019
-
[39]
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]
Part of special issue: 24th International Symposium on Mathematical Theory of Networks and Systems (MTNS)
-
[41]
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
work page 2022
-
[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
work page 2023
-
[43]
PhD thesis, KU Leuven, Leuven, Belgium, 1996
Jan Verschelde.Homotopy Continuation Methods for Solving Polynomial Systems. PhD thesis, KU Leuven, Leuven, Belgium, 1996
work page 1996
-
[44]
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
work page 1999
-
[45]
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
work page 1987
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.