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.     

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

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

Three-Dimensional Space Interpolation of Grey / Depth Image Sequence-A New Technique of Computer Graphics Synthesis

This paper advances a three-dimensional space interpolation method of grey / depth image sequence, which breaks free from the limit of original practical photographing route. Pictures can cruise at will in space. By using space sparse sampling, great memorial capacity can be saved and reproduced scenes can be controlled. To solve time consuming and complex computations in three-dimensional interpolation algorithm, we have studied a fast and practical algorithm of scattered space lattice and that of "Warp" algorithm with proper depth. By several simple aspects of three dimensional space interpolation, we succeed in developing some simple and practical algorithms. Some results of simulated experiments with computers have shown that the new method is absolutely feasible.     

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

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

求解非光滑最优控制问题的自适应网格优化

针对传统直接配点法在求解非光滑最优控制问题时存在离散误差大、精度低的问题, 提出了一种自适应直接配点法。利用局部分段插值多项式逼近最优解, 将最优控制问题离散为非线性规划问题, 并给出了离散误差估计方法, 根据离散误差的大小确定区间内节点的加密量, 提出了自适应网格优化算法, 利用该算法将大部分节点配置在非光滑区域以降低离散误差。最后通过仿真算例将所提算法与传统直接配点法和文献中的拟谱自适应算法分别进行比较,验证了所提算法的高精度和有效性。     

基于非负矩阵分解新的人脸识别方法

非负矩阵分解是一个新的特征提取方法,基于非矩阵分解的理论,提出了具有正交性的投影轴的计算方法和具有统计不相关性的投影轴的计算方法。与原非负矩阵分解方法,提出的方法在某种程度上是降低了特征矢量之间的统计相关性,并且提高识别率。通过在ORL人脸库和YALE人脸库上进行实验,结果表明提出的两种特征提取方法在识别率方面整体上好于原非负矩阵分解特征提取(NMF)方法,甚至超过主成分分析(PCA)法。     

基于二进小波变换的图像分辨率增强算法

增强图像的分辨率意味着在保持图像清晰度的情况下对图像进行放大。传统的分辨率增强技术是图像插值,它通常要求原始图像满足一定的平滑条件,这常常损失增强后图像的奇异性,使图像中物体边缘和纹理变得模糊。本文提出了一种基于图像多分辨率分析的增强算法,通过估计原始图像在更高一级分辨率上的小波系数,可以得到更为清晰的增强效果,同时保留原图像的奇异性。     

Fast and accurate analysis of electromagnetic scattering from targets situated in dielectric half space

Electromagnetic scattering from targets situated in half space is solved by applying fast inhomogeneous plane wave algorithm combined with a tabulation and interpolation method. The integral equation is set up based on derivation of dyadic Green’s functions in this environment. The coupling is divided into nearby region and well-separated region by grouping. The Green’s function can be divided into two parts: primary term and reflected term. In the well-separated region, the two terms are both expressed as ...     

The F5 algorithm in Buchberger’s style

The famous F5 algorithm for computing Gröbner basis was presented by Faugère in 2002. The original version of F5 is given in programming codes, so it is a bit difficult to understand. In this paper, the F5 algorithm is simplified as F5B in a Buchberger’s style such that it is easy to understand and implement. In order to describe F5B, we introduce F5-reduction, which keeps the signature of labeled polynomials unchanged after reduction. The equivalence between F5 and F5B is also shown. At last, some versions of the F5 algorithm are illustrated.     

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

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

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

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

一种改进的双基地SAR数值计算传递函数成像算法

针对收发平台等速度平行飞行双基地SAR条带工作模式,提出了一种改进的双基地SAR数值计算传递函数成像算法.算法通过数值计算得到双基地二雏传递函数,通过场景坐标系向方位-斜距平面的映射校正了原算法中存在的沿距离变化的方位位置畸变,进而采用常规单基地SAR成像处理流程实现对双基地SAR回波数据的成像处理,最后通过点目标仿真验证了算法的有效性.由于距离徙动校正不需要插值计算,因此计算效率较高,适合进行高速并行成像处理.     

一种渐进式平滑轨迹线标绘方法

为实现GIS系统和分布式仿真中运动轨迹线的绘制,提出一种基于Catmull曲线算法的渐进式标绘方法。本方法可根据定位点获得具有连续平滑性质的轨迹线,并随定位点的增加实现轨迹线延伸,延伸的轨迹线可与原轨迹线保持连续平滑性;通过曲线离散化参数调整轨迹线的平滑度;通过依赖于轨迹线的线性插值获取任意时刻的位置信息。实验结果表明,轨迹线标绘方法可以实现基于定位点的渐进式平滑标绘,添加一个定位点的计算时间可在0.1ms内完成。     

基于代数神经网络的分圆多项式判定及学习算法

首先对MP神经元进行推广 ,给出了一元多项式代数神经元、一元多项式代数神经网络 ,设计出一类用于一元多项式二元运算的神经元模型 ,它是单输入单输出的 3层多项式神经网络 ,给出了两种用于判定一多项式为分圆多项式的神经网络模型及学习算法 ,把判定一多项式为分圆多项式转化成线性方程组求解问题 ,通过算例说明了该方法的有效性。     

ON SIMULTANEOUS L~P-APPROXIMATION (0

MIN Guohua Department of Mathematics  East China Institute of Technology  Nanjing  China 《系统科学与复杂性》1993,(3)

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.     

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.     

基于环节的控制系统图形组态仿真软件

介绍了一个基于环节的控制系统图形组态仿真软件的功能和实现方法，及改进的仿真算法，在数值计算方法中，引入了拉各朗日线性插值方法，既大大减少了迭代计算量，又保持了原有的仿真精度，利用这一可视化仿真平台，用户可对线性系统，多变量系统，多变量Smith预估控制系统，采样系统等方便快捷地建立方框图形式的系统仿真模型，从而为复杂系统的分析和设计提供了仿真研究平台，系统界面友好，易于扩展。     

基于起讫点的均衡交通分配改进算法

AnthonyChen (2002)提出的基于起讫点的Frank-Wolfe (ODBFW)算法, 对同一起点的所有OD对搜索最短路树, 采用one-OD-at-a-time流量更新策略, 是一种收敛性能较好的均衡交通分配算法. 主要对ODBFW算法的初始化、线性搜索及最短路搜索算法进行改进, 提出ODBFW改进算法. 将ODBFW改进算法应用于国际上同类研究常用的SiouxFalls网络及我国山东省诸城市实际道路网, 比较标准FW算法、ODBFW算法及ODBFW改进算法的可行性、效率及稳定性. 结果显示, 改进算法效率较标准FW算法有显著提高, 稳定性较好. 在小型测试路网上改进算法较ODBFW算法达到收敛的时间减少近15%, 在大型测试路网上减少近5%.     

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.