SSSC 2019

Certified Numerical Real Root Isolation for Bivariate Polynomial Systems

程进三

中国科学院数学与系统科学研究院

摘要: In this paper, we present a new method for isolating real roots of a bivariate polynomial system. Our method is a subdivision method which is based on real root isolation of univariate polynomials and analyzing the local geometrical properties of the given system. We propose the concept of the orthogonal monotone system in a box and use it to determine the uniqueness and the existence of a simple real zero of the system in the box. We implement our method to isolate the real zeros of a given bivariate polynomial system. The experiments show the effectivity and efficiency of our method, especially for systems with high degrees and sparse terms. Our method also works for non-polynomial systems. It is a joint work with Junyi Wen.

Generalized Hermite Reduction, Creative Telescoping and Definite Integration of D-Finite Functions

Frédéric Chyzak

INRIA, France

摘要: Hermite reduction is a classical algorithmic tool in symbolic integration. It is used to decompose a given rational function as a sum of a function with simple poles and the derivative of another rational function. In this talk, we extend Hermite reduction to arbitrary linear differential operators instead of the pure derivative, and develop efficient algorithms for this reduction. We then apply our generalized Hermite reduction to the computation of linear operators satisfied by single definite integrals of D-finite functions of several continuous or discrete parameters. The resulting algorithm is a generalization of reduction-based methods for creative telescoping.
     (Joint work with A. Bostan, P. Lairez, and B. Salvy.)

Computing the numerical rank of large matrices

李宗錂

国立中山大学

摘要: If rank deficiency for a large matrix is known to be small apriori, there seems no need to compute SVD to find all singular values for determining its rank. While the Householder QR with column pivoting algorithm proposed by Golub and Businger in 1965 works quite well in general for this purpose, there exist counter examples (by W. Kahan) that the method would fail. These failures of this sort had been overcome by T. Chan's RRQR algorithm in 1989. In practice, such as in signal processing, rank updatings and downdatings occur commonly along with the rank-revealing. While the UTV decomposition method for rank revealing proposed by G.W. Stewart in 1992 works quite well inrank updatings, it may not be efficient for the downdatings. Recently, an efficient algorithm for rank revealing is proposed. For the method, both updatings and downdatings become quite straightforward. The related results will also be presented in this talk.

Factorization and Equivalence on Multivariate Polynomial Matrices

刘金旺

湖南科技大学

摘要: A multidimensional $(n-D)$ system can be represented by a $n-D$ polynomial matrix, we firstly investigate the general prime factorizations of $n-D$ polynomial matrices: zero prime factorization, minor prime factorization, factor prime factorization. Second, we investigate the equivalence of $n-D$ polynomial matrix. For a class of $n-D$ polynomial matrices, giving some tractable necessary and sufficient conditions under which matrices are equivalent to their Smith-form, there conditions are easily checked by computing the reduced Gr¨obner bases of some ideals. Finally, we investigate $n-D$ polynomial matrix equivalence recursive problem, i.e., $\diag(1, B)\equiv\diag(1, 1, C)$, $B$ is or not equivalent to $diag(1, C1)$, a negative answer is obtained.

On the connection between lexicographic Groebner bases and triangular sets

牟晨琪

北京航空航天大学

摘要: Lexicographic Groebner bases and triangular sets are standard tools in polynomial elimination theory. In this talk, we present new results on the intrinsic structures of lexicographic Greobner bases and relations between lexicographic Groenber bases and the minimal triangular sets contained in them called W-characteristic sets. It is shown that either this W-characteristic set is normal or there are explicit (pseudo-)divisibility relations between the polynomials in it. Based on these properties of W-characteristic sets, we introduce the concept of characteristic pair consisting of a reduced lexicographic Groebner basis and its normal W-characteristic set, and design an algorithm for decomposing any polynomial set into finitely many characteristic pairs with associated zero relations, which provide representations of the zero of the polynomial set in terms of those of Groebner bases and in terms of those of triangular sets simultaneously. Several nice properties of the decomposition and the resulting characteristic pairs, in particular relationships between the Groebner basis and the W-characterisitic set in each pair, are established.
     This talk is based on joint work with Dongming Wang and Rina Dong.

Real root classification and its applications

唐晓弦

Texas A&M University, USA

摘要: Classifying parameters according to numbers of real solutions of a general zero-dimensional polynomial system is a fundamental problem in computational real algebraic geometry. In this talk, we give an introduction to a standard method of real root classification and many applications in system biology and statistics.

Comprehensive Groebner System: Algorithms and Applications

王定康

中国科学院数学与系统科学研究院

摘要: We will introduce the definition of comprehensive Groebner System (CGS) and present some efficient algorithms to compute the CGS of a parametric polynomial system. We will also give some applications using CGS, including solving system of parametric polynomial equations, discovering geometric theorems automatically, performing quantifier elimination over an algebraic closed field and computing greatest common divisors of multivariate polynomials with parameters.

Efficient Algorithms for Solving Poly-Power Constraints

徐鸣

华东师范大学

摘要: We first consider a class of univariate real functions---poly-powers---that extend integer exponents to real algebraic exponents for polynomials. Our purpose is to isolate positive roots of such a function into disjoint intervals, each contains exactly one positive root and together contain all, which can be easily refined to any desired precision. To this end, we classify poly-powers into simple and non-simple ones, depending on the number of linearly independent exponents. For the former, based on Gelfond--Schneider theorem, we present two complete isolation algorithms---exclusion and differentiation. For the latter, their completeness depends on Schanuel's conjecture.
    We then studies the satisfiability problem of poly-power constraints that are conjunctions of poly-power equations and inequalities. To solve the poly-power constraint, we present a sound and complete procedure that incorporates conflict-driven learning with the exclusion algorithm for isolating positive roots of poly-powers. Furthermore, we introduce a kind of optimal interval-splitting, based on the Stern--Brocot tree and on binary rational numbers respectively, so that the operands occurring in the execution are chosen to be as simple as possible. The solving procedure, thereby, turns out to be promisingly efficient on randomly generated examples.

Safety Verification of Nonlinear Hybrid Systems Based on Bilinear Programming

杨争峰

华东师范大学

摘要: In safety verification of hybrid systems, barrier certificates are generated by solving the verification conditions derived from non-negative representations of different types. In this talk, we present a new computational method, sequential linear programming projection, for directly solving the set of verification conditions represented by the Krivine-Vasilescu-Handelman's positivstellensatz. The key idea is to decompose it into two successive optimization problems that refine the desired barrier certificate and those undetermined multipliers, respectively, and solve it in an iterative scheme. The most important benefit of the proposed approach lies in that it is much more effective than the LP relaxation method in producing real barrier certificates, and possesses a much lower computational complexity than the popular sum of square relaxation methods, which is demonstrated by the theoretical analysis on complexity and the experiment on a set of examples gathered from the literature.