Polynomial Root Finding via Eigendecomposition

70 concepts49 papers1 proposal

Finding the roots of a system of non-linear polynomial equations is a foundational challenge across computational science. Traditional numerical approaches, such as the iterative Newton-Raphson method, require a highly accurate initial guess and are prone to missing roots or getting trapped in local minima. Conversely, purely symbolic methods like Gröbner bases provide global solutions but suffer from exponential computational blowup.

The core insight of eigenvalue-based root finding is to bridge this gap by transforming non-linear polynomial systems into linear algebra problems. By reframing root finding as an eigenvalue or generalized eigenvalue problem, practitioners can leverage highly optimized, globally convergent, and numerically robust linear algebra routines (such as the QR or QZ algorithms). This paradigm turns a chaotic non-linear search into a reliable, one-shot matrix decomposition.

The Univariate Baseline: Companion Matrices

To build intuition for why a polynomial root-finding problem can be expressed as an eigenvalue problem, consider a single monic univariate polynomial of degree $n$:

$$p(x) = x^n + a_{n-1}x^{n-1} + \dots + a_1 x + a_0 = 0$$

We can construct a structured $n \times n$ matrix $C$, known as the companion matrix, where the negative coefficients of the polynomial occupy the final column, and ones lie along the subdiagonal:

$$C = \begin{pmatrix} 0 & 0 & \dots & 0 & -a_0 \\ 1 & 0 & \dots & 0 & -a_1 \\ 0 & 1 & \dots & 0 & -a_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \dots & 1 & -a_{n-1} \end{pmatrix}$$

The characteristic polynomial of $C$—defined by $\det(xI - C)$—is exactly equal to $p(x)$. Consequently, the eigenvalues of $C$ are precisely the roots of $p(x)$. As John F. Canny demonstrated in Efficient Techniques for Multipolynomial Resultant Algorithms, this reduction allows univariate polynomial systems to be solved efficiently using standard numerical linear algebra routines rather than unstable root-hunting heuristics.

Scaling to Multivariate Systems: The Action Matrix

How do we extend this concept to a system of multiple polynomials in multiple variables? The trick lies in treating multiplication as a linear transformation.

Suppose we have a system of equations that defines a finite number of discrete solution points (a zero-dimensional ideal). We can look at the vector space of all possible polynomials modulo our system's equations. In this coordinate ring, multiplying any polynomial by a coordinate variable (say, $x_1$) is a strictly linear operation because it distributes over addition.

The matrix representing this multiplication operation is called the action matrix (or multiplication matrix). If we choose a basis of monomials for our quotient space, the action matrix $M_{x_1}$ maps each basis monomial to its product with $x_1$, simplified using the polynomial equations of our system.

To see why this works, let $x^* = (x_1^*, x_2^*, \dots, x_m^*)$ be a joint root of our polynomial system. Evaluating a basis vector of monomials $v(x)$ at this specific root satisfies a beautiful property:

$$M_{x_1} v(x^*) = x_1^* v(x^*)$$

This is exactly the definition of an eigenvalue problem! The eigenvector is the monomial basis evaluated at the root, and the corresponding eigenvalue is the coordinate value $x_1^*$ of that root. As Philippe Dreesen et al. explained in Back to the Roots: Polynomial System Solving, Linear Algebra, Systems Theory, finding the roots of a polynomial system can be reframed as a generalized eigenvalue problem where specific matrices are constructed from the nullspace basis and the polynomial's underlying algebraic structure.

Constructing the Matrix: Macaulay and Resultant Frameworks

To build these action matrices without performing full symbolic Gröbner basis computations, researchers rely on elimination templates like Macaulay matrices or resultants.

A Macaulay matrix linearizes a polynomial system by treating every distinct monomial as an independent variable. By stacking the original equations and their monomial shifts into a large coefficient matrix, the non-linear system becomes a large, sparse linear system. In Weighted/Structured Total Least Squares problems and polynomial system solving, Philippe Dreesen et al. showed that identifying a basis for the null space of this Macaulay matrix allows practitioners to extract the necessary multiplication relations and formulate a generalized eigenvalue problem. This strategy has also been extended by Shuqi Zhang et al. in Limit Cycle Identification in Nonlinear Polynomial Systems to identify polynomial coefficients and isolate complex oscillations via structured matrix decompositions.

