Resultant elimination via implicit equation interpolation

It is well known that resultant elimination is an effective method of solving multivariate polynomial equations. In this paper, instead of computing the target resultants via variable by variable elimination, the authors combine multivariate implicit equation interpolation and multivariate resultant elimination to compute the reduced resultants, in which the technique of multivariate implicit equation interpolation is achieved by some high probability algorithms on multivariate polynomial interpolation and univariate rational function interpolation. As an application of resultant elimination, the authors illustrate the proposed algorithm on three well-known unsolved combinatorial geometric optimization problems. The experiments show that the proposed approach of resultant elimination is more efficient than some existing resultant elimination methods on these difficult problems.     

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.     

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.     

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.     

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.     

基于NURBS曲线轨迹规划与速度规划的研究

提出了一种基于非均匀有理B样条曲线(NURBS)的运动轨迹规划插补算法,与传统插补方法相比,该插补器能够保持高速度和高精度加工性能,而且能够抑制在插补过程当中产生的轮廓误差和速度波动.在插补过程中由于限制轮廓误差的需要而产生了一些速度尖点,在这些尖点处的加速度和加加速度往往都非常大,这些对机床的伺服马达产生很大的冲击力,提出的插补算法能够根据允许的最大轮廓误差、最大加速度、最大加加速度来对插补速度进行自适应调整,使其满足插补要求.通过一个NURBS曲线插补的MATLAB仿真的例子,说明了该曲线插补算法能够满足高速、高精度加工的要求.     

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.     

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.     

An algorithm for the discretization of an ideal projector

Ideal interpolation is a generalization of the univariate Hermite interpolation. It is well known that every univariate Hermite interpolant is a pointwise limit of some Lagrange interpolants. However, a counterexample provided by Shekhtman Boris shows that, for more than two variables, there exist ideal interpolants that are not the limit of any Lagrange interpolants. So it is natural to consider: Given an ideal interpolant, how to find a sequence of Lagrange interpolants (if any) that converge to it. The authors call this problem the discretization for ideal interpolation. This paper presents an algorithm to solve the discretization problem. If the algorithm returns “True”, the authors get a set of pairwise distinct points such that the corresponding Lagrange interpolants converge to the given ideal interpolant.     

Rational Solutions of High-Order Algebraic Ordinary Differential Equations

This paper considers algebraic ordinary differential equations(AODEs) and study their polynomial and rational solutions. The authors first prove a sufficient condition for the existence of a bound on the degree of the possible polynomial solutions to an AODE. An AODE satisfying this condition is called noncritical. Then the authors prove that some common classes of low-order AODEs are noncritical. For rational solutions, the authors determine a class of AODEs, which are called maximally comparable, such that the possible poles of any rational solutions are recognizable from their coefficients. This generalizes the well-known fact that any pole of rational solutions to a linear ODE is contained in the set of zeros of its leading coefficient. Finally, the authors develop an algorithm to compute all rational solutions of certain maximally comparable AODEs, which is applicable to 78.54% of the AODEs in Kamke's collection of standard differential equations.     

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.     

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.     

水下接触爆炸作用下加筋板的动态响应分析

主要仿真模拟计算了加筋板结构在水下接触爆炸荷载作用下的动力响应。以加筋板模型为研究对象,建立了平板、井字加筋板、十字加筋板三种模型。利用非线性有限元程序LS-DYNA,分别模拟计算出它们在水下接触爆炸荷载作用下的动力响应。分析了各个模型计算结果,对比了位移、等效应力、压力等变量,得出结论:加筋板具有分散爆炸冲击波的作用,加筋板抵抗爆炸冲击波冲击的能力更强,结构更偏于安全。     

Selecting an adaptive sequence for computing recursive M-estimators in multivariate linear regression models

