Efficient Algorithms For Solving Poly-power Constraints

Nowdays information technologies are deeply affecting every aspect of scientific research,industrial manufacture and our daily life.It is known that a great deal of practical problems can be reduced or partially reduced to the problems of solving nonlinear equations or nonlinear constraints.Since the numerical algorithms are inexact and generally incomplete,with the growth in demand on system reliability,traditional numerical solving methods become more and more incompetent.Thus,the interdisciplinary research on algebra and computer science emerges as the times require.On one hand,the proofs based on algebraic theories ensure the exactness and the completeness of the solving methods.On the other hand,the development of computer science provides strong support for the efficient implementation of the methods.As is known to all,how to exactly solve polynomial equations and constraints has been thoroughly studied in the past half century.On the contrary,how to solve transcendental equations and constraints has not been looked into adequately to date due to the intrinsic hardness.Usually,complex systems always involve transcendental functions.Thus,the research on these constraint solving problems is essential and meaningful.In this dissertation,we study the solving methods for equations and constraints involving a particular class of transcendental functions — poly-powers,which extend integer exponents to real algebraic exponents for polynomials.The main contributions are listed as follows:· Theory: Properties of roots of transcendental functions are studied based on the transcendental number theory.Some necessary and sufficient conditions related to the existences of algebraic roots,multiple roots and common roots of poly-powers are proved based on Gelfond–Schneider theorem and Schanuel’s conjecture,which are decidable by checking finitely many critical points and provide a solid theoretical foundation to the algorithms proposed later.· Algorithm: Solving problems for poly-powers are studied based on algebraic methods.First,the factorization for poly-powers is given based on the theory of field extension.Then,the positive root isolation for poly-powers are presented based on exclusion and differentiation respectively.Finally,the conflict-driven solving procedure is proposed for poly-power constraints.· Implementation: To improve the efficiencies of the aforementioned algorithms,the strategy of “simplest operand” is adopted.“Simplest operand” means operands are chosen to be as simple as possible.Based on two effective encoding methods — Stern-Brocot tree and binary rational numbers,two optimal interval-splitting are proposed respectively to choose the operands with smallest code lengths,whose effectivenesses are demonstrated by randomly generated samples.Therefore,the dissertation focuses on the poly-power constraint solving,and establishes the trifold results from theory,algorithm and implementation.The conditions related to the existences of poly-powers’ roots reveal the features of such transcendental functions.Besides,the rationales of the solving algorithms and the optimal interval-splitting are likely to be inspirational to other constraint solving problems.