Real Numerical Algebraic Geometry

The authors are hosting an AMS sponsored Mathematics Research Community (MRC) on real numerical algebraic geometry. The research program developed by the authors will focus on theory and algorithm design for real numerical algebraic geometry along with solving problems arising in applications such as kinematics and chemical reaction networks. This article provides some background and an introduction to the themes of this MRC. Interested pure and applied researchers in mathematics and fields related to the applications are encouraged to apply.

1. Real Numerical Algebraic Geometry

Numerical algebraic geometry (65H14 in MSC2020) is the mathematical subject area focused on numerically computing and manipulating solution sets to systems of polynomial equations. The name numerical algebraic geometry was coined in 1996 in a paper by Sommese and Wampler 21. By performing computations over the complex numbers, which is algebraically closed, one can prove many results regarding polynomial system solving leading to computationally feasible algorithms that can be implemented using floating-point arithmetic. For example, one can compute the irreducible components of the solution set of a given polynomial system and represent it on a computer via a so-called numerical irreducible decomposition with witness sets. The books 322 provide a general overview of numerical algebraic geometry.

For most applications of polynomial systems in science and engineering, only real solutions are of interest. Some examples include computing the equilibria of a dynamical system, synthesizing a mechanism to perform given tasks, and reconstructing three-dimensional models from two-dimensional images in computer vision. Of course, if a polynomial system has only finitely many solutions over the complex numbers, then one approach is to compute all of the complex solutions and retain only the real subset of solutions. Although such an approach has been used effectively on problems of modest size, the number of real solutions are typically only a very small fraction of the number of complex solutions, so much computation is wasted. For example, a problem in four-bar synthesis has only 384 real solutions out of 8652 complex solutions 24 while a problem in computing equilibria of a dynamical system has only 2 equilibria out of $\approx 10^{18}$ complex solutions 9. Thus, a key research area is to develop numerical approaches for computing and manipulating only the real solution set to a system of polynomial equations yielding real numerical algebraic geometry.

Since the real numbers are not algebraically closed, much of the theory underpinning techniques in numerical algebraic geometry no longer holds when considering only the real solutions. However, there is a growing body of algorithms for numerically computing and manipulating the real solution set to a system of polynomial equations. This includes critical-point methods for sampling real points, routing functions and road-maps for deciding connectivity, and cell decompositions to provide a full description.

Figure 1.

A curve traced by a Griffis-Duffy platform, an exceptional Stewart-Gough platform.

2. Exploring the Real Parameter Space

Polynomial systems arising in science and engineering typically depend upon parameters such as reaction rates, lengths, and temperature. Since the behavior of the real solution sets can change as the parameters vary, one can explore the parameter space to determine the different behaviors. One tool for exploration is a parameter homotopy of the form

$$\begin{equation*} H(x,t) = F(x; t\cdot p_0 + (1-t)\cdot p^*)=0. \end{equation*}$$

Moving from $t=1$ to $t=0$ deforms the parameters $p$ from the starting parameters $p_0$ to the target parameters $p^*$. A parameter homotopy allows for efficient computation of solutions to $F(x;p^*)=0$ for many different parameters $p^*$. Such information can be used to provide insight into the geography of the parameter space. Figure 2 presents a decomposition of the parameter space based on the number of real solutions when the lengths of two legs of a 3RPR mechanism are changed 16. The color represents the number of real solutions such that the darker the color, the more real solutions there are. The boundaries correspond with the discriminant locus.

Figure 2.

Parameter space decomposition for 3RPR mechanism based on number of real solutions.

If one performs a real parameter homotopy inside of a connected component in the complement of the discriminant locus, then there must be a bijection between real solutions for the start and target parameters. Parameter space exploration coupled with learning the boundaries has showed that corresponding real parameter homotopies significantly decrease the computational cost of computing the real solutions 4, especially when the number of real solutions is small in comparison to the total number of complex solutions. For example, in the trifocal pose geometry problem illustrated in Figure 3, there are a total of 312 nonsingular, isolated solutions, yet only about 35 of them are real on average 13. Computer vision showcases minimal problems where the number of real solutions is drastically smaller than the total degree. Therefore, continuing to expand current methods to focus on just real solutions can have a large impact on efficient and fast solving for many parameter instances within applications.

Figure 3.

Trifocal pose geometry: three pinhole cameras view a point-plus-tangent 13.

When using a sequence of parameter homotopies, it is natural to consider what happens to the solutions when one performs a loop in parameter space and returns to the original set of parameters. Classically, the monodromy group encapsulates all the possible permutations of the isolated solutions. A simple example of a nontrivial monodromy loop is demonstrated using the complex square root via $F(x,t) = x^2-t=0$. As shown in Figure 4, starting at $(x,t)=(1,1)$ and tracking the solution $x(t)$ for $t=e^{i\theta }$ as $\theta$ goes from $0$ to $2\pi$ will return to $(x,t) = (-1,1)$. Thus, the monodromy group is the symmetric group on two elements since the two solutions $x=\pm 1$ at $t=1$ can be interchanged.

