Various methods can obtain certified estimates for roots of polynomials. Many applications in science and engineering additionally utilize the value of functions evaluated at roots. For example, critical values are obtained by evaluating an objective
function at critical points. For analytic evaluation functions, Newtons method naturally applies to yield certified estimates. These estimates no longer apply, however, for Holder continuous functions, which are a generalization of Lipschitz continuous functions where continuous derivatives need not exist. This work develops and analyzes an alternative approach for certified estimates of evaluating locally Holder continuous functions at roots of polynomials. An implementation of the method in Maple demonstrates efficacy and efficiency.
Many algorithms for determining properties of real algebraic or semi-algebraic sets rely upon the ability to compute smooth points. Existing methods to compute smooth points on semi-algebraic sets use symbolic quantifier elimination tools. In this pa
per, we present a simple algorithm based on computing the critical points of some well-chosen function that guarantees the computation of smooth points in each connected compact component of a real (semi)-algebraic set. Our technique is intuitive in principal, performs well on previously difficult examples, and is straightforward to implement using existing numerical algebraic geometry software. The practical efficiency of our approach is demonstrated by solving a conjecture on the number of equilibria of the Kuramoto model for the $n=4$ case. We also apply our method to design an efficient algorithm to compute the real dimension of (semi)-algebraic sets, the original motivation for this research.
The monodromy group is an invariant for parameterized systems of polynomial equations that encodes structure of the solutions over the parameter space. Since the structure of real solutions over real parameter spaces are of interest in many applicati
ons, real monodromy action is investigated here. A naive extension of monodromy action from the complex numbers to the real numbers is shown to be very restrictive. Therefore, we define a real monodromy structure which need not be a group but contains tiered characteristics about the real solutions. This real monodromy structure is applied to an example in kinematics which summarizes all the ways performing loops parameterized by leg lengths can cause a mechanism to change poses.
The Galois/monodromy group of a family of geometric problems or equations is a subtle invariant that encodes the structure of the solutions. Computing monodromy permutations using numerical algebraic geometry gives information about the group, but ca
n only determine it when it is the full symmetric group. We give numerical methods to compute the Galois group and study it when it is not the full symmetric group. One algorithm computes generators while the other gives information on its structure as a permutation group. We illustrate these algorithms with examples using a Macaulay2 package we are developing that relies upon Bertini to perform monodromy computations.
This paper presents two new constructions related to singular solutions of polynomial systems. The first is a new deflation method for an isolated singular root. This construction uses a single linear differential form defined from the Jacobian matri
x of the input, and defines the deflated system by applying this differential form to the original system. The advantages of this new deflation is that it does not introduce new variables and the increase in the number of equations is linear in each iteration instead of the quadratic increase of previous methods. The second construction gives the coefficients of the so-called inverse system or dual basis, which defines the multiplicity structure at the singular root. We present a system of equations in the original variables plus a relatively small number of new variables that completely deflates the root in one step. We show that the isolated simple solutions of this new system correspond to roots of the original system with given multiplicity structure up to a given order. Both constructions are exact in that they permit one to treat all conjugate roots simultaneously and can be used in certification procedures for singular roots and their multiplicity structure with respect to an exact rational polynomial system.
We give a Descartes-like bound on the number of positive solutions to a system of fewnomials that holds when its exponent vectors are not in convex position and a sign condition is satisfied. This was discovered while developing algorithms and softwa
re for computing the Gale transform of a fewnomial system, which is our main goal. This software is a component of a package we are developing for Khovanskii-Rolle continuation, which is a numerical algorithm to compute the real solutions to a system of fewnomials.
Motivated by the recently observed phenomenon of topology trivialization of potential energy landscapes (PELs) for several statistical mechanics models, we perform a numerical study of the finite size $2$-spin spherical model using both numerical pol
ynomial homotopy continuation and a reformulation via non-hermitian matrices. The continuation approach computes all of the complex stationary points of this model while the matrix approach computes the real stationary points. Using these methods, we compute the average number of stationary points while changing the topology of the PEL as well as the variance. Histograms of these stationary points are presented along with an analysis regarding the complex stationary points. This work connects topology trivialization to two different branches of mathematics: algebraic geometry and catastrophe theory, which is fertile ground for further interdisciplinary research.
This paper is concerned with certifying that a given point is near an exact root of an overdetermined or singular polynomial system with rational coefficients. The difficulty lies in the fact that consistency of overdetermined systems is not a contin
uous property. Our certification is based on hybrid symbolic-numeric methods to compute the exact rational univariate representation (RUR) of a component of the input system from approximate roots. For overdetermined polynomial systems with simple roots, we compute an initial RUR from approximate roots. The accuracy of the RUR is increased via Newton iterations until the exact RUR is found, which we certify using exact arithmetic. Since the RUR is well-constrained, we can use it to certify the given approximate roots using alpha-theory. To certify isolated singular roots, we use a determinantal form of the isosingular deflation, which adds new polynomials to the original system without introducing new variables. The resulting polynomial system is overdetermined, but the roots are now simple, thereby reducing the problem to the overdetermined case. We prove that our algorithms have complexity that are polynomial in the input plus the output size upon successful convergence, and we use worst case upper bounds for termination when our iteration does not converge to an exact RUR. Examples are included to demonstrate the approach.
In this paper, we study iterative methods on the coefficients of the rational univariate representation (RUR) of a given algebraic set, called global Newton iteration. We compare two natural approaches to define locally quadratically convergent itera
tions: the first one involves Newton iteration applied to the approximate roots individually and then interpolation to find the RUR of these approximate roots; the second one considers the coefficients in the exact RUR as zeroes of a high dimensional map defined by polynomial reduction, and applies Newton iteration on this map. We prove that over fields with a p-adic valuation these two approaches give the same iteration function, but over fields equipped with the usual Archimedean absolute value, they are not equivalent. In the latter case, we give explicitly the iteration function for both approaches. Finally, we analyze the parallel complexity of the differen