In this paper, the authors consider an adaptive recursive algorithm by selecting an adaptive sequence for computing M-estimators in multivariate linear regression models. Its asymptotic property is investigated. The recursive algorithm given by Miao and Wu (1996) is modified accordingly. Simulation studies of the algorithm is also provided. In addition, the Newton-Raphson iterative algorithm is considered for the purpose of comparison.     

基于阈值判断的区域指导插值算法

针对传统图像放大算法对边缘区域划分不准确造成图像质量较低,而自适应插值放大方法模型复杂且计算量大的问题,提出一种基于阈值判断的区域指导(area directed threshold judgment, ADT)插值算法。该算法利用阈值判断的方法对插值点周围进行区域划分,结合近邻法和众数法确定插值点所属区域,根据插值点类型不同,利用不同权值大小的线性插值公式实现自适应插值,提高图像质量。仿真测试结果表明,与基于协方差的自适应插值算法相比,ADT算法在图像质量降低不显著的前提下,能显著提高插值速度;与双线性插值算法相比,图像峰值信噪比平均增加2.19 dB。     

基于对应点的三维医学图像相关性插值

现有的插值方法在进行医学断层图像插值时，要么不能兼顾灰度和形状的变化，要么计算量太大。为解决这一问题，文中提出一种基于对应点的三维医学图像相关性插值算法。通过对两幅断层图像进行门限分割，获得体素的分割值。在相同密度物质的区域内，采用体素的相关性来进行插值，不同密度物质区域采用缩放区域大小作为插值数据，使新的图像不仅在灰度上，而且在组织形状上，介于原来的断层图像之间，满足了医学图像插值的要求。与线性插值相比，新算法的视觉效果好，计算误差小；与小波插值相比，新算法的计算量极大地减少。插值结果可有效地应用于构建三维体模型.     

基于小波分析的图像插值技术研究

基于小波分析理论，提出一种医学图像断层间的插值方法。通过对医学图像的小波变换，插值图像边缘对应的高频子图，得到在轮廓上过渡的图像：对小进变换的低频子图，在小窗口邻城内利用灰度直方图统计得到其概率灰废值并寻找最佳插值匹配点。使得插值图像在灰度上得到很好的过渡；通过小波逆变换得到最终的插值图像。通过与以往算法的对比和分析，本算法所获得的插值图像在形状和灰度方面均达到了较高的清晰度，满足断层图像的插值要求，可有效用于医学图像的三维重构。     

基于基2-FFT的伪码快速捕获实现新算法

讨论了基于基2-FFT的伪码快速捕获方法,论述了其中常见的数据内插处理算法并提出Sinc数据内插新方法。Sinc数据内插算法采用Sinc内插滤波器来实现数据的精确内插,以满足基2-FFT的数据点数需要。仿真表明,采用Sinc数据内插方法实现的基2-FFT伪码快速捕获系统,其捕获性能优于传统的补零法和线性内插法。Sinc内插算法更适合在低信噪比下工作和对捕获时间有严格要求的系统。     

Solvability of vector Ky Fan inequalities with applications

This paper aims to study the solvability of vector Ky Fan inequalities and the compactness of its solution sets. For vector-valued functions with the cone semicontinuity and the cone quasicon- vexity in infinite dimensional spaces, the authors prove some existence results of the solutions and the compactness of the solution sets. Especially, some results for the vector Ky Fan inequalities on noncompact sets are built and the compactness of its solution sets are also discussed. As applications, some existence theorems of the solutions of vector variational inequalities are obtained.     

Semi-algebraically connected components of minimum points of a polynomial function

In a recent article, the authors provided an effective algorithm for both computing the global infimum of f and deciding whether or not the infimum of f is attained, where f is a multivariate polynomial over the field R of real numbers. As a complement, the authors investigate the semi- algebraically connected components of minimum points of a polynomial function in this paper. For a given multivariate polynomial f over R, it is shown that the above-mentioned algorithm can find at least one point in each semi-algebraically connected component of minimum points of f whenever f has its global minimum.