Elimination Theory in Differential and Difference Algebra

Elimination theory is central in differential and difference algebra. The Wu-Ritt characteristic set method, the resultant and the Chow form are three fundamental tools in the elimination theory for algebraic differential or difference equations. In this paper, the authors mainly present a survey of the existing work on the theory of characteristic set methods for differential and difference systems,the theory of differential Chow forms, and the theory of sparse differential and difference resultants.     

A triangular decomposition algorithm for differential polynomial systems with elementary computation complexity

In this paper, a new triangular decomposition algorithm is proposed for ordinary differential polynomial systems, which has triple exponential computational complexity. The key idea is to eliminate one algebraic variable from a set of polynomials in one step using the theory of multivariate resultant. This seems to be the first differential triangular decomposition algorithm with elementary computation complexity.     

The Fitzpatrick-Neville-Type Algorithm for Multivariate Vector-Valued Osculatory Rational Interpolation

In this paper,the authors first apply the Fitzpatrick algorithm to multivariate vectorvalued osculatory rational interpolation.Then based on the Fitzpatrick algorithm and the properties of an Hermite interpolation basis,the authors present a Fitzpatrick-Neville-type algorithm for multivariate vector-valued osculatory rational interpolation.It may be used to compute the values of multivariate vector-valued osculatory rational interpolants at some points directly without computing the interpolation function explicitly.     

An Improved Early Termination Sparse Interpolation Algorithm for Multivariate Polynomials

This paper presents an improved early termination algorithm for sparse black box multivariate polynomials, which reduces the interpolation problem into several sub-interpolation problems with less variables and fewer terms. Actually, all interpolations are eventually reduced to the interpolation of a list of polynomials with less terms than that of the original polynomial. Extensive experiments show that the new algorithm is much faster than the original algorithm.     

Bayesian empirical likelihood estimation of quantile structural equation models

Structural equation model (SEM) is a multivariate analysis tool that has been widely applied to many fields such as biomedical and social sciences. In the traditional SEM, it is often assumed that random errors and explanatory latent variables follow the normal distribution, and the effect of explanatory latent variables on outcomes can be formulated by a mean regression-type structural equation. But this SEM may be inappropriate in some cases where random errors or latent variables are highly nonnormal. The authors develop a new SEM, called as quantile SEM (QSEM), by allowing for a quantile regression-type structural equation and without distribution assumption of random errors and latent variables. A Bayesian empirical likelihood (BEL) method is developed to simultaneously estimate parameters and latent variables based on the estimating equation method. A hybrid algorithm combining the Gibbs sampler and Metropolis-Hastings algorithm is presented to sample observations required for statistical inference. Latent variables are imputed by the estimated density function and the linear interpolation method. A simulation study and an example are presented to investigate the performance of the proposed methodologies.     

Computing the Determinant of a Matrix with Polynomial Entries by Approximation

Computing the determinant of a matrix with the univariate and multivariate polynomial entries arises frequently in the scientific computing and engineering fields. This paper proposes an effective algorithm to compute the determinant of a matrix with polynomial entries using hybrid symbolic and numerical computation. The algorithm relies on the Newton’s interpolation method with error control for solving Vandermonde systems. The authors also present the degree matrix to estimate the degree of variables in a matrix with polynomial entries, and the degree homomorphism method for dimension reduction. Furthermore, the parallelization of the method arises naturally.     

Computing Sparse GCD of Multivariate Polynomials via Polynomial Interpolation

The problem of computing the greatest common divisor (GCD) of multivariate polynomials, as one of the most important tasks of computer algebra and symbolic computation in more general scope, has been studied extensively since the beginning of the interdisciplinary of mathematics with computer science. For many real applications such as digital image restoration and enhancement, robust control theory of nonlinear systems, L₁-norm convex optimization in compressed sensing techniques, as well as algebraic decoding of Reed-Solomon and BCH codes, the concept of sparse GCD plays a core role where only the greatest common divisors with much fewer terms than the original polynomials are of interest due to the nature of problems or data structures. This paper presents two methods via multivariate polynomial interpolation which are based on the variation of Zippel’s method and Ben-Or/Tiwari algorithm, respectively. To reduce computational complexity, probabilistic techniques and randomization are employed to deal with univariate GCD computation and univariate polynomial interpolation. The authors demonstrate the practical performance of our algorithms on a significant body of examples. The implemented experiment illustrates that our algorithms are efficient for a quite wide range of input.     

