Numerical algebraic geometry

Numerical algebraic geometry is a field of computational mathematics, particularly computational algebraic geometry, which numerically solves polynomial systems and uses those solutions for various purposes.

Homotopy continuation

See also: System of polynomial equations § Homotopy continuation

See also: Numerical continuation

The primary computational method used in numerical algebraic geometry is homotopy continuation, in which a homotopy is formed between two systems, and point solutions of one are continued to the other. This is a specification of the more general method of numerical continuation.

Let $z$ represent the variables of the system. By abuse of notation, and so facilitate the spectrum of ambient spaces over which one can solve system, we do not use vector notation for $z$. Similarly for the systems $f$ and $g$.

Current canonical notation calls the start system $g$, and the target system -- the system to be solved -- $f$. A very common homotopy, the straight line homotopy, between $f$ and $g$ is $$H(z,t)=(1-t)f(z)+tg(z).$$

In the above homotopy, one starts the path variable at $t_{\text{start}}=1$ and continues toward $t_{\text{end}}=0$. Another common choice is to run from $0$ to $1$. In principle, the choice is completely arbitrary. In practice, regarding endgame methods for computing singular solutions using homotopy continuation, the target time being $0$ can significantly ease analysis, so this perspective is here taken.

Regardless of the choice of start and target times, the $H$ ought to be formulated such that $H(z,t_{\text{start}})=g(z)$, and $H(z,t_{\text{end}})=f(z)$.

One has a choice in $g(z)$, including

• Roots of unity
• Total degree
• Polyhedral
• Multi-homogeneous

and beyond these, specific start systems which closely mirror the structure of $f$ may be formed for particular systems. The choice of start system impacts the computational time it takes to solve $f$, in that those which are easy to formulate (such as total degree) tend to have higher numbers of paths to track, and those which take significant effort (such as the polyhedral method) are much sharper. There is currently no great way to predict which will lead to the quickest time to solve.

Actual continuation is typically done using predictor-corrector methods, with additional features as implemented. Predicting is done using a standard ODE predictor method, such as Runge-Kutta, and correction often uses Newton-Raphson iteration.

Because $f$ and $g$ are polynomial, homotopy continuation in this context is theoretically guaranteed to compute all solutions of $f$, due to Bertini's theorem. However, this guarantee is not practical, because of issues arising from limitations of the modern computer, most namely finite precision. That is, despite the strength of the probability-1 argument underlying this theory, without using a priori certified tracking methods, some paths may fail to track perfectly for various reasons.

Witness set

A witness set $W$ is a data structure used to describe algebraic varieties. The witness set for an affine variety that is equidimensional consists of three pieces of information. The first piece of information is a system of equations $F$. These equations define the algebraic variety ${\bf {V}}(F)$ that is being studied. The second piece of information is a linear space ${\cal {L}}$. The dimension of ${\cal {L}}$ is the codimension of ${\bf {V}}(F)$, and chosen to intersect ${\bf {V}}(F)$ transversely. The third piece of information is the list of points in the intersection ${\cal {{L}\cap {\bf {V}}(F)}}$. This intersection has finitely many points and the number of points is the degree of the algebraic variety ${\bf {V}}(F)$. Thus, witness sets encode the answer to the first two questions one asks about an algebraic variety: What is the dimension, and what is the degree? Witness sets also allow one to perform a numerical irreducible decomposition, component membership tests, and component sampling. This makes witness sets a good description of an algebraic variety.

Software

There is a variety of software packages which implement portions of the theoretical body of numerical algebraic geometry. Some notable packages include, in alphabetic order:

• alphaCertified
• Bertini
• Hom4PS
• PHCPack