Computing border bases

This paper presents several algorithms that compute border bases of a zero-dimensional ideal. The first relates to the FGLM algorithm as it uses a linear basis transformation. In particular, it is able to compute border bases that do not contain a reduced Gröbner basis. The second algorithm is based on a generic algorithm by Bernard Mourrain originally designed for computing an ideal basis that need not be a border basis. Our fully detailed algorithm computes a border basis of a zero-dimensional ideal from a given set of generators. To obtain concrete instructions we appeal to a degree-compatible term ordering σ and hence compute a border basis that contains the reduced σ-Gröbner basis. We show an example in which this computation actually has advantages over Buchberger's algorithm. Moreover, we formulate and prove two optimizations of the Border Basis Algorithm which reduce the dimensions of the linear algebra subproblems.     

Border bases and kernels of homomorphisms and of derivations

Border bases are an alternative to Gröbner bases. The former have several more desirable properties. In this paper some constructions and operations on border bases are presented. Namely; the case of a restriction of an ideal to a polynomial ring (in a smaller number of variables), the case of the intersection of two ideals, and the case of the kernel of a homomorphism of polynomial rings. These constructions are applied to the ideal of relations and to factorizable derivations.     

多项式组的特征分解

任一多项式理想的特征对是指由该理想的约化字典序Grobner基G和含于其中的极小三角列C构成的有序对(G,C).当C为正则列或正规列时,分别称特征对(G,C)为正则的或正规的.当G生成的理想与C的饱和理想相同时,称特征对(G,C)为强的.一组多项式的(强)正则或(强)正规特征分解是指将该多项式组分解为有限多个(强)正则或(强)正规特征对,使其满足特定的零点与理想关系.本文简要回顾各种三角分解及相应零点与理想分解的理论和方法,然后重点介绍(强)正则与(强)正规特征对和特征分解的性质,说明三角列、Ritt特征列和字典序Grobner基之间的内在关联,建立特征对的正则化定理以及正则、正规特征对的强化方法,进而给出两种基于字典序Grobner基计算、按伪整除关系分裂和构建、商除可除理想等策略的(强)正规与(强)正则特征分解算法.这两种算法计算所得的强正规与强正则特征对和特征分解都具有良好的性质,且能为输入多元多项式组的零点提供两种不同的表示.本文还给出示例和部分实验结果,用以说明特征分解方法及其实用性和有效性.     

On the generalized Ball bases

The Ball basis was introduced for cubic polynomials by Ball, and two different generalizations for higher degree m polynomials have been called the Said–Ball and the Wang–Ball basis, respectively. In this paper, we analyze some shape preserving and stability properties of these bases. We prove that the Wang–Ball basis is strictly monotonicity preserving for all m. However, it is not geometrically convexity preserving and is not totally positive for m>3, in contrast with the Said–Ball basis. We prove that the Said–Ball basis is better conditioned than the Wang–Ball basis and we include a stable conversion between both generalized Ball bases. The Wang–Ball basis has an evaluation algorithm with linear complexity. We perform an error analysis of the evaluation algorithms of both bases and compare them with other algorithms for polynomial evaluation.     

A fast algorithm for the multivariate Birkhoff interpolation problem

Multivariate Birkhoff interpolation is the most complicated polynomial interpolation problem and the theory about it is far from systematic and complete. In this paper we derive an Algorithm B-MB (Birkhoff-Monomial Basis) and prove B-MB giving the minimal interpolation monomial basis w.r.t. the lexicographical order of the multivariate Birkhoff problem. This algorithm is the generalization of Algorithm MB in [L. Cerlinco, M. Mureddu, From algebraic sets to monomial linear bases by means of combinatorial algorithms, Discrete Math. 139 (1995) 73-87] which is a well known fast algorithm used to compute the interpolation monomial basis of the Hermite interpolation problem.     

A fast algorithm for the multivariate Birkhoff interpolation problem

Multivariate Birkhoff interpolation is the most complicated polynomial interpolation problem and the theory about it is far from systematic and complete. In this paper we derive an Algorithm B-MB (Birkhoff-Monomial Basis) and prove B-MB giving the minimal interpolation monomial basis w.r.t. the lexicographical order of the multivariate Birkhoff problem. This algorithm is the generalization of Algorithm MB in [L. Cerlinco, M. Mureddu, From algebraic sets to monomial linear bases by means of combinatorial algorithms, Discrete Math. 139 (1995) 73–87] which is a well known fast algorithm used to compute the interpolation monomial basis of the Hermite interpolation problem.     