Alternatively, resultant methods eliminate variables systematically. The hidden-variable resultant method treats one variable as a constant parameter, reducing a multivariate system to a univariate polynomial whose coefficients are matrix polynomials. As Vanni Noferini et al. described in Numerical Instability of Resultant Methods for Multidimensional Rootfinding, this maps the multidimensional root-finding problem directly into a linear eigenvalue problem.

[Multivariate Polynomial System]
               │
               ▼ (Treat one variable as constant / Shift monomials)
[Macaulay or Resultant Matrix Template]
               │
               ▼ (Extract Null Space or Block Elimination)
   [Linear Action Matrix (M_x)]
               │
               ▼ (Eigendecomposition: QR / QZ Algorithm)
[Eigenvalues = Coordinates of the Global Roots]

This transformation bypasses local optimization entirely. For instance, Epaminondas D. Fritzilas et al. utilized resultant-based algorithms in Algebraic algorithms for structure determination in biological chemistry to convert geometric constraints into generalized eigenvalue problems, extracting exact spatial coordinates directly from the resulting eigenvalues.

Real-World Applications and Minimal Solvers

This paradigm has revolutionized fields requiring real-time, robust geometric estimation, such as computer vision, robotics, and ray tracing. In computer vision, "minimal solvers" must compute camera pose or calibration parameters from the smallest possible set of noisy data points.

By pre-calculating an elimination template offline, solvers can execute online in microseconds. For example, Zuzana Kukelova et al. designed a real-time solver for radial lens distortion in A minimal solution to the autocalibration of radial distortion by constructing an action matrix via Gauss-Jordan elimination.

To further optimize these pipelines, Snehal Bhayani et al. introduced a technique in A Sparse Resultant Based Method for Efficient Minimal Solvers that integrates a linear auxiliary equation into the polynomial system. As explained by the authors in a subsequent refinement, Correction: Sparse Resultant-Based Minimal Solvers in Computer Vision and Their Connection with the Action Matrix, this structures the resultant matrix into distinct blocks, transforming complex or polynomial eigenvalue problems into regular, highly stable eigenvalue problems.

A similar logic applies to geometric intersections. In A noniterative method for robustly computing the intersections between a line and a curve or surface, Xiao Xiao et al. formulated a generalized eigenvalue problem where the eigenvalues represent the parametric coordinates of line-surface intersections, eliminating the need for iterative searching.

Beyond vision and graphics, Donald Peebles applied the action matrix method to ultrasound calibration in Similarity Registration Problems for 2D/3D Ultrasound Calibration, while Apostolos Chalkis et al. demonstrated in Efficient sampling in spectrahedra and volume approximation that determining where a trajectory hits the non-linear boundary of a spectrahedron can be solved as a polynomial eigenvalue problem, enabling efficient geometric sampling in high dimensions.

Numerical Stability and Open Challenges

While the transformation to an eigenvalue problem offers a powerful global solution mechanism, it is not without trade-offs. The process of linearization can fundamentally alter the conditioning of the problem.

As Vanni Noferini et al. highlighted in Numerical Instability of Resultant Methods for Multidimensional Rootfinding, the hidden-variable resultant method can introduce severe numerical instabilities. In many cases, small perturbations in the original polynomial coefficients can lead to massive errors in the computed eigenvalues of the linearized matrix. Consequently, contemporary research focuses heavily on structuring these matrices—such as using specialized determinant algorithms or balancing techniques—to preserve numerical precision and ensure that the stability of modern eigendecomposition algorithms translates perfectly back to the original polynomial space.

Key Foundational Work

Efficient Techniques for Multipolynomial Resultant Algorithms (1991) — contributed 2 concept elements to this direction.
Solutions of Systems of Algebraic Equations and Linear Maps on Residue Class Rings (1992) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_eigenvalue_based_root_finding_6f8a5a46,
  title = {eigenvalue-based root finding},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/eigenvalue-based-root-finding/rdr_6f8a5a469ef84706bb9a03f430995142},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_eigenvalue_based_root_finding_6f8a5a46_v1,
  title = {eigenvalue-based root finding},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/eigenvalue-based-root-finding/rdr_6f8a5a469ef84706bb9a03f430995142/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake