Point estimation of simultaneous methods for solving polynomial equations: A survey (II)

The construction of computationally verifiable initial conditions which provide both the guaranteed and fast convergence of the numerical root-finding algorithm is one of the most important problems in solving nonlinear equations. Smale's “point estimation theory” from 1981 was a great advance in this topic; it treats convergence conditions and the domain of convergence in solving an equation f(z)=0$f(z)=0$ using only the information of f   at the initial point _z0$z_0$. The study of a general problem of the construction of initial conditions of practical interest providing guaranteed convergence is very difficult, even in the case of algebraic polynomials. In the light of Smale's point estimation theory, an efficient approach based on some results concerning localization of polynomial zeros and convergent sequences is applied in this paper to iterative methods for the simultaneous determination of simple zeros of polynomials. We state new, improved initial conditions which provide the guaranteed convergence of frequently used simultaneous methods for solving algebraic equations: Ehrlich–Aberth's method, Ehrlich–Aberth's method with Newton's correction, Börsch-Supan's method with Weierstrass’ correction and Halley-like (or Wang–Zheng) method. The introduced concept offers not only a clear insight into the convergence analysis of sequences generated by the considered methods, but also explicitly gives their order of convergence. The stated initial conditions are of significant practical importance since they are computationally verifiable; they depend only on the coefficients of a given polynomial, its degree n and initial approximations to polynomial zeros.     

Mean value conjectures for rational maps

Let p be a polynomial in one complex variable. Smale's mean value conjecture estimates |p′(z)| in terms of the gradient of a chord from (z,?p(z)) to some stationary point on the graph of p. The conjecture does not immediately generalize to rational maps since its formulation is invariant under the group of affine maps, not the full Möbius group. Here we give two possible generalizations to rational maps, both of which are Möbius invariant. In both cases we prove a version with a weaker constant, in parallel to the situation for Smale's mean value conjecture. Finally, we discuss some candidate extremal rational maps, namely rational maps all of whose critical points are fixed points.     

A Deterministic Algorithm to Compute Approximate Roots of Polynomial Systems in Polynomial Average Time

We describe a deterministic algorithm that computes an approximate root of n complex polynomial equations in n unknowns in average polynomial time with respect to the size of the input, in the Blum–Shub–Smale model with square root. It rests upon a derandomization of an algorithm of Beltrán and Pardo and gives a deterministic affirmative answer to Smale’s 17th problem. The main idea is to make use of the randomness contained in the input itself.     

Computation of efficient compromise arcs in Convex Quadratic Multicriteria Optimization

Given a Convex Quadratic Multicriteria Optimization Problem, we show the stability of the Domination Problem. By modifying Benson’s single parametric method, which is based on the Domination Problem, we are able to show the existence of an efficient compromise arc connecting any two efficient points. Moreover, we deduce an algorithm which realizes the modification in polynomial time.Part of the article is taken from the author’s doctoral dissertation at the University of Eichstätt-Ingolstadt     

Polynomial Time Uniform Word Problems

We have two polynomial time results for the uniform word problem for a quasivariety Q: (a) The uniform word problem for Q can be solved in polynomial time iff one can find a certain congruence on finite partial algebras in polynomial time. (b) Let Q* be the relational class determined by Q. If any universal Horn class between the universal closure S(Q*) and the weak embedding closure S?(Q*) of Q* is finitely axiomatizable then the uniform word problem for Q is solvable in polynomial time. This covers Skolem's 1920 solution to the uniform word problem for lattices and Evans' 1953 applications of the weak embeddability property for finite partial V algebras.     

A branch-and-cut algorithm for a generalization of the Uncapacitated Facility Location Problem

Summary We introduce a generalization of the well-know Uncapacitated Facility Location Problem, in which clients can be served not only by single facilities but also by sets of facilitities. The problem, calledGaneralized Uncapacitated Facility Lacition Problem (GUFLP), was inspired by the Index Selection Problem in physical database design. We for mulate GUFLP as a Set Packing Problem, showing that our model contains all the clique inequalities (in polynomial number). Moreover, we describe and exact separation procedure for odd-hole inequalities, based on the particular structure of the problem. These results are used within a branch-and-cut algorithm for the exact solution of GUFLP. Computational results on two different classes of test problems are given.     

Approximation by neural networks and learning theory

We consider the problem of Learning Neural Networks from samples. The sample size which is sufficient for obtaining the almost-optimal stochastic approximation of function classes is obtained. In the terms of the accuracy confidence function, we show that the least-squares estimator is almost-optimal for the problem. These results can be used to solve Smale's network problem.     

Generalized loop‐erased random walks and approximate reachability

In this paper we extend the loop‐erased random walk (LERW) to the directed hypergraph setting. We then generalize Wilson's algorithm for uniform sampling of spanning trees to directed hypergraphs. In several special cases, this algorithm perfectly samples spanning hypertrees in expected polynomial time. Our main application is to the reachability problem, also known as the directed all‐terminal network reliability problem. This classical problem is known to be # P‐complete, hence is most likely intractable (Ball and Provan, SIAM J Comput 12 (1983) 777–788). We show that in the case of bi‐directed graphs, a conjectured polynomial bound for the expected running time of the generalized Wilson algorithm implies a FPRAS for approximating reachability. Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 201‐223, 2014     

实对称型上的Schur子空间及应用

本文构作了Schur型多项式,将其作为研究实对称型的基础.研究了具有零点(1,1,...,1)的实对称型形成的子空间,即Schur子空间.建立了这种子空间的构造性理论,并应用于计算(构造)实代数几何中比较关心的对称型正性判定问题,以及给出一些特殊类型的Hilbert第17问题的构造解.     

On the Stability of a Retarded Functional Differential Equation Edgeworth Process

Following Smale's notations, let n and 1 denote respectively the number of agents and commodities in a pure exchange barter economy. Let u₁,u₂, ... u_n denote n real valued functions representing the individuals preferences and which depend on the past as well as present holdings. We assume that the mechanism which describes the adjustment in the quantities traded at any point in time be given by an Edgeworth process in the form of an autonomous retarded functional differential equation type. The aim of this study is first to develop necessary conditions for this type of mechanism to converge to the set of Pareto-points. Second, we examine the conditions under which positive results may be obtained as solutions of the Eggeworth dynamic approach the boundary of the smooth submanifold of feasible allocations W. Third, necessary conditions are developped to assure local stabiltyof a Pareto point. Finally, we investigate the conditions under which a Pareto point is unstable. The result on asymptotic behavior uses the ideas of LaSalle'Theorem and those on stability are proved by means of Liapunov'theory, using Hale'stability Theorem on retarded functional differential equations.     

Further results on Hilbert’s Tenth Problem

Hilbert's Tenth Problem(HTP) asks for an algorithm to test whether an arbitrary polynomial Diophantine equation with integer coefficients has solutions over the ring Z of integers.This was finally solved negatively by Matiyasevich in 1970.In this paper we obtain some further results on HTP over Z.We prove that there is no algorithm to determine for any P(z_1,...,z_9) ∈ Z[z_1,...,z_9] whether the equation P(z_1,...,z_9)=0 has integral solutions with z_9≥0.Consequently,there is no algorithm to test whether an arbitrary polynomial Diophantine equation P(z_1,...,z_(11))=0(with integer coefficients) in 11 unknowns has integral solutions,which provides the best record on the original HTP over Z.We also prove that there is no algorithm to test for any P(z_1,...,z_(17))∈Z[z_1,...,z_(17)] whether P(z_1,...,z_(17))=0 has integral solutions,and that there is a polynomial Q(z_1,...,z_(20))∈Z[z_1,...,z_(20)] such that {Q(z_1~2,...,z_(20)~2):z_1,...,z_(20)∈Z}∩ {0,1,2,...} coincides with the set of all primes.     

Lifting/Descending Processes for Polynomial Zeros

The recently proposed Chebyshev-like lifting map for the zeros of a univariate polynomial was motivated by its applications to splitting a univariate polynomial p(z) numerically into factors, which is a major step of some most efficient algorithms for approximating polynomial zeros. We complement the Chebyshev-like lifting process by a descending process, decrease the estimated computational cost of performing the algorithm, demonstrate its correlation to Graeffe's lifting/descending process, and generalize lifting from Graeffe's and Chebyshev-like maps to any fixed rational map of the zeros of the input polynomial.     

Transgenetic algorithm for the Traveling Purchaser Problem

In this paper an evolutionary algorithm is presented for the Traveling Purchaser Problem, an important variation of the Traveling Salesman Problem. The evolutionary approach proposed in this paper is called transgenetic algorithm. It is inspired on two significant evolutionary driving forces: horizontal gene transfer and endosymbiosis. The performance of the algorithm proposed for the investigated problem is compared with other recent works presented in the literature. Computational experiments show that the proposed approach is very effective for the investigated problem with 17 and 9 new best solutions reported for capacitated and uncapacitated instances, respectively.     

On some structured inverse eigenvalue problems

