Algorithms for computing Gröbner bases of ideal interpolation

Xue Jiang; Yihe Gong; Xue Jiang; Yihe Gong

doi:10.3934/math.2024948

AIMS Mathematics

2024, Volume 9, Issue 7: 19459-19472. doi: 10.3934/math.2024948

Previous Article Next Article

Research article

Algorithms for computing Gröbner bases of ideal interpolation

Xue Jiang ¹,
Yihe Gong ^{2
,
,}

1.
School of Mathematics and Statistics, Changchun University of Science and Technology, Changchun 130000, China
2.
College of Science, Northeast Electric Power University, Jilin 132000, China

Received: 22 April 2024 Revised: 28 May 2024 Accepted: 31 May 2024 Published: 13 June 2024
MSC : 13P10, 68W30

This paper proposes algorithms for computing the reduced Gröbner basis of the vanishing ideal of a finite set of points in the frame of ideal interpolation. We also consider the case that the points have multiplicity conditions. First, we introduce the definition of "reverse" reduced team and compute the interpolation monomial basis of a single point ideal interpolation problem; then we translate the interpolation condition functionals into formal power series via Taylor expansion; this will help convert the general ideal interpolation problem to a single point ideal interpolation problem; and finally, the reduced Gröbner basis is read from formal power series by Gaussian elimination. Our algorithm has a polynomial time complexity, and an example is given to illustrate its effectiveness.
- ideal interpolation,
- vanishing ideal,
- Gröbner basis,
- Gaussian elimination,
- Taylor expansion
Citation: Xue Jiang, Yihe Gong. Algorithms for computing Gröbner bases of ideal interpolation[J]. AIMS Mathematics, 2024, 9(7): 19459-19472. doi: 10.3934/math.2024948

Related Papers:

Abstract

This paper proposes algorithms for computing the reduced Gröbner basis of the vanishing ideal of a finite set of points in the frame of ideal interpolation. We also consider the case that the points have multiplicity conditions. First, we introduce the definition of "reverse" reduced team and compute the interpolation monomial basis of a single point ideal interpolation problem; then we translate the interpolation condition functionals into formal power series via Taylor expansion; this will help convert the general ideal interpolation problem to a single point ideal interpolation problem; and finally, the reduced Gröbner basis is read from formal power series by Gaussian elimination. Our algorithm has a polynomial time complexity, and an example is given to illustrate its effectiveness.

References

[1]	J. Abbott, A. Bigatti, M. Kreuzer, L. Robbiano, Computing ideals of points, J. Symb. Comput., 30 (2000), 341–356. https://doi.org/10.1006/jsco.2000.0411 doi: 10.1006/jsco.2000.0411
[2]	D. A. Cox, J. Little, D. O'Shea, Ideal, varieties, and algorithms, Cham: Springer, 2015. https://doi.org/10.1007/978-3-319-16721-3
[3]	C. de Boor, Ideal interpolation, In: Approximation theory XI, Nashville: Nashboro Press, 2004, 59–91.
[4]	C. de Boor, A. Ron, On multivariate polynomial interpolation, Constr. Approx., 6 (1990), 287–302. https://doi.org/10.1007/BF01890412 doi: 10.1007/BF01890412
[5]	C. de Boor, B. Shekhtman, On the pointwise limits of bivariate Lagrange projectors, Linear Algebra Appl., 429 (2008), 311–325. https://doi.org/10.1016/j.laa.2008.02.024 doi: 10.1016/j.laa.2008.02.024
[6]	J. B. Farr, S. H. Gao, Computing Gröbner bases for vanishing ideals of finite sets of points, In: Applied algebra, algebraic algorithms and error-correcting codes, Heidelberg: Springer, 2006,118–127. https://doi.org/10.1007/11617983_11
[7]	X. Jiang, S. G. Zhang, B. X. Shang, The discretization for bivariate ideal interpolation, J. Comput. Appl. Math., 308 (2016), 177–186. https://doi.org/10.1016/j.cam.2016.05.012 doi: 10.1016/j.cam.2016.05.012
[8]	M. Lederer, The vanishing ideal of a finite set of closed points in affine space, J. Pure Appl. Algebra, 212 (2008), 1116–1133. https://doi.org/10.1016/j.jpaa.2007.08.002 doi: 10.1016/j.jpaa.2007.08.002
[9]	Z. Li, S. G. Zhang, T. Dong, Y. H. Gong, Error formulas for Lagrange projectors determined by Cartesian sets, J. Syst. Sci. Complex., 31 (2018), 1090–1102. https://doi.org/10.1007/s11424-017-6159-8 doi: 10.1007/s11424-017-6159-8
[10]	M. G. Marinari, H. M. Möller, T. Mora, Gröbner bases of ideals defined by functionals with an application to ideals of projective points, Appl. Algebr. Eng. Comm., 4 (1993), 103–145. http://doi.org/10.1007/bf01386834. doi: 10.1007/bf01386834
[11]	H. M. Möller, B. Buchberger, The construction of multivariate polynomials with preassigned zeros, In: Computer algebra. EUROCAM 1982. Lecture notes in computer science, Heidelberg: Springer, 1982, 24–31. https://doi.org/10.1007/3-540-11607-9_3
[12]	T. Sauer, Polynomial interpolation of minimal degree and Gröbner bases, In: Gröbner bases and applications, Cambridge: Cambridge University Press, 1998,483–494. https://doi.org/10.1017/CBO9780511565847.030
[13]	T. Sauer, Lagrange interpolation on subgrids of tensor product grids, Math. Comp., 73 (2004), 181–190. http://doi.org/10.1090/s0025-5718-03-01557-6 doi: 10.1090/s0025-5718-03-01557-6
[14]	X. Y. Wang, S. G. Zhang, T. Dong, A bivariate preprocessing paradigm for the Buchberger-Möller algorithm, J. Comput. Appl. Math., 234 (2010), 3344–3355. https://doi.org/10.1016/j.cam.2010.04.035 doi: 10.1016/j.cam.2010.04.035
[15]	B. Shekhtman, Ideal interpolation: translations to and from algebraic geometry, In: Approximate commutative algebra, Vienna: Springer, 2009,163–192. https://doi.org/10.1007/978-3-211-99314-9_6

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)