Overdetermined systems

We're tracking a solution of an overdetermined system.

Overdetermined systems

A system of polynomial equations $f=(f_1(x_1,\ldots, x_m),\ldots, f_n(x_1,\ldots,x_m))$ is called overdetermined, if it has more equations than variables; i.e., when $n>m$. HomotopyContinuation.jl features Newtons method for overdetermined systems for tracking solutions. We show in an example how it can be used.

Example: the rational normal curve

The rational normal curve is a 1-dimensional algebraic variety within the 3-dimensional complex space:

$$ C = \{(x,y,z) \in \mathbb{C}^3 \mid xz-y^2 = 0,\, y-z^2=0, \, x-yz = 0\}. $$

Since $C$ is cut out by 3 equations one might expect it to be 0-dimensional, but it is not. In fact, the rational normal curve is a first example of a non-complete intersection.

Intersecting the rational normal curve with a linear space

Let $L$ be a random linear space of dimension 2. Then, almost surely, the intersection $C\cap L$ is finite. The goal of this example is to compute one of the points in $C\cap L$. First, let us generate the equations of $C$ and $L$.

using HomotopyContinuation, LinearAlgebra
@polyvar x y z
f = [x*z-y^2, y-z^2, x-y*z]
ℓ = randn(ComplexF64, 4) ⋅ [x, y, z, 1];

One is tempted to compute $C\cap L$ by executing solve([f;ℓ]) and simply compute all solutions. But this command will return an error message.

ERROR: The input system is overdetermined. Therefore it is necessary to provide an explicit startsystem.
for details.

The problem here is that for overdetermined system we can’t construct generic starting systems. The reason is simple: a generic overdetermined system has no solutions at all. Nevertheless, if we have a starting system and some of its solutions at hand, we can track them towards $[f, \ell]$.

For instance, the point $p=(1, 1, 1)$ lies both on $C$ and $\{(x,y,z)\in \mathbb{C}^3 \mid x-y+z -1= 0\}$. We can track this solution towards $[f, \ell]$ by executing the following:

ℓ₁ = [1, -1, 1, -1] ⋅ [x, y, z, 1];
p = [1, 1, 1, 1];
solve([f; ℓ₁], [f; ℓ], [p])
AffineResult with 1 tracked paths
• 1 non-singular finite solution (0 real)
• 0 singular finite solutions (0 real)
• 0 solutions at infinity
• 0 failed paths
• random seed: 589721

The syntax [p] is because solve takes as input an array of solutions.