On the degree elevation of Bernstein polynomial representation

The polynomials determined in the Bernstein (Bézier) basis enjoy considerable popularity in computer-aided design (CAD) applications. The common situation in these applications is, that polynomials given in the basis of degree n have to be represented in the basis of higher degree. The corresponding transformation algorithms are called algorithms for degree elevation of Bernstein polynomial representations. These algorithms are only then of practical importance if they do not require the ill-conditioned conversion between the Bernstein and the power basis. We discuss all the algorithms of this kind known in the literature and compare them to the new ones we establish. Some among the latter are better conditioned and not more expensive than the currently used ones. All these algorithms can be applied componentwise to vector-valued polynomial Bézier representations of curves or surfaces.     

A bivariate preprocessing paradigm for the Buchberger-Möller algorithm

For the last almost three decades, since the famous Buchberger-Möller (BM) algorithm emerged, there has been wide interest in vanishing ideals of points and associated interpolation polynomials. Our paradigm is based on the theory of bivariate polynomial interpolation on cartesian point sets that gives us a related degree reducing interpolation monomial and Newton bases directly. Since the bases are involved in the computation process as well as contained in the final output of the BM algorithm, our paradigm obviously simplifies the computation and accelerates the BM process. The experiments show that the paradigm is best suited for the computation over finite prime fields that have many applications.     

Waring’s problem with digital restrictions in $$ \mathbb{F} $$q[ X]

We present a generalization of a result due to Thuswaldner and Tichy to the ring of polynomials over a finite fields. In particular, we want to show that every polynomial of sufficiently large degree can be represented as sum of kth powers, where the bases evaluated on additive functions meet certain congruence restrictions.     

Sharp precision in Hensel lifting for bivariate polynomial factorization

Popularized by Zassenhaus in the seventies, several algorithms for factoring polynomials use a so-called lifting and recombination scheme. Concerning bivariate polynomials, we present a new algorithm for the recombination stage that requires a lifting up to precision twice the total degree of the polynomial to be factored. Its cost is dominated by the computation of reduced echelon solution bases of linear systems. We show that our bound on precision is asymptotically optimal.

     

A discrete adapted hierarchical basis solver for radial basis function interpolation

In this paper we develop a discrete Hierarchical Basis (HB) to efficiently solve the Radial Basis Function (RBF) interpolation problem with variable polynomial degree. The HB forms an orthogonal set and is adapted to the kernel seed function and the placement of the interpolation nodes. Moreover, this basis is orthogonal to a set of polynomials up to a given degree defined on the interpolating nodes. We are thus able to decouple the RBF interpolation problem for any degree of the polynomial interpolation and solve it in two steps: (1) The polynomial orthogonal RBF interpolation problem is efficiently solved in the transformed HB basis with a GMRES iteration and a diagonal (or block SSOR) preconditioner. (2) The residual is then projected onto an orthonormal polynomial basis. We apply our approach on several test cases to study its effectiveness.     

New methods for generating permutation polynomials over finite fields

We present two methods for generating linearized permutation polynomials over an extension of a finite field Fq. These polynomials are parameterized by an element of the extension field and are permutation polynomials for all nonzero values of the element. For the case of the extension degree being odd and the size of the ground field satisfying , these parameterized linearized permutation polynomials can be used to derive non-parameterized nonlinear permutation polynomials via a recent result of Ding et al.     

Hybrid vector transformations

We present in this paper hybrid and semi-hybrid vector extrapolation methods. For a vector sequence transformation, we will define the generalized residual which allows us to introduce a new hybrid vector transformation. When solving linear systems, this new transformation reduces to the hybrid procedure defined by Brezinski and Redivo Zaglia (1994) which is a generalization of the smoothing technique. In the second part of this paper, we define a new composite transformation called semi-hybrid. When applied to linearly generated sequences, we will show that the residual polynomial of the semi-hybrid transformation is the product of two residual polynomials.     

Massively parallel computation of many-variable polynomial interpolation

In this paper, we present homogeneous polynomials in many variables. We show how the hypercube representation of these polynomials (introduced by Beauzamy et al. in [1], and derived from Bombieri's work in Beauzamy et al. [2]) allows us to build interpolation polynomials, that is, polynomials taking prescribed values at prescribed points in . We then show that the construction is robust and give quantitative estimates on how the constructed polynomial is perturbed if either the data, the points, or both are perturbed. The theorems, constructions, and algorithms answer questions asked by Dr. Ken Clark, U.S. Army Research Office.

In the final part of the paper, we present the explicit algorithms, implemented on the Connection Machines CM200 and CM5 at the Etablissement Technique Central de l'Armement, Arcueil. This algorithm is efficient, especially when the number of variables is high, and it takes all advantage of the massively parallel architecture.     

Regularity of lex-segment ideals: Some closed formulas and applications

A closed formula for computing the regularity of the lex-segment ideal in terms of the Hilbert function is given. This regularity bounds the one of any ideal with the same Hilbert function. As a consequence, we give explicit expressions to bound the regularity of a projective scheme in terms of the coefficients of the Hilbert polynomial.

We also characterize, in terms of their coefficients, which polynomials are Hilbert polynomials of some projective scheme.

Finally, we provide some applications to estimates for the maximal degree of generators of Gröbner bases in terms of the degrees of defining equations.

     

Computations in differential and difference modules

Constructive methods based on the Gröbner bases theory have been used many times in commutative algebra over the past 20 years, in particular, they allow the computation of such important invariants of manifolds given by systems of algebraic equations as their Hilbert polynomials. In differential and difference algebra, the analogous roles play characteristic sets.In this paper, algorithms for computations in differential and difference modules, which allow for the computation of characteristic sets (Gröbner bases) in differential, difference, and polynomial modules and differential (difference) dimension polynomials, are described. The algorithms are implemented in the algorithmic language REFAL.     

有限域上多项式集的简单分解

研究如何将任意有限域上的多项式集分解为有限多个简单列.为了解决这一问题,首先研究简单列和根理想之间的关系,然后基于已有的正则分解算法和有限域上理想的根的两种计算方法设计一个有限域上多项式集的简单分解算法.计算试验表明,文章给出的算法是有效的.     

Pivoting in Extended Rings for Computing Approximate Gr?bner Bases

It is well known that in the computation of Gr?bner bases arbitrarily small perturbations in the coefficients of polynomials may lead to a completely different staircase, even if the solutions of the polynomial system change continuously. This phenomenon is called artificial discontinuity in Kondratyev’s Ph.D. thesis. We show how such phenomenon may be detected and even “repaired” by using a new variable to rename the leading term each time we detect a “problem”. We call such strategy the TSV (Term Substitutions with Variables) strategy. For a zero-dimensional polynomial ideal, any monomial basis (containing 1) of the quotient ring can be found with the TSV strategy. Hence we can use TSV strategy to relax term order while keeping the framework of Gr?bner basis method so that we can use existing efficient algorithms (for instance the F ₅ algorithm) to compute an approximate Gr?bner basis. Our main algorithms, named TSVn and TSVh, can be used to repair artificial e{\epsilon}-discontinuities. Experiments show that these algorithms are effective for some nontrivial problems.     

On the Key Equation Over a Commutative Ring

We define alternant codes over a commutative ring R and a corresponding key equation. We show that when the ring is a domain, e.g. the p-adic integers, the error-locator polynomial is the unique monic minimal polynomial (equivalently, the unique shortest linear recurrence) of the finite sequence of syndromes and that it can be obtained by Algorithm MR of Norton.WhenR is a local ring, we show that the syndrome sequence may have more than one (monic) minimal polynomial, but that all the minimal polynomials coincide modulo the maximal ideal ofR . We characterise the set of minimal polynomials when R is a Hensel ring. We also apply these results to decoding alternant codes over a local ring R: it is enough to find any monic minimal polynomial over R and to find its roots in the residue field. This gives a decoding algorithm for alternant codes over a finite chain ring, which generalizes and improves a method of Interlando et. al. for BCH and Reed-Solomon codes over a Galois ring.     

Solving polynomial least squares problems via semidefinite programming relaxations

A polynomial optimization problem whose objective function is represented as a sum of positive and even powers of polynomials, called a polynomial least squares problem, is considered. Methods to transform a polynomial least square problem to polynomial semidefinite programs to reduce degrees of the polynomials are discussed. Computational efficiency of solving the original polynomial least squares problem and the transformed polynomial semidefinite programs is compared. Numerical results on selected polynomial least square problems show better computational performance of a transformed polynomial semidefinite program, especially when degrees of the polynomials are larger.