Gröbner bases and generalized Padé approximation
HTML articles powered by AMS MathViewer
- by Jeffrey B. Farr and Shuhong Gao PDF
- Math. Comp. 75 (2006), 461-473 Request permission
Abstract:
It is shown how to find general multivariate Padé approximation using the Gröbner basis technique. This method is more flexible than previous approaches, and several examples are given to illustrate this advantage. When the number of variables is small compared to the degree of approximation, the Gröbner basis technique is more efficient than the linear algebra methods in the literature.References
- J. Abbott, A. Bigatti, M. Kreuzer, and L. Robbiano, Computing ideals of points, J. Symbolic Comput. 30 (2000), no. 4, 341–356. MR 1784266, DOI 10.1006/jsco.2000.0411
- William W. Adams and Philippe Loustaunau, An introduction to Gröbner bases, Graduate Studies in Mathematics, vol. 3, American Mathematical Society, Providence, RI, 1994. MR 1287608, DOI 10.1090/gsm/003
- E.R. Berlekamp and L.R. Welch, Error correction for algebraic block codes, U.S. Patent No. 4,633,470, issued December 30, 1986.
- 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, 2nd ed., Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1997. An introduction to computational algebraic geometry and commutative algebra. MR 1417938
- David Cox, John Little, and Donal O’Shea, Using algebraic geometry, Graduate Texts in Mathematics, vol. 185, Springer-Verlag, New York, 1998. MR 1639811, DOI 10.1007/978-1-4757-6911-1
- Annie Cuyt, How well can the concept of Padé approximant be generalized to the multivariate case?, J. Comput. Appl. Math. 105 (1999), no. 1-2, 25–50. Continued fractions and geometric function theory (CONFUN) (Trondheim, 1997). MR 1690577, DOI 10.1016/S0377-0427(99)00028-X
- Jeffrey B. Farr and Shuhong Gao, Computing Gröbner bases for vanishing ideals of finite sets of points, preprint. (Available at http://www.math.clemson.edu/~sgao/pub.html)
- Jeffrey B. Farr, Shuhong Gao, and Daniel L. Noneaker, Construction and decoding performance of random linear codes, in preparation.
- Patrick Fitzpatrick, On the key equation, IEEE Trans. Inform. Theory 41 (1995), no. 5, 1290–1302. MR 1366325, DOI 10.1109/18.412677
- Patrick Fitzpatrick and John Flynn, A Gröbner basis technique for Padé approximation, J. Symbolic Comput. 13 (1992), no. 2, 133–138. MR 1153639, DOI 10.1016/S0747-7171(08)80087-9
- Mariano Gasca and Thomas Sauer, Polynomial interpolation in several variables, Adv. Comput. Math. 12 (2000), no. 4, 377–410. Multivariate polynomial interpolation. MR 1768957, DOI 10.1023/A:1018981505752
- Venkatesan Guruswami and Madhu Sudan, Improved decoding of Reed-Solomon and algebraic-geometry codes, IEEE Trans. Inform. Theory 45 (1999), no. 6, 1757–1767. MR 1720630, DOI 10.1109/18.782097
- J. Karlsson and H. Wallin, Rational approximation by an interpolation procedure in several variables, Padé and rational approximation (Proc. Internat. Sympos., Univ. South Florida, Tampa, Fla., 1976) Academic Press, New York, 1977, pp. 83–100. MR 0481778
- Martin Kreuzer and Lorenzo Robbiano, Computational commutative algebra. 1, Springer-Verlag, Berlin, 2000. MR 1790326, DOI 10.1007/978-3-540-70628-1
- John B. Little, David Ortiz, Ricardo Ortiz-Rosado, Rebecca Pablo, and Karen Ríos-Soto, Some remarks on Fitzpatrick and Flynn’s Gröbner basis technique for Padé approximation, J. Symbolic Comput. 35 (2003), no. 4, 451–461. MR 1976578, DOI 10.1016/S0747-7171(03)00041-5
- C. H. Lutterodt, A two-dimensional analogue of Padé approximant theory, J. Phys. A 7 (1974), 1027–1037. MR 408510, DOI 10.1088/0305-4470/7/9/007
- 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
- Lorenzo Robbiano, On the theory of graded structures, J. Symbolic Comput. 2 (1986), no. 2, 139–170. MR 849048, DOI 10.1016/S0747-7171(86)80019-0
Additional Information
- Jeffrey B. Farr
- Affiliation: Centre for Experimental and Constructive Mathematics (CECM) and Department of Mathematics, Simon Fraser University, Burnaby, British Columbia, Canada V5A 1S6
- Email: jfarr@cecm.sfu.ca
- Shuhong Gao
- Affiliation: Department of Mathematical Sciences, Clemson University, Clemson, South Carolina 29634-0975
- MR Author ID: 291308
- Email: sgao@ces.clemson.edu
- Received by editor(s): February 10, 2004
- Received by editor(s) in revised form: December 10, 2004
- Published electronically: October 12, 2005
- Additional Notes: This work was supported in part by the National Science Foundation (NSF) under Grant DMS0302549, the National Security Agency (NSA) under Grant MDA904-02-1-0067, and the DoD Multidisciplinary University Research Initiative (MURI) program administered by the Office of Naval Research (ONR) under Grant N00014-00-1-0565. MITACS also partially supported the first author.
- © Copyright 2005
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 75 (2006), 461-473
- MSC (2000): Primary 41A21, 13P10, 41A63
- DOI: https://doi.org/10.1090/S0025-5718-05-01790-4
- MathSciNet review: 2176409