Abstract
In this paper we study 0-dimensional polynomial ideals defined by a dual basis, i.e. as the set of polynomials which are in the kernel of a set of linear morphisms from the polynomial ring to the base field. For such ideals, we give polynomial complexity algorithms to compute a Gröbner basis, generalizing the Buchberger-Möller algorithm for computing a basis of an ideal vanishing at a set of points and the FGLM basis conversion algorithm.
As an application to Algebraic Geometry, we show how to compute in polynomial time a minimal basis of an ideal of projective points.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Backelin, J.: Communication at MEGA '90
Backelin, J., Fröberg, R.: How we proved that there exactly 924 cyclic 7-roots, Proc. ISSAC 91, 103–111, ACM (1991)
Becker, T., Weispfenning, V.: The Chinese remainder, multivariate interpolation and Gröbner bases. Proc. ISSAC 91, 64–69, ACM (1991)
Buchberger, B.: Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal, Ph.D. Thesis, Innsbruck, (1965)
Buchberger, B.: Gröbner bases: an algorithmic method in polynomial ideal theory in Recent trends in multidimensional systems theory, Bose, N. K. (ed.) Dordrecht: Reidel 1985
Buchberger, B.: A criterion for detecting unnecessary reductions in the construction of Gröbner bases. Proc. Eurosam 79. Lecture Notes in Computer Science vol. 72 pp. 3–21. Berlin, Heidelberg, New York: Springer 1979
Buchberger, B., Möller, H. M.: The construction of multivariate polynomials with preassigned zeroes, Proc. EUROCAM 82, Lecture Notes in Computer Science vol. 144 pp. 24–31. Berlin, Heidelberg, New York: Springer 1982
Cerlienco, L., Mureddu, M.: Combinatorial algorithms for polynomial interpolation in dimension ≧ 2 (in preparation)
Eliahou, S.: Minimal syzygies of monomial ideals and Gröbner bases (preprint)
Faugere, J. C., Gianni, P., Lazard, D., Mora, T.: Efficient computation of zero-dimensional Gröbner bases by change of ordering. J. Symb. Comp. (submitted) (1989)
Gebauer, R., Möller, H. M.: On an installation of Buchberger's Algorithm, J. Symb. Comp.6, 275–286 (1988)
Gianni, P., Mora, T.: Algebraic solution of systems of polynomial equations using Gröbner bases. Lecture Notes in Computer Science vol. 356, pp. 247–257. Berlin, Heidelberg, New York: Springer 1989
Giusti, M.: Complexity of standard bases in projective dimension zero II. Proc. AAECC 8. Lecture Notes in Computer Science vol. 508, pp. 322–328. Berlin, Heidelberg, New York: Springer 1991
Giusti, M., Heintz, J.: Algorithmes — disons rapides — pour la décomposition d'une variété en composantes irréductibles et équidimensionnelles, Proc. MEGA '90. Basel: Birkhäuser 1991
Gröbner, W.: Algebraische Geometrie, Vol. 2, Bibliographisches Institut Mannheim (1967–1968)
Heuser, H. G.: Functional analysis. New York: Wiley 1982
Lakshman, Y. N.: A single exponential bound on the complexity of computing Gröbner bases of zero dimensional ideals. Proc. MEGA '90. Basel: Birkhauser 1991
Lakshman, Y. N.: On the complexity of computing Gröbner bases of zero dimensional ideals, Ph.D. Thesis, Rensselaer Polytechnique Institute, Troy (1990)
Lazard, D.: Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations, Proc. Eurocal 83. Lecture Notes in Computer Science vol. 162, pp. 146–156. Berlin, Heidelberg, New York: Springer 1983
Marihari, M. G., Möller, H. M., Mora, T.: Gröbner bases of ideals given by dual bases. Proc. ISSAC 91, ACM 55–63 (1991)
Möller, H. M., Mora, T.: New constructive methods in classical ideal theory. J. Algebra100, 138–178 (1986)
Ramella, L: Algoritmi di computer algebra relativi agli ideali di punti dello spazio proiettivo, Ph.D. Thesis, Univ. Napoli (1990)
Robbiano, L.: Bounds for degrees and number of elements in Gröbner bases. Proc. AAECC 8. Lecture Notes in Computer Science vol. 508. Berlin, Heidelberg, New York: Springer 1991
Author information
Authors and Affiliations
Additional information
Dedicated to our friend Mario Raimondo
Rights and permissions
About this article
Cite this article
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. AAECC 4, 103–145 (1993). https://doi.org/10.1007/BF01386834
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01386834