Although the monodromy group captures some structure within the solutions over the complex numbers, it can fail to capture interesting behavior about the real solutions. For example, returning to the 3RPR mechanism whose parameter space decomposition is provided in Figure 2, a nontrivial monodromy action corresponds with a nonsingular assembly mode change. This is important for engineers to understand when controlling parallel manipulators due to the possible change of pose at the “home” position. Although the complex monodromy group is the full symmetric group, the six real solutions in the red region actually break into two subsets of 3 that can only permute amongst themselves 16. In particular, starting with a “home” position pose, it is possible to return to two other poses. Since this behavior is not captured with the classical monodromy group over the complex number, this exemplifies the impact of having methods that focus on the real numbers to understand the behavior of the real solutions.

Figure 4.

Monodromy loop: as $t$ circles in $\mathbb{C}$ around 0, $x$ interchanges between $1$ and $-1$.

For positive-dimensional real solution sets, sampling techniques combined with topological data analysis can be used to build graphs that approximate the topological structure. For example, Figure 5 shows the configuration space of a parallel five-bar manipulator 12 which can be used for path planning to efficiently connect different configurations while avoiding configurations that are problematic from a mechanical perspective.

Figure 5.

Path planning in configuration space for a parallel five-bar manipulator.

In addition to sampling, other approaches for numerically computing positive-dimensional real solution sets include cell decompositions 5 and decompositions using routing functions 1018, which will be explored as part of this MRC.

3. Number of Real Solutions

A natural question to ask of any parameterized system with generically finitely many complex solutions is the minimum and maximum number of real solutions. For example, assembling a Stewart-Gough platform corresponds with solving a parameterized polynomial system which generically has 40 complex solutions. In 1998, a set of parameters was found such that all 40 solutions are real, meaning that the corresponding Stewart-Gough platform robot can be assembled in 40 different ways 11. Similar questions arise in many application areas including parameters for a chemical reaction network to have multiple real equilibria.

Another example is to determine the maximum number of equilibria for the Kuramoto model, which is a mathematical model used to describe synchronization. With three oscillators, the maximum number of real equilibria matches the generic root count over the complex numbers, namely $6$. With four oscillators, it was conjectured using parameter space exploration that the maximum number of real equilibria was $10$, which is strictly smaller than the generic complex root count of $14$. This upper bound of $10$ for four oscillators was proven in 15 with Figure 6 illustrating the approach which computed at least one sample point in each component. The cases with five or more oscillators remain open.

Figure 6.

Parameter space decomposition arising from $n=4$ Kuramoto with sample points in each component 15.

A natural question concerning parameterized families is whether there always exists a real solution, i.e., if the minimum number of real solutions is positive. Of course, if there is an odd number of nonsingular complex solutions to a polynomial system with real coefficients, then there is always a real solution since nonreal solutions arise in complex conjugate pairs. For problems with an even number, the answer can be quite challenging. This is relevant, for example, in computer vision, in which one may want to determine if there always exists a real reconstruction given any location of the image features. An open problem in real enumerative geometry is to determine if there always exists a real plane conic that passes through the origin and intersects each of six given real lines. Over the complex numbers, there are 18 such plane conics generically and all experimental evidence to date suggests that at least two of them are always real, e.g., 1417, while a proof remains elusive. An instance of this problem is shown in Figure 7.

Figure 7.

Real plane conic intersecting six given real lines and passing through the origin (green).

4. Software

Software packages implementing various numerical algebraic geometric algorithms include Bertini 2,Hom4PS2 19, HomotopyContinuation.jl 8, NAG4M2 20, and PHCpack 23. Paramotopy 1 provides efficient methods for parameterized polynomial systems using Bertini. Some examples of software in real numerical algebraic geometry are Bertini_real 5 for computing a cell decomposition of curves and surfaces, polyTop 6 for computing topological information of a real surface, and HypersurfaceRegions.jl 7 for computing complements of an arrangement of real hypersurfaces from 1018.

5. You are Invited!

The authors invite early-career applicants to join our AMS MRC during the summer of 2025 on these topics. The goal of this collaborative workshop is to bring together mathematicians and domain experts in kinematics, computer vision, and chemical reaction networks to develop new methods and to solve problems using real numerical algebraic geometry. The problems to be undertaken in the workshop generally fall into one or more of the following categories:

•

development and refinement of algorithms characterizing the real solution set, such as counting connected components, sampling points on connected components, and capturing monodromy structures;

•

approaches for quickly computing real solutions;

•

methods for exploring the behavior of real solutions over a parameter space; and

•

exploration of applications, such as robot kinematics, computer vision, or chemical equilibrium. Among these, the characterization of robot and mechanism workspaces, singularities, and connectivity is an especially rich source of interesting problems.

In addition to research collaborations, there will be professional development opportunities to learn about research in industry and expand professional networks. We invite you to apply and join us in exploring real numerical algebraic geometry!