Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Gröbner bases and generalized Padé approximation

Authors: Jeffrey B. Farr and Shuhong Gao
Journal: Math. Comp. 75 (2006), 461-473
MSC (2000): Primary 41A21, 13P10, 41A63
Published electronically: October 12, 2005
MathSciNet review: 2176409
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. J. Abbott, A. Bigatti, M. Kreuzer, and L. Robbiano, Computing ideals of points, J. Symbolic Comput. 30 (2000), 341-356. MR 1784266 (2001j:13026)
  • 2. William W. Adams and Philippe Loustaunau, An introduction to Gröbner bases, Graduate Studies in Mathematics, 3, American Mathematical Society, Providence, RI, 1994. MR 1287608 (95g:13025)
  • 3. E.R. Berlekamp and L.R. Welch, Error correction for algebraic block codes, U.S. Patent No. 4,633,470, issued December 30, 1986.
  • 4. B. Buchberger and H. M. Möller, The construction of multivariate polynomials with preassigned zeros. Computer algebra, EUROCAM '82, pp. 24-31, Lecture Notes in Comput. Sci., vol. 144, Springer, Berlin-New York, 1982. MR 0680050 (84b:12003)
  • 5. David Cox, John Little, and Donal O'Shea, Ideals, varieties, and algorithms, 2nd ed., Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1997. MR 1417938 (97h:13024)
  • 6. David Cox, John Little, and Donal O'Shea, Using algebraic geometry, Graduate Texts in Mathematics, 185, Springer-Verlag, New York, 1998. MR 1639811 (99h:13033)
  • 7. Annie Cuyt, How well can the concept of Padé approximant be generalized to the multivariate case?, Continued fractions and geometric function theory (CONFUN) (Trondheim, 1997), J. Comput. Appl. Math. 105 (1999), no. 1-2, 25-50. MR 1690577 (2000e:41029)
  • 8. Jeffrey B. Farr and Shuhong Gao, Computing Gröbner bases for vanishing ideals of finite sets of points, preprint. (Available at
  • 9. Jeffrey B. Farr, Shuhong Gao, and Daniel L. Noneaker, Construction and decoding performance of random linear codes, in preparation.
  • 10. Patrick Fitzpatrick, On the key equation, IEEE Transactions on Information Theory 41 (1995), no. 5, 1290-1302. MR 1366325 (96i:94033)
  • 11. Patrick Fitzpatrick and John Flynn, A Gröbner basis technique for Padé approximation, J. Symbolic Comput. 13 (1992), 133-138.MR 1153639 (93b:68037)
  • 12. Mariano Gasca and Thomas Sauer, Polynomial interpolation in several variables, in Multivariate polynomial interpolation, Adv. Comput. Math. 12 (2000), no. 4, 377-410. MR 1768957 (2001d:41010)
  • 13. 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 (2000j:94033)
  • 14. 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, 1976), pp. 83-100, Academic Press, New York, 1977. MR 0481778 (58:1877)
  • 15. Martin Kreuzer and Lorenzo Robbiano, Computational Commutative Algebra 1, Springer-Verlag, Berlin, 2000. MR 1790326 (2001j:13027)
  • 16. 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), 451-461. MR 1976578 (2004e:41011)
  • 17. C.H. Lutterodt, A two-dimensional analogue of Padé approximant theory, J. Phys. A 7 (1974), 1027-1037. MR 0408510 (53:12274)
  • 18. 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 (94g:13019)
  • 19. Lorenzo Robbiano, On the theory of graded structures, J. Symbolic Comput. 2 (1986), no. 2, 139-170. MR 0849048 (87j:13010)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 41A21, 13P10, 41A63

Retrieve articles in all journals with MSC (2000): 41A21, 13P10, 41A63

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

Shuhong Gao
Affiliation: Department of Mathematical Sciences, Clemson University, Clemson, South Carolina 29634-0975

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.
Article copyright: © Copyright 2005 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society