On the unique minimal monomial basis of Birkhoff interpolation problem

This paper studies the minimal monomial basis of the n-variable Birkhoff interpolation problem. First, the authors give a fast B-Lex algorithm which has an explicit geometric interpretation to compute the minimal monomial interpolation basis under lexicographic order and the algorithm is in fact a generalization of lex game algorithm. In practice, people usually desire the lowest degree interpolation polynomial, so the interpolation problems need to be solved under, for example, graded monomial order instead of lexicographic order. However, there barely exist fast algorithms for the nonlexicographic order problem. Hence, the authors in addition provide a criterion to determine whether an n-variable Birkhoff interpolation problem has unique minimal monomial basis, which means it owns the same minimal monomial basis w.r.t. arbitrary monomial order. Thus, for problems in this case, the authors can easily get the minimal monomial basis with little computation cost w.r.t. arbitrary monomial order by using our fast B-Lex algorithm.     

A New Algorithm for Computing the Extended Hensel Construction of Multivariate Polynomials

This paper presents a new algorithm for computing the extended Hensel construction(EHC) of multivariate polynomials in main variable x and sub-variables u_1, u_2, ···, u_m over a number field K. This algorithm first constructs a set by using the resultant of two initial coprime factors w.r.t. x, and then obtains the Hensel factors by comparing the coefficients of x~i on both sides of an equation. Since the Hensel factors are polynomials of the main variable with coefficients in fraction field K(u_1, u_2, ···, u_m), the computation cost of handling rational functions can be high. Therefore,the authors use a method which multiplies resultant and removes the denominators of the rational functions. Unlike previously-developed algorithms that use interpolation functions or Gr?bner basis, the algorithm relies little on polynomial division, and avoids multiplying by different factors when removing the denominators of Hensel factors. All algorithms are implemented using Magma, a computational algebra system and experiments indicate that our algorithm is more efficient.     

New Implicit Enumeration Method for Polynomial 0-1 Programming

A new implicit enumeration method for polynomial zero-one programming is proposed in this article. By adopting the p-norm surrogate constraint method, a polynomial zero-one programming problem with multiple constraints can be converted into an equivalent polynomial zero-one programming problem with a single surrogate constraint. A new solution scheme is then devised to take the advantage of this prominent feature in carrying out the “fathoming” procedure and the “backtrack” procedure in a searching process of an implicit enumeration. We demonstrate the efficiency of this new algorithm by some promising computational results. Finally, we conclude by proposing certain topics for future research.     

一类非线性系统的模糊建模与仿真

将模糊推理建模法应用于一阶非线性系统，推导出基于该方法建模后得到的数学模型，即变系数线性微分方程。首先根据模糊逻辑系统的插值机理将被控对象的模糊推理规则库归结为某种线性插值函数，然后将这些插值函数转化为变系数线性微分方程，从而得到控制系统的数后将这些插值函数转化为变系数线性微分方程，从而得到控制系统的数学模型。仿真结果表明，用模糊推理建模法得到的模型关于真实模型具有较高的逼近精度。     

Obtaining exact interpolation multivariate polynomial by approximation

In some fields such as Mathematics Mechanization, automated reasoning and Trustworthy Computing, etc., exact results are needed. Symbolic computations are used to obtain the exact results. Symbolic computations are of high complexity. In order to improve the situation, exact interpolating methods are often proposed for the exact results and approximate interpolating methods for the approximate ones. In this paper, the authors study how to obtain exact interpolation polynomial with rational coefficients by approximate interpolating methods.     

运动目标位置的合成

研究由脱靶量和经纬仪位置获得和预测运动目标位置的方法。提出利用解方程组确定插值多项式系数的方法。与Lagrange插值多项式相比 ,使用这种方法得到的多项式在形式上更加简单。利用插值多项式 ,根据非整数倍周期时的偏差量 ,给出偏差量在整数倍周期时的带有延时作为参数的表示式。利用这一表示式 ,在目标作匀加速运动的前提下提出了延时的辨识方法 ,从而解决了目标位置合成中的难题。     

多项式0-1规划中隐枚举算法的改进及应用

提出了一个求解多项式0-1规划问题的隐枚举算法.通过应用p次范数约束划归,多项式0-1规划问题的多个约束可以被一单一等价约束来替代.利用这一显著特性,新算法在搜寻最优解过程中,能改进探寻(fathoming)和折返(backtrack)策略以提高隐枚举法的计算效率.通过一个算例说明这个新算法的计算步骤并对随机产生的问题进行了测试,得到了较好的结果.     

