F [ x ]-lattice basis reduction algorithm and multisequence synthesis

By means ofF[x]-lattice basis reduction algorithm, a new algorithm is presented for synthesizing minimum length linear feedback shift registers (or minimal polynomials) for the given multiple sequences over a fieldF. Its computational complexity isO(N ²) operations inF whereN is the length of each sequence. A necessary and sufficient condition for the uniqueness of minimal polynomials is given. The set and exact number of all minimal polynomials are also described whenF is a finite field.     

Local hybrid approximation for scattered data fitting with bivariate splines

We suggest a local hybrid approximation scheme based on polynomials and radial basis functions, and use it to improve the scattered data fitting algorithm of (Davydov, O., Zeilfelder, F., 2004. Scattered data fitting by direct extension of local polynomials to bivariate splines. Adv. Comp. Math. 21, 223–271). Similar to that algorithm, the new method has linear computational complexity and is therefore suitable for large real world data. Numerical examples suggest that it can produce high quality artifact-free approximations that are more accurate than those given by the original method where pure polynomial local approximations are used.     

Certified dense linear system solving

A randomized algorithm is given for solving a system of linear equations over a principal ideal domain. The algorithm returns a solution vector which has minimal denominator. A certificate of minimality is also computed. A given system has a Diophantine solution precisely when the minimal denominator is one. Cost estimates are given for systems over the ring of integers and ring of polynomials with coefficients from a field.     

Gröbner bases in exterior algebra

We show that the Buchberger algorithm for commutative polynomials over a field may be generalised to an algebraic structure which embeds such polymomials, the exterior polynomial algebra, and which is a natural domain for linear geometry. In particular, those finite sets of exterior polynomials which induce confluent reduction relations are characterised, and a means of algorithmically constructing them from a given set presented. A distinguished subset of such bases consists of the exterior algebra version of Gröbner bases. We characterise such bases and demonstrate how to construct them algorithmically from a given finite set of exterior polynomials.     

Termination of the F5 algorithm

The F5 algorithm, which calculates the Gröbner basis of an ideal generated by homogeneous polynomials, was proposed by Faugère in 2002; simultaneously, the correctness of this algorithm was proved under the condition of termination. However, termination itself was demonstrated only for a regular sequence of polynomials. In this paper, it is proved that the algorithm terminates for any input data. First, it is shown that if the algorithm does not terminate, it eventually generates two polynomials where the first is a reductor for the second. However, it is not argued that such a reduction is permitted by all the criteria introduced in F5. Next, it is shown that if such a pair exists, then there exists another pair for which the reduction is permitted by all the criteria, which is impossible.     

Partial realization and the Euclidean algorithm

The authors show how the Euclidean algorithm fits into the behavioral framework of exact modeling and how it computes solutions of the scalar minimal partial realization problem. It turns out that the Euclidean algorithm can be considered as a special instance of Wolovich's procedure (1974) to achieve row reducedness for a given polynomial 2×2 matrix. The authors show in detail how this approach yields a parameterization of all minimal solutions in terms of polynomials that are sequentially produced by the Euclidean algorithm     

多项式的正性和凸性

在计算机辅助几何设计(CAGD)中,曲面曲线的凸性是一种重要的特性.旨在解决多项式的正性和凸性问题.凸性可以通过正性来解决.通过推广经典的Sturm定理,得到一种多项式正性的算法.由此提出了任意阶多项式为正的一个充要条件,也提出了一个实用的算法,从而可以只用此多项式的系数来表示得到的充要条件.     

Fast computation of Gröbner basis of homogenous ideals of $$ \mathbb{F} $$[ x,y]

This paper provides a fast algorithm for Grobnerbases of homogenous ideals of F[x, y] over a finite field F. We show that only the 8-polynomials of neighbor pairs of a strictly ordered finite homogenours generating set are needed in the computing of a Grobner base of the homogenous ideal. It reduces dramatically the number of unnecessary 5-polynomials that are processed. We also show that the computational complexity of our new algorithm is O（N^2）, where N is the maximum degree of the input generating polynomials. The new algorithm can be used to solve a problem of blind recognition of convolutional codes. This problem is a new generalization of the important problem of synthesis of a linear recurring sequence.     

构造径向基函数的一般方法及其在图象处理中的应用

gi．引言对于函数J：＊”＋R如果存在函数h：B＋R使得对VxE＊”;都有人对二周卜DD）,其中卜D为X的欧几里得范数,则称函数人X）为一个径向函数．径向函数具有本质上的一维性,它可以将任意高继问题映射为一维问题处理．当一个径向函数的平移和伸缩能够构成某函数空间的基底时,利用该基底的线性组合便可以设计径向基函数网络．径向基函数网络的降维特性为多层前馈网络的学习提供了一条新颖而简捷的途径山,现已广泛应用于非线性函数逼近、信号及图象处理等领域［‘,‘,‘］．它不仅具有良好的推广能力,而且避免了象反传算法那样繁…     

Un particolare metodo per la determinazione di autovalori di matrici tridiagonali simmetriche

In this paper we given an algorithm of low computational complexity which determines the eigenvalues of a symmetric tridiagonal matrix. The algorithm uses the technique of spectrum slicing together with methods for finding the zeros of polynomials. An application of algorithm for computing Gauss quadrature formulas is given.

---

---

Lavoro svolto nell'ambito del Gruppo Nazionale di Informatica Matematica del C.N.R.     

Finding shortest paths on surfaces using level sets propagation

