Some examples of the use of distances as coordinates for Euclidean geometry

Distance geometry provides us with an implicit characterization of the Euclidean metric in terms of a system of polynomial equations and inequalities. With the aid of computer algebra programs, these equations and inequalities in turn provide us with a coordinate-free approach to proving theorems in Euclidean geometry analytically. This paper contains a brief summary of the mathematical results on which this approach is based, together with some examples showing how it is applied. In particular, we show how it can be used to derive the topological structure of a simple linkage mechanism.     

Guaranteed estimates of the domain of attraction for a class of hybrid systems

This paper addresses the estimation of the domain of attraction for a class of hybrid nonlinear systems where the state space is partitioned into several regions. Each region is described by polynomial inequalities, and the union of all the regions is a complete cover of the state space. The system dynamics are defined on each region independently from the others by polynomial functions. First, the problem of computing the largest sublevel set of a Lyapunov function included in the domain of attraction is considered. An approach is proposed for addressing this problem based on linear matrix inequalities, which provides a lower bound of the sought estimate by establishing negativity of the Lyapunov function derivative on each region. Second, a sufficient and necessary condition is provided for establishing optimality of the found lower bound, which requires to solve linear algebra operations in typical cases. Third, the problem of looking for Lyapunov functions that maximize the estimate of the domain of attraction is considered, describing several strategies where the proposed approach can be readily adopted. Copyright © 2014 John Wiley & Sons, Ltd.     

A Normal Form for Function Rings of Piecewise Functions

Computer algebra systems often have to deal with piecewise continuous functions. These are, for example, the absolute value function, signum, piecewise defined functions but also functions that are the supremum or infimum of two functions. We present a new algebraic approach to these types of problems. This paper presents a normal form for a function ring containing piecewise polynomial functions of a real variable. We give a complete rule system to compute the normal form of an expression. The main result is that this normal form can be used to decide extensional equality of two piecewise functions. Also we define supremum and infimum for piecewise functions; in fact, we show that the function ring forms a lattice. Additionally, a method to solve equalities and inequalities in this function ring is presented. Finally, we give a “user interface” to the algebraic representation of the piecewise functions.     

多项式非线性系统的并行分布辨识

在状态空间方程中引入输入和状态的多项式函数,以此多项式函数表示非线性因素.为了辨识多项式非线性系统中的各系统矩阵,对于矢量化各系统矩阵组成的未知参数矢量,分别在无约束和有约束条件下采用两并行分布算法求解.在以状态方程等式为约束条件时,将各状态瞬时刻值与由系统矩阵组成的未知参数矢量合并为一个新的优化矢量.对于优化矢量的辨识,给出了并行分布算法的求解过程和迭代式.最后,通过仿真算例验证了所提出方法的有效性.     

Exact,analytic, and locally approximate solutions to discrete event-simulation problems

We demonstrate how discrete event simulation problems can be encoded within a probabilistic proc algebra. From this encoding we can exploit vavious solution techniques to derive exact numerical solutions, analytic solutions and piecewise polynomial approximations for system properties. Our approach allows us to combine the advantages of simulation, viz problem decomposition and an executable representation, with standard analytic and numerical computation methods for calculating system properties.     

Regional stability of two‐dimensional nonlinear polynomial Fornasini‐Marchesini systems

This paper addresses the problem of regional stability analysis of 2‐dimensional nonlinear polynomial systems represented by the Fornasini‐Marchesini second state‐space model. A method based on a polynomial Lyapunov function is proposed to ensure local asymptotic stability and provide an estimate of the domain of attraction of the system zero equilibrium point. The proposed results that build on recursive algebraic representations of the polynomial vector function of the system dynamics and Lyapunov function are tailored via linear matrix inequalities that are required to be satisfied at the vertices of a given bounded convex polyhedral region of the state space. Numerical examples demonstrate the effectiveness of the proposed method.     

Algorithms and methods in differential algebra

