计算多项式函数的全局下确界和全局最小值的有效算法

通过捕获所谓的严格临界点, 本文提出了一个计算实多项式函数的全局下确界和全局最小值的有效方法. 对于实数域R 上一个n 元多项式f, 该方法可用来判定f 在Rⁿ 上是否具有有限的全局下确界. 在f 具有有限的全局下确界的情况下, f 的下确界可严格地表示为码(h; a, b), 其中h 是一个实单元多项式, a 和b 是使得a < b 的两个有理数, 而(h; a, b) 代表h(z) 在开区间]a, b[ 中仅有的实根.此外, 当f 具有有限下确界时, 本文的方法可进一步判定f 的下确界能否达到. 在我们的算法设计中,著名的吴方法起着重要作用.     

Global minimization of multivariate polynomials using nonstandard methods

The purpose of this paper is to present two algorithms for global minimization of multivariate polynomials. For a multivariate real polynomial f, we provide an effective algorithm for deciding whether or not the infimum of f is finite. In the case of f having a finite infimum, the infimum of f can be accurately coded as (h; a, b), where h is a real polynomial in one variable, a and b is two rational numbers with a?<?b, and (h, a, b) stands for the only real root of h in the open interval ]a, b[. Moreover, another algorithm is provided to decide whether or not the infimum of f is attained when the infimum of f is finite. Our methods are called ??nonstandard??, because an infinitesimal element is introduced in our arguments.     

Determination of the limits for multivariate rational functions

The purpose of this paper is to solve the problem of determining the limits of multivariate rational functions.It is essential to decide whether or not limxˉ→0f g=0 for two non-zero polynomials f,g∈R[x1,...,xn]with f(0,...,0)=g(0,...,0)=0.For two such polynomials f and g,we establish two necessary and sufcient conditions for the rational functionf g to have its limit 0 at the origin.Based on these theoretic results,we present an algorithm for deciding whether or not lim(x1,...,xn)→(0,...,0)f g=0,where f,g∈R[x1,...,xn]are two non-zero polynomials.The design of our algorithm involves two existing algorithms:one for computing the rational univariate representations of a complete chain of polynomials,another for catching strictly critical points in a real algebraic variety.The two algorithms are based on the well-known Wu’s method.With the aid of the computer algebraic system Maple,our algorithm has been made into a general program.In the final section of this paper,several examples are given to illustrate the efectiveness of our algorithm.     

Solving polynomial optimization problems via the truncated tangency variety and sums of squares

Let f,g_i,i=1,…,l,h_j,j=1,…,m, be polynomials on Rⁿ and S?{x∈Rⁿ∣g_i(x)=0,i=1,…,l,h_j(x)≥0,j=1,…,m}. This paper proposes a method for finding the global infimum of the polynomial f on the semialgebraic set S via sum of squares relaxation over its truncated tangency variety, even in the case where the polynomial f does not attain its infimum on S. Under a constraint qualification condition, it is demonstrated that: (i) The infimum of f on S and on its truncated tangency variety coincide; and (ii) A sums of squares certificate for nonnegativity of f on its truncated tangency variety. These facts imply that we can find a natural sequence of semidefinite programs whose optimal values converge, monotonically increasing to the infimum of f on S.     

Global Minimization of a Multivariate Polynomial using Matrix Methods

The problem of minimizing a polynomial function in several variables over R ⁿ is considered and an algorithm is given. When the polynomial has a minimum the algorithm returns the global minimal value and finds at least one point in every connected component of the set of minimizers. A characterization of such points is given. When the polynomial does not have a minimum the algorithm computes its infimum. No assumption is made on the polynomial.     

Improvements upon the Chevalley-Warning-Ax-Katz-type estimates

Let f be a polynomial over finite field Fq with q elements and let N(f=0) denote the number of zeros of f in Fq. The q-divisibility properties of N(f=0) have been studied by many authors, such as Chavelley, Warning, Ax, Katz, etc. In this paper, by reducing the degree of a given polynomial meanwhile remaining the number of its zeros unchanged, we present an improvement upon the Chevalley-Warning-Ax-Katz-type estimates in many cases. Furthermore, our result can improve Cao-Sun's reduction recently obtained on counting the number of zeros of general diagonal equations over finite fields.     

Geometric configurations of singularities for quadratic differential systems with three distinct real simple finite singularities

In this work we classify, with respect to the geometric equivalence relation, the global configurations of singularities, finite and infinite, of quadratic differential systems possessing exactly three distinct finite simple singularities. This relation is finer than the topological equivalence relation which does not distinguish between a focus and a node or between a strong and a weak focus or between foci (or saddles) of different orders. Such distinctions are, however, important in the production of limit cycles close to the foci (or loops) in perturbations of the systems. The notion of geometric equivalence relation of configurations of singularities allows us to incorporate all these important geometric features which can be expressed in purely algebraic terms. The geometric classification of all configurations of singularities, finite and infinite, of quadratic systems was initiated in a work published in 2013 when the classification was done for systems with total multiplicity m _f of finite singularities less than or equal to one. That work was continued in an article which is due to appear in 2014 where the geometric classification of configurations of singularities was done for the case m _f = 2. In this article we go one step further and obtain the geometric classification of singularities, finite and infinite, for the subclass mentioned above. We obtain 147 geometrically distinct configurations of singularities for this family. We give here the global bifurcation diagram of configurations of singularities, both finite and infinite, with respect to the geometric equivalence relation, for this class of systems. The bifurcation set of this diagram is algebraic. The bifurcation diagram is done in the 12-dimensional space of parameters and it is expressed in terms of polynomial invariants, a fact which gives us an algorithm for determining the geometric configuration of singularities for any quadratic system in this particular class.     

Order Varieties and Monotone Retractions of Finite Posets

In this paper we introduce a new version of the concept of order varieties. Namely, in addition to closure under retracts and products we require that the class of posets should be closed under taking idempotent subalgebras. As an application we prove that the variety generated by an order-primal algebra on a finite connected poset P is congruence modular if and only if every idempotent subalgebra of P is connected. We give a polynomial time algorithm to decide whether or not a variety generated by an order-primal algebra admits a near unanimity function and so we answer a problem of Larose and Zádori.     

Verified error bounds for multiple roots of systems of nonlinear equations

It is well known that it is an ill-posed problem to decide whether a function has a multiple root. Even for a univariate polynomial an arbitrary small perturbation of a polynomial coefficient may change the answer from yes to no. Let a system of nonlinear equations be given. In this paper we describe an algorithm for computing verified and narrow error bounds with the property that a slightly perturbed system is proved to have a double root within the computed bounds. For a univariate nonlinear function f we give a similar method also for a multiple root. A narrow error bound for the perturbation is computed as well. Computational results for systems with up to 1000 unknowns demonstrate the performance of the methods.     

Global residues for sparse polynomial systems

We consider families of sparse Laurent polynomials f₁,…,f_n with a finite set of common zeros Z_f in the torus Tⁿ=(C−{0})ⁿ. The global residue assigns to every Laurent polynomial g the sum of its Grothendieck residues over Z_f. We present a new symbolic algorithm for computing the global residue as a rational function of the coefficients of the f_i when the Newton polytopes of the f_i are full-dimensional. Our results have consequences in sparse polynomial interpolation and lattice point enumeration in Minkowski sums of polytopes.     

Explicit determination of generalized symmetric and alternating Galois groups

This paper shows a probabilistic algorithm to decide whether the Galois group of a given irreducible polynomial with rational coefficients is the generalized symmetric group C_p?S_m or the generalized alternating group C_p?A_m. In the affirmative case, we give generators of the group with their action on the set of roots of the polynomial.     

A homological approach to representations of algebras I: The wild case

We prove that the pure global dimension of a polynomial ring over an integral domain k in a finite or countable number n?2 of commuting (non-commuting, resp.) variables is t + 1, provided $\text{|k| = ?}{}_{\mathrm{t}}$. As an application, we determine the pure global dimension of wild algebras of quiver type, also (in case k is an algebraically closed field) of the wild local and wild commutative algebras of finite k-dimension.     

Weight hierarchies of a family of linear codes associated with degenerate quadratic forms

Weight hierarchies of linear codes have been an interesting topic due to their important values in theory and applications in cryptography. In this paper, we restrict a degenerate quadratic form f over a finite field of odd characteristic to subspaces and introduce a quotient space related to the degenerate quadratic form f. From the polynomial f over the quotient space, a non-degenerate quadratic form is induced. Some related results on the subspaces and quotient spaces are obtained. Based on these results, the weight hierarchies of a family of linear codes related to f are determined.     

On the Minimizing Trajectory of Convex Functions with Unbounded Level Sets

We consider a convex function f(x) with unbounded level sets. Many algorithms, if applied to this class of functions, do not guarantee convergence to the global infimum. Our approach to this problem leads to a derivation of the equation of a parametrized curve x(t), such that an infimum of f(x) along this curve is equal to the global infimum of the function on ⁿ .We also investigate properties of the vectors of recession, showing in particular how to determine a cone of recession of the convex function. This allows us to determine a vector of recession required to construct the minimizing trajectory.     

Read-Once Functions Revisited and the Readability Number of a Boolean Function

In this paper, we present the first polynomial time algorithm for recognizing and factoring read-once functions. The algorithm is based on algorithms for cograph recognition and a new efficient method for checking normality. Its correctness is based on a classical characterization theorem of Gurvich which states that a positive Boolean function is read-once if and only if it is normal and its co-occurrance graph is P₄-free.We also investigate the problem of factoring certain non-read-once functions. In particular, we show that if the co-occurrence graph of a positive Boolean function f is a tree, then the function is read-twice. We then extend this further proving that if f is normal and its corresponding graph is a partial k-tree, then f is a read 2^k function and a read 2^k formula for F for f can be obtained in polynomial time.     

d-Orthogonality via generating functions

In this paper, starting from a suitable generating function of a polynomial set, we show how to decide whether the considered polynomial set is d-orthogonal and, if it is so, how to determine the corresponding d-dimensional functional vector. Then, we apply the obtained results to some known and new d-orthogonal polynomial sets. For the known ones, we give new proofs for some already obtained results.     

Global Rigidity: The Effect of Coning

Recent results have confirmed that the global rigidity of bar-and-joint frameworks on a graph G is a generic property in Euclidean spaces of all dimensions. Although it is not known if there is a deterministic algorithm that runs in polynomial time and space, to decide if a graph is generically globally rigid, there is an algorithm (Gortler et al. in Characterizing generic global rigidity, arXiv:, 2007) running in polynomial time and space that will decide with no false positives and only has false negatives with low probability. When there is a framework that is infinitesimally rigid with a stress matrix of maximal rank, we describe it as a certificate which guarantees that the graph is generically globally rigid, although this framework, itself, may not be globally rigid. We present a set of examples which clarify a number of aspects of global rigidity.     

Efficient Pattern Matching on Graph Patterns of Bounded Treewidth

This paper deals with a problem to decide whether a given graph structure appears as a pattern in the structure of a given graph. A graph pattern is a connected graph with structured variables. A variable is an ordered list of vertices that can be replaced with a connected graph by a kind of hyperedge replacements. The graph pattern matching problem (GPMP) is the computational problem to decide whether a given graph pattern matches a given graph. In this paper, we show that GPMP is solvable in polynomial time if for a given graph pattern p, the lengths of all variables of p are 2 and the base graph of p is of bounded treewidth.     

Parametric Integer Programming Algorithm for Bilevel Mixed Integer Programs

We consider discrete bilevel optimization problems where the follower solves an integer program with a fixed number of variables. Using recent results in parametric integer programming, we present polynomial time algorithms for pure and mixed integer bilevel problems. For the mixed integer case where the leader’s variables are continuous, our algorithm also detects whether the infimum cost fails to be attained, a difficulty that has been identified but not directly addressed in the literature. In this case, it yields a “better than fully polynomial time” approximation scheme with running time polynomial in the logarithm of the absolute precision. For the pure integer case where the leader’s variables are integer, and hence optimal solutions are guaranteed to exist, we present an algorithm which runs in polynomial time when the total number of variables is fixed.     

Global gradient estimate on graph and its applications

Continuing our previous work(ar Xiv:1509.07981v1),we derive another global gradient estimate for positive functions,particularly for positive solutions to the heat equation on finite or locally finite graphs.In general,the gradient estimate in the present paper is independent of our previous one.As applications,it can be used to get an upper bound and a lower bound of the heat kernel on locally finite graphs.These global gradient estimates can be compared with the Li–Yau inequality on graphs contributed by Bauer et al.[J.Differential Geom.,99,359–409(2015)].In many topics,such as eigenvalue estimate and heat kernel estimate(not including the Liouville type theorems),replacing the Li–Yau inequality by the global gradient estimate,we can get similar results.