key: cord-0047243-7zii8l7z
authors: Hauenstein, Jonathan D.; Regan, Margaret H.
title: Evaluating and Differentiating a Polynomial Using a Pseudo-witness Set
date: 2020-06-06
journal: Mathematical Software - ICMS 2020
DOI: 10.1007/978-3-030-52200-1_6
sha: c02b8b567451fc6088182a13fbebba5dd0acfab3
doc_id: 47243
cord_uid: 7zii8l7z

Polynomials which arise via elimination can be difficult to compute explicitly. By using a pseudo-witness set, we develop an algorithm to explicitly compute the restriction of a polynomial to a given line. The resulting polynomial can then be used to evaluate the original polynomial and directional derivatives along the line at any point on the given line. Several examples are used to demonstrate this new algorithm including examples of computing the critical points of the discriminant locus for parameterized polynomial systems.

Parameterized polynomial systems arise in various applications in science and engineering, such as in computer vision [15, 17, 22] , kinematics [14, 23] , and chemistry [1, 19] . Often in these applications, real solutions are desired. The complement of the discriminant locus associated with the parameterized polynomial system consists of cells where the number of real solutions is constant. Elimination methods (e.g., see [8, Chap. 3] ) theoretically provide an approach to explicitly compute a defining equation for the discriminant locus. If the discriminant locus is a curve or surface, there are several numerical methods that can be used to plot it, e.g., [6, 7, 18] . When the explicit expression is difficult to compute, this paper develops a numerical algebraic geometric approach based on pseudo-witness sets [13] for both evaluating implicitly defined polynomials and directional derivatives. In particular, the approach yields an explicit univariate polynomial equal to the defining equation restricted to a line which can then be evaluated or differentiated as needed. When the parameterized system and line have rational coefficients, the resulting univariate polynomial also has rational coefficients which can be computed exactly from the numerical data [2] .

One application of this new approach is to compute the critical points of the discriminant polynomial which are outside of the discriminant locus without explicitly computing the discriminant. This set of critical points contains at least one point in each compact cell in the complement of the discriminant locus [10] which can be useful for determining the possible number of real solutions as well as the real monodromy structure [11] .

The remainder of the paper is as follows. Section 2 describes the approach based on using pseudo-witness sets. Section 3 presents an algorithm for performing the computations with some illustrative examples. Section 4 provides two examples of computing critical points.

In numerical algebraic geometry, e.g., see [4, 21] , a witness point set for a hypersurface H ⊂ C n consists of the intersection points of H with a line L ⊂ C n . Suppose that f (x) is a given polynomial and H is the hypersurface defined by the vanishing of f . Then, the witness point set for H corresponds with the roots of the univariate polynomial obtained by restricting f to the line L. Since every univariate polynomial is defined up to scale by its roots, one can recover f | L by computing its roots along with knowing f | L (T ) for some value T which is not a root of f | L . The following is an illustration of this basic setup.

Consider the polynomial f (x, y) = y − x 2 with corresponding hypersurface H ⊂ C 2 and the line L ⊂ C 2 defined parametrically by:

Therefore, one can explicitly compute

For t 1 = 1 − √ 2 and t 2 = 1 + √ 2, one has

Hence, f | L (t) = s(t − t 1 )(t − t 2 ) for some constant s which can be computed from, say, requiring f | L (T ) = 1 where T = 2, i.e., s = −1. Therefore, one has recovered f | L (t) in (1) from H ∩ L with f | L (T ) = 1 as illustrated in Fig. 1(a) .

The remainder of this section extends this idea using pseudo-witness sets when f is a polynomial over C that is not known explicitly, but the corresponding hypersurface H arises as the closure of a projection of an algebraic set. For simplicity of presentation, assume that F : [13] for H, say {F, π, M, W }, is a numerical algebraic geometric data structure that permits computations on H without knowing the defining polynomial f for H. The last two items are a linear space M ⊂ C N and a finite set W = V ∩ M. In particular, M = L × L where 

as shown in the following.

The univariate polynomial describing f along the line L is correctly described by (3) .

Proof.

The assumption on T is that f | L (T ) = 0, i.e., L ⊂ H. Hence, f | L is a nonzero polynomial which has finitely many roots, namely t 1 , . . . , t k with multiplicity m 1 , . . . , m k , respectively. Thus,

Since the roots define the univariate polynomial up to scale, the leading coefficient is used to achieve the desired value at T and thus everywhere along L.

The following illustrates a pseudo-witness set and Theorem 1.

Consider the hypersurface H ⊂ C 2 from Example 1 under the assumption that we are given

where t 1 and t 2 are as in Example 1 with m 1 = m 2 = 1. Hence, π(W ) = H ∩ L as in (2) . Therefore, with T = 2 and f | L (T ) = 1, (3) simplifies to f | L (t) in (1).

The only assumption on the line L is that L ⊂ H so that one can find T such that f | L (T ) = 0. Of course, one can check if L ⊂ H by a pseudo-witness set membership test [12] in which case one would simply have f L (t) ≡ 0. Thus, L is not necessarily assumed to intersect H transversely, so the number of roots and multiplicities can vary for different choices of L. Nonetheless, Theorem 1 applies as is illustrated in the following two examples. Clearly, once the univariate polynomial f | L (t) in (3) is computed explicitly, one can easily determine the value of f at any point along L via evaluation. Moreover, if L is parameterized by v · t + u, then f | 

Example 5. For L in Example 3 and Example 4, one has v = (0, 1) and v = (1, 0), respectively. Hence, the corresponding directional derivatives are simply partial derivatives of f (x, y) = y − x 2 with respect to y and x, respectively. From Example 3, one obtains ∂f ∂y (1, t) = 1 while Example 4 yields ∂f ∂x (t, 0) = −2t and ∂ 2 f ∂x 2 (t, 0) = −2.

Theorem 1 immediately justifies Algorithm 1 for explicitly computing a polynomial restricted to a line. The following two examples exemplify this algorithm applied to the discriminant locus. Fig. 2(a) . The pseudo-witness set yields t 1 = 0 and t 2 = 4/3 with m 1 = m 2 = 1. The corresponding scale factor is

Of course, one can easily compute that the discriminant of g satisfying

For the line L ⊂ C The other input for Algorithm 1 is, say, T = −3 with f | L (T ) = −108 for scale. This setup is illustrated in Fig. 2(b) .

The pseudo-witness set yields t 1 = −1.9511, t 2 = −2.3995 + 5.0378i, and t 3 = −2.3995 − 5.0378i with m 1 = m 2 = m 3 = 1. The corresponding scale factor is s = 4 so that f | L (t) = 4t 3 + 27t 2 + 162t + 243.

As in Example 6, one can easily compute that the discriminant of g satisfying f (b(T ), c(T )) = −108 is f (b, c) = 4b 3 + 27c 2 with f (b(t), c(t)) = f | L (t) as above. 

When the line L is fixed, Algorithm 1 computes the restriction of a polynomial f to L. The following presents two examples of combining this idea with homotopy continuation to compute critical points of f , namely ∇f = 0. The set of real solutions to ∇f = 0 with f = 0 contains at least one point in each compact cell of R n ∩ {f = 0} [10] . The website dx.doi.org/10.7274/r0-0mc0-gt33 contains the necessary files to perform these computations using Bertini [3] .

This first example demonstrates the approach given f (x, y) = x 4 − x 2 + y 2 which defines a lemniscate, but utilizes a pseudo-witness set for the computation. The aim is to compute all real solutions of ∇f = 0 and f = 0. For genericity, replace ∇f = 0 with the equivalent condition that the directional derivatives of f in both the α = (α 1 , α 2 ) and β = (β 1 , β 2 ) directions, namely D α f and D β f , vanish for general α and β. We used α 1 = 1, α 2 = 5 + 3 √ −1, β 1 = 4 + √ −1, and β 2 = 1 in our computation.

Since one is setting directional derivatives equal to zero, the scale factor is irrelevant and can be simply set to 1. We first compute a witness set for each of the cubic curves defined by D α f = 0 and D β f = 0 where each of them are expressed in terms of univariate roots following Sect. 2. Then, we simply intersect these two cubic curves using a diagonal homotopy [20] that tracks 3 2 = 9 paths. There are 3 finite endpoints corresponding with the 3 solutions of ∇f = 0, all of which are real and shown in Fig. 3(a) . Two of these have f = 0 with one in each of the two compact cells of R 2 ∩ {f = 0}.

The Kuramoto model [16] is a mathematical model of an oscillating system to describe synchronization. After a standard conversion to polynomials, the discriminant locus for the steady states of the 3-oscillator Kuramoto model is modeled by H = π(V ) where π(ω 1 , ω 2 , c 1 , c 2 , s 1 , s 2 ) = (ω 1 , ω 2 ) and V = V(F ) with F (ω1, ω2, c1, c2, s1, s2 

Letting f be a defining polynomial for H, the aim is to compute the real solutions of ∇f = 0 with f = 0 using a pseudo-witness set for H. As in Sect. 4.1, we replace ∇f = 0 with the equivalent condition that two general directional derivatives vanish. In this case, the vanishing of a general directional derivative of f yields a degree 11 curve, so a diagonal homotopy [20] to intersect the vanishing of two directional derivatives tracks 11 2 = 121 paths. This yields 103 finite solutions consisting of 37 that satisfy f = 0 which can be verified using a membership test via a pseudo-witness set for H [12] . Sorting through these 37 yields 19 real critical points with f = 0. Figure 3 (b) plots the real part of H along with these 19 real critical points on a contour plot of f showing that at least one is contained in each compact cell of R 2 ∩ {f = 0}. 

One-dimensional slow invariant manifolds for spatially homogeneous reactive systems

Recovering exact results from inexact numerical data in algebraic geometry

Bertini: software for numerical algebraic geometry

Numerically solving polynomial systems with Bertini. SIAM

Tensor decomposition and homotopy continuation

Cell decomposition of almost smooth real algebraic surfaces

A numerical method for computing border curves of biparametric real polynomial systems and applications

Ideals, Varieties, and Algorithms, 4th edn

Complex Analytic Geometry

Smooth points on semi-algebraic sets

Real monodromy action

Membership tests for images of algebraic sets by linear projections

Witness sets of projections

Synthesis of three-revolute spatial chains for body guidance

From structure-from-motion point clouds to fast location recognition

Self-entrainment of a population of coupled non-linear oscillators

Dynamic 3D scene analysis from a moving vehicle

Finding all real points of a complex curve

Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems

Solving polynomial systems equation by equation

The Numerical Solution of Systems of Polynomials Arising in Engineering and Science

Photo tourism: exploring photo collections in 3D

Numerical algebraic geometry and algebraic kinematics

Acknowledgments. All authors acknowledge support from NSF CCF-1812746. Additional support for was provided by ONR N00014-16-1-2722 (Hauenstein) and Schmitt Leadership Fellowship in Science and Engineering (Regan).