Gröbner bases, H–bases and interpolation

Sauer, Thomas

doi:10.1090/S0002-9947-00-02646-5

Gröbner bases, H–bases and interpolation
HTML articles powered by AMS MathViewer

by Thomas Sauer PDF

Trans. Amer. Math. Soc. 353 (2001), 2293-2308 Request permission

Abstract:

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

Garrett Birkhoff, The algebra of multivariate interpolation, Constructive approaches to mathematical models (Proc. Conf. in honor of R. J. Duffin, Pittsburgh, Pa., 1978) Academic Press, New York-London-Toronto, Ont., 1979, pp. 345–363. MR 559505
C. de Boor, Gauss elimination by segments and multivariate polynomial interpolation, Approximation and computation (West Lafayette, IN, 1993) Internat. Ser. Numer. Math., vol. 119, Birkhäuser Boston, Boston, MA, 1994, pp. 1–22. MR 1333607
Carl de Boor and Amos Ron, On multivariate polynomial interpolation, Constr. Approx. 6 (1990), no. 3, 287–302. MR 1054756, DOI 10.1007/BF01890412
Carl de Boor and Amos Ron, On polynomial ideals of finite codimension with applications to box spline theory, J. Math. Anal. Appl. 158 (1991), no. 1, 168–193. MR 1113408, DOI 10.1016/0022-247X(91)90275-5
Carl de Boor and Amos Ron, Computational aspects of polynomial interpolation in several variables, Math. Comp. 58 (1992), no. 198, 705–727. MR 1122061, DOI 10.1090/S0025-5718-1992-1122061-0
Carl de Boor and Amos Ron, The least solution for the polynomial interpolation problem, Math. Z. 210 (1992), no. 3, 347–378. MR 1171179, DOI 10.1007/BF02571803
B. Buchberger, Ein algorithmus zum auffinden der basiselemente des restklassenrings nach einem nulldimensionalen polynomideal, Ph.D. thesis, Innsbruck, 1965.
B. Buchberger, Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems, Aequationes Math. 4 (1970), 374–383 (German). MR 268178, DOI 10.1007/BF01844169
N. K. Bose, J. P. Guiver, E. W. Kamen, H. M. Valenzuela, and B. Buchberger, Multidimensional systems theory, Mathematics and its Applications, vol. 16, D. Reidel Publishing Co., Dordrecht, 1985. Progress, directions and open problems in multidimensional systems. MR 804981, DOI 10.1007/978-94-009-5225-6
H. M. Möller and B. Buchberger, The construction of multivariate polynomials with preassigned zeros, Computer algebra (Marseille, 1982) Lecture Notes in Comput. Sci., vol. 144, Springer, Berlin-New York, 1982, pp. 24–31. MR 680050
David Cox, John Little, and Donal O’Shea, Ideals, varieties, and algorithms, Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1992. An introduction to computational algebraic geometry and commutative algebra. MR 1189133, DOI 10.1007/978-1-4757-2181-2
Wolfgang Gröbner, Algebraische Geometrie. $2$. Teil: Arithmetische Theorie der Polynomringe, B. I. Hochschultaschenbücher, vol. 737/737, Bibliographisches Institut, Mannheim-Vienna-Zurich, 1970 (German). MR 0330161
Leopold Kronecker, Leopold Kronecker’s Werke. Bände I–V, Chelsea Publishing Co., New York, 1968 (German). Herausgegeben auf Veranlassung der Königlich Preussischen Akademie der Wissenschaften von K. Hensel. MR 0237286
F. S. Macaulay, The algebraic theory of modular systems, Cambridge Tracts in Math. and Math. Physics, no. 19, Cambridge Univ. Press, 1916.
M. G. Marinari, H. M. Möller, and T. Mora, Gröbner bases of ideals defined by functionals with an application to ideals of projective points, Appl. Algebra Engrg. Comm. Comput. 4 (1993), no. 2, 103–145. MR 1223853, DOI 10.1007/BF01386834
M. G. Marinari, H. M. Möller, and T. Mora, On multiplicities in polynomial system solving, Trans. Amer. Math. Soc. 348 (1996), no. 8, 3283–3321. MR 1360228, DOI 10.1090/S0002-9947-96-01671-6
H. Michael Möller, On the construction of cubature formulae with few nodes using Groebner bases, Numerical integration (Halifax, N.S., 1986) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 203, Reidel, Dordrecht, 1987, pp. 177–192. MR 907119
H. Michael Möller, On the construction of Gröbner bases using syzygies, J. Symbolic Comput. 6 (1988), no. 2-3, 345–359. Computational aspects of commutative algebra. MR 988422, DOI 10.1016/S0747-7171(88)80052-X
H. Michael Möller and Ferdinando Mora, New constructive methods in classical ideal theory, J. Algebra 100 (1986), no. 1, 138–178. MR 839576, DOI 10.1016/0021-8693(86)90071-2
H. M. Möller and T. Sauer, H–bases for polynomial interpolation and system solving, (1999), to appear.
H. Michael Möller and Hans J. Stetter, Multivariate polynomial equations with multiple zeros solved by matrix eigenproblems, Numer. Math. 70 (1995), no. 3, 311–329. MR 1330867, DOI 10.1007/s002110050122
Thomas Sauer, Polynomial interpolation of minimal degree, Numer. Math. 78 (1997), no. 1, 59–85. MR 1483569, DOI 10.1007/s002110050304
—, 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.
H. J. Stetter, Matrix eigenproblems at the heart of polynomial system solving, SIGSAM Bull. 30 (1995), no. 4, 22–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.