Transactions of the American Mathematical Society

Author(s): Thomas Sauer
Journal: Trans. Amer. Math. Soc. 353 (2001), 2293-2308.
MSC (2000): Primary 65D05, 12Y05; Secondary 65H10
Posted: October 11, 2000
Retrieve article in: PDF DVI PostScript
This article is available free of charge

The paper is concerned with a construction for H-bases of polynomial ideals without relying on term orders. The main ingredient is a homogeneous reduction algorithm which orthogonalizes leading terms instead of completely canceling them. This allows for an extension of Buchberger's algorithm to construct these H-bases algorithmically. In addition, the close connection of this approach to minimal degree interpolation, and in particular to the least interpolation scheme due to de Boor and Ron, is pointed out.

1.: G. Birkhoff, The algebra of multivariate interpolation, Constructive Approaches to Mathematical Models (C.V. Coffman and G.J. Fix, eds.), Academic Press Inc., 1979, pp. 345-363. MR 83d:41001
2.: C. de Boor, Gauss elimination by segments and multivariate polynomial interpolation, Approximation and Computation: A Festschrift in Honor of Walter Gautschi (R. V. M. Zahar, ed.), Birkhäuser Verlag, 1994, pp. 1-22. MR 96c:65010
3.: C. de Boor and A. Ron, On multivariate polynomial interpolation, Constr. Approx. 6 (1990), 287-302. MR 91c:41005
4.: -, On polynomial ideals of finite codimension with applications to box spline theory, J. Math. Anal. and Appl. 158 (1991), 168-193. MR 93a:41014
5.: -, Computational aspects of polynomial interpolation in several variables, Math. Comp. 58 (1992), 705-727. MR 92i:65022
6.: -, The least solution for the polynomial interpolation problem, Math. Z. 210 (1992), 347-378. MR 93f:41002
7.: B. Buchberger, Ein algorithmus zum auffinden der basiselemente des restklassenrings nach einem nulldimensionalen polynomideal, Ph.D. thesis, Innsbruck, 1965.
8.: -, Ein algorithmisches Kriterium für die Lösbarkeit eines Gleichungssystems, Aequationes Math. 4 (1970), 374-383. MR 42:3077
9.: -, Gröbner bases: An algorithmic method in polynomial ideal theory, Chapter 6 in N.K. Bose et al., Multidimensional Systems Theory, D. Reidel Publishing Company, 1985, pp. 184-232. MR 87m:93017
10.: B. Buchberger and H. M. Möller, The construction of multivariate polynomials with preassigned zeros, Computer Algebra, EUROCAM '82, European Computer Algebra Conference (G. Goos and J. Hartmanis, eds.), Lecture Notes in Computer Science, vol. 144, Springer Verlag, 1982, pp. 24-31. MR 84b:12003
11.: D. Cox, J. Little, and D. O'Shea, Ideals, varieties and algorithms, Undergraduate Texts in Mathematics, Springer-Verlag, 1992. MR 93j:13031
12.: W. Gröbner, Algebraische geometrie II, B.I-Hochschultaschenbücher, no. 737, Bibliographisches Institut Mannheim, 1970. MR 48:8499
13.: L. Kronecker, Über einige Interpolationsformeln für ganze Funktionen mehrerer Variabeln, L. Kroneckers Werke (H. Hensel, ed.), Teubner / Chelsea Publishing Company, 1895 / 1966, Lecture at the academy of sciences, December 21, 1865, pp. 133-141. MR 38:5576
14.: F. S. Macaulay, The algebraic theory of modular systems, Cambridge Tracts in Math. and Math. Physics, no. 19, Cambridge Univ. Press, 1916.
15.: M. G. Marinari, H. M. Möller, and T. Mora, Groebner bases of ideals defined by functionals with an application to ideals of projective points, Appl. Algebra Engrg. Comm. Comput. 4 (1993), 103-145. MR 94g:13019
16.: -, On multiplicities in polynomial system solving, Trans. Amer. Math. Soc. 348 (1996), no. 8, 3283-3321. MR 96k:13039
17.: H. M. Möller, On the construction of cubature formulae with few nodes using Groebner bases, Numerical Integration (P. Keast and G. Fairweather, eds.), NATO ASI series C, vol. 203, D. Reidel Publishing Corp, 1987, pp. 177-192. MR 88j:65059
18.: -, On the construction of Gröbner bases using syzygies, J. Symbolic Comput. 6 (1988), 345-359. MR 90e:13008
19.: H. M. Möller and F. Mora, New constructive methods in classical ideal theory, J. Alg. 100 (1986), 138-178. MR 88c:13012
20.: H. M. Möller and T. Sauer, H-bases for polynomial interpolation and system solving, (1999), to appear.
21.: H. M. Möller and H. J. Stetter, Multivariate polynomial equations with multiple zeros solved by matrix eigenproblems, Numer. Math. 70 (1995), 311-329. MR 96e:65034
22.: T. Sauer, Polynomial interpolation of minimal degree, Numer. Math. 78 (1997), 59-85. MR 99f:41042
23.: -, Polynomial interpolation of minimal degree and Gröbner bases, Groebner Bases and Applications (Proc. of the Conf. 33 Years of Groebner Bases) (B. Buchberger and F. Winkler, eds.), London Math. Soc. Lecture Notes, vol. 251, Cambridge University Press, 1998, pp. 483-494.
24.: H. J. Stetter, Matrix eigenproblems at the heart of polynomial system solving, SIGSAM Bull. 30 (1995), no. 4, 22-25.
25.: -, Stabilization of polynomial system solving with Groebner bases, Proceedings of the ACM-SIGSAM International Symposium on Symbolic and Algebraic Computation, ISAAC '97, Maui, Association of Computing Machinery, 1997.

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 65D05, 12Y05, 65H10

Thomas Sauer
Affiliation: Mathematisches Institut, Universität Erlangen--Nürmberg, Bismarckstr. $1 \frac12$, D--91054 Erlangen, Germany
Address at time of publication: Justus-Liebig-Universität Gießen, Lehrstuhl für Numerische Mathematik Heinrich-Buff-Ring 44, D-35392 Gießen, Germany
Email: sauer@mi.uni-erlangen.de

DOI: 10.1090/S0002-9947-00-02646-5
PII: S 0002-9947(00)02646-5
Keywords: H--bases, reduction algorithm, interpolation
Received by editor(s): March 11, 1999
Received by editor(s) in revised form: July 12, 1999
Posted: October 11, 2000
Additional Notes: Supported by a Heisenberg fellowship from Deutsche Forschungsgemeinschaft, Grant Sa 627/6.
Copyright of article: Copyright 2000, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6850(e) ISSN 0002-9947(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS