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

DOI10.1016/J.CAM.2010.04.035MaRDI QIDQ989141zbMATH OpenOpenAlexFDO

Authors Xiaoying Wang, Shugong Zhang, Tian Dong

Publication date 27 August 2010

Published in Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1001.1186

zbMATH Keywords

bivariate Lagrange interpolationBuchberger-Möller algorithmCartesian setdegree reducing interpolation space

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Numerical interpolation (65D05)

Abstract: For the last almost three decades, since the famous Buchberger-M"oller(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 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 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.

Review text

The authors apply a preprocessing paradigm for the Buchberger--Möller algorithm. They give first a simple maximal cartesian subset construction algorithm, which computes a maximal cartesian subset \(\Xi'\) containing the original finite affine set of points \(\Xi\). Later they compute certain lower set with respect to \(\Xi'\) and a Gröbner éscalier and a degree reducing interpolation Newton Gröbner basis for the Lagrange interpolation problem on \(\Xi\). They apply the original Buchberger--Möller algorithm after the preprocessing. They implement their results in \texttt{Maple 12} and demonstrate the timings for the computation on sets of distinct random points with respect to the term order \(\prec_{lex}\) or \(\prec_{tdivlex}\).

Recommendations

• Preconditioning the bidomain model with almost linear complexity
• scientific article; zbMATH DE number 1086519
• scientific article; zbMATH DE number 1159872
• scientific article; zbMATH DE number 4000639
• scientific article; zbMATH DE number 877100
• scientific article; zbMATH DE number 3948927
• Novel bivariate moment-closure approximations

Cites work

• A computational algebra approach to the reverse engineering of gene regulatory networks
• Computing Gröbner bases of ideals of few points in high dimensions
• Computing ideals of points
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• From algebraic sets to monomial linear bases by means of combinatorial algorithms
• Gröbner bases of ideals defined by functionals with an application to ideals of projective points
• Gröbner Bases, Coding, and Cryptography: a Guide to the State-of-Art
• scientific article; zbMATH DE number 3876580 (Why is no real title available?)
• scientific article; zbMATH DE number 1120551 (Why is no real title available?)
• scientific article; zbMATH DE number 1163422 (Why is no real title available?)
• scientific article; zbMATH DE number 2172780 (Why is no real title available?)
• scientific article; zbMATH DE number 217454 (Why is no real title available?)
• scientific article; zbMATH DE number 2196434 (Why is no real title available?)
• Interpolation from spaces spanned by monomials
• Lagrange interpolation on subgrids of tensor product grids
• Multivariate Birkhoff interpolation
• Polynomial interpolation in several variables: lattices, differences, and ideals
• The lex game and some applications
• Using Algebraic Geometry

Cited in

(2)

• A two-dimensional improvement for Farr-Gao algorithm
• Finite sets of affine points with unique associated monomial order quotient bases

Describes a project that uses

Uses Software

• Maple

This page was built for publication: A bivariate preprocessing paradigm for the Buchberger-Möller algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q989141)