We present a new algorithm for determining minimal length paths between two regions on a three dimensional surface. The numerical implementation is based on finding equal geodesic distance contours from a given area. These contours are calculated as zero sets of a bivariate function designed to evolve so as to track the equal distance curves on the given surface. The algorithm produces all paths of minimal length between the source and destination areas on the surface given as height values on a rectangular grid     

基于字节指纹极值特征的数据分块算法

针对基于内容的数据分块算法中基本滑动窗口算法不能确定最大数据块的问题,提出一种基于字节指纹极值特征的数据分块算法。算法以上一个块边界点为起点构建最大块长区间,通过定义字节指纹极值域半径函数F并利用函数F值的分布特性,以概率1在允许的最大块长的区间内确定下一个块边界点。该算法克服了基本滑动窗口等分块算法不能确定最大分块长度的不足,其时间复杂度为O(n)。     

TurboTree: a fast algorithm for minimal trees

A branch and bound algorithm is described for searching rapidly for minimal length trees from biological data. The algorithm adds characters one at a time, rather than adding taxa, as in previous branch and bound methods. The algorithm has been programmed and is available from the authors. A worked example is given with 33 characters and 15 taxa. About 8 x 10(12) binary trees are possible with 15 taxa but the branch and bound program finds the minimal tree in less than 5 min on an IBM PC.     

基于约束Jacobi基的多项式反函数逼近及应用

求解多项式反函数是CAGD中的一个基本问题.提出一种带端点Ck约束的反函数逼近算法.利用约束Jacobi基作为有效工具, 推导了它与Bernstein基的转换公式,采用Bernstein多项式的升阶、乘积、积分与组合运算, 给出了求解反函数系数的具体算法.该算法稳定、简易, 克服了以往计算反函数的系数时每次逼近系数需全部重新计算的缺陷.最后通过具体逼近实例验证了文中算法的正确性和有效性, 同时给出了它在PH曲线准弧长参数化中的应用.     

Fast parallel polynomial division via reduction to triangular toeplitz matrix inversion and to polynomial inversion modulo a power

It is known that division with a remainder of two polynomials of degree at most s can be performed over an arbitrary field F of constants using uniform arithmetic and Boolean circuits of depth O(log s log log s) and polynomial size. A new algorithm is presented that yields those bounds via reduction to triangular Toeplitz matrix inversion and to polynomial inversion modulo a power. (If|F| > (s?1)² or if P-uniform computation is allowed, then the depth can be reduced to O(log s).) This approach is new and makes the result conceptually simpler.     

F5C: A variant of Faugère’s F5 algorithm with reduced Gröbner bases

The F5 algorithm for computing Gröbner bases achieves a high level of efficiency through the careful analysis of signatures assigned to each computed polynomial. However, it computes and uses many polynomials that turn out to be redundant. Eliminating these redundant polynomials is a non-trivial task, because they correspond to signatures required for reduction. This paper revisits the theory underlying F5 and describes F5C, a new variant that prunes redundant polynomials, then re-computes signatures to preserve correctness. This strategy successfully reduces both overhead and execution time.     

A multi-dimensional solver for the steady Euler equations

In this paper a numerical algorithm for the solution of the multi-dimensional steady Euler equations in conservative and non-conservative form is presented. Most existing standard and multi-dimensional schemes use flux balances with assumed constant distribution of variables along each cell edge, which interfaces two grid cells. This assumption is believed to be one of the main reasons for the limited advantage gained from multi-dimensional high order discretisations compared to standard one-dimensional ones. The present algorithm is based on the optimisation of polynomials describing the distribution of flow variables in grid cells, where only polynomials that satisfy the Euler equations in the entire grid cell can be selected. The global solution is achieved if all polynomials and by that the flow variables are continuous along edges interfacing neighbouring grid cells. A discrete approximation of a given spatial order is converged if the deviation between polynomial distributions of adjacent grid cells along the interfacing edge of the cells is minimal. Results from the present scheme between first and fifth order spatial accuracy are compared to standard first and second order Roe computations for simple test cases demonstrating the gain in accuracy for a number of sub- and supersonic flow problems.     

Approximate computation of zero-dimensional polynomial ideals

The Buchberger–Möller algorithm is a well-known efficient tool for computing the vanishing ideal of a finite set of points. If the coordinates of the points are (imprecise) measured data, the resulting Gröbner basis is numerically unstable. In this paper we introduce a numerically stable Approximate Vanishing Ideal (AVI) Algorithm which computes a set of polynomials that almost vanish at the given points and almost form a border basis. Moreover, we provide a modification of this algorithm which produces a Macaulay basis of an approximate vanishing ideal. We also generalize the Border Basis Algorithm ([Kehrein, A., Kreuzer, M., 2006. Computing border bases. J. Pure Appl. Algebra 205, 279–295]) to the approximate setting and study the approximate membership problem for zero-dimensional polynomial ideals. The algorithms are then applied to actual industrial problems.     

Optimal Spectral-Galerkin Methods Using Generalized Jacobi Polynomials

We extend the definition of the classical Jacobi polynomials withindexes α, β>−1 to allow α and/or β to be negative integers. We show that the generalized Jacobi polynomials, with indexes corresponding to the number of boundary conditions in a given partial differential equation, are the natural basis functions for the spectral approximation of this partial differential equation. Moreover, the use of generalized Jacobi polynomials leads to much simplified analysis, more precise error estimates and well conditioned algorithms.Mathematics subject classification 1991. 65N35, 65N22, 65F05, 35J05