Abstract
We present an algorithm to compute a Gröbner basis for the vanishing ideal of a finite set of points in an affine space. For distinct points the algorithm is a generalization of univariate Newton interpolation. Computational evidence suggests that our method compares favorably with previous algorithms when the number of variables is small relative to the number of points. We also present a preprocessing technique that significantly enhances the performance of all the algorithms considered. For points with multiplicities, we adapt our algorithm to compute the vanishing ideal via Taylor expansions.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Interpolation Problem
- Monomial Basis
- Polynomial Time Complexity
- Monomial Order
- Multivariate Interpolation
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abbott, J., Bigatti, A., Kreuzer, M., Robbiano, L.: Computing ideals of points. J. Symbolic Comput. 30, 341–356 (2000)
Buchberger, B., Möller, H.M.: The construction of multivariate polynomials with preassigned zeros. In: Calmet, J. (ed.) ISSAC 1982 and EUROCAM 1982. LNCS, vol. 144. Springer, Heidelberg (1982)
Cerlienco, L., Mureddu, M.: From algebraic sets to monomial linear bases by means of combinatorial algorithms. Formal power series and algebraic combinatorics Montreal, PQ, 1992; Discrete Math. 139(1-3), 73–87 (1995)
Cox, D., Little, J., O’Shea, D.: Ideals, varieties, and algorithms, 2nd edn. Undergraduate Texts in Mathematics. Springer, New York (1997)
Cox, D., Little, J., O’Shea, D.: Using algebraic geometry. Graduate Texts in Mathematics, vol. 185. Springer, New York (1998)
Farr, J.B, Gao, S.: Gröbner bases and generalized Padé approximation. Math. Comp. (to appear)
Jeffrey, B.F., Gao, S.: Gröbner bases, Padé approximation, and decoding of linear codes. In: Evans, D., et al. (eds.) Coding Theory and Quantum Computing. Contemp. Math, vol. 381, pp. 3–18. Amer. Math. Soc, Providence (2005)
Faugere, J., Gianni, P., Lazard, D., Mora, T.: Efficient computation of zero-dimensional Gröbner bases by change of ordering. J. Symbolic Comput. 16, 329–344 (1993)
Fitzpatrick, P., O’Keeffe, H.: Gröbner basis solutions of constrained interpolation problems. Fourth special issue on linear systems and control. Linear Algebra Appl. 351/352, 533–551 (2002)
Gasca, M., Sauer, T.: Polynomial interpolation in several variables, in Multivariate polynomial interpolation. Adv. Comput. Math. 12(4), 377–410 (2000)
Guruswami, V., Sudan, M.: Improved decoding of Reed-Solomon and algebraic-geometric codes. IEEE Transactions on Information Theory 46(6), 1757–1767 (1999)
Koetter, R., Vardy, A.: Algebraic Soft-Decision Decoding of Reed-Solomon Codes. IEEE Transactions on Information Theory 49, 2809–2825 (2003)
Laubenbacher, R., Stigler, B.: A computational algebra approach to the reverse engineering of gene regulatory networks. Journal of Theoretical Biology 229, 523–537 (2004)
Marinari, M.G., Möller, H.M., Mora, T.: Gröbner bases of ideals defined by functionals with an application to ideals of projective points. Appl. Algebra Engrg. Comm. Comput. 4(2), 103–145 (1993)
Marinari, M.G., Möller, H.M., Mora, T.: On multiplicities in polynomial system solving. Trans. Amer. Math. Soc. 348(8), 3283–3321 (1996)
Pistone, G., Riccomagno, E., Wynn, H.P.: Algebraic Statistics: Computational Commutative Algebra in Statistics. Monographs on Statistics & Applied Probability 89. Chapman & Hall/CRC, Boca Raton (2001)
Robbiano, L.: Gröbner bases and statistics. Gröben bases and applications (Linz, 1998). London Math. Soc. Lecture Note Ser., vol. 251, pp. 179–204. Cambridge Univ. Press, Cambridge (1998)
Sudan, M.: Decoding of Reed Solomon codes beyond the error-correction bound. J. Complexity 13(1), 180–193 (1997)
Shuhong Gao’s webpage, http://www.math.clemson.edu/~sgao/
David Joyner’s webpage, http://cadigweb.ew.usna.edu/~wdj/gap/curves/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Farr, J.B., Gao, S. (2006). Computing Gröbner Bases for Vanishing Ideals of Finite Sets of Points. In: Fossorier, M.P.C., Imai, H., Lin, S., Poli, A. (eds) Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. AAECC 2006. Lecture Notes in Computer Science, vol 3857. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11617983_11
Download citation
DOI: https://doi.org/10.1007/11617983_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-31423-3
Online ISBN: 978-3-540-31424-0
eBook Packages: Computer ScienceComputer Science (R0)