Computing all solutions to polynomial systems using homotopy continuation

In a previous paper we described a new method for defining homotopies for finding all solutions to polynomial systems. A major feature of this new approach is that the start system for the homotopy need not be a “random” or “generic” system. Also, homotopy paths are strictly increasing in the homotopy parameter. In this paper we establish some principles of implementation and report on the performance of programs that use the new homotopies. A feature of our implementation is that we eliminate divergent paths entirely. We include performance statistics for homotopies derived from more traditional approaches for comparison. Generally, the new approach is faster and more reliable.     

On the solutions to polynomial systems obtained by homotopy methods

Summary A natural class of homotopy methods for solving polynomial systems is considered. It is shown that at least one solution from each connected component of the solution set is obtained. This generalizes the results of previous papers which concentrated on isolated solutions, i.e. connected components with one single point. The number of solution paths ending in a connected component is independent of the particular homotopy in use and defines in a natural way the multiplicity of the connected component. A few numerical experiments illustrate the obtained results.     

Two bijections for the area of Dyck paths

The sum of the areas of (2n+2)-length Dyck paths, or total area, is equal to the number of points with ordinate 1 in Grand-Dyck paths of length 2n+2, n⩾0. A bijective proof of this correspondence is shown by passing through an auxiliary class of marked paths. The sequence of numbers 1,6,29,130,562,… counts the total area of (2n+2)-length Dyck paths as well as the number of points having ordinate 0 and which satisfy an additional condition, on 2n-length paths made up of rise and fall steps. First, a bijection between these points and the triangles constituting the total area of (2n+2)-length Dyck paths is established, and then the correspondence between the above-mentioned points and the points with ordinate 1 on (2n+2)-length Grand-Dyck paths is shown.     

Critical points at infinity and blow up of solutions of autonomous polynomial differential systems via compactification

Critical points at infinity for autonomous differential systems are defined and used as an essential tool. Rn is mapped onto the unit ball by various mappings and the boundary points of the ball are used to distinguish between different directions at infinity. These mappings are special cases of compactifications. It is proved that the definition of the critical points at infinity is independent of the choice of the mapping to the unit ball.We study the rate of blow up of solutions in autonomous polynomial differential systems of equations via compactification methods. To this end we represent each solution as a quotient of a vector valued function (which is a solution of an associated autonomous system) by a scalar function (which is a solution of a related scalar equation).     

Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers

We present a new probabilistic method for solving systems of polynomial equations and inequations. Our algorithm computes the equidimensional decomposition of the Zariski closure of the solution set of such systems. Each equidimensional component is encoded by a generic fiber, that is a finite set of points obtained from the intersection of the component with a generic transverse affine subspace. Our algorithm is incremental in the number of equations to be solved. Its complexity is mainly cubic in the maximum of the degrees of the solution sets of the intermediate systems counting multiplicities.Our method is designed for coefficient fields having characteristic zero or big enough with respect to the number of solutions. If the base field is the field of the rational numbers then the resolution is first performed modulo a random prime number after we have applied a random change of coordinates. Then we search for coordinates with small integers and lift the solutions up to the rational numbers. Our implementation is available within our package Kronecker from version 0.166, which is written in the Magma computer algebra system.     

Regenerative cascade homotopies for solving polynomial systems

A key step in the numerical computation of the irreducible decomposition of a polynomial system is the computation of a witness superset of the solution set. In many problems involving a solution set of a polynomial system, the witness superset contains all the needed information. Sommese and Wampler gave the first numerical method to compute witness supersets, based on dimension-by-dimension slicing of the solution set by generic linear spaces, followed later by the cascade homotopy of Sommese and Verschelde. Recently, the authors of this article introduced a new method, regeneration, to compute solution sets of polynomial systems. Tests showed that combining regeneration with the dimension-by-dimension algorithm was significantly faster than naively combining it with the cascade homotopy. However, in this article, we combine an appropriate randomization of the polynomial system with the regeneration technique to construct a new cascade of homotopies for computing witness supersets. Computational tests give strong evidence that regenerative cascade is superior in practice to previous methods.     

On the cyclicity of weight-homogeneous centers

Let W be a weight-homogeneous planar polynomial differential system with a center. We find an upper bound of the number of limit cycles which bifurcate from the period annulus of W under a generic polynomial perturbation. We apply this result to a particular family of planar polynomial systems having a nilpotent center without meromorphic first integral.     

Theory of formal integrability and DAEs: effective computations

This paper deals with the computation of the formally integrable systems underlying a given quasi-linear polynomial DAE. We use as stopping condition the criterium of differential stability, which happens to be equivalent to the formal integrability in dimension 1. A symbolic method is developed to compute effectively a finite collection of so-called triangular stable DAEs, whose solutions are precisely all the solutions of the initial system. Besides, this algorithm enables to determine the generic points of a triangular DAE, by checking the non-nullity of a single polynomial. This revised version was published online in June 2006 with corrections to the Cover Date.     

Sweeping algebraic curves for singular solutions

Many problems give rise to polynomial systems. These systems often have several parameters and we are interested to study how the solutions vary when we change the values for the parameters. Using predictor-corrector methods we track the solution paths. A point along a solution path is critical when the Jacobian matrix is rank deficient. The simplest case of quadratic turning points is well understood, but these methods no longer work for general types of singularities. In order not to miss any singular solutions along a path we propose to monitor the determinant of the Jacobian matrix. We examine the operation range of deflation and relate the effectiveness of deflation to the winding number. Computational experiments on systems coming from different application fields are presented.     

On the probability distribution of data at points in real complete intersection varieties

We show several estimates on the probability distribution of some data at points in real complete intersection varieties: norms of real affine solutions, condition number of real solution of real systems of multi-variate polynomial equations and convergence radius of Newton's operator for under-determined system of multi-variate polynomial equations.     

Counting solutions to binomial complete intersections

We study the problem of counting the total number of affine solutions of a system of n binomials in n   variables over an algebraically closed field of characteristic zero. We show that we may decide in polynomial time if that number is finite. We give a combinatorial formula for computing the total number of affine solutions (with or without multiplicity) from which we deduce that this counting problem is #P$\#P$-complete. We discuss special cases in which this formula may be computed in polynomial time; in particular, this is true for generic exponent vectors.     

高维代数簇计算的一些结果

本文在［１］的基础上给出计算高维代数簇的特征值方法,进一步结果,得到了不可约集的母点和对应于极大无关变元集的多项式方程组的孤立解之间对应关系的进一步刻画．     

Application of Homotopy Methods to Power Systems

In this paper, the application of homotopy methods to the load flow multi-solution problems of power systems is introduced. By the generalized Bernshtein theorem, the combinatorial number C2n^m is shown to be the BKK bound of the number of isolated solutions of the polynomial system transformed from load flow equations with generically chosen coefficients. As a result of the general Bezout number, the number of paths being followed is reduced significantly in the practical load flow computation. Finally, the complete P-V cures are obtained by tracking the load flow with homotopy methods.     

Multi-valued solutions and branch point singularities for nonlinear hyperbolic or elliptic systems

Multi-valued solutions are constructed for 2 × 2 first-order systems using a generalization of the hodograph transformation. The solution is found as a complex analytic function on a complex Riemann surface for which the branch points move as part of the solution. The branch point singularities are envelopes for the characteristics and thus move at the characteristic speeds. We perform an analysis of stability of these singularities with respect to perturbations of the initial data. The generic singularity types are folds, cusps, and nondegenerate umbilic points with non-zero 3-jet. An isolated singularity is generically a square root branch point corresponding to a fold. Two types of collisions between singularities are generic: At a “tangential” collision between two singularities moving at the same characteristic speed, a cube root branch point is formed, corresponding to a cusp. A “non-tangential” collision, between two square root branch points moving at different characteristic speeds, remains a square root branch point at the collision and corresponds to a nondegenerate umbilic point. These results are also valid for a diagonalizable n-th order system for which there are exactly two speeds. © 1993 John Wiley & Sons, Inc.     

Positive solutions of quasilinear parabolic systems with Dirichlet boundary condition

Coupled systems for a class of quasilinear parabolic equations and the corresponding elliptic systems, including systems of parabolic and ordinary differential equations are investigated. The aim of this paper is to show the existence, uniqueness, and asymptotic behavior of time-dependent solutions. Also investigated is the existence of positive maximal and minimal solutions of the corresponding quasilinear elliptic system. The elliptic operators in both systems are allowed to be degenerate in the sense that the density-dependent diffusion coefficients Di(ui) may have the property Di(0)=0 for some or all i=1,…,N, and the boundary condition is ui=0. Using the method of upper and lower solutions, we show that a unique global classical time-dependent solution exists and converges to the maximal solution for one class of initial functions and it converges to the minimal solution for another class of initial functions; and if the maximal and minimal solutions coincide then the steady-state solution is unique and the time-dependent solution converges to the unique solution. Applications of these results are given to three model problems, including a scalar polynomial growth problem, a coupled system of polynomial growth problem, and a two component competition model in ecology.     

On the number of zeros of Abelian integrals for a polynomial Hamiltonian irregular at infinity

Up to now, most of the results on the tangential Hilbert 16th problem have been concerned with the Hamiltonian regular at infinity, i.e., its principal homogeneous part is a product of the pairwise different linear forms. In this paper, we study a polynomial Hamiltonian which is not regular at infinity. It is shown that the space of Abelian integral for this Hamiltonian is finitely generated as a R[h] module by several basic integrals which satisfy the Picard-Fuchs system of linear differential equations. Applying the bound meandering principle, an upper bound for the number of complex isolated zeros of Abelian integrals is obtained on a positive distance from critical locus. This result is a partial solution of tangential Hilbert 16th problem for this Hamiltonian. As a consequence, we get an upper bound of the number of limit cycles produced by the period annulus of the non-Hamiltonian integrable quadratic systems whose almost all orbits are algebraic curves of degree k+n, under polynomial perturbation of arbitrary degree.     

Independence equivalence classes of paths

The independence equivalence class of a graph G is the set of graphs that have the same independence polynomial as G. A graph whose independence equivalence class contains only itself, up to isomorphism, is independence unique. Beaton, Brown and Cameron [2] showed that paths with an odd number of vertices are independence unique and raised the problem of finding the independence equivalence class of paths with an even number of vertices. The problem is completely solved in this paper.     

Polyhedral end games for polynomial continuation

Bernshtein’s theorem provides a generically exact upper bound on the number of isolated solutions a sparse polynomial system can have in (ℂ^*)ⁿ, with ℂ^* = ℂ\{0}. When a sparse polynomial system has fewer than this number of isolated solutions some face system must have solutions in (ℂ^*)ⁿ. In this paper we address the process of recovering a certificate of deficiency from a diverging solution path. This certificate takes the form of a face system along with approximations of its solutions. We apply extrapolation to estimate the cycle number and the face normal. Applications illustrate the practical usefulness of our approach. This revised version was published online in August 2006 with corrections to the Cover Date.     

First Order Perturbation and Local Stability of Parametrized Systems

A problem frequently encountered in geometric constraint solving and related settings is to ascertain sensitivity of solutions arising from a well constrained input configuration. This is important for tolerancing and motion planning, for example. An example would be determining lines simultaneously tangent to four given spheres (which originates as a line-of-sight problem); how much does a perturbation of the input affect the positioning of these lines. Once translated to an algebraic setting one has a system of polynomial equations with some coefficients parametrized, and wants to determine the solutions and a good approximation of their sensitivity to changes in the parameters. We will compute this sensitivity from first order changes in an appropriate Gröbner basis. We demonstrate the applicability on several examples. We also discuss a more global form of stability, wherein one wants to know about perturbations that might change the character of the solution space e.g. by having fewer than the generic number of solutions.     

Simple bounds and greedy algorithms for decomposing a flow into a minimal set of paths

Given arbitrary source and target nodes s, t and an s–t-flow defined by its flow-values on each arc of a network, we consider the problem of finding a decomposition of this flow with a minimal number of s–t-paths. This problem is issued from the engineering of telecommunications networks for which the task of implementing a routing solution consists in integrating a set of end-to-end paths. We show that this problem is NP-hard in the strong sense and give some properties of an optimal solution. We then propose upper and lower bounds for the number of paths in an optimal solution. Finally we develop two heuristics based on the properties of a special set of solutions called saturating solutions.