Overdetermined Systems of Sparse Polynomial Equations

Foundations of Computational Mathematics - In this paper, we show that for a system of univariate polynomials given in sparse encoding we can compute a single polynomial defining the same zero set...     

Deformation Techniques for Sparse Systems

We exhibit a probabilistic symbolic algorithm for solving zero-dimensional sparse systems. Our algorithm combines a symbolic homotopy procedure, based on a flat deformation of a certain morphism of affine varieties, with the polyhedral deformation of Huber and Sturmfels. The complexity of our algorithm is cubic in the size of the combinatorial structure of the input system. This size is mainly represented by the cardinality and mixed volume of Newton polytopes of the input polynomials and an arithmetic analogue of the mixed volume associated to the deformations under consideration. Research was partially supported by the following grants: UBACyT X112 (2004–2007), UBACyT X847 (2006–2009), PIP CONICET 2461, PIP CONICET 5852/05, ANPCyT PICT 2005 17-33018, UNGS 30/3005, MTM2004-01167 (2004–2007), MTM2007-62799 and CIC 2007–2008.     

On the Complexity of Sparse Elimination

Sparse elimination exploits the structure of a multivariate polynomial by considering its Newton polytope instead of its total degree. We concentrate on polynomial systems that generate zero-dimensional ideals. A monomial basis for the coordinate ring is defined from a mixed subdivision of the Minkowski sum of the Newton polytopes. We offer a new simple proof relying on the construction of a sparse resultant matrix, which leads to the computation of a multiplication map and all common zeros. The size of the monomial basis equals the mixed volume and its computation is equivalent to computing the mixed volume, so the latter is a measure of intrinsic complexity. On the other hand, our algorithms have worst-case complexity proportional to the volume of the Minkowski sum. In order to derive bounds in terms of the sparsity parameters, we establish new bounds on the Minkowski sum volume as a function of mixed volume. To this end, we prove a lower bound on mixed volume in terms of Euclidean volume which is of independent interest.     

Decomposition-based Method for Sparse Semidefinite Relaxations of Polynomial Optimization Problems

We consider polynomial optimization problems pervaded by a sparsity pattern. It has been shown in Lasserre (SIAM J. Optim. 17(3):822–843, 2006) and Waki et al. (SIAM J. Optim. 17(1):218–248, 2006) that the optimal solution of a polynomial programming problem with structured sparsity can be computed by solving a series of semidefinite relaxations that possess the same kind of sparsity. We aim at solving the former relaxations with a decomposition-based method, which partitions the relaxations according to their sparsity pattern. The decomposition-based method that we propose is an extension to semidefinite programming of the Benders decomposition for linear programs (Benders, Comput. Manag. Sci. 2(1):3–19, 2005).     

多项式方程组的主项解耦消元法

本文提出多项式组符号求解的主项解耦 (主项只含主元 )消元法 :视多项式为变元不同幂积的线性组合 ,以主项解耦三角型多项式组 DTS为引导 ,用逐项伪除求余式 ,将多项式组 PS化为与其同解的 DTS.内容涉及 :消元算法、DTS的存在性与结构特性、零点集结构公式等 .亦对 Grobner基法、吴文俊消元法与本文方法之间的相互联系、区别以及特点进行了比较 .研究表明主项解耦消元法适用于一般多项式组且效率较高     

On Solving Parametric Polynomial Systems

Border polynomial and discriminant variety are two important notions related to parametric polynomial system solving, in particular, for partitioning the parameter space into regions where the solutions of the system depend continuously on the parameter values. In this paper, we study the relations between those notions in the case of parametric triangular systems. We also investigate the properties and computation of the non-properness locus of the canonical projection restricted at a parametric regular chain or at its saturated ideal.     

Well Conditioned Spherical Polynomial Systems

We investigate nonnegative spherical polynomials p, normalized to p(1)=1, which minimize the integral over the unit sphere for fixed degree. Such polynomials are useful in the construction of node systems on the sphere which support numerically stable systems of zonal functions, for instance with bounded condition numbers.     

High-Dimensional Adaptive Sparse Polynomial Interpolation and Applications to Parametric PDEs

We consider the problem of Lagrange polynomial interpolation in high or countably infinite dimension, motivated by the fast computation of solutions to partial differential equations (PDEs) depending on a possibly large number of parameters which result from the application of generalised polynomial chaos discretisations to random and stochastic PDEs. In such applications there is a substantial advantage in considering polynomial spaces that are sparse and anisotropic with respect to the different parametric variables. In an adaptive context, the polynomial space is enriched at different stages of the computation. In this paper, we study an interpolation technique in which the sample set is incremented as the polynomial dimension increases, leading therefore to a minimal amount of PDE solving. This construction is based on the standard principle of tensorisation of a one-dimensional interpolation scheme and sparsification. We derive bounds on the Lebesgue constants for this interpolation process in terms of their univariate counterpart. For a class of model elliptic parametric PDE’s, we have shown in Chkifa et al. (Modél. Math. Anal. Numér. 47(1):253–280, 2013) that certain polynomial approximations based on Taylor expansions converge in terms of the polynomial dimension with an algebraic rate that is robust with respect to the parametric dimension. We show that this rate is preserved when using our interpolation algorithm. We also propose a greedy algorithm for the adaptive selection of the polynomial spaces based on our interpolation scheme, and illustrate its performance both on scalar valued functions and on parametric elliptic PDE’s.     