Maximum principle for partially-observed optimal control problems of stochastic delay systems

This paper is concerned with partially-observed optimal control problems for stochastic delay systems. Combining Girsanov’s theorem with a standard variational technique, the authors obtain a maximum principle on the assumption that the system equation contains time delay and the control domain is convex. The related adjoint processes are characterized as solutions to anticipated backward stochastic differential equations in finite-dimensional spaces. Then, the proposed theoretical result is applied to study partially-observed linear-quadratic optimal control problem for stochastic delay system and an explicit observable control variable is given.     

Variable Selection for Structural Equation with Endogeneity

This paper studies variable selection problem in structural equation of a two-stage least squares (2SLS) model in presence of endogeneity which is commonly encountered in empirical economic studies. Model uncertainty and variable selection in the structural equation is an important issue as described in Andrews and Lu (2001) and Caner (2009). The authors propose an adaptive Lasso 2SLS estimator for linear structural equation with endogeneity and show that it enjoys the oracle properties, i.e., the consistency in both estimation and model selection. In Monte Carlo simulations, the authors demonstrate that the proposed estimator has smaller bias and MSE compared with the bridge-type GMM estimator (Caner, 2009). In a case study, the authors revisit the classic returns to education problem (Angrist and Krueger, 1991) using the China Population census data. The authors find that the education level not only has strong effects on income but also shows heterogeneity in different age cohorts.     

Efficient estimation of seemingly unrelated additive nonparametric regression models

This paper is concerned with the estimating problem of seemingly unrelated (SU) nonparametric additive regression models. A polynomial spline based two-stage efficient approach is proposed to estimate the nonparametric components, which takes both of the additive structure and correlation between equations into account. The asymptotic normality of the derived estimators are establishedi. The authors also show they own some advantages, including they are asymptotically more efficient than those based on only the individual regression equation and have an oracle property, which is the asymptotic distribution of each additive component is the same as it would be if the other components were known with certainty. Some simulation studies are conducted to illustrate the finite sample performance of the proposed procedure. Applying the proposed procedure to a real data set is also made.     

A characteristic set method for solving boolean equations and applications in cryptanalysis of stream ciphers*

This paper presents a characteristic more efficient and has better properties than the set method for solving Boolean equations, which is general characteristic set method. In particular, the authors give a disjoint and monic zero decomposition algorithm for the zero set of a Boolean equation system and an explicit formula for the number of solutions of a Boolean equation system. The authors also prove that a characteristic set can be computed with a polynomial number of multiplications of Boolean polynomials in terms of the number of variables. As experiments, the proposed method is used to solve equations from cryptanalysis of a class of stream ciphers based on nonlinear filter generators. Extensive experiments show that the method is quite effective.     

Generating exact nonlinear ranking functions by symbolic-numeric hybrid method

This paper presents a hybrid symbolic-numeric algorithm to compute ranking functions for establishing the termination of loop programs with polynomial guards and polynomial assignments. The authors first transform the problem into a parameterized polynomial optimization problem, and obtain a numerical ranking function using polynomial sum-of-squares relaxation via semidefinite programming (SDP). A rational vector recovery algorithm is deployed to recover a rational polynomial from the numerical ranking function, and some symbolic computation techniques are used to certify that this polynomial is an exact ranking function of the loop programs. At last, the authors demonstrate on some polynomial loop programs from the literature that our algorithm successfully yields nonlinear ranking functions with rational coefficients.     

Discovering non-terminating inputs for multi-path polynomial programs

This paper investigates the termination problems of multi-path polynomial programs （MPPs） with equational loop guards. To establish sufficient conditions for termination and nontermination simultaneously, the authors propose the notion of strong/weak non-termination which under/over- approximates non-termination. Based on polynomial ideal theory, the authors show that the set of all strong non-terminating inputs （SNTI） and weak non-terminating inputs （WNTI） both correspond to tile real varieties of certain polynomial ideals. Furthermore, the authors prove that the variety of SNTI is computable, and under some sufficient conditions the variety of WNTI is also computable. Then by checking the computed SNTI and WNTI varieties in parallel, termination properties of a consid- ered MPP can be asserted. As a consequence, the authors establish a new framework for termination analysis of MPPs.