Real Radical Computation via Semidefinite Programming

17 concepts9 papers1 proposal

When solving systems of polynomial equations, we are often confronted with an frustrating asymmetry: geometric algorithms naturally operate over the complex numbers $\mathbb{C}$, but practical engineering and physics applications almost exclusively care about real solutions $\mathbb{R}$.

As highlighted by Cheng et al. and Lasserre et al., traditional computer algebra methods—such as Gröbner bases or standard elimination theory—treat real and complex roots indiscriminately. If a polynomial system has thousands of complex solutions but only a handful of real ones, computing the entire complex variety just to discard the non-real roots is computationally wasteful. This inefficiency is particularly severe in fields like robotics, computer vision, and optimization, where real-time constraints demand a more targeted approach.

To bypass the complex numbers entirely, a powerful framework has emerged that bridges algebraic geometry and numerical optimization. By combining moment matrices with Semidefinite Programming (SDP), researchers can isolate the real solutions of a polynomial system directly, transforming an intractable symbolic filtering problem into a well-behaved numerical linear algebra task.

The Target: The Real Radical Ideal

To understand why this approach works, we must first look at what we are trying to isolate algebraically. Given a set of polynomial equations, the standard ideal contains all polynomials that can be formed by combining the original equations. However, this ideal still "sees" the complex roots.

To isolate only the real solutions, we target the real radical of the ideal. The real radical consists of all polynomials that vanish on the real variety (the set of all real points satisfying the equations). If we can find a way to compute the real radical directly, we can simplify the underlying equations to describe only the real points of interest, effectively pruning away the complex solution space before any roots are actually calculated.

The Moment Matrix as a Geometric Filter

The core mechanism for isolating the real radical is the moment matrix. Instead of manipulating the polynomials symbolically, we translate the problem into dual space by looking at linear functionals acting on the vector space of polynomials.

Imagine a unknown probability measure $\mu$ that is supported entirely on the real solutions of our polynomial system. We can construct a structured matrix, called the moment matrix $M(y)$, where the rows and columns are indexed by monomials (e.g., $1, x_1, x_2, x_1^2, x_1x_2, \dots$). Each entry in the matrix corresponds to the "moment" of the combined monomials with respect to $\mu$:

$$M(y)_{\alpha, \beta} = \int x^\alpha x^\beta d\mu = \int x^{\alpha + \beta} d\mu$$

Crucially, if a measure $\mu$ is supported on real points, its moment matrix must be positive semidefinite (PSD). This is because for any polynomial $p(x)$ with coefficient vector $c$, the integral of its square must be non-negative:

$$c^T M(y) c = \int p(x)^2 d\mu \ge 0$$

This simple property provides a powerful geometric filter. As Lasserre et al. demonstrated, enforcing PSD constraints on these moment matrices naturally excludes complex roots. Complex numbers do not satisfy this positivity condition under real-valued measures. By using Semidefinite Programming (SDP) to find a maximum-rank PSD moment matrix constrained by our original polynomial equations, we force the optimization process to focus exclusively on the real-valued subspace of the solution set.

Turning Algebra into Linear Algebra via the Kernel

How do we get from a positive semidefinite moment matrix back to the polynomials that define our real roots? The answer lies in the matrix's kernel (or null space).

Suppose a polynomial $p(x)$ vanishes on all the real solutions where our measure $\mu$ is supported. Then the integral of $p(x)^2$ against $\mu$ must be exactly zero:

$$c^T M(y) c = \int p(x)^2 d\mu = 0$$

For a positive semidefinite matrix, $c^T M(y) c = 0$ implies that $M(y)c = 0$. In other words, the coefficient vector $c$ of the polynomial $p(x)$ must reside within the kernel of the moment matrix.

As shown by Lasserre et al., the kernel of a maximum-rank PSD moment matrix constrained by the polynomial equations identifies the real radical ideal exactly. This insight unifies numerical optimization and algebraic geometry:

  1. Optimization (SDP) finds the maximum-rank PSD moment matrix, acting as the real-root filter.
  2. Linear Algebra computes the kernel of this matrix.
  3. Algebraic Geometry interprets this kernel as the set of all polynomials that vanish on the real solutions.

This duality is not unique to moment matrices. Other matrix structures exploit similar kernel properties to isolate root structures. For example, Chen et al. and Chen et al. utilize Macaulay matrices to compute bases for local dual spaces via Noetherian operators. Similarly, Batselier et al. and Dreesen et al. apply realization theory from systems theory to organize monomial bases, showing that the solutions to polynomial systems are embedded within the null spaces of structured coefficient matrices. In all these cases, the algebraic problem of finding vanishing polynomials is transformed into a numerical linear algebra task of finding a matrix null space.

Scaling Up: Border Bases and Prolongation

While the theoretical connection between SDP kernels and the real radical is elegant, solving massive SDPs can become computationally expensive. To make this approach practical for real-world systems, the moment method is often paired with specialized algebraic structures.

One prominent acceleration technique involves border bases. As detailed by Lasserre et al., combining the numerical efficiency of border bases with moment matrices significantly reduces the size of the semidefinite programs required. The border basis provides a stable, structured framework for organizing the monomial terms, allowing the SDP solver to work over a much smaller, targeted set of moments.

Additionally, Lasserre et al. introduced a "prolongation-projection" stopping criterion. Instead of blindly increasing the degree of the moment matrix until global convergence is reached, the algorithm iteratively prolongs the equations to higher degrees and projects them back down, stopping as soon as the kernel dimension stabilizes. This prevents the computational explosion typically associated with high-degree polynomial systems.

By using the positivity of semidefinite matrices as a geometric lens, this framework allows researchers to look past the sea of complex solutions and isolate the real roots directly through the stable, well-understood tools of numerical linear algebra.

Key Foundational Work

Semidefinite Characterization and Computation of Zero-Dimensional Real Radical Ideals (2008) — contributed 5 concept elements to this direction.
A prolongation-projection algorithm for computing the finite real variety of an ideal (2008) — contributed 2 concept elements to this direction.
A moment approach to analyze zeros of triangular polynomial sets (2005) — contributed 1 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_real_only_root_isolation_bf4cd776,
  title = {real-only root isolation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/real-only-root-isolation/rdr_bf4cd77674c641a1a8d30d7850b83772},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_real_only_root_isolation_bf4cd776_v1,
  title = {real-only root isolation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/real-only-root-isolation/rdr_bf4cd77674c641a1a8d30d7850b83772/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake