Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Gröbner bases, H-bases and interpolation

Author: Thomas Sauer
Journal: Trans. Amer. Math. Soc. 353 (2001), 2293-2308
MSC (2000): Primary 65D05, 12Y05; Secondary 65H10
Published electronically: October 11, 2000
MathSciNet review: 1814071
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information


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.

References [Enhancements On Off] (What's this?)

  • 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.

Similar Articles

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

Retrieve articles in all journals with MSC (2000): 65D05, 12Y05, 65H10

Additional Information

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

Keywords: H--bases, reduction algorithm, interpolation
Received by editor(s): March 11, 1999
Received by editor(s) in revised form: July 12, 1999
Published electronically: October 11, 2000
Additional Notes: Supported by a Heisenberg fellowship from Deutsche Forschungsgemeinschaft, Grant Sa 627/6.
Article copyright: © Copyright 2000 American Mathematical Society

American Mathematical Society