This work deals with various finite algorithms that solve two special Structured Inverse Eigenvalue Problems (SIEP). The first problem we consider is the Jacobi Inverse Eigenvalue Problem (JIEP): given some constraints on two sets of reals, find a Jacobi matrix J (real, symmetric, tridiagonal, with positive off-diagonal entries) that admits as spectrum and principal subspectrum the two given sets. Two classes of finite algorithms are considered. The polynomial algorithm which is based on a special Euclid–Sturm algorithm (Householder's terminology) and has been rediscovered several times. The matrix algorithm which is a symmetric Lanczos algorithm with a special initial vector. Some characterization of the matrix ensures the equivalence of the two algorithms in exact arithmetic. The results of the symmetric situation are extended to the nonsymmetric case. This is the second SIEP to be considered: the Tridiagonal Inverse Eigenvalue Problem (TIEP). Possible breakdowns may occur in the polynomial algorithm as it may happen with the nonsymmetric Lanczos algorithm. The connection between the two algorithms exhibits a similarity transformation from the classical Frobenius companion matrix to the tridiagonal matrix. This result is used to illustrate the fact that, when computing the eigenvalues of a matrix, the nonsymmetric Lanczos algorithm may lead to a slow convergence, even for a symmetric matrix, since an outer eigenvalue of the tridiagonal matrix of order n − 1 can be arbitrarily far from the spectrum of the original matrix. This revised version was published online in August 2006 with corrections to the Cover Date.     

New Models of the Generalized Minimum Spanning Tree Problem

We consider a generalization of the Minimum Spanning Tree Problem, called the Generalized Minimum Spanning Tree Problem, denoted by GMST. It is known that the GMST problem is NP-hard. We present a stronger result regarding its complexity, namely, the GMST problem is NP-hard even on trees as well an exact exponential time algorithm for the problem based on dynamic programming. We describe new mixed integer programming models of the GMST problem, mainly containing a polynomial number of constraints. We establish relationships between the polytopes corresponding to their linear relaxations. Based on a new model of the GMST we present a solution procedure that solves the problem to optimality for graphs with nodes up to 240. We discuss the advantages of our method in comparison with earlier methods.     

Human capital externality and chaotic equilibrium dynamics

This study develops a two-period overlapping generations model in which adults undertake educational investment decisions on behalf of young agents. In addition to educational investment, we argue that the accumulation of human capital is also dependent upon the externality from average human capital within the economy. In a departure from the previous literature in this area, we assume that there is a reduction in the overall productivity of human capital accumulation brought about by human capital externality, and show that complicated dynamics will emerge under this circumstance. In addition to displaying the chaotic dynamics in the sense of Li and Yorke, we also verify the existence of Devaney's chaos and Smale's chaos.     

Bifurcations of limit cycles in a Z 4-equivariant quintic planar vector field

In this paper, a Z4-equivariant quintic planar vector field is studied. The Hopf bifurcation method and polycycle bifurcation method are combined to study the limit cycles bifurcated from the compounded cycle with 4 hyperbolic saddle points. It is found that this special quintic planar polynomial system has at least four large limit cycles which surround all singular points. By applying the double homoclinic loops bifurcation method and Hopf bifurcation method, we conclude that 28 limit cycles with two different configurations exist in this special planar polynomial system. The results acquired in this paper are useful for studying the weakened 16th Hilbert＇s Problem.     

Hilbert's Tenth Problem for fields of rational functions over finite fields

Summary We prove that there is no algorithm to solve arbitrary polynomial equations over a field of rational functions in one letter with constants in a finite field of characteristic other than 2 and hence, Hilbert's Tenth Problem for any such field is undecidable.Oblatum 1-XI-1989Supported in part by NSF Grant DMS 8605198.     

New inequalities for the General Routing Problem

A large new class of valid inequalities is introduced for the General Routing Problem which properly contains the class of ‘K-C constraints’. These are also valid for the Rural Postman Problem. A separation algorithm is given for a subset of these inequalities which runs in polynomial time.     

Computational complexity of Van der Heyden's variable dimension algorithm and Dantzig-Cottle's principal pivoting method for solving LCP's

We show that Van der Heyden's variable dimension algorithm and Dantzig and Cottle's principal pivoting method require 2ⁿ–1 pivot steps to solve a class of linear complementarity problems of ordern. Murty and Fathi have previously shown that the computational effort required to solve a linear complementarity problem of ordern by Lemke's complementary pivot algorithm or by Murty's Bard-type algorithm is not bounded above by a polynomial inn. Our study shows that the variable dimension algorithm and the principal pivoting method have similar worst case computational requirements.