Automatically Discovering Relaxed Lyapunov Functions for Polynomial Dynamical Systems

The notion of Lyapunov function plays a key role in the design and verification of dynamical systems, as well as hybrid and cyber-physical systems. In this paper, to analyze the asymptotic stability of a dynamical system, we generalize standard Lyapunov functions to relaxed Lyapunov functions (RLFs), by considering higher order Lie derivatives. Furthermore, we present a method for automatically discovering polynomial RLFs for polynomial dynamical systems (PDSs). Our method is relatively complete in the sense that it is able to discover all polynomial RLFs with a given predefined template for any PDS. Therefore it can also generate all polynomial RLFs for the PDS by enumerating all polynomial templates.     

多项式组特征列的矩阵求法

基于矩阵多元多项式的带余除法,给出了代数情形多项式组特征列的一种新求法,并举例验证了这种方法的有效性.     

Locally Polynomial Method for Solving Systems of Linear Inequalities

Computational Mathematics and Mathematical Physics - A numerical method combining a gradient technique with the projection onto a linear manifold is proposed for solving systems of linear...     

求解混合三角多项式方程组的直接GBQ方法

许多科学与工程领域,我们经常需要求混合三角多项式方程组的全部解.一般来说,混合三角多项式方程组可以通过变量替换及增加二次多项式转化为多项式方程组,进而利用数值方法进行求解,但这种转化会增大问题的规模从而增加计算量.在本文中,我们不将问题转化,考虑利用直接同伦方法求解,并给出基于GBQ方法构造的初始方程组及同伦定理的证明.数值实验结果表明我们构造的直接同伦方法较已有的直接同伦方法更加有效.     

Polynomial Conservation Laws in Quantum Systems

We consider systems with a finite number of degrees of freedom and potential energy that is a finite sum of exponentials with purely imaginary or real exponents. Such systems include the generalized Toda chains and systems with a toric configuration space. We consider the problem of describing all the quantum conservation laws, i.e., the differential operators that are polynomial in the derivatives and commute with the Hamiltonian operator. We prove that in the case where the potential energy spectrum is invariant under reflection with respect to the origin, such nontrivial operators exist only if the system under consideration decomposes into a direct sum of decoupled subsystems. In the general case (without the spectrum symmetry assumption), we prove that the existence of a complete set of independent conservation laws implies the complete integrability of the corresponding classical system.     

Structural Stability of Constrained Polynomial Systems

The structural stability of constrained polynomial differentialsystems of the form a(x, y)x'+b(x, y)y'=f(x, y), c(x, y)x'+d(x,y)y'=g(x, y), under small perturbations of the coefficientsof the polynomial functions a, b, c, d, f and g is studied.These systems differ from ordinary differential equations at‘impasse points’ defined by ad–bc=0. Extensionsto this case of results for smooth constrained differentialsystems [7] and for ordinary polynomial differential systems[5] are achieved here. 1991 Mathematics Subject Classification34C35, 34D30.     

Generic Stability and Boundedness of Semistate Systems

The behaviour of semistate systems is investigated by consideringthe generic concepts of stability and boundedness. These qualitativeconcepts define properties of system motions with respect tocertain families of time-varying subsets of the semistate space.The results yield sufficient conditions and generalize someknown results on pratical and set stability. The criteria derivedinvolve the existence of aggregation functions which, togetherwith their total time derivative along the system motions, canbe sign-indefinite. The approach proposed unifies the analysison finite and infinite time intervals, as well as the analysisof set and Lyapunov-like stability. Some examples are workedout to illustrate the results obtained.     

An Algorithm for Finding All Isolated Zeros of Polynomial Systems

Finding all zeros of polynomial systems is very interesting and it is also useul for many applied science problems.In this paper,based on Wu‘s method,we give an algorithm to find all isolated zeros of polynomial systems (or polynomial equations).By solving Lorenz equations,it is shown that our algo-rithm is efficient and powerful.     

Polynomial Acceleration Methods for Solving Singular Systems of Linear Equations

In this paper we study the polynomial acceleration methods for solving singular linear systems. We establish iterative schemes, show their convergence and find iteration error bounds.