Founded by J.F. Ritt, Differential Algebra is a true part of Algebra so that constructive and algorithmic problems and methods appear in this field. In this talk, I do not intend to give an exhaustive survey of algorithmic aspects of Differential Algebra but I only propose some examples to give an insight of the state of knowledge in this domain. Some problems are known to have an effective solution, others have an efficient effective solution which is implemented in recent computer algebra systems, and the decidability of some others is still an open question, which does not prevent computations from leading to interesting results.Liouville's theory of integration in finite terms and Risch's theorem are examples of problems that computer algebra systems now deal with very efficiently (implementation work by M Bronstein).In what concerns linear differential equations of arbitrary order, a basis for the vector space of all liouvillian solutions can “in principle” be computed effectively thanks to a theorem of Singer's [17, 22]; the complexity bound is actually awful and a lot of work is done or in progress, especially by M. Singer and F. Ulmer, to give realistic algorithms [20, 21] for third-order linear differential equations.Existence of liouvillian first integrals is a way to make precise the notion of integrability of vector fields. Even in the simplest case of three-dimensional polynomial vector fields, no decision procedure is known for this existence.Nevertheless, explicit computations with computer algebra yield interesting solutions for special examples. In this case, the process of looking for so-called Darboux curves can only be called a method but not an algorithm; for a given degree, this search is a classical algebraic elimination process but no bound is known on the degree of the candidate polynomials.This paper insists on the search of liouvillian first integrals of polynomial vector fields and a new result is given: the generic absence of such liouvillian first integrals for factorisable polynomial vector fields in three variables.     

On subsumption and semiunification in feature algebras

We consider a generalization of term subsumption, or matching, to a class of mathematical structures which we call feature algebras. We show how these generalize both first-order terms and the feature structures used in computational linguistics. The notion of term subsumption generalizes to a natural notion of algebra homomorphism. In the setting of feature algebras, unification, corresponds naturally to solving constraints involving equalities between strings of unary function symbols, and semiunification also allows inequalities representing subsumption constraints. Our generalization allows us to show that the semiunification problem for finite feature algebras is undecidable. This implies that the corresponding problem for rational trees (cyclic terms) is also undecidable.     

Massively parallel computations on many-variable polynomials

We show that a multivariate homogeneous polynomial can be represented on a hypercube in such a way that sums, products and partial derivatives can be performed by massively parallel computers. This representation is derived from the theoretical results of Beauzamy-Bombieri-Enflo-Montgomery [1]. The norm associated with it, denoted by [·], is itself a very efficient tool: when products of polynomials are performed, the best constant in inequalities of the form [PQ]C[P][Q] are provided, and the extremal pairs (that is, the pairs of polynomials for which the product is as small as possible) can be identified.Supported by the C.N.R.S (France) and the N.S.F. (USA), by contracts E.T.C.A./C.R.E.A. No. 20351/90 and 20357/91 (Ministry of Defense, France), and by Research Contract EERP-FR 22, DIGITAL Eq. Corp.     

Decompositions of measures on pseudo effect algebras

Recently, in Dvurečenskij (, 2011), it was shown that if a pseudo effect algebra satisfies a kind of the Riesz decomposition property (RDP), then its state space is either empty or a nonempty simplex. This will allow us to prove a Yosida–Hewitt type and a Lebesgue type decomposition for measures on pseudo effect algebra with RDP. The simplex structure of the state space will entail not only the existence of such a decomposition but also its uniqueness.     

Positive trigonometric polynomials for strong stability of difference equations

We follow a polynomial approach to analyse strong stability of continuous-time linear difference equations with several delays. Upon application of the Hermite stability criterion on the discrete-time homogeneous characteristic polynomial, assessing strong stability amounts to deciding positive definiteness of a multivariate trigonometric polynomial matrix. This latter problem is addressed with a converging hierarchy of linear matrix inequalities (LMIs). Numerical experiments indicate that certificates of strong stability can be obtained at a reasonable computational cost for state dimension and number of delays not exceeding 4 or 5.     

Subanalytic solutions of linear difference equations and multidimensional hypergeometric sequences

We consider linear difference equations with polynomial coefficients over C and their solutions in the form of sequences indexed by the integers (sequential solutions). We investigate the C-linear space of subanalytic solutions, i.e., those sequential solutions that are the restrictions to Z of some analytic solutions of the original equation. It is shown that this space coincides with the space of the restrictions to Z of entire solutions and that the dimension of this space is equal to the order of the original equation.We also consider d-dimensional (d≥1) hypergeometric sequences, i.e., sequential and subanalytic solutions of consistent systems of first-order difference equations for a single unknown function. We show that the dimension of the space of subanalytic solutions is always at most 1, and that this dimension may be equal to 0 for some systems (although the dimension of the space of all sequential solutions is always positive).Subanalytic solutions have applications in computer algebra. We show that some implementations of certain well-known summation algorithms in existing computer algebra systems work correctly when the input sequence is a subanalytic solution of an equation or a system, but can give incorrect results for some sequential solutions.     

Symbolic and Numeric Methods for Exploiting Structure in Constructing Resultant Matrices

