×

zbMATH — the first resource for mathematics

Gröbner bases of ideals defined by functionals with an application to ideals of projective points. (English) Zbl 0785.13009
The authors present a systematic approach to the computation of a Gröbner basis for 0-dimensional ideals defined as kernels of linear functionals of the polynomial ring. They construct two algorithms of polynomial complexity to compute such a basis which generalize the FGLM- algorithm and one due to Buchberger and Möller. For the description of the algorithms and different applications they introduce the notations of biorthogonal and triangular sequences representing the dual space of the linear functionals as diagonal or upper triangular matrix and of closed sets \(V\subset\text{Span}_ K(D)\) of differential conditions to describe primary ideals with linear functions given by these conditions. It is proved, that every 0-dimensional ideal is uniquely determined by a finite set of points \(\{y_ 1,\ldots,y_ s\}\subset\overline K^ n\) \((\overline K\) the algebraic closure of \(K)\) and a closed set \(\Delta_ i\subset\text{Span}_{K_ i}(DF)\) of differential conditions for every \(y_{i1}\) where \(y_ i=\{y_{i1},\ldots,y_{in}\}\) is the set of conjugate points and \(K_ i=K(y_{i1},\ldots,y_{in})\) the minimal field extension containing all coordinates of these points.
The first of the two presented algorithms assigns iteratively all monomials to either the ideal \(T(G)\) of leading terms from the given ideal or to the set \(N\) of monomials outside \(T(G)\). The second one constructs inductively a Gröbner set \(F_ i\) for \(\text{Ker}(L_ 1,\ldots,L_ i)\) and a triangular sequence \(\{q_ 1,\ldots,q_ i\}\). Then it is shown in a detailed investigation, that both algorithms are of complexity \(O(ns^ 2+fns^ 2)\), where \(n=\#\{\text{variables}\}\), \(s=\#\{\text{functionals}\}\) and \(f=f(s,c)\) measures the evaluation of \(s\) functionals on \(c\) monomials for a concrete application. This function \(f\) is computed for different examples, so for simple and multiple, rational or algebraic points, for Border-basis and Gröbner- basis functionals. Finally a variant of the whole theory is developed for projective ideals and applied to the computation of a Gröbner-basis for simple projective points. Here it is added a polynomial algorithm to minimize a homogeneous basis.

MSC:
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Backelin, J.: Communication at MEGA ’90
[2] Backelin, J., Fröberg, R.: How we proved that there exactly 924 cyclic 7-roots, Proc. ISSAC 91, 103-111, ACM (1991) · Zbl 0925.13012
[3] Becker, T., Weispfenning, V.: The Chinese remainder, multivariate interpolation and Gröbner bases. Proc. ISSAC 91, 64-69, ACM (1991) · Zbl 0925.13013
[4] Buchberger, B.: Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal, Ph.D. Thesis, Innsbruck, (1965) · Zbl 1245.13020
[5] 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 · Zbl 0587.13009
[6] 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 · Zbl 0417.68029
[7] 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 · Zbl 0549.68026
[8] Cerlienco, L., Mureddu, M.: Combinatorial algorithms for polynomial interpolation in dimension ? 2 (in preparation) · Zbl 1002.41500
[9] Eliahou, S.: Minimal syzygies of monomial ideals and Gröbner bases (preprint)
[10] 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)
[11] Gebauer, R., Möller, H. M.: On an installation of Buchberger’s Algorithm, J. Symb. Comp.6, 275-286 (1988) · Zbl 0675.13013
[12] 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 · Zbl 0692.13012
[13] 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 · Zbl 0825.68396
[14] 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 · Zbl 0755.14018
[15] Gröbner, W.: Algebraische Geometrie, Vol. 2, Bibliographisches Institut Mannheim (1967-1968)
[16] Heuser, H. G.: Functional analysis. New York: Wiley 1982 · Zbl 0465.47001
[17] 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 · Zbl 0734.13017
[18] Lakshman, Y. N.: On the complexity of computing Gröbner bases of zero dimensional ideals, Ph.D. Thesis, Rensselaer Polytechnique Institute, Troy (1990) · Zbl 0734.13017
[19] 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 · Zbl 0539.13002
[20] 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) · Zbl 0925.13011
[21] Möller, H. M., Mora, T.: New constructive methods in classical ideal theory. J. Algebra100, 138-178 (1986) · Zbl 0621.13007
[22] Ramella, L: Algoritmi di computer algebra relativi agli ideali di punti dello spazio proiettivo, Ph.D. Thesis, Univ. Napoli (1990)
[23] 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 · Zbl 0739.13013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.