Resultants characterize the existence of roots of systems of multivariate nonlinear polynomial equations, while their matrices reduce the computation of all common zeros to a problem in linear algebra. Sparse elimination theory has introduced the sparse (or toric) resultant, which takes into account the sparse structure of the polynomials. The construction of sparse resultant, or Newton, matrices is the critical step in the computation of the multivariate resultant and the solution of a nonlinear system. We reveal and exploit the quasi-Toeplitz structure of the Newton matrix, thus decreasing the time complexity of constructing such matrices by roughly one order of magnitude to achieve quasi-quadratic complexity in the matrix dimension. The space complexity is also decreased analogously. These results imply similar improvements in the complexity of computing the resultant polynomial itself and of solving zero-dimensional systems. Our approach relies on fast vector-by-matrix multiplication and uses the following two methods as building blocks. First, a fast and numerically stable method for determining the rank of rectangular matrices, which works exclusively over floating point arithmetic. Second, exact polynomial arithmetic algorithms that improve upon the complexity of polynomial multiplication under our model of sparseness, offering bounds linear in the number of variables and the number of non-zero terms.     

A note on quadratic stability of uncertain linear discrete-timesystems

In this paper we consider a linear discrete-time system depending on a vector of uncertain parameters. Assuming that the system matrix depends on parameters as the ratio of a multiaffine matrix-valued function and a multiaffine polynomial and that the parameters range in a hyper-rectangle, we show that the uncertain system is quadratically stable if and and only if the set of vertex systems is quadratically stable. This allows us to state a necessary and sufficient condition for quadratic stability in terms of the solvability of a feasibility problem involving linear matrix inequalities     

The problem of reasoning from inequalities

This article is the twenty-first of a series of articles discussing various open research problems in automated reasoning. The problem proposed for research asks one to find an inference rule that performs as paramodulation does, but with the focus on inequalities rather than on equalities. Since, too often, inequalities that are present in the input play a passive role during a reasoning program's attempt to complete an assignment, such an inference rule would markedly add to program effectiveness by giving inequalities the potential of playing a key role. For evaluating a proposed solution to this research problem, we suggest as possible test problems theorems from group theory and theorems from ring theory. This work was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under Contract W-13-109-Eng-38.     

Automated derivation of time bounds in uniprocessor concurrentsystems

The successful development of complex real-time systems depends on analysis techniques that can accurately assess the timing properties of those systems. This paper describes a technique for deriving upper and lower bounds on the time that can elapse between two given events in an execution of a concurrent software system running on a single processor under arbitrary scheduling. The technique involves generating linear inequalities expressing conditions that must be satisfied by all executions of such a system and using integer programming methods to find appropriate solutions to the inequalities. The technique does not require construction of the state space of the system and its feasibility has been demonstrated by using an extended version of the constrained expression toolset to analyze the timing properties of some concurrent systems with very large state spaces     

随机马尔可夫切换系统的H∞模型降阶

考虑一类带有时滞的不确定马尔可夫切换系统的H∞模型降阶问题.首先得到了一个矩阵不等式形式的充分条件,使该系统的H∞模型降阶问题对于满足条件的任意不确定性都是可解的;然后依据CCL(conecom plem entarity linearization)方法给出了该问题的求解算法,以及降阶模型的参数化方法.仿真算例说明该方法的有效性.     

Computational Problems of Multivariate Hypergeometric Theory

We consider computational problems of the theory of hypergeometric functions in several complex variables: computation of the holonomic rank of a hypergeometric system of partial differential equations, computing the defining polynomial of the singular hypersurface of such a system and finding its monomial solutions. The presented algorithms have been implemented in the computer algebra system MATHEMATICA.     

基于SOS技术的多项式非线性系统鲁棒控制综合

针对一类具有多项式向量场的仿射不确定非线性系统,借助多项式平方和(Sum of Squares, SOS)技术,研究其状态反馈鲁棒控制综合问题。给出了该类系统鲁棒镇定控制、以及带有保性能和H性能目标的优化控制问题的充分可解性条件。所给出的条件均被描述为由状态依赖线性矩阵不等式(LMI)组成的SOS规划,可由SOS技术直接求解。此外,通过引入附加变量给出了描述多项式矩阵的逆以及有理式矩阵的方法。最后,通过数值仿真验证了方法的有效性     

Approximation of Model Predictive Control Laws for Polynomial Systems

A fast implementation of a given predictive controller for polynomial systems is introduced by approximating the optimal control law with a piecewise constant function defined over a hyper‐cube partition of the system state space. Such a state‐space partition is computed in order to guarantee stability, an a priori fixed trajectory error as well as input and state constraints fulfilment. The presented approximation procedure is achieved by solving a set of nonconvex polynomial optimization problems, whose approximate solutions are computed by means of semidefinite relaxation techniques for semialgebraic problems.